Búsqueda prefijo en un árbol de raíz / trie Patricia

StackOverflow https://stackoverflow.com/questions/794601

Pregunta

Actualmente estoy implementación de un / trie Patricia árbol de raíz (como quieran llamarlo). Quiero utilizarlo para búsquedas de prefijo en un diccionario en un pedazo tenía pocas posibilidades de hardware. Se supone que funciona más o menos como auto-completado, i. mi. mostrando una lista de palabras que coincide con el prefijo mecanografiado.

Mi aplicación se basa en este artículo , pero el código en él doesn 't incluyen búsquedas de prefijo, aunque el autor dice:

  

[...] Digamos que quiere enumerar todos los nodos que tienen llaves con un prefijo común "AB". Se puede realizar una primera búsqueda en profundidad a partir de esa raíz, parando cada vez que se encuentra con bordes traseros.

Pero no veo la forma en que se supone que funciona. Por ejemplo, si construyo un árbol de raíz de estas palabras:

  

enfermedad
  imaginaria
  imaginación
  imaginar
  imitación
  inmediata
  
inmediatamente   inmensa
  en

voy a tener exactamente la misma "mejor partido" para los prefijos "i" y "en" por lo que parece difícil para mí para recoger todas las palabras que coinciden con sólo recorrer el árbol de ese mejor partido.

Además, hay un href="http://code.google.com/p/radixtree/" rel="nofollow noreferrer"> radix aplicación que tiene una búsqueda de prefijo implementado en RadixTreeImpl.java . Ese código comprueba explícitamente todos los nodos (a partir de un cierto nodo) para un partido de prefijo -. Realmente compara bytes

Puede alguien me punto a una descripción detallada sobre la implementación de una búsqueda de prefijo en los árboles Radix? Es el algoritmo utilizado en la implementación de Java la única manera de hacerlo?

¿Fue útil?

Solución

Piense en lo que codifica el trie. En cada nodo, que tiene la ruta que conduce a ese nodo, por lo que en su ejemplo, se empieza a Λ (que es un capital de Lambda, este tipo de letra griega tipo de chupa) el nodo raíz correspondiente a una cadena vacía. Λ tiene hijos por cada letra utilizado, por lo que en el conjunto de datos, que tiene una rama, por "i".

  • Λ
  • Λ → "i"

En la "i" nodo, hay dos niños, uno para "m" y otra para "n". La siguiente carta es "n", por lo que se toma,

  • Λ → "i" → "n"

y puesto que la única palabra que comienza "i", "n" en el conjunto de sus datos es "en", no hay niños de "n". Eso es una coincidencia.

Ahora, digamos que el conjunto de datos, en lugar de tener "en", tenía "infindibulum". (¿Qué SF estoy haciendo referencia se deja como ejercicio.) Seguimos obteniendo a la "n" nodo de la misma manera, pero si luego la siguiente letra que se obtiene es "q", usted sabe la palabra no aparece en el conjunto de datos en absoluto, porque no hay rama "q". En ese punto, se dice "bien, no hay partido". (Tal vez después de empezar a añadir la palabra, tal vez no, dependiendo de la aplicación.)

Pero si la próxima carta es "f", se puede seguir adelante. Puede cortocircuito que con una pequeña embarcación, sin embargo: una vez que se llega a un nodo que representa un camino único, se puede colgar el toda cadena de ese nodo. Al llegar a ese nodo, ya sabes que el resto de la cadena debe ser "findibulum", por lo que ha utilizado el prefijo para que coincida con la cadena entera, y lo devuelve.

Como su utiliza eso? en un montón de no-Unix Command intérpretes, como la vieja VAX DCL, se puede usar un prefijo único de un comando. Así, el equivalente a ls (1) fue DIRECTORY, pero ningún otro comando comenzó con DIR, por lo que podría escribir DIR y que era tan bueno como hacer toda la palabra. Si no pudo recordar el comando correcto, puede escribir simplemente 'D', y pulsa (creo) ESC; la DCL CLI que volvería todos los comandos que comenzaron con D, que podría buscar extremadamente rápido.

Otros consejos

Resulta que las extensiones de GNU para el estándar C ++ lib incluye una aplicación trie Patricia. Se encuentra bajo la extensión estructuras de datos basada en políticas. Ver http://gcc.gnu.org/onlinedocs/libstdc++/ext /pb_ds/trie_based_containers.html

Un algoritmo alternativo: Keep It Simple Stupid

Simplemente haga una lista ordenada de las palabras clave. Cuando usted tiene un prefijo, la búsqueda binaria para encontrar donde ese prefijo se encuentra en la lista. Todas sus terminaciones posibles se encontrarán a partir de ese índice, disponible para utilizarse en su lugar.

Este algoritmo se requiere sólo el 5% del código de un trie Patricia y será fácil de mantener, comprender y actualización. Es casi seguro este simple búsqueda lista será más eficiente.

El único inconveniente es que si usted tiene un gran número de palabras clave largas con prefijos similares, un trie puede ahorrar algo de almacenamiento, ya que no es necesario para mantener el prefijo completo para cada entrada. En la práctica, si usted tiene menos de unos pocos millones de palabras, esto no es un ahorro debido a la sobrecarga puntero del árbol dominará. Este ahorro es más para buscar aplicaciones como bases de datos de secuencias de ADN con millones de caracteres, no palabras clave de texto.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top