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

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ů

1.12.2016 22:13 /František Kučera
Máš rád svobodný software a hardware nebo se o nich chceš něco dozvědět? Přijď na sraz spolku OpenAlt, který se bude konat ve čtvrtek 8. prosince od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5). Sraz bude tentokrát tématický. Bude retro! K vidění budou přístroje jako Psion 5mx nebo Palm Z22. Ze svobodného hardwaru pak Openmoko nebo čtečka WikiReader. Přijďte se i vy pochlubit svými legendami, nebo alespoň na pivo. Moderní hardware má vstup samozřejmě také povolen.
Komentářů: 1

4.9.2016 20:13 /Pavel `Goldenfish' Kysilka
PR: Dne 22.9.2016 proběhne v Praze konference Cloud computing v praxi. Tématy bude např. nejnovější trendy v oblasti cloudu a cloudových řešení, provozování ERP v cloudu, o hostování různých typů softwaru, ale třeba i o zálohování dat nabízeném podnikům formou služby.
Přidat komentář

1.9.2016 11:27 /Honza Javorek
Česká konference o Pythonu, PyCon CZ, stále hledá přednášející skrz dobrovolné přihlášky. Máte-li zajímavé téma, neváhejte a zkuste jej přihlásit, uzávěrka je již 12. září. Konference letos přijímá i přednášky v češtině a nabízí pomoc s přípravou začínajícím speakerům. Řečníci mají navíc vstup zadarmo! Více na webu.
Přidat komentář

27.8.2016 8:55 /Delujek
Dnes po 4 letech komunitního vývoje vyšla diaspora 0.6.0.0
diaspora* je open-source, distribuovaná sociální síť s důrazem na soukromý
Více v oficiálním blog-postu
Přidat komentář

24.8.2016 6:44 /Ondřej Čečák
Poslední týden CFP LinuxDays 2016; pokud byste rádi přednášeli na LinuxDays 2016 8. a 9. října v Praze, můžete svůj příspěvek přihlásit, následovat bude veřejné hlasování.
Přidat komentář

9.8.2016 22:56 /Petr Ježek
Zařazení souborového systému reiser4 do jádra 4.7 znamená konečně konec patchování jádra jen kvůli možnosti použít reiser4.
Přidat komentář

12.7.2016 13:14 /František Kučera
Spolek OpenAlt zve na 130. distribuovaný sraz příznivců svobodného softwaru a otevřených technologií (hardware, 3D tisk, SDR, DIY, makers…), který se bude konat ve čtvrtek 21. července od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5).
Přidat komentář

11.7.2016 16:53 /Redakce Linuxsoft.cz
Konference LinuxDays hledá přednášející. Přihlášky poběží do konce prázdnin, v září bude hlasování a program. Více na https://www.linuxdays.cz/2016/cfp/.
Přidat komentář

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

> Poslední diskuze

4.12.2016 22:54 / František Kučera
Dárek

9.11.2016 7:42 / Mane
hardwood floor waxing

8.11.2016 13:38 / Mira
Konfigurace maldet na Centos serveru

2.11.2016 11:06 / Warlock
Odkaz v PHP

20.10.2016 0:13 / Jan Kuba
Re: Basic

Více ...

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