LINUXSOFT.cz Přeskoč levou lištu
Uživatel: Heslo:  
   CZUKPL

> C++ - Vyhledávání v textu - Brute Force algoritmus

Tento článek je zaměřen na vyhledávání v textu. Nejprve bude zmínka o vyhledávání v textu obecně, poté si řekneme jedno z kritérií, podle kterého se vyhledávací algoritmy dají dělit a představíme si jednoduchý algoritmus Brute Force, na jehož základě je pak postaven složitější Morris-Prattův algoritmus.

8.12.2010 00:00 | Petr Sklenička | Články autora | přečteno 12537×

Vyhledávání v textu obecně

Vyhledávání v textu je činnost, při které hledáme nějaký řetězec (vzorek) v zadaném textu. Problém hledání vzorku v textu patří v oblasti počítačů k poměrně časté činnosti, neboť například textový editor, který by neuměl vyhledat danou část textu, by rozhodně nepatřil k těm kvalitnějším. Dále se s vyhledáváním v textu můžete setkat při analyzování obrazu nebo zvuku.

Algoritmů, který tento problém řeší, existuje celá řada. Všechny tyto algoritmy lze rozdělit do několika skupin. Kritérií, podle kterých můžeme utvořit dané skupiny, je také dost. Jedním takovým nejčastějším kritériem je, zda algoritmus vyžaduje nějaké předzpracování textu nebo vzorku. Celkem tedy vznikají čtyři skupiny algoritmů, které:

  • nevyžadují předzpracování textu ani vzorku
  • vyžadují předzpracování vzorku
  • vyžadují předzpracování textu
  • vyžadují předzpracování jak textu, tak vzorku
Do první skupiny patří velice jednoduchý algoritmus Brute Force, který si v tomto článku vysvětlíme. Pokud se ptáte, proč je článek o triviálním algoritmu, je to proto, že pro pochopení dalších, složitějších algoritmů, je znalost Brute Force velmi vhodná. Například pokročilejší Morris-Prattův algoritmus je pouze jakýmsi vylepšením algoritmu Brute Force. Mezi další algoritmy pro vyhledávání v textu patří například Knuth-Morris-Prattův algoritmus, Shift-Or algoritmus, který využívá bitové operace, nebo třeba Karp-Rabinův algoritmus, který je založen na použití hashovacích funkcí.

Popis algoritmu Brute Force

Jak jsem již výše psal, jedná se o velice triviální algoritmus. Není tedy težké jej pochopit a implementovat, což je sice výhoda, oproti tomu však algoritmus není příliš efektivní. Samozřejmě pokud budeme hledat v krátkém textu, rozdíl oproti lepším algoritmům bude nepatrný. Časová náročnost se ukáže až při hledání ve velmi dlouhém řetězci.

Název Brute Force lze do češtiny přeložit jako "hrubá síla", což tak trochu vystihuje celou podstatu algoritmu. Celé to funguje tak, že procházíme řetězec zleva doprava, znak po znaku. Než si algoritmus vysvětlíme podrobně, zavedeme si čtyři pojmy, které budeme používat.

  • x - takto budeme označovat hledaný text, neboli vzorek
  • t - text, ve kterém budeme hledat výskyt vzorku
  • delka_x - počet znaků, které obsahuje vzorek
  • delka_t - počet znaků, které obsahuje text, ve kterém hledáme
Nyní si uvedeme krátký příklad, jak algoritmus funguje. Definujme si, že hledaný vzorek bude "CBH" a budeme hledat v textu "DSCBHKTER". Délka hledaného vzorku je tedy 3 a délka textu je 9. Algoritmus prochází text znak po znaku, začíná tedy na první pozici, což je písmeno "D".

V tuto chvíli jsme tedy na prvním znaku, na písmenu "D". První písmeno vzorku je "C". Jelikož se sobě "D" a "C" nerovnají, můžeme se posunout na další znak v textu, což je písmeno "S". Ani písmeno "S" však není shodné s prvním písmenem vzorku, pokračujeme tedy dále. Třetím písmemem textu je "C", které se již shoduje s prvním písmenem našeho vzorku. To však ještě neznamená, že jsme vzorek našli. Náš vzorek obsahuje celkem tři písmena, jedno jsme již našli (na třetí pozici v textu), teď je nutné ověřit, jestli i druhé písmeno vzorku je shodné se čtvrtým písmenem vzorku. Druhý znak ve vzorku je "B" a čtvrtý znak v textu je také "B". Víme tedy, že jsme našli řetězec "CB". Náš vzorek je ale "CBH", proto ještě musíme ověřit, jestli jako další znak v textu je písmeno "H". Pokud ano, vzorek bude nalezen na třetí pozici (udává se místo, kde se v textu nachází první znak vzorku). Pátým znakem v textu je skutečně písmeno "H", vzorek jsme tedy úspěšně našli. Takovýmto způsobem pracuje algoritmus Brute Force. Nyní se podívejme, jak jednoduchá je jeho implementace v jazyce C++.

Nějak takto by mohl vypadat kód. Můžete si všimnout, že algoritmus je napsán tak, že najde všechny výskyty vzorku v daném textu, neskončí tedy po nalezení prvního vzorku. Dále si všimněte vnějšího cyklu. Iterační proměnná i se pohybuje v rozmezí [0, delka_t - delka_x]. Na první pohled by se mohlo zdát, že chceme-li projít celý text, je nutné se posunout i na několik posledních míst v textu. Je nutné si ale uvědomit, že pokud máme například vzorek o délce 4 a text o délce 20, poslední pozicí v textu, kde se vzorek může nacházet, je pozice 17. Dále už ne, neboť víme, že vzorek by se tam nevešel.

Myslím si, že algoritmus je poměrně jednoduchý, proto doufám, že jste jej pochopili. Daň za jednoduchost algoritmu je však jeho velká časová náročnost, proto se pro nějaké větší aplikace příliš nehodí.

Verze pro tisk

pridej.cz

 

DISKUZE

Chyba 10.12.2010 23:33 Jaroslav Šmíd
  |- Re: Chyba 11.12.2010 10:51 Pavel `Goldenfish' Kysilka
  | L Re: Chyba 11.12.2010 20:26 Jaroslav Šmíd
  |   L Re: Chyba 12.12.2010 14:18 Pavel `Goldenfish' Kysilka
  L Re: Chyba 11.12.2010 18:56 Petr Sklenička
    L Re: Chyba 11.12.2010 20:19 Jaroslav Šmíd
      |- Re: Chyba 12.12.2010 00:41 Pavel Stěhule
      | L Re: Chyba 13.12.2010 21:07 Aleš Hakl
      |   L Re: Chyba 13.12.2010 21:09 Aleš Hakl
      L Re: Chyba 14.12.2010 11:21 Aleš Hakl




Příspívat do diskuze mohou pouze registrovaní uživatelé.
> Vyhledávání software
> Vyhledávání článků

4.10.2018 21:30 /Ondřej Čečák
LinuxDays 2018 již tento víkend, registrace je otevřená.
Přidat komentář

18.9.2018 23:30 /František Kučera
Zářijový pražský sraz spolku OpenAlt se koná již tento čtvrtek – 20. 9. 2018 od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5). Tentokrát bez oficiální přednášky, ale zato s dobrým jídlem a pivem – volná diskuse na téma IoT, CNC, svobodný software, hardware a další hračky.
Přidat komentář

9.9.2018 14:15 /Redakce Linuxsoft.cz
20.9.2018 proběhne v pražském Kongresovém centru Vavruška konference Mobilní řešení pro business. Návštěvníci si vyslechnou mimo jiné přednášky na témata: Nejdůležitější aktuální trendy v oblasti mobilních technologií, správa a zabezpečení mobilních zařízení ve firmách, jak mobilně přistupovat k informačnímu systému firmy, kdy se vyplatí používat odolná mobilní zařízení nebo jak zabezpečit mobilní komunikaci.
Přidat komentář

12.8.2018 16:58 /František Kučera
Srpnový pražský sraz spolku OpenAlt se koná ve čtvrtek – 16. 8. 2018 od 19:00 v Kavárně Ideál (Sázavská 30, Praha), kde máme rezervovaný salonek. Tentokrát jsou tématem srazu databáze prezentaci svého projektu si pro nás připravil Standa Dzik. Dále bude prostor, abychom probrali nápady na využití IoT a sítě The Things Network, případně další témata.
Přidat komentář

16.7.2018 1:05 /František Kučera
Červencový pražský sraz spolku OpenAlt se koná již tento čtvrtek – 19. 7. 2018 od 18:00 v Kavárně Ideál (Sázavská 30, Praha), kde máme rezervovaný salonek. Tentokrát bude přednáška na téma: automatizační nástroj Ansible, kterou si připravil Martin Vicián.
Přidat komentář

18.6.2018 0:43 /František Kučera
Červnový pražský sraz spolku OpenAlt se koná již tento čtvrtek – 21. 6. 2018 od 18:00 v Kavárně Ideál (Sázavská 30, Praha), kde máme rezervovaný salonek. Tentokrát na téma: F-Droid, aneb svobodný software do vašeho mobilu. Kromě toho budou k vidění i vývojové desky HiFive1 se svobodným/otevřeným čipem RISC-V.
Přidat komentář

23.5.2018 20:55 /Ondřej Čečák
Od pátku 25.5. proběhne na Fakultě informačních technologií ČVUT v Praze openSUSE Conference. Můžete se těšit na spostu zajímavých přednášek, workshopů a také na Release Party nového openSUSE leap 15.0. V na stejném místě proběhne v sobotu 26.5. i seminář o bezpečnosti CryptoFest.
Přidat komentář

20.5.2018 17:45 /Redakce Linuxsoft.cz
Ve čtvrtek 31. května 2018 připravuje webový magazín BusinessIT ve spolupráci s Best Online Média s.r.o. pátý ročník odborné konference Firemní informační systémy 2018. Akce proběhne v kongresovém centru Vavruška (palác Charitas), Karlovo náměstí 5, Praha 2 (u metra Karlovo náměstí) od 9:00 hod. dopoledne do cca 15 hod. odpoledne. Konference je zaměřena na efektivní využití firemních informačních systémů a na to, jak plně využít jejich potenciál. Podrobnější informace na webových stránkách konfrence.
Přidat komentář

   Více ...   Přidat zprávičku

> Poslední diskuze

5.10.2018 17:12 / Jakub Kuljovsky
Re: Jaký kurz a software by jste doporučili pro začínajcího kodéra?

20.9.2018 10:04 / Jan Ober
Jaký kurz a software by jste doporučili pro začínajcího kodéra?

20.9.2018 10:00 / Jan Ober
Re: Gimp

20.2.2018 18:48 / Ivan Majer
portal

20.2.2018 15:57 / Jan Havel
Jak využíváte služby cloudu v podnikání?

Více ...

ISSN 1801-3805 | Provozovatel: Pavel Kysilka, IČ: 72868490 (2003-2018) | mail at linuxsoft dot cz | Design: www.megadesign.cz | Textová verze