Siruri de sufixe

Acest articol a fost adăugat de Lucian Boca •amadaeus Intră aici dacă doreşti să scrii articole sau află cum te poţi implica în celelalte proiecte infoarena!

(Categoria Algoritmi, autori Adrian Vladu, Negruseri Cosmin)

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.

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.

Sa vedem acum ce este un trie de sufixe:
Dat fiind un string A = a₀a₁...a_n-1, notam cu A_i = a_ia_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₁...A_n-11 Intr-un trie, ca in figura de mai jos.
Trie-ul de sufixe corespunzator stringului abac este:

Operatiile pe aceasta structura se realizeaza extrem de usor:

• 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".

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

Desi ideea unui trie de sufixe este incantatoare la prima vedere, implementarea simplista in care inseram pas cu pas sufixele in structura noastra necesita un timp de ordinul O(n²). Exista o structura numita arbore de sufixe [1] care se poate construi in timp liniar fata de lungimea sirului de caractere. Arborele de sufixe este un trie de sufixe in care lanturile din care nu ieseau alte muchii erau comprimate intr-o singura muchie (in exemplul de mai sus acestea ar fi lanturile 2-3-4-5 si 1-7-8-9). Dar implementarea algoritmului de complexitate liniara pentru construirea unui arbore de sufixe este anevoioasa, fapt care ne determina sa cautam o alta structura, mai usor de realizat.

Sa vedem care sunt sufixele lui A, parcurgind arborele in adancime. Avand in vedere faptul ca la parcurgerea in adancime trebuie sa consideram nodurile in ordinea lexicografic crescatoare a muchiilor care le leaga de tata, obtinem urmatorul sir de sufixe: