LINUXSOFT.cz Přeskoč levou lištu

ARCHIV



   

> 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 13282×

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ů

28.11.2018 23:56 /František Kučera
Prosincový sraz spolku OpenAlt se koná ve středu 5.12.2018 od 16:00 na adrese Zikova 1903/4, Praha 6. Tentokrát navštívíme organizaci CESNET. Na programu jsou dvě přednášky: Distribuované úložiště Ceph (Michal Strnad) a Plně šifrovaný disk na moderním systému (Ondřej Caletka). Následně se přesuneme do některé z nedalekých restaurací, kde budeme pokračovat v diskusi.
Komentářů: 1

12.11.2018 21:28 /Redakce Linuxsoft.cz
22. listopadu 2018 se koná v Praze na Karlově náměstí již pátý ročník konference s tématem Datová centra pro business, která nabídne odpovědi na aktuální a často řešené otázky: Jaké jsou aktuální trendy v oblasti datových center a jak je optimálně využít pro vlastní prospěch? Jak si zajistit odpovídající služby datových center? Podle jakých kritérií vybírat dodavatele služeb? Jak volit vhodné součásti infrastruktury při budování či rozšiřování vlastního datového centra? Jak efektivně datové centrum spravovat? Jak co nejlépe eliminovat možná rizika? apod. Příznivci LinuxSoftu mohou při registraci uplatnit kód LIN350, který jim přinese zvýhodněné vstupné s 50% slevou.
Přidat komentář

6.11.2018 2:04 /František Kučera
Říjnový pražský sraz spolku OpenAlt se koná v listopadu – již tento čtvrtek – 8. 11. 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 umění a technologie, IoT, CNC, svobodný software, hardware a další hračky.
Přidat komentář

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ář

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

> Poslední diskuze

13.12.2018 10:57 / Jan Mareš
Re: zavináč

2.12.2018 23:56 / František Kučera
Sraz

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

Více ...

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