La estructura de datos de Trie: una joya olvidada

Desde los primeros días de nuestra vida como programadores, todos nos hemos ocupado de estructuras de datos: matrices, listas enlazadas, árboles, conjuntos, pilas y colas son nuestros compañeros cotidianos, y el programador experimentado sabe cuándo y por qué usarlos. En este artículo, veremos cómo una estructura de datos a menudo descuidada, el trie , realmente brilla en dominios de aplicaciones con características específicas, como juegos de palabras.

Juegos de palabras como ejemplo Trie

Para empezar, consideremos un rompecabezas de palabras simple: encuentre todas las palabras válidas en un tablero de letras de 4x4, conectando letras adyacentes horizontal, vertical o diagonalmente. Por ejemplo, en el siguiente tablero, vemos las letras 'W', 'A', 'I' y 'T' conectadas para formar la palabra “WAIT”.

La solución ingenua para encontrar todas las palabras válidas sería explorar el tablero comenzando desde la esquina superior izquierda y luego avanzar en profundidad hacia secuencias más largas, comenzando nuevamente desde la segunda letra en la primera fila, y así sucesivamente. En un tablero de 4x4, que permite movimientos verticales, horizontales y diagonales, hay 12029640 secuencias, cuya longitud oscila entre uno y dieciséis caracteres.

Ahora, nuestro objetivo es encontrar la mejor estructura de datos para implementar este verificador de palabras válidas, es decir, nuestro vocabulario. Algunos puntos a tener en cuenta:

• Solo necesitamos una única copia de cada palabra, es decir, nuestro vocabulario es un conjunto, desde un punto de vista lógico.
• Necesitamos responder las siguientes preguntas para cualquier palabra dada:
  • ¿La secuencia de caracteres actual comprende una palabra válida?
  • ¿Hay palabras más largas que comiencen con esta secuencia? Si no, podemos abandonar nuestra exploración de profundidad primero, ya que profundizar no producirá ninguna palabra válida.

Para ilustrar el segundo punto, considere el siguiente tablero: No tiene sentido explorar movimientos posteriores, ya que no hay palabras en el diccionario que comiencen con "ASF".

Nos encantaría que nuestra estructura de datos respondiera estas preguntas lo más rápido posible. ¡El tiempo de acceso ~O(1) (para verificar una secuencia) sería ideal!

Podemos definir la interfaz de Vocabulario de esta manera (ver aquí para el repositorio de GitHub):

 public interface Vocabulary { boolean add(String word); boolean isPrefix(String prefix); boolean contains(String word); }

Trie estructura de datos frente a alternativas

La implementación del método contains() requiere una estructura de datos de respaldo que le permita encontrar elementos de manera eficiente, mientras que el método isPrefix() requiere que encontremos el "próximo elemento mayor", es decir, necesitamos mantener el vocabulario ordenado de alguna manera.

Podemos excluir fácilmente conjuntos basados ​​en hash de nuestra lista de candidatos: mientras que una estructura de este tipo nos daría una verificación en tiempo constante de contains() , funcionaría bastante mal en isPrefix() , en el peor de los casos, requeriría que escaneáramos todo colocar.

Por la razón opuesta, también podemos excluir las listas enlazadas ordenadas, ya que requieren escanear la lista al menos hasta el primer elemento que es mayor o igual que la palabra o el prefijo buscado.

Dos opciones válidas son usar una lista respaldada por una matriz ordenada o un árbol binario.
En la lista ordenada con respaldo de matriz, podemos usar la búsqueda binaria para encontrar la secuencia actual si está presente o el siguiente elemento mayor a un costo de O(log2(n)) , donde n es el número de palabras en el diccionario.

Podemos implementar un vocabulario respaldado por una matriz que siempre mantenga un orden como este, usando java.util.ArrayList y java.util.Collections.binarySeach estándar:

 public class ListVocabulary implements Vocabulary { private List<String> words = new ArrayList<String>(); /** * Constructor that adds all the words and then sorts the underlying list */ public ListVocabulary(Collection<String> words) { this.words.addAll(words); Collections.sort(this.words); } public boolean add(String word) { int pos = Collections.binarySearch(words, word); // pos > 0 means the word is already in the list. Insert only // if it's not there yet if (pos < 0) { words.add(-(pos+1), word); return true; } return false; } public boolean isPrefix(String prefix) { int pos = Collections.binarySearch(words, prefix) ; if (pos >= 0) { // The prefix is a word. Check the following word, because we are looking // for words that are longer than the prefix if (pos +1 < words.size()) { String nextWord = words.get(pos+1); return nextWord.startsWith(prefix); } return false; } pos = -(pos+1); // The prefix is not a word. Check where it would be inserted and get the next word. // If it starts with prefix, return true. if (pos == words.size()) { return false; } String nextWord = words.get(pos); return nextWord.startsWith(prefix); } public boolean contains(String word) { int pos = Collections.binarySearch(words, word); return pos >= 0; } }

Si decidiéramos usar un árbol binario, la implementación podría ser aún más corta y elegante (nuevamente, aquí hay un enlace al código):

 public class TreeVocabulary extends TreeSet<String> implements Vocabulary { public TreeVocabulary(Collection<String> c) { super(c); } public boolean isPrefix(String prefix) { String nextWord = ceiling(prefix); if (nextWord == null) { return false; } if (nextWord.equals(prefix)) { Set<String> tail = tailSet(nextWord, false); if (tail.isEmpty()) { return false; } nextWord = tail.iterator().next(); } return nextWord.startsWith(prefix); } /** * There is a mismatch between the parameter types of vocabulary and TreeSet, so * force call to the upper-class method */ public boolean contains(String word) { return super.contains(word); } }

En ambos casos, podemos esperar un rendimiento O(log n) para cada método de acceso ( contains() and isPrefix() ). En cuanto a los requisitos de espacio, tanto la implementación respaldada por matriz como la implementación respaldada por árbol requieren O(n+M) donde n es el número de palabras en el diccionario y M es el tamaño en bytes del diccionario, es decir, la suma de la longitud de las cadenas en el diccionario.

Aplicaciones Trie: cuándo y por qué usar Tries

El rendimiento logarítmico y la memoria lineal no están mal. Pero hay algunas características más de nuestro dominio de aplicación que nos pueden llevar a un mejor rendimiento:

• Podemos asumir con seguridad que todas las palabras están en minúsculas.
• Solo aceptamos letras az, sin puntuación, sin guiones, sin acentos, etc.
• El diccionario contiene muchas formas flexionadas: plurales, verbos conjugados, palabras compuestas (p. ej., casa –> ama de llaves). Por lo tanto, muchas palabras comparten la misma raíz .
• Las palabras tienen una longitud limitada. Por ejemplo, si estamos trabajando en un tablero de 4x4, todas las palabras de más de 16 caracteres se pueden descartar.

Aquí es donde entra el trie (pronunciado “try”). Pero, ¿qué es exactamente un trie? Los intentos son estructuras de datos descuidadas, que se encuentran en libros pero rara vez en bibliotecas estándar.

Para motivarnos, primero consideremos el niño del cartel de la informática: el árbol binario. Ahora, cuando analizamos el rendimiento de un árbol binario y decimos que la operación x es O(log(n)) , estamos hablando constantemente de base logarítmica 2. Pero, ¿y si, en lugar de un árbol binario, usáramos un árbol ternario, donde cada nodo tiene tres hijos (o un abanico de tres). Entonces, estaríamos hablando de la base logarítmica 3. (Esa es una mejora del rendimiento, aunque solo por un factor constante). Esencialmente, nuestros árboles se volverían más anchos pero más cortos, y podríamos realizar menos búsquedas ya que no necesitamos descender mucho tan profunda.

Llevando las cosas un paso más allá, ¿qué pasaría si tuviéramos un árbol con un despliegue igual al número de valores posibles de nuestro tipo de datos?

Esta es la motivación detrás del trie. Y como habrás adivinado, un trie es de hecho un árbol, ¡un árbol trie por así decirlo!

Pero, a diferencia de la mayoría de los árboles binarios que usaría para clasificar cadenas, aquellos que almacenarían palabras completas en sus nodos, cada nodo de un trie contiene un solo carácter (y ni siquiera eso, como veremos pronto) y tiene un fan-out máximo igual a la longitud del alfabeto. En nuestro caso, la longitud del alfabeto es 26; por lo tanto, los nodos del trie tienen una distribución máxima de 26. Y, mientras que un árbol binario equilibrado tiene una profundidad log2(n) , ¡la profundidad máxima del trie es igual a la longitud máxima de una palabra! (Otra vez, más ancha pero más corta.)

Dentro de un trie, las palabras con la misma raíz (prefijo) comparten el área de memoria que corresponde a la raíz.

Para visualizar la diferencia, consideremos un pequeño diccionario compuesto por cinco palabras. Suponga que las letras griegas indican punteros y tenga en cuenta que en el trie, los caracteres rojos indican nodos que contienen palabras válidas .

Implementación de Java Trie

Como sabemos, en el árbol, los punteros a los elementos secundarios generalmente se implementan con una variable izquierda y derecha, porque el abanico máximo se fija en dos.

En un trie que indexa un alfabeto de 26 letras, cada nodo tiene 26 hijos posibles y, por lo tanto, 26 punteros posibles. Por lo tanto, cada nodo presenta una matriz de 26 (punteros a) subárboles, donde cada valor podría ser nulo (si no existe tal hijo) u otro nodo.

Entonces, ¿cómo buscamos una palabra en un trie? Aquí está el método que, dado un String s , identificará el nodo que corresponde a la última letra de la palabra, si existe en el árbol:

 public LowercaseTrieVocabulary getNode(String s) { LowercaseTrieVocabulary node = this; for (int i = 0; i < s.length(); i++) { int index = LOWERCASE.getIndex(s.charAt(i)); LowercaseTrieVocabulary child = node.children[index]; if (child == null) { // There is no such word return null; } node = child; } return node; }

El método LOWERCASE.getIndex(s.charAt(i)) simplemente devuelve la posición del i-ésimo carácter en el alfabeto. En el nodo devuelto, un node de propiedad booleana indica que el nodo corresponde a la última letra de una palabra, es decir, una letra marcada en rojo en el ejemplo anterior. Dado que cada nodo mantiene un contador del número de hijos, si este contador es positivo, entonces hay palabras más largas en el diccionario que tienen la cadena actual como prefijo. Nota: el nodo realmente no necesita mantener una referencia al carácter al que corresponde, porque está implícito en su posición en el trie.

Análisis del rendimiento

Lo que hace que la estructura trie funcione realmente bien en estas situaciones es que el costo de buscar una palabra o un prefijo es fijo y depende únicamente del número de caracteres de la palabra y no del tamaño del vocabulario.

En nuestro dominio específico, dado que tenemos cadenas que tienen como máximo 16 caracteres, son necesarios exactamente 16 pasos para encontrar una palabra que está en el vocabulario, mientras que cualquier respuesta negativa, es decir, la palabra o el prefijo no está en el trie, se puede obtener en un máximo de 16 pasos también! Teniendo en cuenta que hemos ignorado previamente la longitud de la cadena al calcular la complejidad del tiempo de ejecución tanto para la lista ordenada respaldada por matrices como para el árbol, que está oculto en las comparaciones de cadenas, también podemos ignorarlo aquí y afirmar con seguridad que la búsqueda se ha realizado. en tiempo O(1) .

Teniendo en cuenta los requisitos de espacio (y recordando que hemos indicado con M el tamaño en bytes del diccionario), el trie podría tener M nodos en el peor de los casos, si no hay dos cadenas que compartan un prefijo. Pero como hemos observado que hay un alto grado de redundancia en el diccionario, hay mucha compresión por hacer. El diccionario de inglés que se usa en el código de ejemplo tiene 935 017 bytes y requiere 250 264 nodos, con una relación de compresión de alrededor del 73 %.

Sin embargo, a pesar de esto, incluso un trie comprimido generalmente requerirá más memoria que un árbol o una matriz. Esto se debe a que, para cada nodo, se necesitan al menos 26 x sizeof(pointer) bytes, más algunos gastos generales para el objeto y atributos adicionales. En una máquina de 64 bits, cada nodo requiere más de 200 bytes, mientras que un carácter de cadena requiere un solo byte, o dos si consideramos las cadenas UTF.

Pruebas y pruebas de rendimiento

Entonces, ¿qué pasa con el rendimiento? Las implementaciones de vocabulario se probaron en dos situaciones diferentes: verificar 20 000 000 de cadenas aleatorias y encontrar todas las palabras en 15 000 tableros generados aleatoriamente a partir de la misma lista de palabras.

Se analizaron cuatro estructuras de datos: una lista ordenada respaldada por una matriz, un árbol binario, el trie descrito anteriormente y un trie que usa matrices de bytes correspondientes al índice alfabético de los caracteres mismos (una optimización de rendimiento menor y fácil de implementar). Estos son los resultados, en ms:

El número medio de movimientos realizados para resolver el tablero es de 2.188. Para cada movimiento, se realizan una búsqueda de palabras y una búsqueda de prefijos, es decir, para verificar todos los tableros, se realizaron más de 32 millones de búsquedas de palabras y 32 millones de búsquedas de prefijos. Nota: estos se pueden hacer en un solo paso, los mantuve separados para mayor claridad en la exposición. Compactarlos en un solo paso reduciría el tiempo de resolución de los tableros casi a la mitad, y probablemente favorecería aún más el trie.

Como se puede ver arriba, la búsqueda de palabras funciona mejor con el trie incluso cuando se usan cadenas, y es incluso más rápido cuando se usan índices alfabéticos, y estos últimos funcionan más del doble de rápido que un árbol binario estándar. La diferencia en la resolución de los tableros es aún más evidente, ya que la solución rápida trie-alphabet-index es más de cuatro veces más rápida que la lista y el árbol.

Terminando

El trie es una estructura de datos muy especializada que requiere mucha más memoria que los árboles y las listas. Sin embargo, cuando se aplican características de dominio específicas, como un alfabeto limitado y una alta redundancia en la primera parte de las cadenas, puede ser muy eficaz para abordar la optimización del rendimiento.

Referencias

En el capítulo 5 del libro de Robert Sedgewick "Algorithms, 4th edition" se puede encontrar una explicación detallada de los intentos y los alfabetos. El sitio web complementario en Princeton tiene el código para una implementación de Alphabet y TrieST que es más extensa que mi ejemplo.

La descripción del trie y las implementaciones para varios idiomas también se pueden encontrar en Wikipedia y también puede echar un vistazo a este recurso de trie de la Universidad de Boston.