Trie

Na Galipedia, a wikipedia en galego.

En informática, un trie é un tipo de árbore (tree) utilizado para representar listas de palabras sobre un alfabeto finito. Neles os camiños dende a raíz ata as follas están etiquetados coas palabras do conxunto que o trie representa. O trie introduciuse por primeira vez en torno a 1960 para implementar buscas rápidas en conxuntos de dados pequenos.

A seguinte figura mostra o trie correspondente ás palabras casa, cor e dedo. Nela os enlaces están etiquetados cos carácteres das palabras, os nodos intermedios representan puntos entre dous carácteres da palabra e as follas indican o fin dunha palabra.

As palabras que comparten un prefixo, como casa e cor no exemplo, compartirán o anaco do trie correspondente a este. Ao final do camiño etiquetado co prefixo haberá un nodo do que partirán tantos enlaces como palabras comparten ese prefixo. Compre notar que a etiqueta de cada un destes enlaces comezará por un carácter distinto. As palabras almacenadas no trie poden obterse percorrendo cada camiño dende a raíz ata a folla. Para isto percorrerase a estrutura descendendo dende a raíz comparando os símbolos da palabra buscada cos almacenados en cada pola do trie para seleccionar o camiño que se corresponde coa palabra. A busca rematará satisfactoriamente cando a palabra completa é atopada. No caso de non atoparse na estrutura a palabra buscada, a busca rematará ao atopar o primeiro carácter que non se corresponde con ningunha transición dende o nodo.

Os tries nos que cada transición está etiquetada cun único símbolo, un carácter no noso caso, son un tipo de [autómata finito determinista] (DFA, do inglés deterministic finite automaton). A figura mostra o DAF correspondente ao trie anterior.

Os trie son unha opción bastante natural para representar conxuntos de palabras e proporcionan resultados bastantes bos en canto a tempo de busca. Este será proporcional á lonxitude da palabra buscada.

Existen dúas maneiras principais de implementar tries: mediante arrais de punteiros e mediante listas enlazadas. Usar arrais de punteiros supón manter un conxunto de arrais cada un dos cales terá unha posición para cada símbolo do alfabeto. O array raíz corresponderá ao primeiro carácter de cada palabra: terá en cada posición para a que algunha palabra empeza con ese símbolo un punteiro a un novo array, correspondente ao segundo carácter das palabras que empezaban co carácter da posición da que parte o punteiro a este novo array, e así sucesivamente ata o final de cada palabra. Isto comprenderase máis doadamente coa seguinte figura, que mostra o trie das palabras casa, cor e dedo implementado mediante arrais de punteiros:

Como pode apreciarse, a implementación baseada en arrais de punteiros supón un enorme desperdicio de espazo naqueles conxuntos nos que poucas das posibilidades que seguen a un símbolo do alfabeto se producen, como sucede no caso dos dicionarios.

A implementación utilizando listas enlazadas utiliza unidades para representar carácteres. Estas unidades enlazarán entre si mediante punteiros, contando con dous punteiros cada unidade. A unidade raíz apuntará á unidade correspondente ao primeiro carácter da primeira palabra. Esta apuntará cun dos seus punteiros á unidade correspondente ao primeiro carácter da seguinte palabra que empece por un carácter distinto ao da propia unidade. O seu segundo punteiro apuntará á unidade correspondente ao segundo carácter da primeira palabra que empeza coa secuencia dende a raíz ata a unidade. Móstrase na seguinte figura como sería no caso das palabras casa, cor e dedo.

As necesidades que co tempo foron aparecendo de almacenar conxuntos de palabras máis longos contribuíron a realizar melloras nos tries, reducindo a cantidade de espazo que precisaban. Posto que os tries son utilizados para gran número de finalidades, os métodos de compactación desenvoltos adaptáronse aos requirimentos específicos de cada aplicación.