== include(page="template/implica-te/scrie-articole" user_id="amadaeus") ==

(Categoria _Algoritmi_, autori _Adrian Vladu, Negruseri Cosmin_)

(Categoria _Algoritmi_, Autori _Adrian Vladu, Negruseri Cosmin_)

h2. Introducere

Un domeniu important in algoritmica folosita in practica este acela al algoritmilor pe siruri de caractere. Astfel la concursurile de programare sunt prezente foarte multe probleme de prelucrare si procesare a unor siruri de caractere. In cadrul concursurilor si antrenamentelor multi dintre noi s-au lovit de probleme ce s-ar fi rezolvat usor daca se reusea in mod eficient determinarea existentei unui cuvant ca subsecventa a unui alt cuvant. Vom prezenta o structura versatila ce permite acest lucru, inlesnind de multe ori realizarea altor operatii utile pe un string dat.

Un domeniu important in algoritmica folosita in practica este acela al algoritmilor pe siruri de caractere. Astfel, la concursurile de programare sunt prezente foarte multe probleme de prelucrare si procesare a unor siruri de caractere. In cadrul concursurilor si antrenamentelor multi dintre noi s-au lovit de probleme ce s-ar fi rezolvat usor daca se reusea in mod eficient determinarea existentei unui cuvant ca subsecventa a unui alt cuvant. Vom prezenta o structura versatila ce permite acest lucru, inlesnind de multe ori realizarea altor operatii utile pe un string dat.

h2. Ce sunt sirurile de sufixe (suffix arrays)?

Pentru a avea o idee mai buna despre _suffix arrays_, vom face inainte o scurta prezentare a structurii de date numita in engleza _trie_ si a _arborilor de sufixe_ (suffix trees [1]) care sunt o forma speciala a structurii de date trie. Un trie este un arbore menit sa stocheze siruri. Fiecare nod al lui va avea in general un numar de fii egal cu marimea alfabetului sirurilor de caractere care trebuies stocate. In cazul nostru, cu siruri ce contin litere mici ale alfabetului englez, fiecare nod va avea cel mult 26 de fii. Fiecare muchie care porneste din tata spre fii si va fi etichetata cu o litera distincta a alfabetului. Etichetele legaturilor de pe un drum de la radacina pana la o frunza vor alcatui un cuvant stocat in arbore. Dupa cum se observa, cautarea existentei unui cuvant in aceasta structura de date este foarte eficienta si se realizeaza in complexitate $O(M)$, unde $M$ e lungimea cuvantului. Astfel, timpul de cautare nu depinde de numarul de cuvinte pe care trebuie sa il gestioneze structura de date, fapt ce face aceasta structura ideala pentru implementarea dictionarelor.

Pentru a avea o idee mai buna despre _suffix arrays_, vom face inainte o scurta prezentare a structurii de date numita in engleza _trie_ si a _arborilor de sufixe_ (suffix trees [1]) care sunt o forma speciala a structurii de date trie. Un trie este un arbore menit sa stocheze siruri. Fiecare nod al lui va avea in general un numar de fii egal cu marimea alfabetului sirurilor de caractere care trebuies stocate. In cazul nostru, cu siruri ce contin litere mici ale alfabetului englez, fiecare nod va avea cel mult 26 de fii. Fiecare muchie porneste din tata spre fii si va fi etichetata cu o litera distincta a alfabetului. Etichetele legaturilor de pe un drum de la radacina pana la o frunza vor alcatui un cuvant stocat in arbore. Dupa cum se observa, verificarea existentei unui cuvant in aceasta structura de date este foarte eficienta si se realizeaza in complexitate $O(M)$, unde $M$ e lungimea cuvantului. Astfel, timpul de cautare nu depinde de numarul de cuvinte pe care trebuie sa il gestioneze structura de date, fapt ce face aceasta structura ideala pentru implementarea dictionarelor.

Sa vedem acum ce este un _trie de sufixe_:
Dat fiind un string $A$ = $a{~0~}a{~1~}...a{~n-1~}$, notam cu $A{~i~}$ = $a{~i~}a{~i+1~}...a{~n-1~}$ sufixul lui $A$ care incepe la pozitia $i$. Fie $n$ = lungimea lui $A$. Trie-ul de sufixe este format prin comprimarea tuturor sufixelor $A{~1~}...A{~n-1~}$ intr-un trie, ca in figura de mai jos.
Trie-ul de sufixe corespunzator stringului $abac$ este:

Sa vedem acum ce este un _trie de sufixe_. Dat fiind un string $A$ = $a{~0~}a{~1~}...a{~n-1~}$, notam cu $A{~i~}$ = $a{~i~}a{~i+1~}...a{~n-1~}$ sufixul lui $A$ care incepe la pozitia $i$. Fie $n$ = lungimea lui $A$. Trie-ul de sufixe este format prin comprimarea tuturor sufixelor $A{~1~}...A{~n-1~}$ intr-un trie, ca in figura de mai jos. Trie-ul de sufixe corespunzator stringului $abac$ este:

p=. !siruri-de-sufixe?fig01v.png!

* _verificarea daca un string $W$ este substring al lui $A$_ - este suficienta parcurgerea nodurilor, incepand din radacina si urmarind muchiile etichetate corespunzator caracterelor din $W$ (complexitate $O(|W|)$)

* _cautarea celui mai lung prefix comun pentru doua sufixe ale lui $A$_ - se aleg nodurile $u$ si $v$ ale trie-ului corespunzatoare sfarsitului celor doua prefixe, iar prin aplicarea unui algoritm de gasire a LCA (least common ancestor / cel mai apropiat stramos comun) se gaseste nodul corespunzator sfarsitului prefixului cautat. De exemplu, pentru $abac$ si $ac$ se gasesc nodurile $5$ si $6$. Cel mai apropiat stramos comun al lor este $2$, de unde rezulta prefixul $a$. Autorii va recomanda articolul [2] pentru o rezolvare in $O(sqrt(n))$, [3] pentru o prezentare accesibila a unei rezolvari in $O(log n)$ sau $O(1)$, si articolul [4] pentru un algoritm _"state of the art"_.

* _cautarea celui mai lung prefix comun pentru doua sufixe ale lui $A$_ - se aleg nodurile $u$ si $v$ ale trie-ului corespunzatoare sfarsitului celor doua sufixe, iar prin aplicarea unui algoritm de gasire a LCA (Lowest Common Ancestor / cel mai apropiat stramos comun) se gaseste nodul corespunzator sfarsitului prefixului cautat. De exemplu, pentru $abac$ si $ac$ se gasesc nodurile $5$ si $6$. Cel mai apropiat stramos comun al lor este $2$, de unde rezulta prefixul $a$. Autorii va recomanda articolul [2] pentru o rezolvare in $O(sqrt(n))$, [3] pentru o prezentare accesibila a unei rezolvari in $O(log n)$ sau $O(1)$, si articolul [4] pentru un algoritm "state of the art".

* _gasirea celui de-al $k$-lea sufix in ordine lexicografica_ - (complexitate $O(n)$, cu o preprocesare corespunzatoare). De exemplu al $3$-lea sufix al sirului $abac$ este reprezentat in trie-ul nostru de a $3$-a frunza.

p=. !siruri-de-sufixe?fig07.png!

Este usor de observat ca acestea sunt ordonate crescator. Pentru memorare, nu este necesar sa pastram un vector ordonat de sufixe, suficienta fiind pastrarea indicilor fiecarui sufix din sirul ordonat. Pentru exemplul de mai sus obtinem vectorul *$P = (0, 2, 1, 3)$*, acesta fiind array-ul de sufixe pentru stringul $abac$.

Este usor de observat ca acestea sunt ordonate crescator. Pentru memorare, nu este necesar sa pastram un vector ordonat de sufixe, suficienta fiind pastrarea indicilor fiecarui sufix din sirul ordonat. Pentru exemplul de mai sus obtinem vectorul $P = (0, 2, 1, 3)$, acesta fiind array-ul de sufixe pentru stringul $abac$.

h2. Cum construim un sir de sufixe (suffix array)?

h2. Cum construim un sir de sufixe?

Prima metoda care ne vine in minte este sortarea tuturor sufixelor lui $A$ folosind un algoritm de complexitate $O(n lg n)$. Insa compararea a doua sufixe se face in timp $O(n)$, deci complexitatea finala va fi $O(n^2^ lg n)$. Exista totusi un algoritm relativ usor de implementat si inteles, avand o complexitate de $O(n lg n)$. Desi este asimptotic mai mare decat cel al constructiei unui arbore de sufixe (suffix tree), in practica timpul de constructie al unui sir de sufixe este mult mai mic, din cauza constantei care apare in fata algoritmul liniar. De asemenea, cantitatea de memorie folosita in cazul implementarii cu memorie $O(n)$ este de la $3$ pana la $5$ ori mai mica decat in cazul unui arbore de sufixe.

Prima metoda care ne vine in minte este sortarea tuturor sufixelor lui $A$ folosind un algoritm de complexitate $O(n lg n)$. Insa compararea a doua sufixe se face in timp $O(n)$, deci complexitatea finala va fi $O(n^2^ lg n)$. Exista totusi un algoritm relativ usor de implementat si inteles, avand o complexitate de $O(n lg n)$. Desi este asimptotic mai mare decat cel al constructiei unui arbore de sufixe (suffix tree), in practica timpul de constructie al unui sir de sufixe este mult mai mic, din cauza constantei care apare in fata algoritmul liniar. De asemenea, cantitatea de memorie folosita in cazul implementarii cu memorie $O(n)$ este de la 3 pana la 5 ori mai mica decat in cazul unui arbore de sufixe.

Algoritmul se bazeaza pe mentinerea ordinii sufixelor sirului, sortate dupa prefixele lor de lungime $2^k^$. Astfel vom executa $m$ = $[log{~2~}n]$ (marginit superior) pasi, la pasul $k$ stabilind ordinea sufixelor daca sunt luate in considerare doar primele $2^k^$ caractere din fiecare sufix. Se foloseste o matrice $P$ de dimensiune $m x n$.  Notam cu $A{~i~}^k^$ subsecventa lui $A$ de lungime $2^k^$ ce incepe pe pozitia $i$. Pozitia lui $A{~i~}^k^$ in sirul sortat al subsecventelor $A{~j~}^k^$ $(j=1,n)$ se pastreaza in $P{~(k,i)~}$.

Algoritmul se bazeaza pe mentinerea ordinii sufixelor sirului, sortate dupa prefixele lor de lungime $2^k^$. Astfel vom executa $m$ = $[log{~2~}n]$ (marginit superior) pasi, la pasul $k$ stabilind ordinea sufixelor daca sunt luate in considerare doar primele $2^k^$ caractere din fiecare sufix. Se foloseste o matrice $P$ de dimensiune $m x n$.  Notam cu $A{~i~}^k^$ subsecventa lui $A$ de lungime $2^k^$ ce incepe pe pozitia $i$. Pozitia lui $A{~i~}^k^$ in sirul sortat al subsecventelor $A{~j~}^k^$ $(j=0,n-1)$ se pastreaza in $P{~(k,i)~}$.

Pentru a trece de la pasul $k$ la pasul $k+1$ se concateneaza toate secventele $A{~i~}^k^$ cu $A{~i+2^k^~}^ k^$, obtinandu-se astfel substringurile de lungime $2^k+1^$. Pentru stabilirea ordinii se folosesc informatiile obtinute la pasul anterior. Pentru fiecare indice $i$ se pastreaza o pereche de intregi formata din $P{~(k,i)~}$ si $P{~(k,i+2^k^)~}$. Nu trebuie sa ne preocupe faptul ca $i+2^k^$ poate pica in afara sirului, deoarece vom completa sirul cu pseudocaracterul {@$@}, despre care vom considera ca este lexicografic mai mic decat oricare alt caracter. In urma sortarii, perechile vor fi aranjate conform ordinii lexicografice a substringurilor de lungime $2^k+1^$ corespunzatoare. Un ultim lucru care mai trebuie notat este ca la un anumit pas $k$, pot exista doua (sau mai multe) substringuri $A{~i~}^k^$ = $A{~j~}^k^$, iar acestea trebuie etichetate identic ({$P{~(k,i)~}$} trebuie sa fie egal cu {$P{~(k,j)~}$}). O imagine spune mai mult decat o mie de cuvinte:
p=. !siruri-de-sufixe?fig02.png!

*Pasul 0*:

Pasul 0:

p=. !siruri-de-sufixe?fig03.png!

*Pasul 1*:

Pasul 1:

p=. !siruri-de-sufixe?fig04.png!

*Pasul 2*:

Pasul 2:

p=. !siruri-de-sufixe?fig05.png!

*Pasul 3*:

Pasul 3:

p=. !siruri-de-sufixe?fig06.png!

== code(c) |
n <- lungime(A)
pentru i <- 0, n-1

	P(0, i) <- pozitia lui Ai in sirul ordonat al caracterelor lui A

    P(0, i) <- pozitia lui Ai in sirul ordonat al caracterelor lui A

sfarsit pentru
cnt <- 1
pentru k <- 1, [log2 n] (marginit superior)

	pentru i <- 0, n-1
		L(i) <- (P(k-1, i), P(k-1, i+cnt), i)
        sfarsit pentru
	sorteaza L
	calculeaza P(k, i), i = 0, n-1
	cnt <- 2 * cnt

    pentru i <- 0, n-1
        L(i) <- (P(k-1, i), P(k-1, i+cnt), i)
    sfarsit pentru
    sorteaza L
    calculeaza P(k, i), i = 0, n-1
    cnt <- 2 * cnt

sfarsit pentru
==