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.
Deci avem 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⁵ != 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).