Obsah

IN17 Algoritmy pro práci s řetězci
Diskuze

IN17 Algoritmy pro práci s řetězci

(Vyhledávání vzorků v textu. Naivní vyhledávání. Algoritmus Karpův-Rabinův. Algoritmus založený na konečných automatech. Složitost vyhledávání.)

Vypracovanie

Vyhľadávanie vzorky v texte

Je daný text T a vzorka (alebo pattern) P - reťazce nad abecedou ∑. Úlohou je vyhľadať všetky výskyty vzorky v texte. Text je daný ako pole T[1..n], vzorka ako P[1..m].

Hovoríme, že vzorka P sa vyskytuje v texte T s posunom s ak $0 \leq s \leq n-m$ a $T[s+1..s+m] = P[1..m]$ (t.j. $T[s+j] = P[j],\ 1 \leq j \leq m$ ). Číslo s uvedených vlastností sa nazýva platným posunom pre text T a vzorku P.

Problém vyhľadania vzorky môžeme formulovať ako úlohu nájsť pre dané T a P všetky platné posuny. Na riešenie tohto problému môžeme použiť rôzne algoritmy, ktoré sa líšia zložitosťou predspracovania textu a samotného vyhľadávania:

naivné vyhľadávanie
Karp-Rabinov algoritmus
algoritmus založený na konečných automatoch
algoritmus Knuth-Morris-Pratt
algoritmus Boyer-Moore

Naivné vyhľadávanie

NAIVNE_VYHLADAVANIE(T,P) 
for s = 0 to n-m do 
   if P[1..m] = T[s+1..s+m] 
      then print "s je platny posun" fi 
od

Ide o naivné vyhľadávanie: vzorku P postupne „prikladáme“ (posúvame o jedno miesto doprava v texte) k textu T a porovnávame jednotlivé písmená až kým sa vzorka nedá už posunúť (jej prvé písmeno je na pozícii n-m v texte).

Zložitosť: cyklus sa vykoná n-m+1 krát, v každom cykle sa vykoná m porovnaní. Spolu teda $O((n-m+1)m)$ . Iba v najhoršom prípade (vzorka a príslušná časť textu sa líšia len v poslednom písmene) sa vykoná m porovnaní (v najlepšom prípade len 1 porovnanie).

Karp-Rabinov algoritmus

Karp-Rabinov algoritmus využíva naivné vyhľadávanie, ale zameriava sa na zrýchlenie porovnávania vzorky s časťou textu (časť algoritmu $P[1..m] = T[s+1..s+m]$ ), používa na to hašovaciu funkciu.

Predpokladajme, že $\Sigma = \{0,1,...,9\}$ . Každý reťazec nad abecedou $\Sigma$ môžeme chápať ako číslo zapísané v desiatkovej sústave. Označme p číslo zodpovedajúce reťazcu $P[1..n]$ a t_s čísla zodpovedajúce reťazcom $T[s+1..s+m]$ . Problém overiť, či s je platným posunom sa redukuje na problém overiť, či t_s = p.

KARP_RABIN(T[1..n],P[1..m]) 
hpat := hash(P[1..m])  //predspracovanie 
for s = 0 to n-m do 
   hs := hash(T[s+1..s+m]) 
   if (hs == hpat) 
      if P[1..m] = T[s+1..s+m] 
        then print "s je platny posun" fi 
   fi 
od

Najskôr si predspracujeme vzorku (vypočítame jej hash), v našom prípade pomocou Hornerovej schémy (ak a=1, b=2, c=3, cast textu 'ab' = 12, 'bc' = 23) v čase $\Theta (m)$ . Podobne spočítame hash $T[1..m]$ v čase $\Theta (m)$ . Trik Karp-Rabinovho algoritmu spočina v tom, že hash ďalšej časti textu (T[2..m+1] atď.) môžeme vypočítať z predchádazjúceho hasha v konštantnom čase. Zvyšné hashe (t₁..t_n-m teda spočítame v čase $\Theta (n-m)$ .

Ak sú čísla p,t_s príliš veľké, používa sa výpočet modulo q, kde typicky q je prvočíslo také, že 10q ≈ počítačové slovo. Test t_s = p sa nahradí testom $t_s \equiv\ p\ (mod\ q)$ . Číslo s, pre ktoré platí uvedená rovnosť je len potenciálnym posunom, jeho platnosť sa musí overiť porovnaním príslušných reťazcov.

Zložitosť predspracovania je $\Theta (m)$ , zložitosť výpočtu v najhoršom prípade (t.j ak pre všetky s platí skúmaná rovnosť) je $O((n-m+1)m)$ . Zložitosť konkrétneho výpočtu je daná počtom platných posunov. Ak očakávaný počet platných posunov je c, tak očakávaná zložitosť algoritmu je v $O((n-m+1)+cm)$ .

Algoritmus Karp-Rabin je vhodné použiť, ak v texte hľadáme celé vety (neočakávame, že výskytov bude veľa), v tom prípade algoritmus dosahuje priemernú zložitosť $O(n)$ . V prípade hľadania krátkych slov, ktorých je v texte veľa alebo použitia nevhodnej hashovacej funkcie je zložitosť podobná ako pri použití naivného vyhľadávania.

Algoritmus založený na konečných automatoch

Pre danú vzorku P[1..m] skonštruujeme konečný automat $A=(\{0,...,m\},\Sigma,\delta,\{0\},\{m\})$ . Následne text $T[1..n]$ spracujeme automatom A.

FINITE_AUTOMATON_MATCHER(T,A) 
q ← 0 
for i = 1 to n do 
   q ← δ(q,T[i]) 
   if q = m then print i-m je platný posun fi 
od

Zložitosť spracovania textu je $\Theta (n)$ , musíme ale ešte skonštruovať konečný automat A (jeho prechodovú funkciu).

Nech $P_q = P[1]..P[q]$ a $T_q = T[1]..T[q]$ . Definujeme sufixovú funkciu $\sigma : \Sigma^* \rightarrow \{0,1,...,m\}$ , kde $\sigma(x)$ je dĺžka najdlhšieho prefixu vzorky P, ktorý je sufixom slova x.

Napr. pre P = popapopa je $\sigma (\epsilon) = 0$ , $\sigma (papap) = 1$ , $\sigma (papop) = 3$ , $\sigma (popapo) = 6$ .

Konečný automat pre P je $A=(\{0,...,m\},\Sigma,\delta,\{0\},\{m\})$ , kde prechodová funkcia $\delta$ je definovaná predpisom:
$\delta(q,a) = \sigma(P_{q}a)$ Prechodovú funkciu $\delta$ konštruujeme podľa nasledovného algoritmu:

1 AUTOMAT(P,Σ) 
2 for q = 0 to m do 
3    for každé a ∈ Σ  do 
4       k ←  min(m+1,q+2) 
5       repeat k ← k-1 until P_k je sufixom P_qa 
6       δ(q,a) ← k  
7    od 
8 od 
9 return δ

Príkladom automatu, ktorý v texte rozoznáva reťazce abaa je konečný automat v otázke Konečné automaty, ktorý si jemne upravíme:
$\delta(q_{abaa},a) = q_{a}$ $\delta(q_{abaa},b) = q_{ab}$

Predmety

IB108: Návrh algoritmů II, prof. RNDr. Ivana Černá, CSc.
PV030: Textové informační systémy, RNDr. Petr Sojka, Ph.D.

Literatúra

* Rabin-Karp string search algorithm, Wikipedia
* slidy k Návrhu algoritmov II

Vypracoval

Dušan Katona, ICQ: 426 081 873
hotovo: <99%>
môžete kluďne niečo doplniť alebo opraviť

Otázku si přečetl pan RNDr. Jan Bouda a rámcově prošel. Jeho podněty pro doplnění textu, opravy nesrovnalostí a odstranění matoucích či k otázce se nevztahujících textů byly do otázky zaneseny. Tato kontrola je jen rámcová, stále se může stát, že v otázce zůstala zapomenutá chybka či nesrovnalost, vyučující za toto nenese odpovědnost, berte tuto rámcovou kontrolu jako formu pomoci od vyučujících pro studenty.