Z-Algorithm

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 langa cunoscutii algoritmi de potrivire a sirurilor : Rabin Karp si KMP exista si un al treilea algoritm numit Z-Algorithm. In continuare este prezentat acest algoritm.

Introducere

Se dau doua siruri P si T formate din litere mici si mari ale alfabetului englez si din cifre. Se cere gasirea tuturor aparitiilor sirului P ca subsecventa a sirului T. Pe langa algoritmii Rabin-Karp si Kmp care rezolva aceasta problema in O( |P| + |T| ) si Z-Algorithm rezolva aceasta problema in aceeasi complexitate.
Fie S un string iar k > 1, o pozitie din acest string. Incepand de la aceasta pozitie vom considera toate secventele de forma [k..j], unde k <= j <= |S|, astfel incat S[k..j] se potriveste cu prefixul lui S de aceeasi lungime cu secventa [k..j]. Dintre toate pozitiile pe care j le poate lua o vom alege pe cea mai mare, si vom defini valoarea jmax – k + 1 ca fiind Z[k]. Daca S[k] e diferit de primul caracter atunci un astfel de j nu exista iar Z[k] = 0. Altfel spus, Z[k] e definit ca lungimea maxima astfel incat S[k..k+Z[k]-1] se potriveste cu secventa S[1..Z[k]].( Stringul S este indexat incepand cu pozitia 1).

Fie S = {aabadaabcaaba}.
Vom defini Z-boxul pentru pozitia k ca fiind secventa ce incepe la pozitia k si se termina la pozitia k + z[k] – 1. Pentru o pozitie k > 1, vom considera toate Z-boxurile ce incep la pozitia j astfel incat 2 <= j <= k. Dintre toate aceste Z-boxuri vom selecta Z-boxul care are cel mai mare capat drept si il vom numi R[k]. Pe langa acest capat drept vom mai tine si capatul stang al acestui Z-box in L[k]. In continuare sunt prezentate R[k] si L[k] asociate stringului S. Sagetile indica Z-boxul fiecarei pozitii.

Preprocesare

In continuare vom prezenta partea de preprocesare, adica, calcularea vectorului Z[]. Cand aflam valoarea Z[k] vom avea nevoie doar de valorile R[k-1] si L[k-1]. De aceea nu are sens sa tinem aceste valori in 2 vectori asa ca le vom tine in 2 variabile R si L care vor fi actualizate la fiecare pas. Algoritmul incepe sa calculeze vectorul Z[] de la pozitia 2.( Z(1) = lungimea stringului). Sa presupunem ca suntem la pozitia k, k>=2, iar toate celelalte k-1 valori sunt calculate. Algoritmul ia in considerare urmatoarele cazuri :

Cazul 1) : k > R. In acest caz algoritmul nu se poate folosi de nici o informatie obtinuta anterior. Astfel, algoritmul va efectua comparatii intre doua caractere incepand cu cel de pe pozitia k respectiv pozitia 1 pana cand va gasi o nepotrivire. Ca urmare Z[k] ia valoarea lungimii secventei care se potriveste iar L = k si R = k + Z[k] – 1.

Cazul 2) : k <= R. De aceasta data ne putem folosi de informatiile obtinute pentru pozitiile anterioare. Din moment ce k<=R rezulta ca k face parte din Zbox-ul cel mai din dreapta. Prin definitia lui L si R, S[k] apartine secventei S[L..R]. Notam cu A aceasta secventa. A se potriveste cu prefixul de aceeasi lungime a lui S. Astfel caracterul S[k] mai apare in secventa S[1..|A|] la pozitia k` = k – L + 1. Secventa S[k..R] apare si in secventa [1..|A|]. Notam cu B secventa S[k..R]. Secventa B este la fel cu secventa S[k`...|A|], unde |A| = R-L+1. Urmatoarea imagine prezinta aceste lucruri:

Cand k` a fost calculat s-a format un Z-Box de lungime Z[k`]. O sa-l numim C. Substringul C este si el un prefix de-al lui S. Astfel Z[k] va fi egal, cel putin, cu minimul dintre Z[k`] si |B|, unde |B| = R – k + 1. In continuare apar 2 cazuri : 

Cazul 2.a) Z[k`] < |B|. In acest caz Z[k] are aceeasi valoare ca si Z[k`]. Din moment ce Z[k] < |B| variabilele R si L raman neschimbate. Urmatoarea imagine exemplifica acest caz:

Cazul 2.b) Z[k`] >= |B| In acest caz Z[k] va fi cel putin egal cu |B|. Dar acesta mai poate fi extins. Asta l-ar face pe Z[k] mai mare ca si Z[k`]. Astfel algoritmul incearca sa extinda Z-Boxul lui k. Incepe sa faca comparatii de la pozitiile R+1 si |A| + 1, unde |A| = R – L + 1, pana cand gaseste o nepotrivire. Notam cu q pozitia primei nepotriviri. Atunci, Z[k] = q – 1 – (k – 1) = q – k, R = q-1 si L = k. Urmatoarea imagine exemplifica acest caz :