Trie
In informatica, un trie (pronunciato /ˈtriː/ oppure /ˈtraɪ/) è un tipo di struttura dati ad albero ordinato usata per rappresentare un set o un array associativo le cui chiavi sono tipicamente stringhe. A differenza di un albero binario di ricerca, i nodi non conservano una copia della propria chiave, che dipende invece dalla posizione del nodo nell'albero. La radice dell'albero è associata alla stringa vuota, e tutti i discendenti di un nodo condividono il prefisso associato a quel nodo. Non tutti i nodi rappresentano necessariamente una chiave significativa, che tipicamente si trova invece nelle foglie ed eventualmente in alcuni, ma non necessariamente tutti, i nodi interni.
Un trie può essere visto come una particolare istanza di automa a stati finiti deterministico: tutti i linguaggi finiti hanno un corrispondente trie che li rappresenta, e ogni trie può essere associato a un automa a stati finiti deterministico aciclico.
Storia modifica
I trie sono stati descritti per la prima volta da René de la Briandais nel 1959.[1][2] Il termine trie è stato introdotto due anni dopo da Edward Fredkin, che lo pronunciava /ˈtriː/ (come l'inglese tree) e consiste nella sillaba mediana di retrieval.[3][4] Altri autori preferiscono invece la pronuncia /ˈtraɪ/ (come l'inglese try) per evitare confusione con il termine tree nel parlato.[3][4][5]
Implementazione modifica
Un trie può essere implementato in differenti modi, con diversi compromessi tra velocità delle operazioni e consumo di memoria. Una implementazione elementare può essere fatta tramite una lista concatenata di nodi, nella quale ogni nodo contiene un array di puntatori a figli, uno per ogni carattere dell'alfabeto (quindi 26 per l'alfabeto inglese, oppure 256 per l'ASCII). Tale implementazione è molto semplice ed efficiente in tempo, ma inefficiente in termini di memoria, in quanto se le stringhe hanno relativamente pochi prefissi in comune (come avviene ad esempio in prossimità delle foglie) molto spazio risulta occupato da puntatori NULL (nel caso di stringhe ASCII con puntatori di 4 byte, ogni nodo occupa circa 1 kB).[6][7]
Il problema del consumo di memoria può essere mitigato con la tecnica detta alphabet reduction, che consiste nel reinterpretare le stringhe come nuove stringhe, più lunghe, basate su un alfabeto ridotto. Ad esempio, una stringa di n caratteri tra i 256 possibili nell'ASCII 8 bit può essere reinterpretata come una stringa di 2n caratteri su un alfabeto di 16 possibili nibble. In questo modo, il tempo di lookup raddoppia, ma la dimensione degli array di puntatori nei nodi diminuisce di 16 volte, permettendo di risparmiare spazio laddove molti caratteri fossero inutilizzati. Il caso estremo consiste nell'usare un alfabeto di un singolo bit, ovvero rappresentare le stringhe in forma binaria, tuttavia questa scelta è spesso poco conveniente in pratica per via del costo delle operazioni di accesso e manipolazione dei singoli bit in memoria.[8]
Un'implementazione alternativa usa una lista concatenata e rappresenta i nodi come triple (simbolo, figlio, fratello), dove figlio è il primo figlio del nodo, fratello il fratello più prossimo del nodo (il figlio successivo del padre del nodo corrente).[7][9] Con questa codifica dei nodi, il trie può anche essere rappresentato come albero; ne è un esempio la struttura nota come "trie ternario" o albero ternario di ricerca, introdotta da Jon Bentley e Robert Sedgewick.[10]
Note modifica
- ^ René de la Briandais, File searching using variable length keys, Proc. Western J. Computer Conf., 1959, pp. 295–298.
- ^ Brass, p. 336.
- ^ a b Paul E. Black, trie, su Dictionary of Algorithms and Data Structures, National Institute of Standards and Technology, 16 novembre 2009. URL consultato il 15 luglio 2017 (archiviato il 19 maggio 2010).
- ^ a b Franklin Mark Liang, Word Hy-phen-a-tion By Com-put-er (PDF), Stanford University, 1983. URL consultato il 28 marzo 2010 (archiviato il 19 maggio 2010).
- ^ Donald Knuth, 6.3: Digital Searching, in The Art of Computer Programming Volume 3: Sorting and Searching, 2nd, Addison-Wesley, 1997, p. 492, ISBN 0-201-89685-0.
- ^ Brass, p. 341.
- ^ a b Lloyd Allison, Tries, su allisons.org. URL consultato il 18 febbraio 2014.
- ^ Brass, pp. 347–352.
- ^ Sartaj Sahni, Tries, su Data Structures, Algorithms, & Applications in Java, University of Florida. URL consultato il 18 febbraio 2014.
- ^ Brass, p. 353.
Bibliografia modifica
- Peter Brass, Advanced Data Structures, Cambridge University Press, 2008.
Altri progetti modifica
Wikimedia Commons contiene immagini o altri file sul trie
