Trie construido con las palabras

Trie – arbol de prefijos

El trie (también conocido como árbol de prefijos) es una estructura de datos muy útil para resolver problemas asociados con strings. El problema mas conocido es dado una colección de palabras (algo como un diccionario) y una palabra en particular, saber si la palabra se encuentra en la colección de palabras.

Una primera solución podría ser comparar la palabra buscada a cada palabra, pero esta solucion es O(n) ya que se necesitarían al menos n comparaciones donde n es  la cantidad de palabras en la colección. Cuando tenemos demasiadas palabras, esta solución es extremadamente lenta. Otra posible solución podría ser ordenar todas las palabras alfabéticamente  y luego usar búsqueda binaria para encontrar la palabra. Esta solución es mejor, pero tiene la desventaja de que cada vez que introducimos una nueva palabra hay que reordenar la colección completa, lo que es O(n log n).

El trie resuelve este problema eficientemente, ya que tanto agregar como buscar una palabra es O(|s|) donde |s| es la cantidad de caracteres de la palabra s. Esta estructura fue introducida por por Rene de la Briandais y Edward Fredking en 1959. El nombre proviene de la palabra RETRIEVAL, que significa recuperación. Internamente, funciona como un árbol ordenado, donde cada nodo representa un carácter de una palabra insertada en el trie, y los nodos hijos de este son caracteres que aparecen después de el en la palabra. La raíz del árbol es el caracter vacío, ya que se puede considerar que este aparece al principio de cualquier palabra.

El trie también es conocido como árbol de prefijos porque al insertar una palabra en el árbol  se busca primero el mayor prefijo de esa palabra que ya este presente en el árbol, y a partir de ahí se continua insertando hasta donde termine la palabra. La figura a continuación muestra un trie construido con las palabras algo, ala, abeja, y trie.

Trie construido con las palabras
Trie construido con las palabras. Los nodos terminales están resaltados.

Construyendo el trie

Para construir el trie, necesitamos almacenar en cada nodo lo siguiente:

  • Letra que representa
  • Si es o no la ultima letra de alguna palabra
  • Nodo padre
  • Nodos hijos

Adicionalmente, cada nodo implementa un método para saber si un nodo dado es hijo de ese nodo, y para agregar un nuevo hijo. Usando estos métodos se encuentra el mayor prefijo que ya este en el árbol hasta llegar a un nodo hoja, y se comienza a insertar a partir de ahí.

class Node
{
    char content;
    boolean ends;
    Node parent;
    Node[] child = new Node[26];

    public Node(char c, Node pi)
    {
        parent = pi; content = c;
    }

    public Node getChild(char c) { return child[c-'a']; }

    public Node addChild(Node node) { child[node.content - 'a'] = node; }
}

En la linea 6 inicializamos el arreglo en 26 ya que ese es el tamaño del alfabeto ingles. Para un alfabeto mayor, hay que incrementar el tamaño del arreglo. El método getChild retornara el nodo hijo que contiene el caracter c, o null si no hay ninguno. Con esto podemos crear un trie cuya raíz sera el caracter vacío.

class Trie
{
    Node root = new Node('\0', null);

    public void insert(String word) { }

    public boolean search(String word) { }
}

Insertar en el trie

El algoritmo para insertar una palabra en el trie es comenzar en la raíz  y moverse por el árbol buscando el caracter siguiente en la palabra. Mientras se encuentre el caracter, actualizamos la posición en el árbol  Cuando no se encuentre, insertamos a partir de esa posición  Al llegar al final de la palabra, marcamos la posición en que estamos como terminal.

class Trie
{
    Node root = new Node('\0', null);

    public void insert(String word)
    {
        Node current = root;
        for(int i=0; i < word.length(); i++)
        {
            char c = word.charAt(i);
            Node sub = current.getChild(c);
            if (sub != null) current = sub;
            else
            {
                current.addChild(new Node(c, current));
                current = current.getChild(c);
            }
            if (i == word.length()-1) current.ends = true;
        }
    }

    public boolean search(String word) { }
}

Si insertáramos en el trie original la palabra abel, la secuencia de operaciones seria la siguiente:

  1. Comenzamos en la raíz.
  2. Buscamos el caracter ‘a’. Aparece, por tanto nos movemos en el árbol hasta la ‘a’.
  3. Buscamos ‘b’. Aparece, nos movemos a ‘b’.
  4. Buscamos ‘e’. Aparece, nos movemos a ‘e’.
  5. Buscamos ‘l’. No aparece, insertamos ‘l’ como hijo de ‘e’. Nos movemos a ‘l’.
  6. Fin de la palabra, marcamos ‘l’ como terminal.

La imagen a continuación muestra el trie después de insertar la palabra y la ruta recorrida para insertarla.

Despues de insertar la palabra. Los nodos sombreados representan el camino.

Buscar en el trie

Buscar en el trie es similar a la operación de insertar. Comenzamos en la raíz y vamos buscando cada caracter de la palabra y actualizando la posición en el árbol  Si en algún momento no encontramos un caracter, es porque la palabra no fue insertada. Similarmente, si el ultimo caracter no esta marcado como terminal, es porque esta palabra no aparece en el trie, sino aparece una palabra mayor que contiene a esta palabra como prefijo.

class Trie
{
    Node root = new Node('\0', null);

    public void insert(String word)
    {
        Node current = root;
        for(int i=0; i < word.length(); i++)
        {
            char c = word.charAt(i);
            Node sub = current.getChild(c);
            if (sub != null) current = sub;
            else
            {
                current.addChild(new Node(c, current));
                current = current.getChild(c);
            }
            if (i == word.length()-1) current.ends = true;
        }
    }

    public boolean search(String word)
    {
        Node current = root;
        for(int i=0; i < word.length(); i++)
        {
            char c = word.charAt(i);
            Node sub = current.getChild(c);
            if (sub == null) return false;
        }
        return current.ends;
    }
}

El trie también puede ser usado para ordenar todas las palabras. Luego de insertarlas en el árbol  un recorrido en pre-orden muestra cada palabra en orden ascendente, y en post-orden, en orden descendente.

Felices códigos!

Referencias

es.wikipedia.org/wiki/Trie

community.topcoder.com/tc?module=Static&d1=tutorials&d2=usingTries

Problemas

codeforces.com/problemset/problem/271/D

www.spoj.com/problems/PRHYME/

About these ads

Comentar

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s