Ir al contenido
Ayotl
English

← Estructuras de datos desde cero · Lección 28/32

Trie: el árbol de los prefijos

✕
1/7

Una letra por paso

Un trie (se dice como *try*) guarda palabras repartiendo sus letras en un árbol: cada nodo tiene un Map de hijos, uno por cada letra que puede seguir, y una marca fin que dice «aquí termina una palabra».

Las palabras que empiezan igual comparten camino: «sol», «sopa» y «sopes» pasan por la misma s y la misma o, y se separan después. Por eso el trie es la estructura del autocompletado y de los diccionarios.

leccion.js

$ node leccion.js

Pulsa CORRER (o Ctrl+Enter).

Qué mirar

  • De la raíz sale una sola letra, s: las cuatro palabras empiezan con ella.
  • Después de la s hay dos caminos: o (sol, sopa, sopes) y a (salsa).
  • Después de «so» se separan otra vez: l para «sol» y p para «sopa» y «sopes».

Trie (Wikipedia) ↗

Toda la lección en una página

Una letra por paso

Un trie (se dice como *try*) guarda palabras repartiendo sus letras en un árbol: cada nodo tiene un Map de hijos, uno por cada letra que puede seguir, y una marca fin que dice «aquí termina una palabra».

Las palabras que empiezan igual comparten camino: «sol», «sopa» y «sopes» pasan por la misma s y la misma o, y se separan después. Por eso el trie es la estructura del autocompletado y de los diccionarios.

class NodoTrie {
  constructor() {
    this.hijos = new Map();
    this.fin = false;
  }
}

function insertar(raiz, palabra) {
  let nodo = raiz;
  for (const letra of palabra) {
    if (!nodo.hijos.has(letra)) nodo.hijos.set(letra, new NodoTrie());
    nodo = nodo.hijos.get(letra);
  }
  nodo.fin = true;
}

const raiz = new NodoTrie();
for (const p of ["sol", "sopa", "sopes", "salsa"]) insertar(raiz, p);

console.log([...raiz.hijos.keys()]);
console.log([...raiz.hijos.get("s").hijos.keys()]);
console.log([...raiz.hijos.get("s").hijos.get("o").hijos.keys()]);
  • De la raíz sale una sola letra, s: las cuatro palabras empiezan con ella.
  • Después de la s hay dos caminos: o (sol, sopa, sopes) y a (salsa).
  • Después de «so» se separan otra vez: l para «sol» y p para «sopa» y «sopes».

¿Es palabra o sólo el principio de una?

Buscar es bajar letra por letra. Si en algún punto falta el hijo, la palabra no está. Si llegas al final, todavía falta una pregunta: ¿ese nodo tiene fin? «sop» existe como camino, pero nadie guardó «sop» como palabra.

Lo importante es el costo: bajar cuesta O(largo de la palabra). Da igual si el trie tiene cuatro palabras o cien mil.

class NodoTrie {
  constructor() {
    this.hijos = new Map();
    this.fin = false;
  }
}

function insertar(raiz, palabra) {
  let nodo = raiz;
  for (const letra of palabra) {
    if (!nodo.hijos.has(letra)) nodo.hijos.set(letra, new NodoTrie());
    nodo = nodo.hijos.get(letra);
  }
  nodo.fin = true;
}

function bajar(raiz, texto) {
  let nodo = raiz;
  for (const letra of texto) {
    nodo = nodo.hijos.get(letra);
    if (!nodo) return null;
  }
  return nodo;
}

const existe = (raiz, p) => { const n = bajar(raiz, p); return n !== null && n.fin; };
const empiezaCon = (raiz, pre) => bajar(raiz, pre) !== null;

const raiz = new NodoTrie();
for (const p of ["sol", "sopa", "sopes", "salsa"]) insertar(raiz, p);

console.log(existe(raiz, "sopa"));
console.log(existe(raiz, "sop"));
console.log(empiezaCon(raiz, "sop"));
console.log(existe(raiz, "taco"));
  • «sopa» está: el camino existe y su último nodo tiene fin.
  • «sop» no es palabra (false), pero sí es prefijo (true): el camino existe, la marca no.
  • «taco» se cae en la primera letra: de la raíz no sale ninguna t.

Autocompletar

Para sugerir palabras, primero bajas hasta el nodo del prefijo y desde ahí recorres todo lo que cuelga (un recorrido en profundidad), juntando cada camino que llegue a un fin.

El trabajo depende de cuántas sugerencias hay, no del tamaño del diccionario: lo que no empieza con el prefijo ni se toca.

class NodoTrie {
  constructor() {
    this.hijos = new Map();
    this.fin = false;
  }
}

function insertar(raiz, palabra) {
  let nodo = raiz;
  for (const letra of palabra) {
    if (!nodo.hijos.has(letra)) nodo.hijos.set(letra, new NodoTrie());
    nodo = nodo.hijos.get(letra);
  }
  nodo.fin = true;
}

function bajar(raiz, texto) {
  let nodo = raiz;
  for (const letra of texto) {
    nodo = nodo.hijos.get(letra);
    if (!nodo) return null;
  }
  return nodo;
}

function autocompletar(raiz, prefijo) {
  const res = [];
  function juntar(nodo, camino) {
    if (nodo.fin) res.push(camino);
    for (const [letra, hijo] of nodo.hijos) juntar(hijo, camino + letra);
  }
  const nodo = bajar(raiz, prefijo);
  if (nodo) juntar(nodo, prefijo);
  return res;
}

const raiz = new NodoTrie();
for (const p of ["sol", "sopa", "sopes", "sal", "salsa"]) insertar(raiz, p);

console.log(autocompletar(raiz, "sop"));
console.log(autocompletar(raiz, "sal"));
console.log(autocompletar(raiz, "x"));
  • «sop» sugiere «sopa» y «sopes».
  • «sal» se sugiere a sí misma (su nodo tiene fin) y luego a «salsa», que cuelga de ella.
  • «x» no lleva a ningún nodo: arreglo vacío.