====== 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 <math>0 \leq s \leq n-m</math> a <math>T[s+1..s+m] = P[1..m]</math> (t.j. <math>T[s+j] = P[j],\ 1 \leq j \leq m </math>). Čí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 ====
<code pascal>
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
</code>
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 <math>O((n-m+1)m)</math>. 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 <math>P[1..m] = T[s+1..s+m]</math>), používa na to hašovaciu funkciu.

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

<code pascal>
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
</code>

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 <math>\Theta (m)</math>. Podobne spočítame hash <math>T[1..m]</math> v čase <math>\Theta (m)</math>. 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<sub>1</sub>..t<sub>n-m</sub>// teda spočítame v čase <math>\Theta (n-m)</math>.

Ak sú čísla //p,t<sub>s</sub>// 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<sub>s</sub> = p// sa nahradí testom <math>t_s \equiv\ p\ (mod\ q)</math>. Čí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 <math>\Theta (m)</math>, **zložitosť výpočtu** v najhoršom prípade (t.j ak pre všetky //s// platí skúmaná rovnosť) je <math>O((n-m+1)m)</math>. 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 <math>O((n-m+1)+cm)</math>.

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ť <math>O(n)</math>. 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 <math>A=(\{0,...,m\},\Sigma,\delta,\{0\},\{m\})</math>. Následne text <math>T[1..n]</math> spracujeme automatom //A//.
<code pascal>
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
</code>
Zložitosť spracovania textu je <math>\Theta (n)</math>, musíme ale ešte skonštruovať konečný automat //A// (jeho prechodovú funkciu).

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

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

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

<code pascal>
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 δ   
</code>

Zložitosť konštrukcie automatu je <math>O(m^3 |\Sigma |)</math> (riadok 2 **m**-krát, riadok 3 **|Σ|**-krát a riadok 5 v najhoršom prípade **m<sup>2</sup>**-krát). Existuje efektívnejšia procedúra zložitosti <math>O(m|\Sigma |)</math>.
**Zložitosť predspracovania** je teda v <math>O(m|\Sigma |)</math> a **zložitosť vyhľadávania** pomocou konečných automatov v <math>\Theta (n)</math>.

Príkladom automatu, ktorý v texte rozoznáva reťazce //abaa// je konečný automat v otázke [[home:inf:ap9#prechodovym_grafem|Konečné automaty]], ktorý si jemne upravíme:
<math>\delta(q_{abaa},a) = q_{a}</math>
<math>\delta(q_{abaa},b) = q_{ab} </math>

===== Predmety =====
  * [[https://is.muni.cz/auth/predmety/predmet.pl?fakulta=1433;obdobi=3725;id=427609;|IB108]]: Návrh algoritmů II, prof. RNDr. Ivana Černá, CSc.
  * [[https://is.muni.cz/auth/predmety/predmet.pl?fakulta=1433;obdobi=3725;id=427675;|PV030]]: Textové informační systémy, RNDr. Petr Sojka, Ph.D.

===== Literatúra =====
* [[http://en.wikipedia.org/wiki/Karp-Rabin|Rabin-Karp string search algorithm]], Wikipedia
* [[http://www.fi.muni.cz/usr/cerna/NAII/|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.

~~DISCUSSION~~