Ci sono diversi modi di rappresentare i trie, corrispondenti a diversi compromessi tra uso della memoria e velocità delle operazioni. La forma base è quella di un insieme di nodi collegati, dove ogni nodo contiene un array di puntatori figli, uno per ogni simbolo dell’alfabeto (così per l’alfabeto inglese, si memorizzerebbero 26 puntatori figli e per l’alfabeto dei byte, 256 puntatori). Questo è semplice ma dispendioso in termini di memoria: usando l’alfabeto di byte (dimensione 256) e puntatori a quattro byte, ogni nodo richiede un kilobyte di memoria, e quando c’è poca sovrapposizione nei prefissi delle stringhe, il numero di nodi richiesti è approssimativamente la lunghezza combinata delle stringhe memorizzate.:341 Detto altrimenti, i nodi vicino al fondo dell’albero tendono ad avere pochi figli e ce ne sono molti, così la struttura spreca spazio memorizzando puntatori nulli.
Il problema della memorizzazione può essere alleviato da una tecnica di implementazione chiamata riduzione dell’alfabeto, per cui le stringhe originali sono reinterpretate come stringhe più lunghe su un alfabeto più piccolo. Ad esempio, una stringa di n byte può essere alternativamente considerata come una stringa di 2n unità a quattro bit e memorizzata in un trie con sedici puntatori per nodo. Le ricerche devono visitare il doppio dei nodi nel caso peggiore, ma i requisiti di memorizzazione scendono di un fattore otto.:347-352
Un’implementazione alternativa rappresenta un nodo come una tripla (symbol, child, next) e collega i figli di un nodo insieme come una lista collegata singolarmente: child punta al primo figlio del nodo, next al figlio successivo del nodo padre. L’insieme dei figli può anche essere rappresentato come un albero di ricerca binario; un esempio di questa idea è l’albero di ricerca ternario sviluppato da Bentley e Sedgewick.:353
Un’altra alternativa per evitare l’uso di un array di 256 puntatori (ASCII), come suggerito prima, è quella di memorizzare l’array dell’alfabeto come una bitmap di 256 bit che rappresenta l’alfabeto ASCII, riducendo drasticamente la dimensione dei nodi.
Bitwise triesEdit
I tentativi bitwise sono più o meno gli stessi di un normale trie basato sui caratteri, tranne che i singoli bit sono usati per attraversare quello che effettivamente diventa una forma di albero binario. Generalmente, le implementazioni usano un’istruzione speciale della CPU per trovare molto rapidamente il primo bit impostato in una chiave di lunghezza fissa (ad esempio, l’intrinseco __builtin_clz() di GCC). Questo valore viene poi usato per indicizzare una tabella a 32 o 64 voci che punta al primo elemento nel trio bitwise con quel numero di bit zero iniziali. La ricerca procede poi testando ogni bit successivo nella chiave e scegliendo child o child in modo appropriato fino a quando l’elemento viene trovato.
Anche se questo processo potrebbe sembrare lento, è molto cache-local e altamente parallelizzabile a causa della mancanza di dipendenze di registro e quindi in effetti ha prestazioni eccellenti sulle moderne CPU con esecuzione fuori ordine. Un albero rosso-nero, per esempio, ha prestazioni molto migliori sulla carta, ma è altamente ostile alla cache e causa stalli multipli della pipeline e del TLB sulle CPU moderne, il che rende questo algoritmo vincolato dalla latenza della memoria piuttosto che dalla velocità della CPU. In confronto, un trie bitwise accede raramente alla memoria, e quando lo fa, lo fa solo per leggere, evitando così l’overhead della coerenza della cache SMP. Quindi, sta diventando sempre più l’algoritmo di scelta per il codice che esegue molti inserimenti e cancellazioni rapidi, come gli allocatori di memoria (ad esempio, le versioni recenti del famoso allocatore di Doug Lea (dlmalloc) e i suoi discendenti). Il caso peggiore di passi per la ricerca è lo stesso dei bit usati per indicizzare i bidoni nell’albero.
Alternativamente, il termine “trie bitwise” può riferirsi più in generale a una struttura ad albero binario che contiene valori interi, ordinandoli per il loro prefisso binario. Un esempio è il trie x-fast.
Comprimere i triesEdit
Comprimere il trie e unire i rami comuni può talvolta produrre grandi guadagni di prestazioni. Questo funziona meglio nelle seguenti condizioni:
- Il trie è (per lo più) statico, così che non sono richieste inserzioni o cancellazioni di chiavi (ad esempio, dopo la creazione in blocco del trie).
- Sono necessarie solo le ricerche.
- I nodi del trie non sono legati da dati specifici del nodo, o i dati dei nodi sono comuni.
- L’insieme totale delle chiavi memorizzate è molto rado all’interno del loro spazio di rappresentazione (quindi la compressione paga).
Per esempio, può essere usato per rappresentare insiemi di bit radi; cioè, sottoinsiemi di un insieme enumerabile fisso molto più grande. In tal caso, il trie è codificato dalla posizione dell’elemento bit all’interno dell’insieme completo. La chiave è creata dalla stringa di bit necessaria per codificare la posizione integrale di ogni elemento. Tali tentativi hanno una forma molto degenerata con molti rami mancanti. Dopo aver individuato la ripetizione di schemi comuni o aver riempito le lacune inutilizzate, i nodi foglia unici (stringhe di bit) possono essere memorizzati e compressi facilmente, riducendo la dimensione complessiva del trie.
Tale compressione è usata anche nell’implementazione delle varie tabelle di ricerca veloce per il recupero delle proprietà dei caratteri Unicode. Queste potrebbero includere tabelle di mappatura dei casi (ad esempio, per la lettera greca pi, da Π a π), o tabelle di ricerca che normalizzano la combinazione di caratteri base e combinatori (come la a-umlaut in tedesco, ä, o il dalet-patah-dagesh-ole in ebraico biblico, דַּ֫). Per tali applicazioni, la rappresentazione è simile alla trasformazione di una tabella molto grande, unidimensionale e sparsa (ad esempio, i punti di codice Unicode) in una matrice multidimensionale delle loro combinazioni, e quindi utilizzando le coordinate nella iper-matrice come chiave di stringa di un trie non compresso per rappresentare il carattere risultante. La compressione consisterà poi nel rilevare e unire le colonne comuni all’interno dell’iper-matrice per comprimere l’ultima dimensione nella chiave. Per esempio, per evitare di memorizzare l’intero punto di codice Unicode multibyte di ogni elemento che forma una colonna della matrice, si possono sfruttare i raggruppamenti di punti di codice simili. Ogni dimensione dell’iper-matrice memorizza la posizione iniziale della dimensione successiva, in modo che solo l’offset (tipicamente un singolo byte) debba essere memorizzato. Il vettore risultante è a sua volta comprimibile quando è anche rado, quindi ogni dimensione (associata a un livello di livello nel trie) può essere compressa separatamente.
Alcune implementazioni supportano tale compressione dei dati all’interno delle prove dinamiche rade e permettono inserimenti e cancellazioni nelle prove compresse. Tuttavia, questo di solito ha un costo significativo quando i segmenti compressi devono essere divisi o uniti. Deve essere fatto un compromesso tra la compressione dei dati e la velocità di aggiornamento. Una strategia tipica è quella di limitare la gamma di lookup globali per confrontare i rami comuni nel trie sparso.
Il risultato di tale compressione può sembrare simile al tentativo di trasformare il trie in un grafo aciclico diretto (DAG), perché la trasformazione inversa da un DAG a un trie è ovvia e sempre possibile. Tuttavia, la forma del DAG è determinata dalla forma della chiave scelta per indicizzare i nodi, a sua volta limitando la compressione possibile.
Un’altra strategia di compressione è quella di “svelare” la struttura dei dati in un singolo array di byte. Questo a sua volta permette la mappatura della memoria e l’uso della memoria virtuale per caricare in modo efficiente i dati dal disco.
Un altro approccio è quello di “impacchettare” il trie. Liang descrive un’implementazione efficiente in termini di spazio di un trie impacchettato sparso applicato alla sillabazione automatica, in cui i discendenti di ogni nodo possono essere interfogliati in memoria.
Tentativi di memoria esternaEdit
Diverse varianti di trie sono adatte a mantenere insiemi di stringhe in memoria esterna, inclusi gli alberi di suffissi. Una combinazione di trie e B-tree, chiamata B-trie è stata anche suggerita per questo compito; rispetto agli alberi di suffissi, sono limitati nelle operazioni supportate ma anche più compatti, mentre eseguono le operazioni di aggiornamento più velocemente.