Z-Algorithm

categorie, autor etc

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 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 se rezolva mult mai usor cu zalgorithm. Un plus pentru zalgorithm ar fi ca poate fi inteles in totalitate.

Despre ce e vorba ?

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).

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 :
    
    (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;
    
    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();
    
    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.

Analiza complexitatii

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.