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

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ů

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

14.5.2018 7:28 /František Kučera
Květnový pražský sraz spolku OpenAlt se koná již tento čtvrtek – 17. 5. 2018 od 18:00 v Kavárně Ideál (Sázavská 30, Praha), kde máme rezervovaný salonek. Tentokrát na téma: Audio – zvuk v GNU/Linuxu.
Přidat komentář

7.5.2018 16:20 /František Kučera
Na stránkách spolku OpenAlt vyšla fotoreportáž Pražské srazy 2017 dokumentující srazy za uplynulý rok. Květnový pražský sraz na téma audio se bude konat 17. 5. 2018 (místo a čas ještě upřesníme).
Přidat komentář

17.4.2018 0:46 /František Kučera
Dubnový pražský sraz spolku OpenAlt se koná již tento čtvrtek – 19. 4. 2018 od 18:00 v Kavárně Ideál (Sázavská 30, Praha), kde máme rezervovaný salonek. Tématem tohoto srazu bude OpenStreetMap (OSM) aneb svobodné mapy.
Přidat komentář

16.3.2018 22:01 /František Kučera
Kulatý OpenAlt sraz v Praze oslavíme klasicky: u limonády a piva! Přijďte si posedět, dát si dobré jídlo a vybrat z mnoha piv do restaurace Kulový blesk, který najdete v centru Prahy nedaleko metra I. P. Pavlova na adrese Sokolská 13, Praha 2. Sraz se koná ve čtvrtek 22. března a začínáme v 18:00. Heslo: OpenAlt. Vezměte s sebou svoje hračky! Uvítáme, když si s sebou na sraz vezmete svoje oblíbené hračky. Jestli máte nějaký drobný projekt postavený na Arduinu, nějakou zajímavou elektronickou součástku, či třeba i pěkný úlovek z crowdfundingové akce, neváhejte. Oslníte ostatní a o zábavu bude postaráno.
Přidat komentář

13.2.2018 0:41 /František Kučera
Únorový pražský sraz OpenAltu se koná 15. 2. 2018 a tentokrát se vydáme na návštěvu do jednoho pražského datacentra. Sejdeme se v 17:50 v severovýchodní části nástupiště tramvajové zastávky Koh-I-Noor. Po exkurzi se přesuneme do restaurace U Pštrosa (Moskevská 49), kde probereme tradiční témata (svobodný software a hardware, DIY, CNC, SDR, 3D tisk…) a tentokrát bude k vidění i IoT brána od The Things Network.
Přidat komentář

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

> Poslední diskuze

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í?

16.1.2018 1:08 / Ivan Pittner
verejna ip od o2 ubuntu

15.1.2018 17:26 / Mira Harvalik
Re: Jak udělat HTML/Javascript swiping gallery do mobilu?

30.12.2017 20:16 / Michal Knoll
odmocnina

Více ...

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