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í
[editovat | editovat zdroj]Algoritmy můžeme rozdělit podle počtu vzorků, které používají.
Algoritmy používající jeden vzorek
[editovat | editovat zdroj]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ů
[editovat | editovat zdroj]- 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ů
[editovat | editovat zdroj]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
[editovat | editovat zdroj]Reference
[editovat | editovat zdroj]V tomto článku byl použit překlad textu z článku String searching algorithm na anglické Wikipedii.
Literatura
[editovat | editovat zdroj]- 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
[editovat | editovat zdroj]
Obrázky, zvuky či videa k tématu algoritmy pro vyhledávání v textu na Wikimedia Commons - R. S. Boyer and J S. Moore, A fast string searching algorithm, Carom. ACM 20, (10), 262–272(1977).
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 32: String Matching, pp.906–932.
