Arborele sufixului

Un arbore de sufix fix (sufix tree în engleză) este o structură de date care evidențiază structura internă a unui șir într-un mod care facilitează sarcinile comune, cum ar fi găsirea de șiruri de caractere. Arborii sufixului permit rezolvarea exactă a problemei de potrivire în timp liniar (la fel ca alți algoritmi precum Knuth-Morris-Pratt , Boyer-Moore ...), dar principala lor virtute este că pot fi folosiți pentru a rezolva în timp liniar mult mai multe probleme complexe decât potrivirea exactă a modelelor.

Aplicația clasică a arborilor sufi este problema subșirului: dat un text T de lungime n , după o prelucrare prealabilă a textului (construcția arborelui sufixului) care necesită timp $O(n)$ ${\ displaystyle O (n)}$ $Pe)$ , puteți răspunde la timp $O(m)$ ${\ displaystyle O (m)}$ ${\ displaystyle O (m)}$ la întrebarea dacă un șir S de lungime m apare în T.

Cu alte cuvinte, preprocesarea textului necesită timp proporțional cu lungimea lui n, dar după această preprocesare fiecare căutare din textul T al unui șir S necesită doar timp proporțional cu lungimea m a șirului căutat, indiferent de lungimea n a textului T.

Noțiuni de bază

Un arbore suficient A pentru un șir S de lungime n este un arbore înrădăcinat astfel încât:

Există exact n frunze numerotate de la 1 la n .
Fiecare nod intern, excluzând cel mult rădăcina, are cel puțin doi copii.
Fiecare margine este etichetată cu un șir de caractere S.
Două margini care părăsesc același nod nu pot avea etichete care încep cu același caracter.
Concatenarea etichetelor de-a lungul căii de la rădăcină la frunza numerotată i este exact sufixul S [ i , n ] al lui S cu lungimea n - i + 1 .

De exemplu, arborele sufixului pentru șirul „dabdac” este cel prezentat în figură. De-a lungul căii de la rădăcină la frunza 1 citim întregul șir „dabdac” în timp ce de-a lungul căii de la rădăcină la frunza 2 citim sufixul „abdac” care începe din poziția 2 a șirului. Nodul r este rădăcina și nodurile u și w sunt noduri interne. Definiția de mai sus nu garantează existența unui arbore de sufix pentru fiecare șir. Problema este că, dacă un sufix este prefixat cu un alt sufix de S, calea relativă la acel sufix nu se termină cu o frunză. De exemplu, dacă eliminăm ultimul caracter c din șirul „dabdac” obținând șirul „dabda”, sufixul a este prefixat cu „abda” și, prin urmare, calea relativă la a nu se termină într-o frunză, ci se termină într-un intermediar punct al căii referitoare la "abda".

Pentru a evita această problemă, se presupune că fiecare șir S se termină cu un caracter diferit de celelalte caractere din șir, astfel încât niciun sufix să nu poată fi prefixat de un alt sufix. Dacă acest lucru nu este adevărat, putem adăuga oricând la sfârșitul șirului un caracter santinelă care nu aparține alfabetului pe care este construit șirul. Ne vom referi la acest personaj ca $ mai târziu .

În plus, eticheta unei căi de la rădăcină la un nod (intern sau frunză) este concatenarea etichetelor marginilor căii. Eticheta unui nod u este eticheta căii de la rădăcină la u . În special, eticheta rădăcinii este șirul nul, iar eticheta unei frunze este sufixul asociat cu acea frunză.

Adâncimea unui nod este lungimea etichetei sale.

Dacă eticheta unui arc ( u , v ) între două noduri u și v are o lungime k mai mare de 1, arcul ( u , v ) este împărțit în k părți (una pentru fiecare caracter al etichetei) prin intermediul k - 1 noduri implicite ale căror etichete sunt concatenarea etichetei lui u cu caracterele etichetei arcului ( u , v ) care precedă nodul implicit în sine.

De exemplu, în figură, șirul "da" este eticheta nodului w în timp ce șirul "dabd" este eticheta unui nod implicit din interiorul arcului ( w , 1).

Potrivire exactă folosind arborele sufixului

Arborii suficienți rezolvă problema potrivirii exacte pe baza următoarelor etape:

Construiți arborele sufixelor A ale textului T.
Comparați caracterele modelului P cu caracterele singurei căi din A identificate de acestea (amintiți-vă că etichetele marginilor care părăsesc un nod intern încep cu caractere distincte) până când modelul este terminat sau un caracter al modelului care nu apare în orice continuare a drumului parcurs până în acel moment. În acest din urmă caz, P nu apare nicăieri în textul T.
Dacă ajungem la sfârșitul modelului, atunci modelul este egal cu eticheta nodului u (implicit sau explicit) la care am ajuns și, prin urmare, P este prefixat cu toate sufixele asociate cu frunzele subarborelui înrădăcinat în u . Pozițiile de plecare ale acestor sufixe (care sunt memorate în frunze) sunt, prin urmare, toate și numai pozițiile în care P apare în T. Astfel de poziții sunt apoi colectate prin parcurgerea subarborelui înrădăcinat în u .

Construirea arborelui sufixelor se poate face în timp $O(n)$ ${\ displaystyle O (n)}$ $Pe)$ . Așadar, primul pas necesită timp $O(n)$ ${\ displaystyle O (n)}$ $Pe)$ .

În cel de-al doilea pas, pentru fiecare caracter al modelului se face o singură comparație dacă suntem într-un nod implicit (și, prin urmare, există o singură continuare posibilă a căii) și cel mult la fel de multe comparații pe cât sunt arcuri de ieșire, dacă suntem într-un nod explicit. Deoarece primele caractere ale etichetelor arcurilor care ies dintr-un nod explicit sunt toate distincte și alfabetul este prestabilit, numărul comparațiilor este, în orice caz, mai mic sau egal cu numărul de caractere din alfabet, care este o constantă. Prin urmare, este necesar un timp constant pentru fiecare caracter al modelului, iar al doilea pas se efectuează în timp $O(m)$ ${\ displaystyle O (m)}$ ${\ displaystyle O (m)}$ . Al treilea pas necesită timp proporțional cu numărul de noduri ale subarborelui înrădăcinat în vârful u .

Dacă există k apariții ale modelului în textul T , acel subarborel are exact k frunze. Deoarece fiecare nod intern are cel puțin două margini de ieșire, numărul de noduri interne este mai mic sau egal cu k - 1 (egal numai dacă fiecare nod intern are exact două margini de ieșire și, prin urmare, arborele și un arbore binar). Așadar, al treilea pas necesită timp $O(k)$ ${\ displaystyle O (k)}$ ${\ displaystyle O (k)}$ . Deoarece k ≤ n timpul total necesar este $O(n+m)$ ${\ displaystyle O (n + m)}$ ${\ displaystyle O (n + m)}$ , la fel ca și cerințele altor algoritmi de potrivire a modelelor. Dar distribuția muncii este foarte diferită. În alți algoritmi timpul total este împărțit într-un timp $O(m)$ ${\ displaystyle O (m)}$ ${\ displaystyle O (m)}$ pentru a preprocesa modelul P și un tempo $O(n)$ ${\ displaystyle O (n)}$ $Pe)$ pentru a căuta toate aparițiile modelului P în textul T. Pe de altă parte, utilizarea arborelui sufixelor necesită timp $O(n)$ ${\ displaystyle O (n)}$ $Pe)$ să preprocesăm textul T și deci numai timpul $O(m+k)$ ${\ displaystyle O (m + k)}$ ${\ displaystyle O (m + k)}$ pentru a găsi toate k aparițiile oricărui model P din textul T.

Avantajul este clar atunci când trebuie să faceți o mulțime de căutări cu modele diferite într-un singur text mare.

O metodă naivă de construire a arborelui sufixului

Un algoritm simplu pentru construirea arborelui sufix al unui șir S pentru a aprofunda conceptul arborelui sufixului și a dezvolta intuiția despre acesta este următorul. Acest algoritm naiv începe construcția arborelui sufixului cu o singură margine pentru sufixul S [1, n ] $ (întregul șir); apoi adaugă unul câte unul sufixele S [ i , n ] $ pentru i = 2, ..., n +1 (deoarece +1 se datorează simbolului $ ). Indicăm cu $A_{i}$ ${\ displaystyle A_ {i}}$ $Către}$ arborele intermediar care conține sufixele începând din pozițiile de la 1 la i . Copacul $A_{1}$ ${\ displaystyle A_ {1}}$ $A_1$ constă dintr-un singur arc marcat cu șirul S [1, n ] $ care unește rădăcina cu o frunză numerotată 1. Fiecare copac $A_{i+1}$ ${\ displaystyle A_ {i + 1}}$ ${\ displaystyle A_ {i + 1}}$ este construit din $A_{i}$ ${\ displaystyle A_ {i}}$ $Către}$ În felul următor:

Începând de la rădăcina $A_{i}$ ${\ displaystyle A_ {i}}$ $Către}$ căutați cea mai lungă cale de la rădăcină la un nod (implicit sau explicit) a cărui etichetă este prefixată cu sufixul S [ i +1, n ] $ de adăugat. Această căutare se face pornind de la calea nul (care începe și se termină în rădăcină și care are șirul nul ca etichetă) și extinderea acesteia, în măsura în care este posibil, prin adăugarea caracterelor sufixului S [i + 1, n ] $ pe rând. Calea obținută în acest mod este unică prin faptul că următorul caracter al unui nod implicit este unic și etichetele marginilor care părăsesc un nod explicit încep cu caractere distincte. În plus, extensia trebuie să se încheie înainte de sfârșitul sufixului S [ i +1, n ] $, deoarece prezența santinelei $ ne asigură că sufixul S [ i +1, n ] $ nu este prefixat de niciunul dintre cele mai lungi prefixe inserate anterior în copac.
Dacă nodul atins este un nod implicit, acest nod implicit este înlocuit cu un nod explicit, rupând arcul care îl conține în două arcuri (și eticheta în două etichete).
În acest moment, nodul u am ajuns la un nod este explicit cu eticheta de pre Fi x S [i + 1, j] de S [i + 1, n] $ și astfel încât, în copac, nu există nici un nod cu eticheta S [ i +1, j +1]. Deci, toate marginile care ies din u au etichete începând cu un caracter diferit de caracterul S [ j +1]. Adăugăm un arc nou ( u , i +1) cu eticheta S [ j +1, n ] $ care alătură nodului u cu o nouă frunză numerotată i +1. În acest moment arborele conține o singură cale de la rădăcină la frunza i +1 a cărei etichetă este sufixul S [ i +1, n ] $ și, prin urmare, am obținut următorul arbore $A_{i+1}$ ${\ displaystyle A_ {i + 1}}$ ${\ displaystyle A_ {i + 1}}$ .

Presupunând că dimensiunea alfabetului este limitată de o constantă, algoritmul naiv necesită timp $O(n^{2})$ ${\ displaystyle O (n ^ {2})}$ $O (n ^ {2})$ . În cazul în care numărul de simboluri | Σ | al alfabetului Σ nu este limitat de o constantă complexitatea este $O(n^{2}|\Sigma |)$ ${\ displaystyle O (n ^ {2} | \ Sigma |)}$ ${\ displaystyle O (n ^ {2} | \ Sigma |)}$ , care poate fi redus la $O(n^{2}\log {|\Sigma |})$ ${\ displaystyle O (n ^ {2} \ log {| \ Sigma |})}$ ${\ displaystyle O (n ^ {2} \ log {| \ Sigma |})}$ folosind o metodă eficientă pentru a căuta arcul pe care să continui la nodurile explicite.

O animație de construire a arborelui sufixului pentru șirul „dabdac” cu acest algoritm naiv este după cum urmează:

Construirea arborelui sufixului pentru șirul „dabdac” cu un algoritm naiv

Algoritmul lui Ukkonen

Primul care a descoperit un algoritm pentru construcția arborelui sufixului în timp liniar a fost Weiner în 1973. Pentru originalitatea și importanța rezultatului, acest algoritm a fost declarat „algoritmul anului”. În anii următori, acest algoritm a primit din ce în ce mai puțină atenție, probabil pentru că este dificil de înțeles și implementat corect. Câțiva ani mai târziu, Ukkonen a propus un algoritm complet diferit. Necesită mai puțină memorie decât cea a lui Weiner și, în plus, este mai ușor de înțeles pornind, în descriere, de la un algoritm foarte ineficient ( $O(n^{3})$ ${\ displaystyle O (n ^ {3})}$ $O (n ^ 3)$ ) la care se aplică apoi trucuri pentru a reduce complexitatea pentru a o face liniară.

Arborii sufixului implicit

Algoritmul lui Ukkonen construiește o succesiune de arbori de sufixe implicite, ultimul dintre aceștia fiind apoi transformat într-un adevărat arbore de sufix pentru șirul S $ . Definirea arborelui sufix implicit I pentru un șir de caractere S este același ca și arborele sufix din care , totuși, condiția ca calea relativă la fiecare sufix al șirului S se termină într - o frunză este îndepărtată, și, în plus, nul sufixul este, de asemenea, considerat. Deci arborele sufixului implicit există pentru fiecare șir S , chiar și pentru cele cu sufixe care sunt prefixe ale altor sufixe și pentru care nu există un arbore sufix explicit. Pur și simplu, dacă un sufix este un prefix al unui alt sufix, în arborele sufixului implicit calea relativă la acel sufix se termină într-un nod intern (implicit sau explicit) în calea relativă la sufixul căruia este prefix.

Relația dintre arborii sufixului implicit și arborii sufixului explicit este clarificată prin următoarea afirmație: arborele sufixului implicit al unui șir S se obține din arborele sufixului pentru șirul S $ prin eliminarea simbolului santinelă $ de pe toate etichetele pe care îl conțin, eliminarea oricăror arcuri a căror etichetă este redusă la șirul nul și a frunzei corespunzătoare (sunt cu siguranță arcuri care se termină într-o frunză) și în final eliminarea oricăror noduri interne explicite care au un singur arc de ieșire. Deși un arbore de sufix implicit poate să nu aibă o frunză pentru fiecare sufix al șirului S, acesta conține totuși toate sufixele lui S (inclusiv sufixul nul) ca etichete ale unor noduri (implicite sau explicite). Singura problemă este că, dacă acea cale nu se termină într-o frunză, nu există nicio indicație a locului unde se termină calea respectivă. Desigur, dacă niciun sufix (cu excepția celui nul) nu este prefixat la un alt sufix, arborele sufixului implicit și arborele sufixului explicit sunt aceleași.

Descriere abstractă a algoritmului Ukkonen

Algoritmul lui Ukkonen construiește un arbore de sufix implicit $I_{i}$ ${\ displaystyle I_ {i}}$ $Eu_i$ pentru fiecare prefix S [1, i ] al șirului S $ cu lungimea n +1 începând de la $I_{0}$ ${\ displaystyle I_ {0}}$ $I_ {0}$ și creșterea i cu unul până ajungi să construiești $I_{n+1}$ ${\ displaystyle I_ {n + 1}}$ ${\ displaystyle I_ {n + 1}}$ . Deoarece niciun sufix al șirului S $ nu este prefixat cu un alt sufix, arborele sufixului implicit $I_{n+1}$ ${\ displaystyle I_ {n + 1}}$ ${\ displaystyle I_ {n + 1}}$ coincide cu arborele sufixului A al șirului S $ . De fapt, pentru a obține A de la $I_{n+1}$ ${\ displaystyle I_ {n + 1}}$ ${\ displaystyle I_ {n + 1}}$ este necesară o transformare finală datorită faptului că se folosește o reprezentare ușor diferită pentru arborii sufixului implicit decât pentru arborii sufixului.

Prin urmare, descrierea abstractă a algoritmului lui Ukkonen este următoarea:

 UKKONEN (S)
   / * Precondiție: S șir de lungime n. * /
   „Adăugați santinela la S pentru a obține șirul S $ de lungime n + 1.”
   "Construi $I_{0}$  $THE$   $0$   ${\ displaystyle I_ {0}}$   $I_ {0}$  . "
   pentru i ← 0 to n do
     / * Extensie de la Ii la Ii + 1. * /
     pentru j ← 1 la i + 1 do
       „Găsiți sfârșitul căii corespunzătoare sufixului S [j, i]
        din șirul S [1, i] din care $I_{i}$  $THE$   $the$   ${\ displaystyle I_ {i}}$   $Eu_i$  este arborele sufixului
        implicit și, dacă este necesar, extindeți acea cale adăugând
        caracterul S [i + 1] astfel încât sufixul S [j, i + 1] di
        S [1, i + 1] este reprezentat în copac. "

Construcția de $I_{0}$ ${\ displaystyle I_ {0}}$ $I_ {0}$ este ușor. $I_{0}$ ${\ displaystyle I_ {0}}$ $I_ {0}$ are doar rădăcina și nu are arc de ieșire. Reprezintă singurul sufix al prefixului nul S [1, 0], de fapt sufixul nul. Deci, să vedem cum să executăm extensia de la $I_{i}$ ${\ displaystyle I_ {i}}$ $Eu_i$ la $I_{i+1}$ ${\ displaystyle I_ {i + 1}}$ ${\ displaystyle I_ {i + 1}}$ și în special modul în care se efectuează extensia unui sufix S [ j , i ] al lui S [1, i ] în sufixul S [ j , i +1] al lui S [1, i +1].

În continuare extensia din $I_{i}$ ${\ displaystyle I_ {i}}$ $Eu_i$ la $I_{i+1}$ ${\ displaystyle I_ {i + 1}}$ ${\ displaystyle I_ {i + 1}}$ și în special modul în care se efectuează extensia unui sufix S [ j , i ] al lui S [1, i ] în sufixul S [ j , i +1] al lui S [1, i +1].

Avem trei cazuri posibile:

Cazul 1: în arborele curent calea etichetată S [ j , i ] se termină cu o frunză numerotată j . În acest caz, noul caracter S [ i +1] este adăugat la eticheta ultimului arc al acestei căi (cel care se termină în frunză).
Cazul 2: în arborele curent calea etichetată S [ j , i ] se termină cu un nod intern u (implicit sau explicit), dar nici o cale care începe de la u începe cu caracterul S [ i +1]. În acest caz se creează o nouă frunză etichetată j conectată la nodul u cu un arc marcat cu caracterul S [ i +1]. În cazul în care u este un nod implicit, înainte de a face acest lucru, nodul u este înlocuit cu un nod explicit care împarte arcul căruia îi aparține în două părți.
Cazul 3: în arborele curent calea etichetată S [ j , i ] se termină cu un nod intern u (implicit sau explicit) și cel puțin o cale care începe de la u începe cu caracterul S [ i +1]. În acest caz, sufixul S [ j , i +1] este deja prezent în copac și nu trebuie făcut nimic.

După ce am extins toate sufixele lui S [1, i ] suntem siguri că toate sufixele lui S [1, i +1] sunt reprezentate în arborele obținut. De fapt, fiecare sufix non-nul al lui S [1, i +1] este o extensie a unui sufix al lui S [1, i ], iar sufixul nul este întotdeauna reprezentat în orice arbore de sufix implicit.

O animație de construire a arborelui sufixului pentru șirul „adaadac $” cu acest algoritm abstract este după cum urmează:

Construirea arborelui sufixului pentru șirul „adaadac $” cu algoritmul abstract al lui Ukkonen

Implementarea și îmbunătățirea eficienței

În algoritmul abstract, după găsirea nodului (implicit sau explicit) unde sufixul S [ j , i ] se termină în arborele curent, extensia lui S [ j , i ] cu următorul caracter S [ i + 1] ia constantă timp în toate cele trei cazuri 1, 2 și 3. Astfel, un punct cheie în implementarea algoritmului lui Ukkonen este de a găsi o modalitate rapidă de a găsi nodurile unde se termină sufixele S [ j , i ]. Într-o implementare naivă putem găsi nodul în care sufixul S [ j , i ] se termină în timp $O(i-j+1)$ ${\ displaystyle O (i-j + 1)}$ ${\ displaystyle O (i-j + 1)}$ începând de la rădăcina arborelui. Adăugarea peste tot i și j oferă un timp $O(i^{2})$ ${\ displaystyle O (i ^ {2})}$ ${\ displaystyle O (i ^ {2})}$ a calcula $I_{i+1}$ ${\ displaystyle I_ {i + 1}}$ ${\ displaystyle I_ {i + 1}}$ începând de la $I_{i}$ ${\ displaystyle I_ {i}}$ $Eu_i$ și adăugând pe toate e-urile obțineți un timp total $O(n^{3})$ ${\ displaystyle O (n ^ {3})}$ $O (n ^ 3)$ a calcula $I_{n+1}$ ${\ displaystyle I_ {n + 1}}$ ${\ displaystyle I_ {n + 1}}$ .

Prin urmare, acest algoritm pare nebun, deoarece construcția naivă a arborelui sufix necesită timp $O(n^{2})$ ${\ displaystyle O (n ^ {2})}$ $O (n ^ {2})$ . Dar, cu unele trucuri de implementare, este posibilă reducerea complexității la $O(n)$ ${\ displaystyle O (n)}$ $Pe)$ .

Prima îmbunătățire: link sufix

Fie α un șir și x un caracter. Dacă într-un arbore de sufixe (implicit sau explicit) există un nod intern explicit u cu eticheta xα și un nod intern explicit s ( u ) a cărui etichetă este α, atunci o legătură suficientă între u la s ( u ) este pur și simplu o indicatorul u spre s ( u ). Vezi figura anterioară.

Dacă, în timpul fazei de j- - lea, pentru a extinde sufix S [j, i], un nou (non-frunză) nod intern este creat cu xα eticheta (evident cu xα prefix S [j, i]) , apoi o în arborele curent există deja un nod intern explicit cu eticheta α sau acest nod va fi creat imediat după extensia următorului sufix S [ j +1, i ].

Dovadă: un nou nod intern v cu eticheta S [ j , i ] = xα este creat numai dacă sufixul S [ j , i ] este extins cu cazul 2 când în arborele curent calea etichetată S [ j , i ] se termină în un nod intern implicit și această cale continuă cu un caracter c diferit de S [ i +1]. Astfel, în arborele curent, calea etichetei S [ j +1, i ] = α are o continuare începând cu caracterul c . Prin urmare, nodul w cu eticheta S [ j +1, i ] = α este un nod intern (explicit sau implicit). Dacă w este explicit s ( v ) = w . Altfel, dacă w este implicit, calea etichetei S [ j +1, i ] = α care se termină la nodul w poate continua doar cu caracterul c . Apoi, în pasul următor, extensia sufixului S [ j +1, i ] înlocuiește nodul implicit w cu un nod explicit pentru care s ( v ) = w .

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere în arborele sufixului

linkuri externe

Implementări

Potrivirea modelului cu arbori de sufix , pe math.unipd.it . Adus la 6 februarie 2015 (arhivat din original la 6 februarie 2015) .

Portal IT : accesați intrările Wikipedia care se ocupă cu IT