Tries y árboles de prefijos

Qué cubre este capítulo

Todos los árboles que hemos visto hasta ahora se organizan por valores completos: un nodo guarda un número y tú comparas contra él. Un trie tira eso a la basura y se organiza por los caracteres de las cadenas: cada arista es una sola letra, cada camino desde la raíz deletrea un prefijo, y las palabras que comparten prefijo comparten la misma rama. Esa reorganización vuelve casi gratis una operación —"¿existe alguna palabra que empiece con estas letras?"— que se responde bajando por las letras, sin importar cuántas palabras tengas guardadas. Es la estructura detrás del autocompletado, los correctores ortográficos y las tablas de ruteo IP, y su costo se mide en la longitud de la llave, no en el tamaño del diccionario. En este capítulo lo construimos, vemos cómo las palabras van formando un árbol compartido y cómo deja muy atrás a una búsqueda ingenua.

Un poco de historia

El trie se inventó al arrancar los años sesenta, y hasta su nombre es un pequeño acertijo. René de la Briandais describió la estructura en 1959, y Edward Fredkin la bautizó en 1960, sacando "trie" de en medio de "retrieval" (recuperación) — por eso los puristas lo pronuncian "tree" y todos los demás dicen "try" para no confundirlo con "árbol". La idea de Fredkin fue que, para recuperar cadenas, no deberías comparar llaves completas en absoluto: deberías ramificar un carácter a la vez, de modo que los prefijos comunes no cuesten nada extra. Esa idea terminó siendo fundamental para el procesamiento de texto: los tries y sus variantes comprimidas están debajo de los correctores ortográficos, el autocompletado, las tablas de ruteo que reenvían cada paquete de internet por el prefijo IP más largo que coincide, y los tokenizadores dentro de buscadores y compiladores. Sesenta años después, cada vez que el software tiene que responder preguntas sobre los prefijos de un conjunto grande de cadenas, un trie es la respuesta clásica.

La intuición

Imagina archivar palabras no alfabéticamente en una lista, sino recorriendo un camino que se ramifica: para guardar "card" bajas por la rama c, luego a, luego r, luego d, creando esos pasos si no existen. Ahora guarda "care" — el camino c-a-r ya existe, así que lo reutilizas y solo agregas la e final. El prefijo compartido "car" se guarda exactamente una vez, y las dos palabras se separan solo donde de verdad difieren. Haz esto con un diccionario completo y obtienes un árbol donde cada nodo interno es un prefijo compartido y cada palabra completa queda marcada en el nodo donde termina.

Esa estructura vuelve triviales las preguntas sobre prefijos. Para preguntar "¿alguna palabra empieza con 'car'?" nada más recorres c-a-r y ves si el camino existe — nunca miras una sola palabra guardada, y el costo son tres pasos ya sea que el diccionario tenga diez palabras o diez millones. Para autocompletar "car" caminas hasta ese nodo y luego juntas cada fin de palabra en el subárbol de abajo, visitando únicamente las palabras que sí coinciden. Y buscar una palabra exacta es el mismo recorrido, con una sutileza: llegar al final del camino no basta — el nodo final debe estar marcado como palabra, porque tener "car" guardada también te da el camino para "ca", aunque "ca" quizá no sea una palabra. La marca es lo que distingue una palabra guardada de un simple prefijo de otra.

Complejidad: cómo escala

insert, search y starts_with son todas $O(L)$ en la longitud de la llave — das un paso por carácter. El autocompletado bajo un prefijo es $O(L + m)$, donde m es el tamaño total de las palabras que coinciden, porque después del recorrido O(L) hasta el nodo del prefijo visita exactamente las coincidencias y nada más. Ninguna de estas depende de N, el número de palabras, y ese es el titular. El espacio es el punto débil del trie: guarda un nodo por cada carácter de prefijo distinto, con un mapa de hijos por nodo, así que un trie puede usar más memoria que una simple lista de palabras — aunque los prefijos compartidos recuperan buena parte de eso. La gráfica corre consultas por prefijo contra diccionarios de tamaño creciente:

La línea del scan sube con el tamaño del diccionario — vuelve a leer cada palabra en cada consulta, O(N·L) — mientras que la línea del trie se mantiene comparativamente plana, porque cada consulta solo recorre su propio prefijo. Con 320000 palabras el trie respondió 500 consultas por prefijo unas 8 veces más rápido que el scan, y la brecha se abre conforme crece N, justo como predice O(L) contra O(N·L).

En qué es bueno y en qué no

El trie es la estructura correcta cuando tus preguntas son sobre prefijos de cadenas. Autocompletado, "todas las palabras que empiezan con", sugerencias de corrector ortográfico, coincidencia del prefijo más largo para ruteo IP, y búsquedas en diccionarios donde quieres fallar rápido ante prefijos imposibles — todo eso es lo que el trie vuelve barato y una tabla hash simplemente no puede hacer. Además mantiene sus llaves ordenadas gratis (un recorrido en preorden las entrega alfabéticamente) y puede comprimir muchísimo cuando muchas llaves comparten prefijos.

Donde es la herramienta equivocada es en la pura membresía. Si lo único que preguntas es "¿está presente esta palabra exacta?", un hash set responde también en O(L) — lo que tarda en hashear la llave — y usa muchísima menos memoria que el bosque de nodos y mapas de hijos de un trie. Los tries también sufren con alfabetos grandes (un mapa de hijos de Unicode completo por nodo pesa mucho) y con llaves que comparten pocos prefijos, donde el árbol es casi puro ramaje y muy poco compartido. El trie se gana su memoria solo cuando la pregunta son los prefijos y el compartir es real; si no, un hash set es más ligero.

Los datos, o las entradas

El enfrentamiento arma diccionarios de palabras aleatorias sobre un alfabeto pequeño (para que los prefijos se compartan de verdad) y mide consultas por prefijo conforme crece el diccionario, para aislar la independencia del trie respecto a N. La animación inserta siete palabras escogidas a mano — cat, car, card, care, dog, do, dot — para que veas cómo se ramifican los prefijos compartidos y cómo se encienden los finales de palabra.

Constrúyelo, una función a la vez

insert recorre los caracteres, creando nodos según hace falta, y marca el final:

def insert(self, word):
    """O(L) for a word of length L: walk down one character at a time, creating
    child nodes where the path doesn't exist yet. Words sharing a prefix reuse the
    same nodes — 'car' and 'card' share the first three."""
    node = self.root
    for ch in word:
        if ch not in node.children:
            node.children[ch] = TrieNode()
        node = node.children[ch]
    if not node.is_word:
        node.is_word = True
        self._n += 1

search es el mismo recorrido, con la verificación crucial de que el nodo final esté marcado como palabra:

def search(self, word):
    """O(L): follow the characters. The word is present only if the whole path
    exists AND its final node is marked a word-end — 'car' being stored doesn't
    mean 'ca' is a word, even though its path exists."""
    node = self._find(word)
    return node is not None and node.is_word

starts_with es el superpoder del trie: solo hay que revisar que el camino del prefijo exista:

def starts_with(self, prefix):
    """O(L): the trie's superpower. Is there ANY word with this prefix? Just check
    whether the path exists — you never look at the words themselves."""
    return self._find(prefix) is not None

def _find(self, s):
    node = self.root
    for ch in s:
        if ch not in node.children:
            return None
        node = node.children[ch]
    return node

Y el autocompletado camina hasta el prefijo y luego junta cada palabra debajo de él:

def words_with_prefix(self, prefix):
    """Autocomplete: walk to the prefix node, then collect every word-end below it.
    O(L + size of the subtree) — it visits only words that actually match, never the
    rest of the dictionary."""
    node = self._find(prefix)
    out = []
    if node is None:
        return out

    def dfs(n, suffix):
        if n.is_word:
            out.append(prefix + suffix)
        for ch, child in sorted(n.children.items()):
            dfs(child, suffix + ch)

    dfs(node, "")
    return out

Míralo funcionar

Aquí hay un trie construido con siete palabras. La raíz (•) se ramifica por la primera letra; los nodos verdes marcan dónde termina una palabra completa; el naranja resalta el camino que se acaba de insertar. Ve paso a paso y observa cómo ocurre el compartir: "cat" traza c-a-t, luego "car" reutiliza c-a y solo agrega la r, y después "card" y "care" reutilizan c-a-r y se ramifican en la última letra. Del otro lado, "do" es una palabra y además un prefijo de "dog" y "dot", así que su nodo es a la vez verde (una palabra) y un punto de ramificación. Los prefijos compartidos se guardan exactamente una vez — ese compartir es toda la estructura:

El código completo

Las dos versiones en un solo lugar; cambia entre ellas. La pestaña desde cero es el trie. La pestaña de librería es la alternativa ingenua — recorrer la lista de palabras buscando un prefijo, más un set para la membresía — porque Python no trae un trie integrado (el paquete de terceros pygtrie llena ese hueco, y un trie es en el fondo nada más diccionarios anidados).

"""The trie (prefix tree) — a tree keyed by the characters of strings rather than by
whole values. Each edge is one character, each root-to-node path spells a prefix, and
words that share a prefix share the same branch, so the prefix is stored once.

That layout makes the trie's signature operation — "is there any word starting with
this prefix?" — an O(L) walk down L characters, independent of how many words are
stored. It's the structure behind autocomplete, spell-checkers, and IP routing tables,
and its cost is measured in the length of the key, not the size of the dictionary.
"""


class TrieNode:
    __slots__ = ("children", "is_word")

    def __init__(self):
        self.children = {}       # char -> TrieNode
        self.is_word = False     # does a word END here (vs. just passing through)?


class Trie:
    def __init__(self):
        self.root = TrieNode()
        self._n = 0

    # region: insert
    def insert(self, word):
        """O(L) for a word of length L: walk down one character at a time, creating
        child nodes where the path doesn't exist yet. Words sharing a prefix reuse the
        same nodes — 'car' and 'card' share the first three."""
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        if not node.is_word:
            node.is_word = True
            self._n += 1
    # endregion

    # region: search
    def search(self, word):
        """O(L): follow the characters. The word is present only if the whole path
        exists AND its final node is marked a word-end — 'car' being stored doesn't
        mean 'ca' is a word, even though its path exists."""
        node = self._find(word)
        return node is not None and node.is_word
    # endregion

    # region: starts_with
    def starts_with(self, prefix):
        """O(L): the trie's superpower. Is there ANY word with this prefix? Just check
        whether the path exists — you never look at the words themselves."""
        return self._find(prefix) is not None

    def _find(self, s):
        node = self.root
        for ch in s:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node
    # endregion

    # region: words_with_prefix
    def words_with_prefix(self, prefix):
        """Autocomplete: walk to the prefix node, then collect every word-end below it.
        O(L + size of the subtree) — it visits only words that actually match, never the
        rest of the dictionary."""
        node = self._find(prefix)
        out = []
        if node is None:
            return out

        def dfs(n, suffix):
            if n.is_word:
                out.append(prefix + suffix)
            for ch, child in sorted(n.children.items()):
                dfs(child, suffix + ch)

        dfs(node, "")
        return out
    # endregion

    def __len__(self):
        return self._n

"""Python has no built-in trie; the third-party `pygtrie` is the ready-made option, and
a trie is really just nested dicts (`dict` of `dict` of …), which is how you'd hand-roll
one. The instructive counterpart, though, is the NAIVE way to answer a prefix query
without a trie: scan the whole word list and keep the ones that start with the prefix.
That's O(N·L) per query, against the trie's O(L + matches) — and the face-off shows the
trie pulling away as the dictionary grows.
"""


# region: scan_prefix
def words_with_prefix_scan(words, prefix):
    """The naive prefix query: check every word in the dictionary — O(N·L) per query,
    where a trie is O(L + number of matches) and never touches the non-matching words."""
    return sorted(w for w in words if w.startswith(prefix))
# endregion


# region: set_membership
def contains_scan(word_set, word):
    """Membership via a set — O(L) to hash the word, like the trie's search, but a set
    can't answer prefix queries at all without scanning."""
    return word in word_set
# endregion

Desde cero vs librería

Este enfrentamiento no es Python contra C: es la estructura de datos correcta contra la equivocada, y el trie gana volviéndose más rápido en relación con la alternativa conforme crece el problema. Con 320000 palabras respondió las consultas por prefijo 8× más rápido que el scan, y ese múltiplo sigue subiendo con el diccionario, porque el scan es O(N·L) por consulta mientras que el trie es O(L). Esta es la lección con la que abrió el capítulo de complejidad, en su forma más clara: la constante del scan es diminuta (un str.startswith en C dentro de una comprehension) y aun así pierde de manera contundente, porque una peor clase de complejidad no se salva con una mejor constante una vez que N es lo bastante grande. Elige la estructura cuyo costo no crece con lo que sí crece —aquí, el diccionario— y ganas sin importar qué tan bien afinada esté la alternativa.

Dónde te lo vas a encontrar de verdad

Los tries mueven todas las funciones de prefijo que usas. El autocompletado de tu barra de búsqueda, tu editor y tu shell recorre un trie de posibles terminaciones. Los correctores ortográficos guardan sus diccionarios como tries para sugerir correcciones por prefijo. Cada router de internet reenvía paquetes por coincidencia del prefijo más largo sobre un trie comprimido de rangos de direcciones IP — probablemente el trie más crítico en desempeño del mundo. Los compiladores y los buscadores tokenizan texto contra tries de palabras clave y términos. La bioinformática indexa genomas con tries (y con su primo, el suffix tree, dos capítulos más adelante). Y el texto predictivo T9 de los teléfonos viejos, y los teclados de deslizar de los nuevos, por debajo son tries. Cada vez que la pregunta es sobre los inicios de las cadenas, esta es la estructura.

Puntos clave

Un trie organiza las cadenas por sus caracteres, compartiendo prefijos comunes en ramas compartidas, así que insert, search y las consultas por prefijo cuestan todas $O(L)$ en la longitud de la llave y son independientes del tamaño N del diccionario — que es justo lo que vuelve prácticamente gratis el autocompletado y el "¿alguna palabra con este prefijo?". Lo paga con memoria (un nodo por carácter), que las variantes comprimidas como los radix trees recuperan, y solo vale la pena cuando los prefijos son de verdad tu pregunta; para pura membresía, un hash set es más ligero.

El trie es la primera de las estructuras especializadas del bloque de árboles: un árbol moldeado para un tipo de consulta. Los siguientes dos capítulos continúan ese tema con árboles construidos para consultas de rango sobre arrays: el segment tree y el Fenwick tree, que responden "¿cuál es la suma (o el mínimo, o el máximo) de este rango?" y "actualiza este elemento" ambas en O(log n), donde un array simple te obliga a elegir entre consultas rápidas o actualizaciones rápidas.