Clasele 11-12 lecția 14 - 7 ian 2015

Din capitolul despre șiruri de caractere intenționez să omitem următoarele secțiuni:

• reprezentări;
• quicksort ternar;
• căutare naivă / prin metoda Rabin-Karp / cu automate finite / prin metoda Knuth-Morris-Pratt.

Am acoperit în detaliu aceste subiecte la juniori, în lecțiile Clasele 9-10 lecția 10 - 19 nov 2014 și Clasele 9-10 lecția 11 - 26 nov 2014. Dacă nu sunteți familiari cu ele, citiți-le și puneți întrebări unde aveți nelămuriri. La seniori sunt șanse mari să vă izbiți de aceste subiecte în timp de concurs.

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 trie, oricât de compactați, 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ă refolosim memoria.

Implementare

Pentru implementare, un punct bun de pornire este problema Trie (infoarena). Iată și o implementare a mea care trece toate testele.

Ce am învățat eu din această implementare?

• Alocarea statică se dovedește, din nou, mai rapidă decât cea dinamică (cu malloc()). Sursa mea este mai rapidă decât toate cele cu care am confruntat-o, care folosesc alocare dinamică.
• Problema Trie în particular poate fi rezolvată și cu un vector de șiruri sortate + căutare binară. Iată o sursă care ia 100p. Sursa este cam de două ori mai lentă, dar folosește mult mai puțină memorie pe testele mari.

• Compactare: comprimăm lanțurile neramificate într-un singur nod. Vezi arborii de sufixe.

Aplicații

În general, trie-urile sunt bune pentru colecții de șiruri care au multe prefixe comune. Altfel, trie-urile risipesc prea multă memorie, iar o tabelă hash este mai eficientă.

Trie-urile sunt folositoare mai ales când avem nevoie să ordonăm sau să comparăm șiruri de caractere.

Sortarea de stringuri

Se inserează toate stringurile în trie, apoi se parcurge trie-le în preordine. Atenție, ea poate fi lentă și consumatoare de memorie! Un qsort ternar va rupe o sortare cu trie scrisă neglijent.

Căutare după prefix (autocomplete)

Se inserează toate stringurile în trie. Pentru un prefix dat, este ușor să găsim toate stringurile care încep cu acel prefix: navigăm prin trie până la prefix (dacă putem), apoi enumerăm stringurile din subarbore.

Căutarea celui mai lung prefix

Se dă o colecție de șiruri S și mai multe interogări constând din câte un prefix P. Pentru fiecare P, trebuie să găsim prefixul maxim comun între P și orice șir din S.

Soluțaa: navigăm prin trie pornind de la rădăcină, urmând literele lui P, fie până când nu mai putem avansa, fie când P se termină. Prefixul maxim comun este dat de calea de la rădăcină la nodul final.

T9 (autocomplete pe tastaturi numerice)

Pentru a tasta texte pe tastaturi numerice, fiecare cifră are asociate 3 sau 4 litere. De exemplu, 3 este asociat cu DEF, 4 cu GHI, 6 cu MNO. Metoda standard de tastare presupune apăsări multiple pentru a obține o literă. Pentru a obține F, trebuie să apăsăm tasta 3 de 3 ori.

Metoda T9 folosește o singură apăsare. Dacă apăsăm 4663, aceasta poate coincide cuvintelor GOOD, GOOF, HOOD, HOOF etc. Utilizatorul poate naviga printre aceste variante, iar sistemul învață, cu timpul, care sunt cuvintele mai des folosite.

Cum implementăm această metodă folosind un trie?

Algoritmul Aho-Corasick

O descriere bună aici.

Algoritmul Aho-Corasick este o generalizare a algoritmului KMP, permițând căutarea mai multor șabloane 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, iar o stare poate fi finală pentru mai multe șabloane.
• 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”.

Arbori de sufixe (suffix trees)

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 cel puțin 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]

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).

Pentru reducerea timpului la O(n) există un algoritm al lui Ukkonen, care este însă dificil. Nu vom insista pe el, deoarece folosim arborii de sufixe doar ca suport pentru a înțelege, data viitoare, șirurile de sufixe.

Aplicații

Vom prezenta aici o sumedenie de probleme rezolvabile cu arbori de sufixe. În practică, folosim mai degrabă șirurile de sufixe, dar arborii de sufixe sunt mai ușor de vizualizat.

Căutarea unui subșir în șir

După ce construim arborele de sufixe al lui S, căutarea lui P se reduce la enumerarea tuturor sufixelor care încep cu P. Așadar, navigăm în subarbore la nodul corespunzător lui P și tipărim toate frunzele din subarbore.

Aflarea celui mai lung subșir comun

Dându-se două șiruri S și T, dorim să aflăm cel mai lung subșir. Extindem șirurile cu simboluri diferite, de exemplu $ și # (sau putem folosi $1, $2, ...). Construim un singur arbore de sufixe din ambele șiruri. Apoi trebuie să găsim nodul aflat la distanța maximă de rădăcină (exprimată în număr de caractere) care conține în subarbore atât simboluri $, cât și #. Putem afla această informație printr-o parcurgere în postordine a arborelui.

Rotația circulară minimă dpdv lexicografic

Se dă un șir, de exemplu S = CABA. Să se găsească cea mai mică rotație circulară a lui (în acest caz ABAC).

Soluție: construim arborele de sufixe al șirului SS (S dublat). În acesta, căutăm, de la stânga la dreapta, primul sufix de lungime cel puțin |S|. Este important să nu acceptăm subșiruri mai scurte. De exemplu, sufixul minim este „A”, dar, dacă îi anexăm restul lui S, obținem ACAB, care nu este rotația minimă.

Notă: Există și un algoritm liniar pentru această problemă (algoritmul lui Booth, o adaptare a algoritmului KMP). Discuție.

Găsirea celui mai lung subșir palindrom

Dându-se un șir, să se găsească cel mai lung subșir al său care este palindrom.

Problema este netrivială în O(n). Considerați exemplul S = abcdexyxfdcba. Răspunsul este P = xyx.

Notă: Există și un algoritm liniar pentru această problemă (algoritmul lui Manacher). Discuție.

Comparații cu KMP și cu Aho-Corasick

Arborii de sufixe subsumează KMP. Ei sunt mai greu de codat și mai ineficienți, deoarece KMP are constantă mică.

Arborii de sufixe sunt eficienți pentru multe căutări, când șirul S este fixat, iar șabloanele P variază.

Spre deosebire de Aho-Corasick, care preprocesează șabloanele, arborii de sufixe preprocesează șirul.

Temă

• Tema 11 seniori