Structura de date Trie: O bijuterie neglijată

Încă din primele zile din viața noastră ca programatori, ne-am ocupat cu toții de structuri de date: matrice, liste conectate, arbori, seturi, stive și cozi sunt însoțitorii noștri de zi cu zi, iar programatorul experimentat știe când și de ce să le folosească. În acest articol, vom vedea cum o structură de date adesea neglijată, trie , strălucește cu adevărat în domeniile de aplicații cu caracteristici specifice, cum ar fi jocurile de cuvinte.

Jocuri de cuvinte ca exemplu

Pentru început, să luăm în considerare un simplu puzzle de cuvinte: găsiți toate cuvintele valide într-o tablă de litere 4x4, conectând literele adiacente orizontal, vertical sau în diagonală. De exemplu, în panoul următor, vedem literele „W”, „A”, „I” și „T” conectându-se pentru a forma cuvântul „WAIT”.

Soluția naivă pentru găsirea tuturor cuvintelor valide ar fi explorarea tablei pornind din colțul din stânga sus și apoi deplasând mai întâi adâncimea la secvențe mai lungi, începând din nou de la a doua literă din primul rând și așa mai departe. Într-o tablă 4x4, care permite mișcări verticale, orizontale și în diagonală, există 12029640 de secvențe, cu lungimea de la unu la șaisprezece caractere.

Acum, scopul nostru este să găsim cea mai bună structură de date pentru a implementa acest verificator de cuvinte valide, adică vocabularul nostru. Câteva puncte de reținut:

• Avem nevoie doar de o singură copie a fiecărui cuvânt, adică vocabularul nostru este un set, din punct de vedere logic.
• Trebuie să răspundem la următoarele întrebări pentru orice cuvânt dat:
  • Secvența de caractere curentă cuprinde un cuvânt valid?
  • Există cuvinte mai lungi care încep cu această secvență? Dacă nu, putem abandona explorarea în profunzime, deoarece aprofundarea nu va da niciun cuvânt valid.

Pentru a ilustra al doilea punct, luați în considerare următoarea tablă: Nu are rost să explorați mișcările ulterioare, deoarece nu există cuvinte în dicționar care să înceapă cu „ASF”.

Ne-ar plăcea ca structura noastră de date să răspundă la aceste întrebări cât mai repede posibil. ~O(1) timpul de acces (pentru verificarea unei secvențe) ar fi ideal!

Putem defini interfața Vocabulary astfel (vezi aici pentru depozitul GitHub):

 public interface Vocabulary { boolean add(String word); boolean isPrefix(String prefix); boolean contains(String word); }

Încercați Structura de date vs. Alternative

Implementarea metodei contains() necesită o structură de date de rezervă care să vă permită să găsiți elemente în mod eficient, în timp ce metoda isPrefix() ne cere să găsim „următorul element mai mare”, adică trebuie să păstrăm vocabularul sortat într-un fel.

Putem exclude cu ușurință seturi bazate pe hash din lista noastră de candidați: în timp ce o astfel de structură ne-ar oferi o verificare în timp constant pentru contains() , ar funcționa destul de slab pe isPrefix() , în cel mai rău caz necesitând să scanăm întregul a stabilit.

Din motivul opus, putem exclude și listele legate sortate, deoarece necesită scanarea listei cel puțin până la primul element care este mai mare sau egal cu cuvântul sau prefixul căutat.

Două opțiuni valide folosesc o listă sortată susținută de matrice sau un arbore binar.
Pe lista sortată bazată pe matrice, putem folosi căutarea binară pentru a găsi secvența curentă dacă este prezentă sau următorul element mai mare cu un cost de O(log2(n)) , unde n este numărul de cuvinte din dicționar.

Putem implementa un vocabular susținut de matrice care menține întotdeauna ordinea ca acesta, folosind standardul java.util.ArrayList și java.util.Collections.binarySeach :

 public class ListVocabulary implements Vocabulary { private List<String> words = new ArrayList<String>(); /** * Constructor that adds all the words and then sorts the underlying list */ public ListVocabulary(Collection<String> words) { this.words.addAll(words); Collections.sort(this.words); } public boolean add(String word) { int pos = Collections.binarySearch(words, word); // pos > 0 means the word is already in the list. Insert only // if it's not there yet if (pos < 0) { words.add(-(pos+1), word); return true; } return false; } public boolean isPrefix(String prefix) { int pos = Collections.binarySearch(words, prefix) ; if (pos >= 0) { // The prefix is a word. Check the following word, because we are looking // for words that are longer than the prefix if (pos +1 < words.size()) { String nextWord = words.get(pos+1); return nextWord.startsWith(prefix); } return false; } pos = -(pos+1); // The prefix is not a word. Check where it would be inserted and get the next word. // If it starts with prefix, return true. if (pos == words.size()) { return false; } String nextWord = words.get(pos); return nextWord.startsWith(prefix); } public boolean contains(String word) { int pos = Collections.binarySearch(words, word); return pos >= 0; } }

Dacă am decis să folosim un arbore binar, implementarea ar putea fi și mai scurtă și mai elegantă (din nou, iată un link către cod):

 public class TreeVocabulary extends TreeSet<String> implements Vocabulary { public TreeVocabulary(Collection<String> c) { super(c); } public boolean isPrefix(String prefix) { String nextWord = ceiling(prefix); if (nextWord == null) { return false; } if (nextWord.equals(prefix)) { Set<String> tail = tailSet(nextWord, false); if (tail.isEmpty()) { return false; } nextWord = tail.iterator().next(); } return nextWord.startsWith(prefix); } /** * There is a mismatch between the parameter types of vocabulary and TreeSet, so * force call to the upper-class method */ public boolean contains(String word) { return super.contains(word); } }

În ambele cazuri, ne putem aștepta la performanța O(log n) pentru fiecare metodă de acces ( contains() și isPrefix() ). În ceea ce privește cerințele de spațiu, atât implementarea susținută de matrice, cât și implementarea susținută de arbore necesită O(n+M) unde n este numărul de cuvinte din dicționar și M este dimensiunea octetilor dicționarului, adică suma lungimii șirurile din dicționar.

Aplicații Trie: Când și de ce să folosiți Tries

Performanța logaritmică și memoria liniară nu sunt rele. Dar mai există câteva caracteristici ale domeniului nostru de aplicații care ne pot conduce la o performanță mai bună:

• Putem presupune cu siguranță că toate cuvintele sunt litere mici.
• Acceptăm numai litere az — fără semne de punctuație, fără cratime, fără accente etc.
• Dicționarul conține multe forme flexate: plurale, verbe conjugate, cuvinte compuse (de exemplu, casă –> menajeră). Prin urmare, multe cuvinte au aceeași tulpină .
• Cuvintele au o lungime limitată. De exemplu, dacă lucrăm pe o placă 4x4, toate cuvintele mai lungi de 16 caractere pot fi aruncate.

Aici intervine trie (pronunțat „try”). Dar ce este exact un trie? Încercările sunt structuri de date neglijate, găsite în cărți, dar rareori în bibliotecile standard.

Pentru motivație, să luăm mai întâi în considerare copilul poster al Computer Science: arborele binar. Acum, când analizăm performanța unui arbore binar și spunem că operația x este O(log(n)) , vorbim constant de baza logaritmică 2. Dar dacă, în loc de arbore binar, am folosi un arbore ternar, unde fiecare nod are trei copii (sau un fan-out din trei). Apoi, am vorbi de baza de jurnal 3. (Aceasta este o îmbunătățire a performanței, deși doar printr-un factor constant.) În esență, copacii noștri ar deveni mai largi, dar mai scurti și am putea efectua mai puține căutări, deoarece nu trebuie să coborâm destul de mult atat de adanc.

Făcând lucrurile cu un pas mai departe, ce se întâmplă dacă am avea un arbore cu fan-out egal cu numărul de valori posibile ale tipului nostru de date?

Aceasta este motivația din spatele încercării. Și după cum probabil ați ghicit, un trie este într-adevăr un copac, un trie tree ca să spunem așa!

Dar, spre deosebire de majoritatea arborilor binari pe care i-ați folosi pentru sortarea șirurilor de caractere, cei care ar stoca cuvinte întregi în nodurile lor, fiecare nod al unui trie deține un singur caracter (și nici măcar asta, așa cum vom vedea în curând) și are un evantai maxim egal cu lungimea alfabetului. În cazul nostru, lungimea alfabetului este de 26; prin urmare, nodurile trie au un fan-out maxim de 26. Și, în timp ce un arbore binar echilibrat are log2(n) adâncime, adâncimea maximă a trie este egală cu lungimea maximă a unui cuvânt! (Din nou, mai lat, dar mai scurt.)

În cadrul unei încercări, cuvintele cu aceeași rădăcină (prefix) împărtășesc zona de memorie care corespunde tulpinii.

Pentru a vizualiza diferența, să luăm în considerare un mic dicționar format din cinci cuvinte. Să presupunem că literele grecești indică indicatori și rețineți că în trie, caracterele roșii indică noduri care dețin cuvinte valide .

Implementarea Java Trie

După cum știm, în arbore pointerii către elementele copii sunt de obicei implementați cu o variabilă stânga și dreapta, deoarece fan-out-ul maxim este fixat la doi.

Într-o încercare de indexare a unui alfabet de 26 de litere, fiecare nod are 26 de copii posibili și, prin urmare, 26 de indicatori posibili. Fiecare nod prezintă astfel o matrice de 26 (pointeri către) sub-arbori, unde fiecare valoare poate fi fie nulă (dacă nu există un astfel de copil) sau un alt nod.

Cum, atunci, căutăm un cuvânt într-o încercare? Iată metoda care, dat un String s , va identifica nodul care corespunde ultimei litere a cuvântului, dacă acesta există în arbore:

 public LowercaseTrieVocabulary getNode(String s) { LowercaseTrieVocabulary node = this; for (int i = 0; i < s.length(); i++) { int index = LOWERCASE.getIndex(s.charAt(i)); LowercaseTrieVocabulary child = node.children[index]; if (child == null) { // There is no such word return null; } node = child; } return node; }

Metoda LOWERCASE.getIndex(s.charAt(i)) returnează pur și simplu poziția celui de-al i -lea caracter în alfabet. Pe nodul returnat, un node de proprietate boolean indică faptul că nodul corespunde ultimei litere a unui cuvânt, adică unei litere marcate cu roșu în exemplul anterior. Deoarece fiecare nod păstrează un numărător al numărului de copii, dacă acest contor este pozitiv, atunci există cuvinte mai lungi în dicționar care au șirul curent ca prefix. Notă: nodul nu trebuie să păstreze o referință la caracterul căruia îi corespunde, deoarece este implicit în poziția sa în trie.

Analizând Performanța

Ceea ce face ca structura trie să funcționeze într-adevăr bine în aceste situații este că costul căutării unui cuvânt sau prefix este fix și depinde doar de numărul de caractere din cuvânt și nu de dimensiunea vocabularului.

În domeniul nostru specific, deoarece avem șiruri care au cel mult 16 caractere, sunt necesari exact 16 pași pentru a găsi un cuvânt care se află în vocabular, în timp ce orice răspuns negativ, adică cuvântul sau prefixul nu se află în încercare, poate fi obținut. și în cel mult 16 pași! Având în vedere că am ignorat anterior lungimea șirului atunci când calculăm complexitatea timpului de rulare atât pentru lista sortată susținută de matrice, cât și pentru arbore, care este ascuns în comparațiile de șiruri, putem la fel de bine să o ignorăm aici și să afirmăm în siguranță că căutarea este făcută. în timp O(1) .

Având în vedere cerințele de spațiu (și amintindu-ne că am indicat cu M dimensiunea octeților dicționarului), trie-ul ar putea avea M noduri în cel mai rău caz, dacă nu există două șiruri de caractere care au un prefix comun. Dar, din moment ce am observat că există un grad ridicat de redundanță în dicționar, este mult de făcut. Dicționarul englez care este folosit în exemplul de cod are 935.017 octeți și necesită 250.264 de noduri, cu un raport de compresie de aproximativ 73%.

Cu toate acestea, în ciuda acestui fapt, chiar și o încercare comprimată va necesita, de obicei, mai multă memorie decât un arbore sau o matrice. Acest lucru se datorează faptului că, pentru fiecare nod, sunt necesare cel puțin 26 x sizeof(pointer) bytes, plus o suprasarcină pentru obiect și atribute suplimentare. Pe o mașină pe 64 de biți, fiecare nod necesită mai mult de 200 de octeți, în timp ce un caracter șir necesită un singur octet sau doi dacă luăm în considerare șirurile UTF.

Încercări și teste de performanță

Deci, ce zici de performanță? Implementările de vocabular au fost testate în două situații diferite: verificarea a 20.000.000 de șiruri aleatorii și găsirea tuturor cuvintelor din 15.000 de panouri generate aleator din aceeași listă de cuvinte.

Au fost analizate patru structuri de date: o listă sortată susținută de matrice, un arbore binar, trie descris mai sus și un trie care utilizează matrice de octeți corespunzător indexului alfabetic al caracterelor în sine (o optimizare minoră și ușor de implementat). Iată rezultatele, în ms:

Numărul mediu de mișcări făcute pentru a rezolva tabla este de 2.188. Pentru fiecare mutare se face o căutare de cuvinte și o căutare de prefix, adică, pentru verificarea tuturor panourilor, au fost efectuate mai mult de 32M de căutări de cuvinte și 32M de căutări de prefix. Notă: acestea se puteau face într-un singur pas, le-am ținut separate pentru claritate în expunere. Compactarea lor într-un singur pas ar reduce timpul de rezolvare a plăcilor aproape la jumătate și, probabil, ar favoriza și mai mult încercarea.

După cum se poate vedea mai sus, căutarea cuvântului funcționează mai bine cu trie chiar și atunci când se utilizează șiruri de caractere și este chiar mai rapidă atunci când se utilizează indici alfabetici, aceștia din urmă având performanțe de peste două ori mai rapide decât un arbore binar standard. Diferența în rezolvarea tablelor este și mai evidentă, soluția rapidă trie-alphabet-index fiind de peste patru ori mai rapidă decât lista și arborele.

Încheierea

Trie este o structură de date foarte specializată, care necesită mult mai multă memorie decât arbori și liste. Cu toate acestea, atunci când se aplică caracteristici specifice domeniului, cum ar fi un alfabet limitat și o redundanță ridicată în prima parte a șirurilor, poate fi foarte eficient în abordarea optimizării performanței.

Referințe

O explicație extinsă a încercărilor și alfabetelor poate fi găsită în capitolul 5 al cărții lui Robert Sedgewick „Algoritmi, ediția a 4-a”. Site-ul web însoțitor de la Princeton are codul pentru o implementare a Alphabet și TrieST care este mai extins decât exemplul meu.

Descrierea încercării și a implementărilor pentru diferite limbi pot fi găsite și pe Wikipedia și puteți arunca o privire și la această resursă de încercare a Universității din Boston.