Trie

Código en:JavaC#PythonJavaScript

En resumen: Un trie es un árbol de letras donde el comienzo común de las palabras se guarda una sola vez, así que una búsqueda por prefijo (autocompletado) cuesta tanto como la longitud del prefijo.

Problema

El cuadro de búsqueda

La tienda tiene 200 000 productos. Un cliente escribe «co» en el cuadro de búsqueda, y debajo deben aparecer sugerencias: «cola», «coco», «cojín». Con cada letra nueva, las sugerencias cambian.

La primera solución recorre todos los nombres y comprueba cuáles empiezan por lo escrito. Eso es una búsqueda lineal: 200 000 comprobaciones por cada tecla pulsada. Mil clientes escribiendo a la vez hacen cientos de millones de comprobaciones por segundo.

Y la mayoría de los nombres ni siquiera empiezan por «c». ¿Para qué mirarlos?

La idea

Un árbol de letras

Dibuja los nombres como caminos. Desde la raíz salen ramas según la primera letra, de cada una según la segunda, y así sucesivamente. «cola», «cojín» y «coco» empiezan por «co»: esas dos letras se guardan una sola vez, y las ramas se separan solo después.

Este árbol es un trie (de retrieval, que casi siempre se lee como «trai»). Cada nodo guarda:

• sus hijos, por letra: una colección letra → nodo;
• una marca de que aquí termina un nombre. Un nombre puede terminar dentro de otro: «cola» y «colador».

Una búsqueda por prefijo tiene dos partes:

1. Bajar por las letras del prefijo, un paso por letra. Si falta una letra, no hay tales productos.
2. Recolectar: recorrer la rama bajo el último nodo. Cada nodo con la marca «aquí termina un nombre» es una sugerencia.

Bajar cuesta tanto como las letras del prefijo, no como los productos.

Míralo

Insertar y buscar por prefijo

SortedDictionary mantiene los hijos ordenados por letra, así que las sugerencias salen en orden alfabético.

class Node
{
    public readonly SortedDictionary<char, Node> Kids = [];
    public bool End;
    public int Count;
}

class Trie
{
    private readonly Node root = new();

    public void Insert(string name, int count)
    {
        Node at = root;
        foreach (char ch in name)
        {
            if (!at.Kids.TryGetValue(ch, out Node? next))
            {
                next = new Node();
                at.Kids[ch] = next;
            }
            at = next;
        }
        at.End = true;
        at.Count = count;
    }

    public List<string> Complete(string prefix)
    {
        Node? at = root;
        foreach (char ch in prefix)
        {
            if (!at.Kids.TryGetValue(ch, out at)) return [];
        }
        var found = new List<string>();
        Collect(at, prefix, found);
        return found;
    }

    private void Collect(Node at, string word,
        List<string> found)
    {
        if (at.End) found.Add(word);
        foreach (var (ch, kid) in at.Kids)
        {
            Collect(kid, word + ch, found);
        }
    }
}

Recolectar es recursión, como en la lección «Recursión»: cada nodo recoge sus nombres y se lo pide a sus hijos. El caso base es un nodo sin hijos.

Cuatro productos y tres búsquedas:

var trie = new Trie();
trie.Insert("cola", 120);
trie.Insert("cojín", 15);
trie.Insert("coco", 40);
trie.Insert("té", 60);
Console.WriteLine("co: [" + string.Join(", ", trie.Complete("co")) + "]");
Console.WriteLine("col: [" + string.Join(", ", trie.Complete("col")) + "]");
Console.WriteLine("m: [" + string.Join(", ", trie.Complete("m")) + "]");

Salida

co: [coco, cojín, cola]
col: [cola]
m: []

class Node
{
    public readonly SortedDictionary<char, Node> Kids = [];
    public bool End;
    public int Count;
}

class Trie
{
    private readonly Node root = new();

    public void Insert(string name, int count)
    {
        Node at = root;
        foreach (char ch in name)
        {
            if (!at.Kids.TryGetValue(ch, out Node? next))
            {
                next = new Node();
                at.Kids[ch] = next;
            }
            at = next;
        }
        at.End = true;
        at.Count = count;
    }

    public List<string> Complete(string prefix)
    {
        Node? at = root;
        foreach (char ch in prefix)
        {
            if (!at.Kids.TryGetValue(ch, out at)) return [];
        }
        var found = new List<string>();
        Collect(at, prefix, found);
        return found;
    }

    private void Collect(Node at, string word,
        List<string> found)
    {
        if (at.End) found.Add(word);
        foreach (var (ch, kid) in at.Kids)
        {
            Collect(kid, word + ch, found);
        }
    }
}

Paso a paso, en palabras

1. Un trie vacío: solo la raíz. Cada paso hacia abajo es una letra, así que un camino desde la raíz deletrea un nombre.
2. Insert(«cola»): todavía no hay letras, así que cada paso crea un nodo nuevo. El último se vuelve verde: aquí termina un nombre.
3. «cojín» empieza como «cola»: las dos primeras letras ya existen y solo se pasa por ellas. Hay nodos nuevos solo donde los nombres se separan.
4. «coco» también comparte el comienzo, y «té» abre su propia rama desde la raíz. Cuatro nombres, un comienzo común.
5. Complete(«co»): dos pasos hacia abajo, uno por cada letra del prefijo. Esa es toda la búsqueda, sin importar cuántos productos haya.
6. Recolección: solo se recorre la rama bajo el prefijo, con los hijos en orden alfabético. Cada nodo verde es un nombre y va a la lista.
7. Tres sugerencias: coco, cojín, cola. «té» ni siquiera se miró: su rama no está bajo el prefijo.

«té» nunca se mira: su rama no está bajo «co».

Pruébalo

Predice la salida

Tres productos. Un nombre es el comienzo de otro:

var trie = new Trie();
trie.Insert("cola", 1);
trie.Insert("cordón", 1);
trie.Insert("colador", 1);
Console.WriteLine("col: [" + string.Join(", ", trie.Complete("col")) + "]");

Respuesta

col: [cola, colador]

col: [colador]

col: [cola, colador, cordón]

Comprobar

Pruébalo

Completa

¿Qué convierte a un nodo en una sugerencia al recolectar?

if (at.) found.Add(word);

Comprobar

La idea

Lo que cuesta

• Insertar: un paso por letra del nombre: O(m), donde m es su longitud.
• Bajar por un prefijo: un paso por letra del prefijo: O(m), sin importar cuántos productos haya.
• Recolectar: tan grande como la rama bajo el prefijo. Si muestras solo las 5 primeras sugerencias, te detienes después de la quinta.

Ejecuta los tres modos. El catálogo son n nombres de 4 a 8 letras, en orden alfabético. El cliente escribe 20 prefijos de dos letras, y para cada uno hacen falta los 5 primeros nombres. Se cuentan los caracteres que mira la búsqueda: la comparación de una letra del nombre con una letra del prefijo o un paso de un nodo a un hijo. El trie se construye una vez, al cargar el catálogo, y no se cuenta.

• Recorrer todos los nombres O(n)
• Búsqueda binaria en el catálogo ordenado O(log n)
• Trie O(1)

Algoritmo	n = 10	n = 1000	n = 10.000	n = 100.000
Recorrer todos los nombres	223	11.778	93.071	1.303.482
Búsqueda binaria en el catálogo ordenado	125	542	676	808
Trie	46	403	342	266

El código se ejecuta en tu navegador, en JavaScript. La cantidad de operaciones es la misma en todos los lenguajes, porque el algoritmo es el mismo. El tiempo depende de la máquina, así que solo sirve para comparar. «≈» es una estimación a partir de la curva: un n tan grande no lo ejecutamos, para que la página no se congele.

class Node
{
    public readonly SortedDictionary<char, Node> Kids = [];
    public bool End;
    public int Count;
}

class Trie
{
    private readonly Node root = new();

    public void Insert(string name, int count)
    {
        Node at = root;
        foreach (char ch in name)
        {
            if (!at.Kids.TryGetValue(ch, out Node? next))
            {
                next = new Node();
                at.Kids[ch] = next;
            }
            at = next;
        }
        at.End = true;
        at.Count = count;
    }

    public List<string> Complete(string prefix)
    {
        Node? at = root;
        foreach (char ch in prefix)
        {
            if (!at.Kids.TryGetValue(ch, out at)) return [];
        }
        var found = new List<string>();
        Collect(at, prefix, found);
        return found;
    }

    private void Collect(Node at, string word,
        List<string> found)
    {
        if (at.End) found.Add(word);
        foreach (var (ch, kid) in at.Kids)
        {
            Collect(kid, word + ch, found);
        }
    }
}

Con 100 000 nombres, el recorrido mira 1 303 482 caracteres, la búsqueda binaria en el catálogo ordenado 808 y el trie 266. Cuantos más nombres, más denso es el árbol y antes se recogen los cinco: con 1000 nombres el trie mira 403 caracteres, con 100 000 menos.

La búsqueda binaria está aquí porque el catálogo está ordenado: entonces encuentra el primer nombre con el prefijo en log₂ n comparaciones (búsqueda binaria). Más sobre eso abajo.

Míralo

Lo más comprado primero

El orden alfabético no es el más útil. Si un cliente escribe «co», es más probable que busque cola que cojín. Por eso cada nodo donde termina un nombre guarda también cuántas veces se compró el producto (count). Las sugerencias se ordenan por eso:

public int CountOf(string name)
{
    Node at = root;
    foreach (char ch in name) at = at.Kids[ch];
    return at.Count;
}

public List<string> Suggest(string prefix, int k) =>
    Complete(prefix).OrderByDescending(CountOf).Take(k).ToList();

var trie = new Trie();
trie.Insert("cola", 120);
trie.Insert("cojín", 15);
trie.Insert("coco", 40);
trie.Insert("té", 60);
trie.Insert("colador", 8);
trie.Insert("cordón", 25);
Console.WriteLine("co: [" + string.Join(", ", trie.Suggest("co", 3)) + "]");

Salida

co: [cola, coco, cordón]

La ordenación es estable (mira la estabilidad): con el mismo número de compras se mantiene el orden alfabético.

Más precisamente, para curiosos

Aquí cada búsqueda recoge todos los nombres bajo el prefijo y luego los ordena. Para «c» en un catálogo real son decenas de miles. Por eso los grandes buscadores guardan, en cada nodo, las 5 a 10 primeras sugerencias ya listas para la rama de debajo. La búsqueda se reduce a bajar, y el precio se paga al insertar: cada nodo del camino de un nombre nuevo comprueba si entra entre sus mejores.

Pruébalo

Encuentra el error

Un compañero escribió la recolección, pero las sugerencias están llenas de trozos de palabras:

private void Collect(Node at, string word, List<string> found)
{
    found.Add(word);
    foreach (var (ch, kid) in at.Kids)
    {
        Collect(kid, word + ch, found);
    }
}

var trie = new Trie();
trie.Insert("cola", 120);
trie.Insert("cojín", 15);
trie.Insert("coco", 40);
trie.Insert("té", 60);
Console.WriteLine("co: [" + string.Join(", ", trie.Complete("co")) + "]");

Salida

co: [co, coc, coco, coj, cojí, cojín, col, cola]

¿En qué línea está el error?

Elige la línea con el error.

1private void Collect(Node at, string word, List<string> found)2{3 found.Add(word);4 foreach (var (ch, kid) in at.Kids)5 {6 Collect(kid, word + ch, found);7 }8}

Comprobar

La idea

Mayúsculas y caracteres que se parecen

Para el trie, «C» y «c» son letras distintas: hijos distintos del nodo. Un cliente que escribe «Cola» o « cola» con un espacio delante no encuentra nada. Por eso tanto el nombre al insertar como el texto al buscar pasan por una misma normalización: sin espacios en los extremos, un espacio entre palabras, minúsculas.

static string Normalize(string text) =>
    string.Join(' ', text.Split(' ', StringSplitOptions.RemoveEmptyEntries))
        .ToLowerInvariant();

var trie = new Trie();
trie.Insert("cola", 120);
trie.Insert("cojín", 15);
trie.Insert("coco", 40);
trie.Insert("té", 60);
trie.Insert("colador", 8);
trie.Insert("cordón", 25);
trie.Insert("café", 30);
Console.WriteLine("CoLa: [" + string.Join(", ", trie.Complete(Normalize("  CoLa "))) + "]");
Console.WriteLine("cafe: [" + string.Join(", ", trie.Complete(Normalize("cafe"))) + "]");

Salida

CoLa: [cola, colador]
cafe: []

La segunda búsqueda no encuentra nada, aunque el catálogo tiene «café». «e» y «é» son caracteres distintos, hijos distintos en el árbol. Lo mismo pasa con letras que se ven exactamente iguales: la «a» latina y la letra cirílica que se ve idéntica, en una tienda que vende en dos alfabetos. La normalización no lo arregla por sí sola: hace falta una sustitución explícita (por ejemplo, quitar las tildes) si quieres perdonarlo.

Más precisamente, para curiosos

ToLowerInvariant() da la misma regla en cualquier máquina. ToLower() usa el idioma de la máquina, y en una turca «I» pasa a «ı» (i sin punto). Una cosa más: char en C# es de 16 bits. Las letras latinas y cirílicas caben en un char, pero un emoji ocupa dos, y un trie por char lo parte por la mitad.

Cómo es en los otros lenguajes: Java y C# recorren por char de 16 bits, Python y for…of en JavaScript por caracteres. Para las letras latinas y cirílicas no hay diferencia.

La idea

Memoria, y cuándo basta un arreglo ordenado

Cada nodo guarda sus hijos. Hay dos maneras:

• Una colección letra → nodo, como aquí: el nodo guarda solo los hijos que tiene.
• Un arreglo de casillas, una por letra: 26 para el alfabeto latino, unas 30 para el español con la ñ y las vocales con tilde, 32 con espacio y guion. El hijo se encuentra enseguida por el número de la letra, pero cada nodo guarda todas las casillas, también las vacías.

¿Cuántas están vacías? El trie del Bench para 100 000 nombres (631 833 letras) tiene 210 642 nodos, en promedio un hijo por nodo: el comienzo común es corto y luego cada nombre sigue por su cuenta. Un arreglo de 30 casillas por nodo guarda más de 6,3 millones de referencias, de las que están ocupadas 210 641. La colección es más pequeña, y el arreglo es más rápido solo en los niveles de arriba, donde los hijos son muchos.

Si los nombres cambian poco y solo necesitas «todos los que empiezan por …», un arreglo ordenado suele bastar. La búsqueda binaria encuentra el primer nombre que no va antes del prefijo, y las coincidencias quedan juntas después de él:

List<string> names = ["coco", "cojín", "cola", "colador", "cordón", "té"];
string prefix = "co";
int at = names.BinarySearch(prefix, StringComparer.Ordinal);
if (at < 0) at = ~at;
var found = new List<string>();
while (at < names.Count && names[at].StartsWith(prefix, StringComparison.Ordinal))
{
    found.Add(names[at++]);
}
Console.WriteLine($"{prefix}: [{string.Join(", ", found)}]");

Salida

co: [coco, cojín, cola, colador, cordón]

Cuidado: la comparación de strings por defecto en C# depende del idioma de la máquina. La ordenación y BinarySearch deben usar una misma regla, aquí StringComparer.Ordinal (por código de carácter). Un resultado negativo es ~ del punto de inserción.

Un trie gana cuando los nombres se añaden y se quitan todo el tiempo, cuando necesitas contadores y lo más comprado para cada prefijo, o cuando buscas letra por letra mientras el cliente escribe: cada letra nueva es un paso desde el nodo que ya alcanzaste.

Ejercicio

Cuántos productos empiezan por…

Resuelve la tarea en tu editor.

El conteo bajo un prefijo. Junto a cada sugerencia el cuadro muestra cuántos productos empiezan por lo escrito. Añade al nodo un contador de cuántos nombres pasan por él, y un método CountPrefix que baja por el prefijo y devuelve el contador, sin recoger nombres. Inserta todo el catálogo de la tarjeta «Lo más comprado primero» y comprueba los prefijos «co», «col», «t» y «m»:

Salida

co: 5
col: 2
t: 1
m: 0

Más tareas

• Borrar. Un producto deja de venderse. Quita el nombre del trie sin romper los nombres que pasan por los mismos nodos.
• Número de nodos. Cuenta los nodos después de insertar el catálogo y compáralos con el total de letras de los nombres.
• Letra por letra. Haz una búsqueda que conserve el nodo alcanzado y, por cada letra nueva, dé solo un paso.

Test

Ponte a prueba

1. El catálogo tiene 200 000 productos. ¿Cuántos pasos da el trie para llegar al nodo del prefijo «cola»?

4: uno por letraUnos 18: log₂ de 200 000200 000: uno por producto

2. ¿Por qué un nodo tiene una marca aparte «aquí termina un nombre»?

Porque un nombre puede terminar dentro del camino de otro: «cola» es el comienzo de «colador»Para que bajar sea más rápidoPorque las hojas no tienen hijos

3. Los nombres de los productos cambian una vez al día, y solo necesitas «todos los que empiezan por …». ¿Qué basta?

Un trie, pase lo que paseUn arreglo ordenado y una búsqueda binaria del primer nombre con el prefijoRecorrer todos los nombres

4. El cliente escribe «Cola», y el catálogo tiene «cola». ¿Qué haces?

Nada: la búsqueda ignora las mayúsculasGuardar cada producto dos vecesNormalizar ambos: minúsculas y sin espacios de más, tanto al insertar como al buscar

Comprobar

Empezar la lección de nuevo

Lecciones relacionadas

• Se basa en: Complejidad en espacio · Búsqueda lineal · Búsqueda binaria · Ordenamiento estable y el ordenamiento incorporado
• Continúa en: Reconocer un problema de DP
• Ejercicios sobre el tema: Estructuras de datos