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. Trie.jpg

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. Afd.jpg

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.

Commons
Commons ten máis contidos multimedia sobre: Trie