h1. Z-Algorithm
categorie, autor etc
h2. Date Generale
h2(#introducere). Date Generale
Determinarea tuturor apariţiilor unui model, într-un text, este o problemă frecvent întâlnită la editoarele de texte. De obicei, textul este un document în editare şi modelul căutat este un anumit cuvânt, dat de utilizator. Algoritmi eficienţi pentru această problemă pot ajuta la îmbunătăţirea performanţelor editoarelor de texte. Algoritmi de potrivire a şirurilor sunt utilizaţi, de asemenea, în căutarea de modele particulare în secvenţe ADN.
Pe lângă cunoscuţii algoritmi de potrivire a şirurilor - Rabin Karp şi KMP - există şi un al treilea algoritm numit Z-Algorithm. În continuare este prezentat acest algoritm.
Determinarea tuturor apariţiilor unui model, într-un text, este o problemă frecvent întâlnită la editoarele de texte. De obicei, textul este un document în editare şi modelul căutat este un anumicat cuvânt, dat de utilizator. Algoritmi eficienţi pentru această problemă pot ajuta la îmbunătăţirea performanţelor editoarelor de texte. Algoritmi de potrivire a şirurilor sunt utilizaţi, de asemenea, în căutarea de modele particulare în secvenţe ADN. Problema poate fi rezolvata in mai multe moduri cu diferite complexitati. Complexitatea vizata este O(|P|+|T|). Exista 3 algoritmi care rezolva problema in aceasta complexitate : Rabin Karp, KMP si Z-Algorithm. Rabin Karp sa comporta in practia mai prost din punct de vedere al timpului de executie, asa ca am sa il scot din start. Mari diferente intre KMP si Z-Algorithm nu exista, functia prefix din KMP respectiv functia zValues din zAlgorithm facand aproximativ acelasi lucru. O diferenta ar fi nivelul de intelegere a celor 2 algoritmi, z-algorithm poate fi inteles mai usor decat KMP. Alegerea algoritmului variaza in functie de problema si de cel care o rezolva. De exemplu problema '_X_':http://www.infoarena.ro/problema/x se rezolva mult mai usor cu zalgorithm. Un plus pentru zalgorithm ar fi ca poate fi inteles in totalitate.
h2. Introducere
Se dau două şiruri $P$ şi $T$ formate din litere mici şi mari ale alfabetului englez, şi din cifre. Se cere găsirea tuturor apariţiilor şirului $P$ ca subsecvenţă a şirului $T$. Pe lângă algoritmii Rabin-Karp şi KMP, care rezolvă această problemă în $O(|P| + |T|)$, şi Z-Algorithm rezolvă această problemă în aceeaşi complexitate.
Fie $S$ un string iar $k > 1$, o poziţie din acest string. Începând de la această poziţie vom considera toate secvenţele de forma $[k..j]$, unde $k <= j <= |S|$, astfel încât $S[k..j]$ se potriveşte cu prefixul lui $S$ de aceeaşi lungime cu secvenţa $[k..j]$. Dintre toate poziţiile pe care $j$ le poate lua o vom alege pe cea mai mare, si vom defini valoarea $jmax – k + 1$ ca fiind $Z[k]$. Dacă $S[k]$ e diferit de primul caracter, atunci un astfel de $j$ nu există iar $Z[k] = 0$. Altfel spus, $Z[k]$ e definit ca lungimea maximă astfel încât $S[k..k+Z[k]-1]$ se potriveşte cu secvenţa $S[1..Z[k]]$. (Stringul $S$ este indexat începând cu poziţia $1$).
h1. Despre ce e vorba ?
Fie $S = {aabadaabcaaba}$.
Vom defini Z-boxul pentru poziţia $k$ ca fiind secvenţa ce începe la poziţia $k$ şi se termină la poziţia $k + z[k] – 1$. Pentru o poziţie $k > 1$, vom considera toate Z-boxurile ce încep la poziţia $j$ astfel încât $2 <= j <= k$. Dintre toate aceste Z-boxuri vom selecta Z-boxul care are cel mai mare capăt drept şi îl vom numi $R[k]$. Pe lângă acest capăt drept vom mai ţine şi capătul stâng al acestui Z-box în $L[k]$. În continuare sunt prezentate $R[k]$ şi $L[k]$ asociate stringului $S$. Săgeţile indică Z-boxul fiecarei poziţii.
Algorimul e folosit pentru a gasi aparitiile unui text pattern intr-un alt text. Se da textul P si textul T; vrem sa gasim toate aparitiile lui P in T. Algoritmul vine cu o idee in felul urmator: fie stringul S si fie vectorul Z(i) = lungimea celei mai lungi secvente ce incepe la pozitia i si se gaseste la inceputul stringului S; adica, de exemplu daca Z(i) = 5 => secventa 0...4 e la fel cu i,..,i+5-1(fiind cea mai mare => S(5) != S(i+5)) . Bun, acum cunoscand aceste valori pentru fiecare pozitie din S problema determinarii tutoror aparitiilor devine una usoara. Definim stringul S = P(pattern) + T(textul in care vrem sa gasim pattern-ul). Acum avand Z(i) calculat ne vom uita la valorile din Z()de la pozitiile de unde incepe textul T(adica de la pozitia P.size(), stringul S e indexat de la 0); O aparitie e valabila daca Z(i) >= n(n = lungimea pattern-ului).
h1. Cum se calculeaza $Z()$ ?
Am voi arata cum se calculeaza valorile vectorului $Z()$ Z in complexitatea $O( |S| )$. Fie stringul S si vectorul Z(); definesc zBox ca fiind cea mai din dreapta secventa care apare la inceputul sirului. Deci pe parcursul calcularii vectorului Z() voi tine 2 variabile de genul St = capatul stang unde incepe secventa; Dr = capatul drept, unde se termina( Acest zBox va fi tot timpul cea mai din dreapta secventa; **!Atentie** asta nu inseamna ca e si cea mai lunga). Acum presuspun ca sunt la pozitia i. Vreau sa calculez Z(i). Valorile 0...i-1 sunt deja calculate.
Pentru inceput voi imparti pe 2 cazuri :
* **Cazul 1) i > Dr** => nu pot face nici o observatie logica, deci voi face brutul; adica voi lua caracater cu caracater si voi compara : iau caracterul i si il compar cu caracterul 0, apoi caracterul i+1 il compar cu caracterul 1(ma opresc cand gasesc 2 caractere diferite)
* **Cazul 2) i <= Dr**;
Pentru inceput o sa definesc :
lungAlpha = lungimea zBox-ului = Dr – St + 1;
lungBeta = lungimea secventei de la pozitia i la capatul drept al zBox-ului, adica = Dr – i + 1;
Imi propun sa mut zBox-ul la inceputul sirului (pentru ca eu stiu ca se afla acolo)
Fie aceasta noua secventa zBox2; valorea Z[i] o voi calcula pe baza unor observatii logice din zBox2; asa ca o sa am nevoie de simetricul lui i in raport cu zBox2 si de simetricul lui Dr tot in raport cu zBox2 =>
Dr2 = 0 + lungAlpha – 1;
i2 = Dr2 – lungBeta + 1;
Acest caz se imparte, la randul lui, in alte 3 subcazuri
** **Cazul 2.a: Z[i2] < lungBeta**(adica cea mai lunga secventa ce se gaseste la inceputul sirului si incepe la pozitia i2 nu depaseste zBox-ul)
=> **Z[i] = Z[i2];**
Fie stringul S :
!zalgorithm?A.bmp!
(nu prea are relevanta sa contina si caracatere)
Fie St = 7, Dr = 12 si i = 10; acum voi muta zBox-ul la inceput =>
lungAlpha = 6; lungBeta = 3;
St2 = 0; Dr2 = 5; i2 = 3;
Eu am calculat Z[i2] si stiu ca e < lungBeta => **Z[i] = Z[i2]**, e adevarat pentru ca Zbox e la fel cu Zbox2;
** **Cazul 2.b) Z[i2] > lungBeta** => **Z[i] = lungBeta**;
!zalgorithm?B2.bmp!
Acum voi face o modificare, i-ul va fi 11 nu 10 (pentru a fi mai clar pe exemplu)=>
St = 7, Dr = 12, I = 11; => St2 = 0; Dr2 = 5; i2 = 4;
Eu stiu acum ca Z[i2] > lungBeta; deci secventa [4..5] e la fel cu [0..1] si e la fel cu [11..12]
Avand in vedere ca Z[i2] > lungBeta => si caracterul 6 e la fel cu caracterul 2;
Doar ca se poate face o observatie din care rezulta ca **Z[i] = lungBeta**; Pentru a demonstra ca e asa voi presupune ca contrariul => Z[i] > lungBeta => S(13 = S(6) (care e = S(2)) daca acest lucru ar fi adevarat atunci Zbox-ul nu ar fi secventa [7..12] ci ar fi secventa [7..13] => Presupunerea initiala e **falsa** => **Z(i) = lungBeta**;
** **Cazul 2.c) Z[i2] = lungBeta** => **Z[i] = lungBeta + compara()**;
!zalgorithm?C.bmp!
Acum Z(i2) == lungBeta, de aici rezulta urmatoarele observatii :
S(2) != S(6)
S(6) != S(13)
Doar ca asta nu inseamna ca S(2) != S(13)(s-ar putea sa fie la fel; trebuie verificate) => **Z(i) = lungBeta + compara(lungBeta, Dr + 1)**;
Compara(i, j) = e o functie care primeste 2 indici si incepe sa compare caracaterele incepand cu cei 2 indici pana cand gaseste 2 caractere diferite.
p=. !zalgorithm?forIntroduction1.bmp!
h1. Analiza complexitatii
p=. !zalgorithm?forIntroduction2.bmp!
In primul rand complexitatea este liniara O(n + m); n = lungimea stringului P, m = lungimea stringului T; Complexitatea este liniara deoarece fiecare element este vizitat de cel mult 2 ori iar zBox-ul e tot timpul cea mai din dreapta secventa iar functia **compara()** realizeaza cel mult **n+m** comparatii.
h2. Preprocesare
În continuare vom prezenta partea de preprocesare, adică, calcularea vectorului $Z[]$. Când aflam valoarea $Z[k]$ vom avea nevoie doar de valorile $R[k-1]$ şi $L[k-1]$. De aceea nu are sens să ţinem aceste valori în doi vectori, aşa că le vom ţine în două variabile $R$ şi $L$ care vor fi actualizate la fiecare pas. Algoritmul începe să calculeze vectorul $Z[]$ începând cu poziţia $2$, $Z(1)$ fiind egal cu lungimea stringului. Să presupunem că ne aflăm la poziţia $k$, $k >= 2$, iar toate celelalte $k-1$ valori sunt calculate. Algoritmul ia în considerare următoarele cazuri:
* $Cazul 1: k > R.$ În acest caz algoritmul nu se poate folosi de nici o informaţie obţinută anterior. Astfel, algoritmul va efectua comparaţii între două caractere începând cu cel de pe poziţia $k$, respectiv poziţia $1$, până când va găsi o nepotrivire. Ca urmare, $Z[k]$ ia valoarea lungimii secvenţei care se potriveşte iar $L = k$ şi $R = k + Z[k] – 1$.
p=. !zalgorithm?case1.bmp!
* $Cazul 2: k <= R.$ De această dată ne putem folosi de informaţiile obţinute pentru poziţiile anterioare. Din moment ce $k <= R$ rezultă că poziţia $k$ face parte din Zbox-ul cel mai din dreapta. Prin definiţia lui $L$ şi $R$, $S[k]$ aparţine secventei $S[L..R]$. Notăm cu $A$ această secvenţă. $A$ se potriveşte cu prefixul de aceeaşi lungime al lui $S$. Astfel, caracterul $S[k]$ mai apare în secvenţa $S[1..|A|]$ la pozitia $k' = k – L + 1$. Secvenţa $S[k..R]$ apare şi în secvenţa $[1..|A|]$. Notăm cu $B$ secvenţa $S[k..R]$. Secvenţa $B$ coincide cu secvenţa $S[k'...|A|]$, unde $|A| = R - L + 1$. Următoarea imagine prezintă aceste lucruri:
p=. !zalgorithm?case2.bmp!
Cand $k'$ a fost calculat, s-a format un Z-Box de lungime $Z[k']$. O să-l numim $C$. Substringul $C$ este şi el un prefix de-al lui $S$. Astfel, $Z[k]$ va fi egal, cel puţin, cu minimul dintre $Z[k']$ şi $|B|$, unde $|B| = R – k + 1$. În continuare apar două cazuri:
* $Cazul 2a: Z[k'] < |B|.$ În acest caz $Z[k]$ are aceeaşi valoare ca şi $Z[k']$. Din moment ce $Z[k] < |B|$, variabilele $R$ şi $L$ rămân neschimbate. Următoarea imagine exemplifică acest caz:
p=. !zalgorithm?case2_a.bmp!
* $Cazul 2b: Z[k'] >= |B|$. În acest caz $Z[k]$ va fi cel puţin egal cu $|B|$. Dar acesta mai poate fi extins. Asta l-ar face pe $Z[k]$ mai mare decât $Z[k']$. Astfel, algoritmul încearca să extindă Z-Boxul lui $k$. Începe să facă comparaţii de la poziţiile $R + 1$ şi $|B| + 1$, unde $|B| = R – k + 1$, până când găseşte o nepotrivire. Notăm cu $q$ poziţia primei nepotriviri. Atunci, $Z[k] = q – 1 – (k – 1) = q – k$, $R = q - 1$ şi $L = k$. Următoarea imagine exemplifică acest caz:
p=. !zalgorithm?case2_b.bmp!
h2. Analiza complexităţii
După cum am menţionat anterior, algoritmul are complexitatea $O(|S|)$. Complexitatea liniara se datoreaza faptului că fiecare element este vizitat de cel mult $2$ ori, iar variabila $R$ doar creşte.
h2. Aplicaţii
Cum poate fi folosit vectorul $Z[]$? $Z[k] =$ lungimea celei mai lungi secvenţe ce începe la pozitia $k$ şi în acelasi timp se află la începutul şirului. Fie stringul $Pattern$ şi stringul $Text$. Pentru a afla toate apariţiile stringului $Pattern$ în $Text$ vom crea un nou string $S = Pattern + Text$, care va reprezenta suportul pe care vom calcula vectorul $Z[]$. Dupa calcularea acestuia putem afla numărul de apariţii. Astfel, ne propunem să vedem pentru fiecare poziţie din $S$ dacă $Pattern$ apare pe poziţia curentă. O apariţie pe pozitia $k$ e valida dacă şi numai dacă $Z[k] >= |Pattern|$ şi $k > |Pattern|$.
Probleme în care poate fi aplicat algoritmul prezentat:
* 'Potrivirea sirurilor':problema/strmatch
* 'X':problema/x
* 'Aparitii2':problema/aparitii2
* "Password":http://codeforces.com/contest/126/problem/B
