Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-05-21 18:16:37.
Revizia anterioară   Revizia următoare  

Siruri de sufixe

Acest articol a fost adăugat de amadaeusLucian 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 = a0a1...an-1, notam cu Ai = aiai+1...an-1 sufixul lui A care incepe la pozitia i. Fie n = lungimea lui A. Trie-ul de sufixe este format prin comprimarea tuturor sufixelor A1...An-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(n2). 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:

abacA0
acA2
bacA1
cA3

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.

Cum construim un sir de sufixe (suffix array)?

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(n2 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 2k. Astfel vom executa m = [log2n] (marginit superior) pasi, la pasul k stabilind ordinea sufixelor daca sunt luate in considerare doar primele 2k caractere din fiecare sufix. Se foloseste o matrice P de dimensiune m x n. Notam cu Aik subsecventa lui A de lungime 2k ce incepe pe pozitia i. Pozitia lui Aik in sirul sortat al subsecventelor Ajk (j=1,n) se pastreaza in P(k,i).

Pentru a trece de la pasul k la pasul k+1 se concateneaza toate secventele Aik cu Ai+2k k, obtinandu-se astfel substringurile de lungime 2k+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+2k). Nu trebuie sa ne preocupe faptul ca i+2k 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 2k+1 corespunzatoare. Un ultim lucru care mai trebuie notat este ca la un anumit pas k, pot exista doua (sau mai multe) substringuri Aik = Ajk, 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:

bobocel

Pasul 0:

0404123
bobocel

Pasul 1:

0405123
bobocel
obocel$

Pasul 2:

0516234
bobocel
obocel$
bocel$$
ocel$$$

Pasul 2:

0516234
bobocel
obocel$
bocel$$
ocel$$$
cel$$$$
el$$$$$
l$$$$$$
$$$$$$$

Iata un pseudocod ce sugereaza pasii principali ce trebuie urmati:

n <- lungime(A)
pentru i <- 0, n-1
	P(0, i) <- pozitia in sirul ordonat al caracterelor lui A a lui Ai
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)
	sorteaza L
	calculeaza P(k, i), i = 0,n-1
	cnt <- 2 * cnt

De remarcat ca nu este neparat necesara o anumita numerotare a substringurilor, atat timp cat intre ele este pastrata o relatie de ordine valida. In vederea atingerii complexitatii O(n lg n) pentru sortare se recomanda folosirea metodei radix sort (de doua ori sortare prin numarare), aceasta avand complexitate O(n). Insa, pentru usurarea implementarii, se poate folosi functia sort() din STL (Standard Template Library, o librarie ce contine unele structuri de date si algoritmi in limbajul C++). Desi complexitatea va creste la O(n lg2 n) in cazul cel mai defavorabil, implementarea devine simtitor mai simpla, iar in practica diferentele sunt abia sesizabile pentru siruri cu lungime mai mica decat 100 000.

Mai jos puteti vedea o implementare extrem de scurta pentru suffix array in O(n lg2 n).

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define MAXN  65536
#define MAXLG 17

char A[MAXN];
struct entry {
    int nr[2], p;
} L[MAXN];
int P[MAXLG][MAXN], N, i, stp, cnt;

int cmp(struct entry a, struct entry b)
{
    return a.nr[0] == b.nr[0] ? (a.nr[1] < b.nr[1] ? 1 : 0) : (a.nr[0] < b.nr[0] ? 1 : 0);
}

int main(void)
{
    gets(A);
    for (N = strlen(A), i = 0; i < N; i ++)
        P[0][i] = A[i] - 'a';
    for (stp = 1, cnt = 1; cnt >> 1 < N; stp ++, cnt <<= 1)
    {
        for (i = 0; i < N; i ++)
        {
            L[i].nr[0] = P[stp - 1][i];
            L[i].nr[1] = i + cnt < N ? P[stp - 1][i + cnt] : -1;
            L[i].p = i;
        }
        sort(L, L + N, cmp);
        for (i = 0; i < N; i ++)
            P[stp][L[i].p] = i > 0 && L[i].nr[0] == L[i - 1].nr[0] && L[i].nr[1] == L[i - 1].nr[1] ? P[stp][L[i - 1].p] : i;
    }
    return 0;
}

Sirul de sufixe se va gasi pe ultima linie a matricei P. Cautarea celui de-al k-lea sufix in ordine lexicografica este acum imediata, deci nu vom reveni asupra acestui aspect.
Cantitatea de memorie folosita poate fi redusa renuntand la folosirea intregii matrice P si pastrindu-se la fiecare pas doar ultimele doua linii ale acesteia. In acest caz, insa, structura nu va mai fi capabila sa execute eficient operatia ce urmeaza.