Tries para búsquedas por prefijo: autocompletado y coincidencia del prefijo más largo

Qué es

El diccionario del NIST define un trie como un árbol para almacenar cadenas con un nodo por cada prefijo común. Cada arista lleva un símbolo (un byte, un carácter o un bit), y un marcador terminal o una hoja identifica las claves almacenadas. Buscar una clave recorre una arista por símbolo, de modo que el costo depende de la longitud de la clave, no del número de claves almacenadas. Todas las claves que comparten un prefijo viven en el subárbol bajo el nodo de ese prefijo. Un árbol radix (Patricia o trie compacto) fusiona cadenas de nodos con un solo hijo en una única arista etiquetada para ahorrar memoria. La tabla de enrutamiento IPv4 del kernel de Linux es un LC-trie cuya búsqueda, según describe su documentación, retrocede a través del trie para encontrar el prefijo coincidente más largo para una dirección de destino.

Por qué importa

Dos operaciones resultan incómodas con tablas hash: "toda clave que empieza por X" y "la clave almacenada más larga que es prefijo de X". Los tries convierten la primera en un recorrido de subárbol y la segunda en un único descenso que recuerda el último nodo terminal por el que se pasó. El autocompletado, los enrutadores de rutas HTTP, la coincidencia del prefijo más largo en IP, los tokenizadores y las listas de bloqueo se reducen todos a una de las dos.

Cómo aplicarlo

• Fijar primero el alfabeto: los bytes son lo más simple; para texto, normalizar (NFC de Unicode, plegado de mayúsculas/minúsculas) de forma idéntica al insertar y al buscar, y decidir si los nodos son puntos de código o bytes UTF-8.
• Elegir la disposición de los nodos según la densidad del alfabeto: un arreglo de hijos para alfabetos pequeños y densos, un pequeño arreglo ordenado o un mapa hash para alfabetos dispersos, compresión radix cuando las claves comparten tramos largos.
• Autocompletado: descender hasta el nodo del prefijo y luego recorrer con un límite de resultados; almacenar conteos por nodo o un top-k en caché para responder "las terminaciones más frecuentes" sin recorrer todo el subárbol.
• Coincidencia del prefijo más largo: recorrer la consulta, registrar el nodo terminal más profundo visto, y devolverlo cuando el recorrido termine o falle.
• Antes de construir uno, probar con un arreglo ordenado: bisect_left sobre el prefijo seguido de un barrido mientras las entradas sigan empezando por él resuelve el autocompletado sobre datos estáticos con mucha menos memoria. Un trie se amortiza con actualizaciones frecuentes, consultas de prefijo más largo o prefijos compartidos muy largos.

Trampas

Los nodos ingenuos con 256 punteros cuestan kilobytes cada uno; la memoria, no la velocidad, suele ser el problema. La eliminación debe podar los nodos no terminales que quedan sin hijos. Los desajustes de normalización hacen invisibles a las claves. El recorrido recursivo sobre claves largas puede agotar la pila. Los tries no responden consultas de infijo, sufijo o difusas; esas necesitan otros índices.