Trie

Un trie de las claves "A", "to", "tea", "ted", "ten", "i", "in", and "inn".

Introducidos en 1959 independientemente por Rene de la Briandais[1] y Edward Fredking,[2] un trie es una estructura de datos de tipo árbol que permite la recuperación de información (de ahí su nombre del inglés reTRIEval). La información almacenada en un trie es un conjunto de claves, donde una clave es una secuencia de símbolos pertenecientes a un alfabeto. Las claves son almacenadas en las hojas del árbol y los nodos internos son pasarelas para guiar la búsqueda. El árbol se estructura de forma que cada letra de la clave se sitúa en un nodo de forma que los hijos de un nodo representan las distintas posibilidades de símbolos diferentes que pueden continuar al símbolo representado por el nodo padre. Por tanto la búsqueda en un trie se hace de forma similar a como se hacen las búsquedas en un diccionario:

Se empieza en la raíz del árbol. Si el símbolo que estamos buscando es A entonces la búsqueda continúa en el subárbol asociado al símbolo A que cuelga de la raíz. Se sigue de forma análoga hasta llegar al nodo hoja. Entonces se compara la cadena asociada a el nodo hoja y si coincide con la cadena de búsqueda entonces la búsqueda ha terminado en éxito, si no entonces el elemento no se encuentra en el árbol.

Por eficiencia se suelen eliminar los nodos intermedios que sólo tienen un hijo, es decir, si un nodo intermedio tiene sólo un hijo con cierto carácter entonces el nodo hijo será el nodo hoja que contiene directamente la clave completa.

Es muy útil para conseguir búsquedas eficientes en repositorios de datos muy voluminosos. La forma en la que se almacena la información permite hacer búsquedas eficientes de cadenas que comparten prefijos.

Definición formal

Un trie es un caso especial de autómata finito determinista (S, Σ, T, s, A) llamado autómata finito determinista acíclico AFDA, que sirve para almacenar un conjunto de cadenas E en el que:

Ventajas

Las ventajas principales de los tries sobre los árboles de búsqueda binaria (BST) son:

Aplicaciones

Como sustitución de otras estructuras de datos

Como sustitución de una Tabla hash

Un Trie puede usarse para reemplazar una Tabla hash, sobre la que presenta las siguientes ventajas:

Las principales desventajas de los tries respecto a las tablas hash son:

Como representación de diccionarios

Una aplicación frecuente de los tries es el almacenamiento de diccionarios, como los que se encuentran en los teléfonos móviles. Estas aplicaciones se aprovechan de la capacidad de los tries para hacer búsquedas, inserciones y borrados rápidos. Sin embargo, si sólo se necesita el almacenamiento de las palabras (p.ej. no se necesita almacenar información auxiliar de las palabras del diccionario) un autómata finito determinista acíclico mínimo usa menos espacio que un trie.

Los tries también son útiles en la implementación de algoritmos de correspondencia aproximada, como los usados en el software de corrección ortográfica.

Algoritmos

El siguiente pseudocódigo determina si una cadena representa un trie.

function find(node, key) {
  if (key is an empty string) {  # base case
    return is node terminal?
  } else {  # recursive case
    c = first character in key  # this works because key is not empty
    tail = key minus the first character
    child = node.children[c]
    if (child is null) {  # unable to recurse, although key is non-empty
      return false
    } else {
      return find(child, tail)
    }
  }
}

Nota: children es un array con los hijos del nodo; y un nodo terminal es aquél que contiene una palabra válida.

Ordenamiento

El orden lexicográfico de un conjunto de claves se puede realizar con un algoritmo simple basado en tries de la siguiente forma:

Referencias

  1. Rene de la Briandais, "File searching using variable length keys". In Proceedings of the Western Joint Computer Conference, pages 295-298, 1959
  2. E. Fredkin, "Trie Memory" Comm. ACM 3 pp. 490-499 (1960).
This article is issued from Wikipedia - version of the Sunday, June 14, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.