común - Trie(árbol de prefijo) en Python

python capitalize a title

Question

No sé si este es el lugar para preguntar acerca de los algoritmos. Pero veamos si tengo alguna respuesta ... :)

Si algo no está claro estoy muy feliz de aclarar las cosas.

Acabo de implementar un Trie en python. Sin embargo, un poco parecía ser más complicado de lo que debería (como alguien que ama la simplicidad). Tal vez alguien ha tenido un problema similar?

Mi objetivo era minimizar el número de nodos almacenando el mayor prefijo común de un sub-trie en su raíz. Por ejemplo, si tuviéramos las palabras stackoverflow , stackbase y stackbased , entonces el árbol se vería así:

              [s]tack
[o]verflow ______/ /_______ [b]ase
                                  /___ [d]

Tenga en cuenta que todavía se puede pensar en los bordes que tienen un carácter (el primero del nodo secundario).

Find -query es fácil de implementar. La inserción no es difícil, pero es algo más compleja de lo que quiero ... :(

Mi idea fue insertar las claves una después de la otra (comenzando desde un punto vacío), primero buscando la clave k ( Buscar (k)) que se insertará, y luego reorganizar / dividir los nodos localmente en el lugar donde El procedimiento de búsqueda se detiene. Resultan 4 casos: (Sea k la clave que queremos insertar y k ''la clave del nodo, donde finalizó la búsqueda)

1. k es idéntico a k ''
2. k es un prefijo "propio" de k ''
3. k ''es un prefijo "propio" de k
4. k y k ''comparten algún prefijo común, pero ninguno de los casos (1), (2) o (3) ocurre.

Parece que cada uno de los casos son únicos y, por lo tanto, implican diferentes modificaciones del Trie. PERO: ¿es realmente tan complejo? ¿Me estoy perdiendo de algo? ¿Hay un mejor enfoque?

Gracias :)

Answer 1

Algo de una tangente, pero si está super preocupado por la cantidad de nodos en su Trie, puede considerar unirse a sus sufijos de palabras también. Echaré un vistazo a la idea de DAWG (Directed Acyclic Word Graph): http://en.wikipedia.org/wiki/Directed_acyclic_word_graph

La desventaja de estos es que no son muy dinámicos y crearlos puede ser difícil. Pero, si su diccionario es estático, pueden ser súper compactos.

Answer 2

De un vistazo, parece que has implementado una Patricia Trie . Este enfoque también se denomina compresión de ruta en algunas publicaciones. Debería haber copias de ese documento que no estén detrás del muro de pago de ACM, que incluirá un algoritmo de inserción.

También hay otro método de compresión que puede querer ver: compresión de nivel. La idea detrás de la compresión de ruta es reemplazar las cadenas de nodos secundarios individuales con un súper nodo único que tiene un recuento de "omisión". La idea detrás de la compresión de nivel es reemplazar los subárboles completos o casi completos por un súper nodo con un recuento de "grados" que indica cuántos dígitos de la clave descodifica el nodo. También hay un tercer enfoque llamado compresión de ancho, pero me temo que mi memoria me falla y no pude encontrar una descripción con Google rápido.

La compresión de nivel puede acortar considerablemente la ruta promedio, pero los algoritmos de inserción y eliminación se vuelven bastante complicados ya que necesitan administrar los nodos trie de manera similar a los arreglos dinámicos. Para los conjuntos de datos correctos, los árboles comprimidos de nivel pueden ser rápidos . Por lo que recuerdo, son el segundo enfoque más rápido para almacenar tablas de enrutamiento IP, el más rápido es algún tipo de troceo hash.

Answer 3

Mire: Judy-arrays y la interfaz de python en http://www.dalkescientific.com/Python/PyJudy.html

Answer 4

No veo nada malo en su enfoque. Si está buscando una solución de picos, tal vez la acción tomada en el caso 4 sea realmente factible para los primeros tres casos, es decir, busque el prefijo común para k y k'' y reconstruya el nodo con eso en mente. Si sucede que las claves son prefijos de una a otra, el trie resultante seguirá siendo correcto, solo la implementación hizo un poco más de trabajo de lo que realmente tenía que hacer. Pero, de nuevo, sin ningún código que ver, es difícil decir si esto funciona en su caso.

Answer 5

Tengo una pregunta con respecto a su implementación. ¿Cuál es el nivel de granularidad en el que decide dividir las cadenas para crear el árbol de prefijos? Puedes dividir la pila como s, t, a, c, k o st, ta, ac, ck y muchos otros ngramas de la misma. La mayoría de las implementaciones de árbol de prefijo tienen en cuenta un alfabeto para el idioma, basado en este alfabeto, usted hace la división.

Si estuvieras creando una implementación de árbol de prefijos para python, entonces tus alfabetos serían cosas como def,:, if, else ... etc

Elegir el alfabeto correcto hace una gran diferencia en la construcción de árboles de prefijos eficientes. En cuanto a sus respuestas, puede buscar los paquetes PERL en CPAN que realizan el cálculo de subcadenas más largo usando trie''s. Puede que tengas algo de suerte ya que la mayor parte de su implementación es bastante sólida.