Trie

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

• Σ es el alfabeto sobre el que están definidas las cadenas;
• S, el conjunto de estados, cada uno de los cuales representa un prefijo de E;
• la función de transición: ; está definida como sigue: T(x,σ) = xσ si , e indefinida en otro caso;
• el estado inicial s corresponde a la cadena vacía λ;
• el conjunto de estados de aceptación es igual a E.

Su nombre procede del término inglés retrieval.

Ventajas

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

• búsqueda de claves más rápida. La búsqueda de una clave de longitud m tendrá en el peor de los casos un coste de O(m). Un BST tiene un coste de O(logn), siendo n el número de elementos del árbol, ya que la búsqueda depende de la profundidad del árbol, logarítmica con el número de claves.
• menos espacio requerido para almacenar gran cantidad de cadenas pequeñas, puesto que las claves no se almacenan explícitamente
• mejor funcionamiento para el algoritmo de búsqueda del prefijo más largo

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:

• el tiempo de búsqueda en una Tabla hash imperfecta es del orden de O(n), mientras que en un trie es del orden de O(l). Esto es debido a las colisiones de claves.
• en un trie no se producen colisions de claves
• no hay que definir una función de hash, o modificarla si añadimos más claves
• los contenedores que almacenan distintos valores asociados a una única clave sólo son necesarios si tenemos más de un valor asociada a una única clave. En una tabla hash siempre se necesitan estos contenedores para las colisiones de clave
• un trie puede proporcionarnos un ordenamiento alfabético de las entradas por clave

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

• en determinados casos pueden ser más lentos que las tablas hash en la búsqueda de datos, especialmente si los datos son consultados desde dispositivos de almacenamiento secundario, como disco duro, donde el tiempo de acceso es elevado con respecto a memoria principal
• no es sencillo representar todas las claves como cadenas, como los números reales, que pueden tener distintas representaciones en forma de cadena para un mismo número, p.ej. 1, 1.00, 1.000, +1.000,...
• a menudo los tries son más ineficientes respecto al espacio que las tablas hash
• los tries no suelen estar disponibles con las herramientas de desarrollo software, todo lo contrario que las tablas hash

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:

• insertar todas las claves en el trie
• obtener todas las claves mediante un recorrido en pre-orden, para obtener un ordenamiento lexicográfico en orden ascendente; o mediante un recorrido en post-orden, para obtener un ordenamiento lexicográfico en orden descendente. El recorrido pre-orden y el recorrido post-orden son algoritmos de búsqueda en profundidad en árboles.