O vyhledávání v textu


V dnešní době, kdy se většina dokumentů (ať už na úřadech nebo v běžných podmínkách) vede na počítačích, a tedy v elektronické podobě, je potřeba míti dostatečně silné nástroje k tomu, aby se v daných dokumentech vyhledal nějaký text (slovo, věta apod.) v co nejkratším možném čase. Proto se řadu let vyvíjí různé algoritmy, které tento úkol s odlišnými úspěchy plní.

Tyto algoritmy jsou běžnému uživateli počítače schovány v jiných větších celcích jako jsou různé textové editory, kde je občas nutné nějaké to slovo v textu vyhledat (potažmo zaměnit za jiné). Dalším příkladem mohou být vyhledávací systémy v knihovnách, vyhledávání v databázích, všelijaké vyhledávací servery apod. Principy vyhledávání vzorků v textu se také používají i v jiných oborech než v informatice, příkladem může být například hledání "vzorků" v DNA šroubovici.

Z toho vyplývá, že vyhledávání v textu je poměrně rozsáhlý problém o jehož užitečnosti jistě není sporu. Proto je určitě užitečné uvést si nějaké příklady algoritmů, které tento problém řeší, popsat je a porovnat.


Algoritmy se mohou dělit do několika možných kategorií podle toho za jakým účelem se používají nebo podle svého původu. Můžeme se tedy setkat s algoritmy, které vyhledávají pouze jeden vzorek v daném textu, v jiných případech je možno vyhledávat množinu více vzorků. Rozdíl je také v tom, že některé algoritmy naleznou pouze první výskyt vzorku v textu, jiné naleznou všechny výskyty. Existují algoritmy, které se inspirovaly i jinými obory informatiky jako je např. teorie automatů.


V tomto článku bych se rád věnoval zejména dvěma algoritmům. Prvním je Knuth-Morris-Prattův algoritmus (KMP), druhým je Boyer-Mooreův algoritmus (BM). Společným rysem obou je skutečnost, že vyhledávají všechny výskyty jednoho vzorku v daném textu. Na KMP se dá nahlížet jako na upravený konečný (v tomto případě vyhledávací) automat. BM se na druhou stranu jeví jako naivní vyhledávací algoritmus se dvěmi důležitými heuristikami.

Představitelem skupiny algoritmů, které vyhledávají celou množinu vzorků je např. algoritmus Aho-Corasickové, který je založen na poznatcích právě z teorie automatů.

V dalším odstavci bych rád zmínil další dva zajímavé a relativně nové algoritmy: Baeza-Yates-Gonnet, který je založen na vyhledávání pomocí bitových masek, a algoritmus Quicksearch, jehož autorem je D.M. Sunday.


Nejprve si však zaveďme několik důležitých pojmů a definic, které se budou hodit k pozdějšímu popisu a zkoumání algoritmů.


I přesto, že většina lidí v principu chápe, co vyhledávání v textu je, definujme si tento pojem alespoň trochu přesněji a formálněji.

Nejprve si vysvětlíme některé základní pojmy potřebné pro popis daného problému. Abecedou Σ rozumíme konečnou množinu znaků. Například Σ={0,1} nebo Σ={a,b,...,z}. Prvky této množiny se často nazývají znaky, písmena nebo symboly. Slovem v abecedě Σ je míněna konečná posloupnost znaků z této abecedy. Prázdným slovem se rozumí posloupnost délky 0 a obvykle se značí ε (ε nepatří do Σ).

Množina všech slov v abecedě Σ se značí Σ*. Na této množině je definována operace skládání (konkatenace), která dvěma slovům x a y délek m a n přiřadí slovo xy délky m+n. Tato operace je asociativní (to znamená, že (xy)z je to samé slovo jako x(yz)) a pro více než jednoprvkovou abecedu nekomutativní (v případě jednoprvkové abecedy: aa"=" aa, pokud Σ ={a}; v případě víceprvkové např. xy není rovno yx pro x, y navzájem různá). Roli jednotkového prvku této operace hraje prázdné slovo ε, tedy xε=εx=x pro každé x z ε.

Nechť x je prvkem Σ*. Potom délkou slova x rozumíme počet znaků v x. Zapisujeme |x|. Tedy jak bylo poznamenáno |ε|=0.

Řekneme, že slovo x z Σ* je předponou (prefixem) slova y z Σ*, existuje-li takové slovo u z Σ*, že xu=y. Takové u zřejmě existuje nejvýše jedno a je-li neprázdné, říkáme, že x vlastní předpona. Obdobně, řekneme, že slovo x z Σ* je příponou (suffixem) slova y z Σ*, existuje-li takové slovo v z Σ*, že vx=y. Opět takové v existuje nejvýše jedno a je-li neprázdné, mluvíme o vlastní příponě. Zřejmě platí, že ε je vlastní příponou a předponou každého slova z Σ*. Podobně každé slovo je svou jedinou nevlastní příponou i předponou.

Pro příklad si uveďme, že slovo ab je předponou slova abbdad a to předponou vlastní. Zároveň je vlastní příponou slova abbab.

Pro další účely si zaveďme ještě jeden jednoduchý pojem, prefix o k znacích. Prefix vzorku P[1..m] o k znacích, tedy P[1..k], budeme značit Pk. Podobně budeme mít tento pojem i pro prohledávaný text (Tk).

Nyní se vraťme k formulaci problému vyhledávání v textu. Nechť máme danou abecedu Σ a tím i množinu Σ*. Předpokládejme, že máme dány dva textové řetězce (nejlepší je představit si je jako pole jednotlivých znaků). Řetězec P = p1...pm (nebo jako pole znaků P[1..m]) budeme nazývat vzorek. Jeho délka je m. Řetězec T = t1...tn (T[1..n]) bude prohledávaný text délky n. Oba řetězce jsou slova z Σ*.

Říkáme, že vzorek P se v textu T nachází s posunutím s (jinými slovy řečeno, nachází se v textu T na pozici s+1), jestliže 0<=s<=n-m a zároveň T[s+1..s+m]=P[1..m] (pro všechna j 1<=j<=m ts+j=pj). Pokud se vzorek P v prohledávaném textu T nachází nazýváme s platným posunem . Jinak je tento posun neplatný.

školní rok : 2004 -2005
Tato stránka je testovací a vznikla pro účely výuky Programování webu v Dreamweaveru MX 2004