Există mai multe moduri de a reprezenta încercările, care corespund unor compromisuri diferite între utilizarea memoriei și viteza operațiilor. Forma de bază este cea a unui set legat de noduri, în care fiecare nod conține o matrice de pointeri copii, câte unul pentru fiecare simbol din alfabet (astfel, pentru alfabetul englezesc, s-ar stoca 26 de pointeri copii, iar pentru alfabetul de octeți, 256 de pointeri). Acest lucru este simplu, dar risipitor din punct de vedere al memoriei: folosind alfabetul de octeți (dimensiune 256) și pointeri de patru octeți, fiecare nod necesită un kilooctet de stocare, iar atunci când există o suprapunere redusă a prefixelor șirurilor de caractere, numărul de noduri necesare este aproximativ egal cu lungimea combinată a șirurilor stocate.:341 Altfel spus, nodurile din apropierea părții inferioare a arborelui tind să aibă puțini copii și există mulți dintre ei, astfel încât structura irosește spațiu stocând pointeri nuli.
Problema de stocare poate fi atenuată printr-o tehnică de implementare numită reducere a alfabetului, prin care șirurile originale sunt reinterpretate ca șiruri mai lungi pe un alfabet mai mic. De exemplu, un șir de n octeți poate fi considerat alternativ ca un șir de 2n unități de patru biți și stocat într-o trie cu șaisprezece pointeri pe nod. În cel mai rău caz, căutările trebuie să viziteze de două ori mai multe noduri, dar cerințele de stocare scad de opt ori.:347-352
O altă implementare alternativă reprezintă un nod ca o triplă (symbol, child, next) și leagă copiii unui nod împreună ca o listă legată individual: child indică primul copil al nodului, next indică următorul copil al nodului părinte. Setul de copii poate fi reprezentat, de asemenea, ca un arbore de căutare binar; un exemplu al acestei idei este arborele de căutare ternar dezvoltat de Bentley și Sedgewick.:353
O altă alternativă pentru a evita utilizarea unui tablou de 256 de pointeri (ASCII), așa cum s-a sugerat anterior, este de a stoca tabloul alfabetului ca un bitmap de 256 de biți reprezentând alfabetul ASCII, reducând drastic dimensiunea nodurilor.
Încercări de tip bitwiseEdit
Încercările bitwise sunt cam la fel ca o trie normală bazată pe caractere, cu excepția faptului că biții individuali sunt utilizați pentru a traversa ceea ce devine efectiv o formă de arbore binar. În general, implementările folosesc o instrucțiune specială a CPU pentru a găsi foarte rapid primul bit setat într-o cheie de lungime fixă (de exemplu, intrinsecul __builtin_clz() al GCC). Această valoare este apoi utilizată pentru a indexa un tabel cu 32 sau 64 de intrări care indică primul element din trierea în sensul biților cu acel număr de biți cu zero în față. Căutarea continuă apoi prin testarea fiecărui bit următor din cheie și alegerea corespunzătoare a child sau child până la găsirea elementului.
Deși acest proces poate părea lent, este foarte bine localizat în memoria cache și foarte paralelizabil datorită lipsei dependențelor de registre și, prin urmare, are de fapt performanțe excelente pe procesoarele moderne cu execuție în afara ordinii. Un arbore roșu-negru, de exemplu, are performanțe mult mai bune pe hârtie, dar este foarte neprietenos cu memoria cache și cauzează multiple blocaje în pipeline și TLB pe procesoarele moderne, ceea ce face ca acest algoritm să fie limitat de latența memoriei mai degrabă decât de viteza procesorului. În comparație, un bitwise trie accesează rareori memoria, iar atunci când o face, o face doar pentru a citi, evitând astfel costurile de coerență a cache-ului SMP. Prin urmare, acesta devine din ce în ce mai mult algoritmul preferat pentru codul care efectuează multe inserții și ștergeri rapide, cum ar fi alocatorii de memorie (de exemplu, versiunile recente ale faimosului alocator al lui Doug Lea (dlmalloc) și ale descendenților săi). În cel mai rău caz, numărul de pași pentru căutare este același cu cel al biților utilizați pentru a indexa bini în arbore.
Alternativ, termenul „bitwise trie” se poate referi mai general la o structură arborescentă binară care conține valori întregi, ordonându-le după prefixul lor binar. Un exemplu este trie-ul x-fast.
Comprimarea încercărilorEdit
Comprimarea trie-ului și fuzionarea ramurilor comune poate produce uneori câștiguri mari de performanță. Acest lucru funcționează cel mai bine în următoarele condiții:
- Trie este (în mare parte) statică, astfel încât nu sunt necesare inserții sau ștergeri de chei (de exemplu, după crearea în bloc a trie).
- Sunt necesare doar căutări.
- Nodurile trie nu sunt codificate de date specifice nodurilor sau datele nodurilor sunt comune.
- Setul total de chei stocate este foarte rarefiat în cadrul spațiului lor de reprezentare (astfel încât compresia dă roade).
De exemplu, poate fi utilizat pentru a reprezenta seturi de biți rarefiat; adică subansambluri ale unui set enumerabil fix mult mai mare. Într-un astfel de caz, trie este codificată de poziția elementului de bit în cadrul setului complet. Cheia este creată din șirul de biți necesar pentru a codifica poziția integrală a fiecărui element. Astfel de încercări au o formă foarte degenerată, cu multe ramuri lipsă. După detectarea repetării modelelor comune sau umplerea golurilor nefolosite, nodurile foliare unice (șiruri de biți) pot fi stocate și comprimate cu ușurință, reducând dimensiunea totală a trie.
O astfel de compresie este utilizată și în implementarea diferitelor tabele de căutare rapidă pentru recuperarea proprietăților caracterelor Unicode. Acestea ar putea include tabele de mapare a majusculelor și minusculelor (de exemplu, pentru litera greacă pi, de la Π la π), sau tabele de căutare care normalizează combinația dintre caracterele de bază și cele de combinare (cum ar fi a-umlaut în germană, ä, sau dalet-patah-dagesh-ole în ebraica biblică, דַּ֫). Pentru astfel de aplicații, reprezentarea este similară cu transformarea unui tabel foarte mare, unidimensional și rarefiat (de exemplu, punctele de cod Unicode) într-o matrice multidimensională a combinațiilor acestora, iar apoi utilizarea coordonatelor din hipermatrice ca cheie de șir de caractere a unei trie necomprimate pentru a reprezenta caracterul rezultat. Compresia va consta apoi în detectarea și fuzionarea coloanelor comune în cadrul hipermatricii pentru a comprima ultima dimensiune din cheie. De exemplu, pentru a evita stocarea întregului punct de cod Unicode multibyte al fiecărui element care formează o coloană a matricei, pot fi exploatate grupările de puncte de cod similare. Fiecare dimensiune a hipermatricii stochează poziția de început a dimensiunii următoare, astfel încât este necesar să se stocheze doar decalajul (de obicei un singur octet). Vectorul rezultat este el însuși compresibil atunci când este, de asemenea, rarefiat, astfel încât fiecare dimensiune (asociată unui nivel de strat în trie) poate fi comprimată separat.
Câteva implementări suportă o astfel de comprimare a datelor în cadrul încercărilor rarefiate dinamice și permit inserții și ștergeri în încercările comprimate. Cu toate acestea, acest lucru are de obicei un cost semnificativ atunci când segmentele comprimate trebuie să fie divizate sau fuzionate. Trebuie să se facă un compromis între compresia datelor și viteza de actualizare. O strategie tipică constă în limitarea intervalului de căutări globale pentru compararea ramurilor comune din trie-ul rar.
Rezultatul unei astfel de comprimări poate părea similar cu încercarea de a transforma trie-ul într-un graf aciclic direcționat (DAG), deoarece transformarea inversă dintr-un DAG într-un trie este evidentă și întotdeauna posibilă. Cu toate acestea, forma DAG-ului este determinată de forma cheii alese pentru a indexa nodurile, ceea ce, la rândul său, limitează compresia posibilă.
O altă strategie de compresie constă în „desfacerea” structurii de date într-o matrice de un singur octet.Această abordare elimină necesitatea indicatorilor de nod, reducând substanțial cerințele de memorie. Aceasta, la rândul său, permite cartografierea memoriei și utilizarea memoriei virtuale pentru a încărca eficient datele de pe disc.
O altă abordare este „împachetarea” triei. Liang descrie o implementare eficientă din punct de vedere spațial a unei trie compactate rare aplicate la despărțirea automată a cratimei, în care descendenții fiecărui nod pot fi intercalați în memorie.
Încercări de memorie externăEdit
Diverse variante de trie sunt potrivite pentru a menține seturi de șiruri de caractere în memoria externă, inclusiv arbori de sufixe. O combinație de trie și B-tree, numită B-trie, a fost, de asemenea, sugerată pentru această sarcină; în comparație cu arborii de sufixe, aceștia sunt limitați în ceea ce privește operațiile suportate, dar și mai compacți, efectuând în același timp mai rapid operațiile de actualizare.
.