Note de curs, clasele 11-12, 28 noiembrie 2013

La acest cerc am apucat să predăm doar parțial arborii de sufixe. Nu am predat suffix links și tot ce urmează, dar am lăsat notele aici ca să nu le fragmentez.

Trie

Definiție: un trie este un arbore de prefixe care stochează (multe) șiruri de caractere într-o manieră compactă.

Avantaje

Când discutăm despre avantaje, ne gândim și ce alte structuri de date mai folosim pentru căutare: tabele hash, arbori binari echilibrați, skip lists etc. Trie-urile sunt mai bune în multe situații.

• Sortarea este o simplă parcurgere în preordine (asemănătoare cu radix sort)
• În general, suportă ușor interogări de următorul / precedentul în ordinea sortată.
• Răspund rapid la căutări de prefixe (ceea ce o tabelă hash nu suportă)
• Viteza căutării nu depinde de mărimea dicționarului, (!) ci doar de lungimea șirului
• Fiecare nod trebuie să rețină dacă este un prefix sau un șir complet (sau numărul de șiruri complete, dacă pot exista duplicate)
• Pot fi mai rapizi decât tabelele hash, căci nu necesită calcularea codului hash
• Sunt folosiți pentru interogări de dicționare și sugestii de autocompletare
• Căutări cu șabloane multiple (vezi mai jos, algoritmul Aho-Corasick)

Reprezentare

Principalele întrebări sunt:

• Vreau să țin un vector cu toți copiii posibili, chiar dacă nu există? Dacă vorbim de biți sau chiar cifre zecimale, da. Dacă vorbim de toate literele alfabetului latin, s-ar putea ca 26 de fii să ocupe prea multă memorie, mai ales dacă mare parte din cele 26 de ramuri sunt nefolosite.
• Dacă încerc să reduc numărul de fii, țin un vector ordonat sau o listă înlănțuită? Într-un vector ordonat pot căuta binar fiul pe care vreau să cobor. În schimb, vectorul ordonat trebuie realocat, ceea ce este scump.
  • Putem face realocarea dublând spațiul vectorului
• Cum reduc mărimea frunzelor? Este important să nu aloc vectorul de fii în toate frunzele.

Pentru dicționare mari, arborii cer de 3-4 ori mai multă memorie decât lista simplă de șiruri, dar oferă avantajele sus-menționate.

Puteți citi o analiză aprofundată privind diversele metode de reprezentare și echilibrul între memorie folosită și viteză.

Ștergerea dintr-un trie poate fi ușor complicată dacă dorim să eliberăm memoria.

Compactare: comprimăm lanțurile neramificate într-un singur nod. Vezi suffix trees.

Implementare

• exemple de cod
• neapărat inserări / căutări iterative!

Algoritmul Aho-Corasick

O descriere bună aici.

Algoritmul Aho-Corasick este o generalizare a algoritmului KMP, permițând căutarea mai multor șiruri simultan. El acceptă un șir S și un set de k șabloane și tipărește toate perechile (i, j) astfel încât șablonul i apare în S la poziția (finală) j.

• Construiește un trie cu toate șabloanele;
• Îl extinde cu pointeri înapoi pentru a obține un DFA similar cu cel folosit în KMP.
  • se face printr-o parcurgere BFS a trie-ului
  • notă: mai multe stări sunt finale
• Iterează prin S, tipărind toate perechile (i, j) găsite

Exemplu: P = { he, she, his, hers }. Observăm că nodul din trie corespunzător lui „she” este o potrivire și pentru șablonul „he”.

Probleme

• Trie (infoarena). Este un punct fantastic de plecare, căci are date mari de test și puteți testa diversele reprezentări.
• Dictree este o aplicație directă a trie-urilor
• Xormax este o problemă pe trie-uri de biți
• Problema Trie trimite și la alte probleme

Arbori de sufixe (suffix trees)

În limita timpului disponibil.

Definiție: arborele de sufixe ale unui șir S de lungime n:

• are exact n frunze numerotate de la 1 la n
• nodurile interne au exact doi fii, cu posibila excepție a rădăcinii
• fiecare muchie este etichetată cu un subșir al lui S
• muchiile care pornesc dintr-un nod sunt etichetate cu șiruri care încep cu litere diferite
• etichetele de pe calea de la rădăcină la frunza i, citite în ordine, formează sufixul S[i..n]

Aplicații: tone de probleme pe șiruri de caractere

Construcție

Adăugăm un caracter nou la sfârșitul șirului, care să nu apară în șir (sau în alfabet). Facem aceasta deoarece este important ca nici un sufix al șirului să nu fie prefix pentru alt sufix (exemplu: abcab).

Observăm că sunt cel mult 2n noduri, deoarece fiecare nod intern are cel puțin doi fii.

Construcția naivă (inserează, pe rând, toate sufixele) este O(n²).

Cum reducem memoria la O(n)? Nu stocăm subșiruri pe fiecare muchie. Avem deja șirul original, deci stocăm perechi (poziție, lungime). Sunt cel mult 2n noduri, deci memoria necesară este O(n).

Cum reducem timpul la O(n)?

• arbore implicit: ștergem caracterul $, ștergem muchiile fără etichetă, ștergem nodurile cu un singur fiu
• algoritmul lui Ukkonen: construim arborii de sufixe T_i(S) pentru i = 1, 2, ..., 'n'. Acești pași se numesc faze.
• extensia de la T_i(S) la T_{i + 1}(S) se face prin trei reguli
  1. când S[j..i] se termină într-o frunză, extindem eticheta cu caracterul S[i + 1]
  2. când S[j..i] nu se termină într-o frunză și caracterul următor nu este S[i + 1], sparge muchia în două și inserează un nod
  3. când S[j..i] nu se termină într-o frunză și caracterul următor este S[i + 1], nu avem nimic de făcut

Până aici, algoritmul este chiar mai rău: avem n faze, fiecare cu O(n) extensii, iar fiecare extensie este O(n); deci algoritmul total este O(n³).

• suffix links: de la un subșir {zA} la un subșir {A}, pentru toate nodurile interne
• dorim să accelerăm fiecare extensie, eliminând nevoia de a reparcurge arborele din rădăcină
  • exemplu: aabbabaa
  • cum arătăm că fiecare nod intern chiar are un suffix link (că legătura către părinte nu cade undeva în mijlocul unei muchii)?
  • cum sunt menținute suffix links pe parcursul unei faze?
• accelerarea skip/count: sărim o muchie întreagă când căutăm un sufix în arbore
• s(v) este mai sus cu cel mult un nivel decât v
• rezultă că o fază poate fi terminată în O(n), deoarece
  • pornim din rădăcină
  • terminăm într-o frunză de adâncime cel mult n
  • urcăm cel mult 1 la fiecare extensie

Deci avem un algoritm de O(n²). Îi adăugăm două optimizări de viteză pentru a-l face liniar.

• dar regulile 1, 2 și 3 nu se aplică arbitrar; într-o fază se va aplica mereu regula 1 de un număr de ori, apoi, 2, apoi 3
• în particular, principiul show stopper spune că, dacă pentru S[j...i+1] am folosit regula 3, vom folosi tot regula 3 pentru tot restul fazei
  • demonstrație: dacă șirul S[j...i+1] există deja în arbore, atunci el este un subșir repetat. Copia lui anterioară include și S[k...i+1] pentru j < k <= j + 1
• atunci algoritmul poate încheia faza curentă și trece la faza următoare imediat ce descoperă că a ajuns la regula 3
• fast leaf update: o frunză, odată creată, va rămâne mereu o frunză
• dacă în faza i am aplicat regula 1 până la pasul r, putem aplica aceeași regula 1 până la pasul r și în faza i + 1
• deci realizăm primele r extensii în timp constant

La final, trebuie să reconvertim arborele implicit în arborele de sufixe propriu-zis. Pentru aceasta, facem o iterație normală cu caracterul $.

Aplicații

• Cel mai lung subșir (comun) crescător
• rotația circulară lexicografic minimă
• subsumează KMP
  • mai ineficient și mai greu de codat pentru o singură instanță, deoarece KMP are constantă mică
  • dar mult mai eficient pentru mai multe căutări, când șirul este fixat, iar șabloanele variază
  • compară și cu Aho-Corasick, care preprocesează șabloanele, nu șirul