Algoritmy pro vyhledávání v textu

Algoritmy pro vyhledávání v textu jsou důležitou třídou algoritmů pro práci s textovými řetězci. Slouží ke hledání místa, kde se jeden či více řetězců (vzorků) shoduje s částí většího textu.

Nechť Σ je abeceda (konečná množina). Formálně jsou vzorek i prohledávaný text řetězce prvků množiny Σ, což může být běžně používaná abeceda (například písmena A až Ž), binární abeceda (Σ = {0,1}) nebo abeceda DNA (Σ = {A,C,G,T}) používaná v bioinformatice.

V praxi může mít způsob, jakým je řetězec zakódován, vliv na samotný vyhledávací algoritmus. Obzvláště pokud je použita proměnná délka kódování, trvá dlouho (vzhledem k délce textu N) nalezení N-tého znaku a znatelně to zpomaluje mnoho pokročilejších vyhledávacích algoritmů. Abychom tento problém vyřešili, můžeme místo samotného řetězce hledat posloupnost, pomocí níž je zakódován. Pokud však k tomu kódování není přizpůsobeno, může takové řešení vést k falešným shodám.

Základní rozdělení

Algoritmy můžeme rozdělit podle počtu vzorků, které používají.

Algoritmy používající jeden vzorek

Nechť m je délka vzorku a n je délka prohledávaného textu.

AlgoritmusČas potřebný pro předzpracováníČas potřebný pro vyhledání
Naivní vyhledávání0Θ((n-m+1) m)
Rabinův–Karpův algoritmusΘ(m)průměrně Θ(n+m),
nejhůře Θ((n-m+1) m)
vyhledávání založené na konečném automatuΘ(m |Σ|)Θ(n)
Knuthův–Morrisův–Prattův algoritmusΘ(m)Θ(n)
Boyerův–Mooreův algoritmusΘ(m + |Σ|)Ω(n/m), O(n)

Algoritmy používající konečnou množinu vzorků

  • Aho–Corasick algoritmus pro shodů řetězců
  • Commentz–Walter algoritmus
  • Rabin–Karp algoritmus pro vyhledávání v textu

Algoritmy používající nekonečně mnoho vzorků

V tomto případě nemohou být vzorky jednoduše vyjmenovány. Obvykle je reprezentujeme pomocí regulární gramatiky nebo regulárního výrazu.

Odkazy

Reference

V tomto článku byl použit překlad textu z článku String searching algorithm na anglické Wikipedii.

Literatura

  • POKORNÝ, Jaroslav; SNÁŠEL, Václav; HÚSEK, Dušan, 1998. Dokumentografické informační systémy. Praha: Karolinum – vydavatelství Univerzity Karlovy. 158 s. ISBN 80-7184-764-X. S. 25–35. 
  • MELICHAR, Bořivoj, 1994. Textové informační systémy. Praha: vydavatelství ČVUT. 101 s. ISBN 80-01-01206-9. S. 11–43. 

Externí odkazy