Algoritmy vyhledávání v textu

Knuth-Morris-Pratt

$$\begin{array}{rl}& \text{KMP – vyhledaˊvaˊnıˊ jedneˊ jehly}\\ & \text{Vstup: Jehla }\iota [\mathrm{1..}J],\text{seno }\sigma [\mathrm{1..}S]\\ & \text{Vyˊstup: Vsˇechny pozice }k\text{ tak, zˇe }\sigma [k..k+J-1]=\iota \\ & \text{Pomocnaˊ konstrukce automatu – prefixoveˊ funkce}\\ & Z[0]\leftarrow \text{nedef},Z[1]\leftarrow 0\\ & \text{for }i=\mathrm{2..}J:\\ & s\leftarrow Z[i-1]\\ & \text{while }s\ne 0\wedge \iota [s+1]\ne \iota [i]:s\leftarrow Z[s]\\ & \text{if }\iota [s+1]=\iota [i]:s\leftarrow s+1\\ & Z[i]\leftarrow s\\ & \text{Hledaˊnıˊ znaku˚ v seneˇ}\\ & s\leftarrow 0\\ & \text{for }i=\mathrm{1..}S:\\ & \text{while }s\ne 0\wedge \iota [s+1]\ne \sigma [i]:s\leftarrow Z[s]\\ & \text{if }\iota [s+1]=\sigma [i]:s\leftarrow s+1\\ & \text{if }s=J:\text{ohlaˊsıˊme }i-J+1,s\leftarrow Z[s]\\ & \text{Komplexnost: }\Theta (J+S)\end{array}$$

Analýza a důkaz správnosti:

• Konstrukce prefix‑funkce $Z[i]$ říká, jaký je nejdelší vlastní prefix jehly, který je zároveň suffixem $\iota [\mathrm{1..}i]$. Tvoříme to spojenými kroky posunů přes $Z$ dopředu a zpět – každým znakem buď $s$ přibude, nebo „skočíme zpátky“ po $Z[s]$. Celkem tedy každé $i$ provede amortizovaně konstantu operací, dohromady $\Theta (J)$.
• Během hledání v seně platí invariant: $s$ označuje délku nejdelšího prefixu jehly, který je_suffixem_ právě čtené části sena. Analogicky k výstavě automatu. Pohybem $while$ se „vracíme“ pomocí $Z$, pokud nedojde ke shodě, a při shodě zvyšujeme $s$. Celkem v každé pozici se provede maximálně 1 dopředný či zpětný krok, tedy $\Theta (S)$.
• Správnost: Jakmile $s$ dosáhne $J$, máme úplné shodné $\sigma [i-J+\mathrm{1..}i]=\iota$. Poté $s$ nastavíme na $Z[s]$, abychom mohli pokrýt i překrývající se výskyty.

---

Aho-Corasicková

Popis problému

Chceme nalézt všechny dvojice $(k,i)$ takové, že $\sigma [k:k+J_i]={\iota }_i$, tj. jehla ${\iota }_i$ se vyskytuje v seně $\sigma$ na pozici $k$.

Výstup může být superlineární – například pokud jsou jehly vzájemnými sufixy.

Cílem je nalezení všech výskytů v čase

$$\Theta \left(\sum _i{J}_i+S+V\right),$$

kde $J_i$ jsou délky jehel, $S$ délka sena a $V$ počet výskytů.

---

Struktura automatu

Automat se skládá z:

• Dopředných hran: písmenkový strom prefixů jehel.
• Zpětných hran: vedou do nejdelšího vlastního sufixu stavu, který je zároveň jiným stavem.
• Zkratek: vedou do nejbližšího koncového stavu po zpětných hranách.

U každého stavu si pamatujeme:

• $Zp\check{e}t(s)$ – kam vede zpětná hrana,
• $Zkratka(s)$ – zkrácená hrana do koncového stavu,
• $Slovo(s)$ – je-li ve stavu koncové slovo,
• $Dop\check{r}edu(s,x)$ – kam vede dopředná hrana po znaku $x$.

---

$$\begin{array}{rl}& \text{Procedura AcKrok (jeden krok automatu)}\\ & \text{Vstup: Jsme ve stavu }s,\text{ prˇecˇetli jsme znak }x\\ & 1.\text{Dokud }\text{Doprˇedu}(s,x)=\varnothing \wedge s\ne \text{korˇen}:s\leftarrow \text{Zpeˇt}(s)\\ & 2.\text{Pokud }\text{Doprˇedu}(s,x)\ne \varnothing :s\leftarrow \text{Doprˇedu}(s,x)\\ & \text{Vyˊstup: Novyˊ stav }s\end{array}$$ $$\begin{array}{rl}& \text{Algoritmus AcHledej (spusˇteˇnıˊ automatu na danyˊ rˇeteˇzec)}\\ & \text{Vstup: Seno }\sigma ,\text{ zkonstruovanyˊ automat}\\ & 1.s\leftarrow \text{korˇen}\\ & 2.\text{Pro znaky }x\in \sigma \text{ postupneˇ provaˊdıˊme:}\\ & 3.s\leftarrow \text{AcKrok}(s,x)\\ & 4.j\leftarrow s\\ & 5.\text{Dokud }j\ne \varnothing :\\ & 6.\text{Je-li }\text{Slovo}(j)\ne \varnothing :\\ & 7.\text{Ohlaˊsıˊme }\text{Slovo}(j)\\ & 8.j\leftarrow \text{Zkratka}(j)\end{array}$$ $$\begin{array}{rl}& \text{Algoritmus AcKonstrukce}\\ & \text{Vstup: Slova }{\iota }_1,\dots ,{\iota }_n\\ & 1.\text{Zalozˇıˊme strom, kteryˊ obsahuje pouze korˇen }r\\ & 2.\text{Vlozˇıˊme do stromu slova }{\iota }_1,\dots ,{\iota }_n,\text{ nastavıˊme }\text{Slovo}\text{ ve vsˇech stavech}\\ & 3.\text{Zpeˇt}(r)\leftarrow \varnothing ,\text{Zkratka}(r)\leftarrow \varnothing \\ & 4.\text{Zalozˇıˊme frontu }F\text{ a vlozˇıˊme do nıˊ syny korˇene}\\ & 5.\text{Pro vsˇechny syny }s\text{ korˇene: }\text{Zpeˇt}(s)\leftarrow r,\text{Zkratka}(s)\leftarrow \varnothing \\ & 6.\text{Dokud }F\ne \varnothing :\\ & 7.\text{Vybereme }i\text{ z fronty }F\\ & 8.\text{Pro vsˇechny syny }s\text{ vrcholu }i:\\ & 9.z\leftarrow \text{AcKrok}(\text{Zpeˇt}(i),\text{pıˊsmeno na hraneˇ }is)\\ & 10.\text{Zpeˇt}(s)\leftarrow z\\ & 11.\text{Pokud }\text{Slovo}(z)\ne \varnothing :\text{Zkratka}(s)\leftarrow z\\ & 12.\text{Jinak }\text{Zkratka}(s)\leftarrow \text{Zkratka}(z)\\ & 13.\text{Vlozˇıˊme }s\text{ do fronty }F\\ & \text{Vyˊstup: Strom, pole }\text{Slovo},\text{Zpeˇt},\text{Zkratka}\end{array}$$

---

Důkaz složitosti

• Každý krok v $AcHledej$ běží v čase $O(1)$ (díky zpětným a zkratkovým hranám).
• Hlásíme výskyty v čase $O(V)$.
• Konstrukce automatu běží v čase $\Theta \left(\sum J_i\right)$, protože každé hledání jedné jehly simuluje algoritmus KMP. Celková složitost:

$$\Theta \left(\sum _i{J}_i+S+V\right)$$