Diferente pentru suffix-array-liniar intre reviziile #53 si #81

Nu exista diferente intre titluri.

Diferente intre continut:

h1. Suffix array in O(N)
h1. Suffix array in {$O(N)$}
(Categoria _Algoritmi_, Autor _Cosmin Gheorghe_)
(Categoria _Structuri de date_, Autor _Cosmin Gheorghe_)
In articolul ce urmeaza voi prezenta o metoda de sortare lexicografica a tuturor sufixelor unui sir in timp liniar.
h2. 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).
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
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)
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)
h3. Notatii:
* numim sufix de tip k, un sufix a carui pozitie de inceput da restul k prin impartire la 3 (0 <= k < 3)
* {$S{~i~}$} -> sufixul care incepe pe pozitia i
* {$S[~k,i~]$} -> sufixul de tip k care incepe pe pozitia i
* {$C[~i~]$} -> caracterul de pe pozitia i din sirul S
* numim sufix de tip {$k$}, un sufix a carui pozitie de inceput da restul {$k$} prin impartire la {$3 (0 <= k < 3)$}
* {$S{~i~}$} -> sufixul care incepe pe pozitia {$i$}
* {$S[~k,i~]$} -> sufixul de tip {$k$} care incepe pe pozitia {$i$}
* {$C[~i~]$} -> caracterul de pe pozitia {$i$} din sirul {$S$}
h2. Algoritm
h3. Pas 0:
h3. 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]@}
{$[0 &nbsp;1 &nbsp;2][3 &nbsp;4 &nbsp;5][6 &nbsp;7 &nbsp;8][9 10 11]$}
{$[y &nbsp;a &nbsp;b][b &nbsp;a &nbsp;d][a &nbsp;b &nbsp;b][a &nbsp;d &nbsp;o]$}
 
(in functie de restul impartirii la 3 al pozitiilor sufixelor)
Pas 1:
h3. Pas {$1$}:
Sortam sufixele de tip 1 si 2
Sortam sufixele de tip {$1$} si {$2$}
Pentru aceasta formam sirul
R = abbadabbado0bbadabbado00
{$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)
{$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 {$C{~i~}$} cu {$i$} mai mare ca lungimea sirului {$C{~i~}$} este un caracter minim din punct de vedere lexicografic cu celelalte caractere (in cazul de fata {$0$}).
 
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'$}.
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.
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:
**Exemplu:**
R' = { 1, 2, 4, 6, 4, 5, 3, 7 }
SR' = {0, 1, 6, 7, 2, 5, 3, 7 }
{$R' &nbsp;= { 1, 2, 4, 6, 4, 5, 3, 7 }$}
{$SR' = { 0, 1, 6, 4, 2, 5, 3, 7 }$}
Pas 2:
h3. Pas {$2$}:
Sortam sufixele de tip 0.
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
Orice sufix de tip {$0$} poate fi considerat ca o pereche (caracter, sufix de tip {$1$}): {$S[~0,i~]$} = [$C{~i~}$] + {$S{~1,i+1~}$}
Se poate folosi radix sort pentru a sorta aceste perechi.
Pas 3:
h3. 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:
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)
# sufix de tip {$0$} ({$S{~i~}$}) cu sufix de tip {$1$} ({$S[~j~]$}) -> (caracter, sufix de tip {$1$}) - (caracter, sufix de tip {$2$}) : ({$C{~i~}$} + {$S{~1,i+1~}$}) - ({$C{~j~}$} + {$S{~2,j+1~}$})
# sufix de tip {$0$} ({$S{~i~}$}) cu sufix de tip {$2$} ({$S{~j~}$}) -> (caracter, caracter, sufix de tip {$2$}) - (caracter, caracter, sufix de tip {$1$}) : ({$C{~i~}$} + {$C{~i+1~}$} + {$S{~2,i+2~}$}) - ({$C{~j~}$} + {$C{~j+1~}$} + {$S{~1,j+2~}$})
Analiza complexitatii:
h2. 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).
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)$}.

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
3690