Revizia anterioară Revizia următoare
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 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.
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 S1 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]. Urmatoarea imagine prezinta R[k] si L[k] asociate stringului S. Sagetile indica Z-boxul fiecarei pozitii.
