Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-02-05 11:55:09.
Revizia anterioară   Revizia următoare  

Suffix array in O(N)

(Categoria Algoritmi, Autor Cosmin Gheorghe)

In articolul ce urmeaza voi prezenta o metoda de sortare lexicografica a tuturor sufixelor unui sir in timp liniar.

Obiectiv

Fie S un sir de caractere pe alfabetul [1, N] (S este o secventa de numere din intervalul [1, N]). Restrictia de fata pe un alfabet [1, N] nu este foarte serioasa. Caracterele din sir se pot sorta initial si inlocui cu numere (normalizare).

Dorim obtinerea unui vector care contine toate sufixele sortate lexicografic. Structura rezultata se numeste suffix array si este foarte utila atat in aplicatii practice cat si la concursuri :).

Executia algoritmului va fi explicata pe sirul S = "yabbadabbado"
0  1  2  3  4  5  6  7  8  9  10 11
y  a  b  b  a  d  a  b  b  a  d  o

Cautam sa obtinem vectorul SS = {1, 6, 4, 9, 3, 8, 2, 7, 5, 10, 11, 0} (fiecare sufix este codificat cu pozitia sa de inceput in sir)

Notatii:

  • numim sufix de tip k, un sufix a carui pozitie de inceput da restul k prin impartire la 3 (0 <= k < 3)
  • Si -> sufixul care incepe pe pozitia i
  • Sk,i -> sufixul de tip k care incepe pe pozitia i
  • Ci -> caracterul de pe pozitia i din sirul S

Algoritm

Pas 0:

Impartim sirul in bucati de cate trei astfel:
[0, 1, 2][3, 4, 5][6, 7, 8][9,10,11]
{[y a b][b a d][a b b][a d o]|
(in functie de restul impartirii la 3 al pozitiilor sufixelor)

Pas 1:

Sortam sufixele de tip 1 si 2

Pentru aceasta formam sirul
R = abbadabbado0bbadabbado00
ale carui caractere sunt tripletele:
R = [abb][ada][bba][do0][bba][dab][bad][o00] (fiecare grup de 3 litere este luat ca un singur caracter)

Mai explicit vom imparti sirul S in felul urmator:
( [C1 C2 C3][C4 C5 C6][C7 C8 C9] ... ) + ( [C2 C3 C4][C5 C6 C7][C8 C9 C10] ... ) (unde A + B este concatenarea sirului A cu sirul B)
Pentru Ci cu i mai mare ca lungimea sirului Ci este un caracter minim din punct de vedere lexicografic cu celelalte caractere (in cazul de fata 0).

Pentru codificarea tripletelor in caractere, se poate folosi radix sort pentru sortarea tripletelor si apoi inlocuirea fiecaruia cu numarul care corespunde cu pozitia lui in sortare (se normalizeaza). Se obtine astfel sirul R'.

Se observa usor ca prin sortarea sufixelor din R' se obtine ordinea relativa a sufixelor din S de tip 1 si 2. Aceasta se face prin aplicarea aceluiasi algoritm recursiv pana la cazuri elementare.

Exemplu:

R' = { 1, 2, 4, 6, 4, 5, 3, 7 }
SR' = {0, 1, 6, 7, 2, 5, 3, 7 }

Pas 2:

Sortam sufixele de tip 0.

Pentru aceasta ne folosim de rezultatele obtinute la pasul anterior.
Orice sufix de tip 0 poate fi considerat ca o pereche (caracter, sufix de tip 1): S0,i = Ci + S1,i+1
Se poate folosi radix sort pentru a sorta aceste perechi.

Pas 3:

Interclasam cei doi vectori sortati de sufixe. Avem doua cazuri la comparare. Acestea pot fi reduse la compararea sufixelor de tip 1 cu sufixe de tip 2 astfel:

  1. sufix de tip 0 (Si) cu sufix de tip 1 (Sj) -> (caracter, sufix de tip 1) - (caracter, sufix de tip 2) : (Ci + S1,i+1) - (Cj + S2,j+1)
  2. sufix de tip 0 (Si) cu sufix de tip 2 (Sj) -> (caracter, caracter, sufix de tip 2) - (caracter, caracter, sufix de tip 1) : (Ci + Ci+1 + S2,i+2) - (Cj + Cj+1 + S1,j+2)

Analiza complexitatii:

Se observa ca fiecare pas poate fi efectuat in timp liniar.
Algoritmul se repeta pe un sir de lungime 2N / 3. De aici complexitatea poate fi data de recurenta T(N) = T(2N / 3) + O(N) => T(N) = O(N).