Algoritmy pro vyhledávání v textu

Technology

12 hours ago

Author

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ů. +more 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

Literatura

Externí odkazy

R. S. +more Boyer and J S. Moore, [url=http://www. cs. utexas. edu/~moore/publications/fstrpos. pdf]A fast string searching algorithm[/url], 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. . Chapter 32: String Matching, pp. 906-932.