Trie (árbol de prefijos) en Python

Question

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

Si algo no está claro, estoy muy contento 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 prefijo común más grande de un subtitulo en su raíz. Por ejemplo, si tuviéramos las palabras stackoverflow, stackbase y stackbased, entonces el árbol sería algo como esto:

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

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

Buscar -query es simple de implementar. inserción no es difícil, pero algo más complejo de lo que quiero .. :(

Mi idea era insertar las teclas una tras otra (partiendo de un trie vacío), por primera vez en busca de la a-ser -Inserted key k (Find (k)), y luego reorganizar/dividir los nodos localmente en el lugar donde se detiene el procedimiento de búsqueda. Resultan ser 4 casos: (Sea k la clave que queremos insertar y k 'ser la clave del nodo, donde terminó la búsqueda)

1. k es idéntica a k'
2. k es un prefijo "adecuada" de k '
3. k' es un prefijo "adecuada" de k
4. k y k' compartir algunas prefijo común, pero ninguno de los casos (1), (2) o (3) ocurrir.

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

Gracias :)

Answer 1

De un vistazo, parece que ha implementado un Patricia Trie. Este enfoque también se denomina compresión de ruta en algunos de los documentos. Debería haber copias de ese documento que no estén detrás del paywall de ACM, que incluirá un algoritmo de inserción.

También hay otro método de compresión que puede consultar: compresión de nivel. La idea detrás de la compresión de ruta es reemplazar cadenas de nodos secundarios individuales con un único supernodo que tiene un recuento de "omisión".La idea detrás de la compresión de nivel es reemplazar subárboles completos o casi completos con un supernodo con un recuento de "grado" que indica cuántos dígitos de la clave decodifica 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 de ello con Google rápido.

compresión Nivel puede acortar la trayectoria promedio considerablemente, pero los algoritmos de inserción y extracción llegar a ser muy complicado, ya que necesitan para gestionar los nodos trie de manera similar a como matrices dinámicas. Para los conjuntos de datos correctos, los árboles comprimidos de nivel pueden ser rápido. Por lo que recuerdo, son el segundo método más rápido para almacenar tablas de enrutamiento IP, el más rápido es algún tipo de hash trie.

Answer 2

No veo nada de malo con su enfoque. Si está buscando una solución de pico, tal vez la acción tomada en el caso 4 es realmente factible para los primeros tres casos, IE encuentre el prefijo común en k y k' y reconstruya el nodo con eso en mente. Si sucede que las claves son prefijos entre sí, la trie resultante seguirá siendo correcta, 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 para mirar es difícil decir si esto funciona en su caso.

Answer 3

Algo de la tangente, pero si son muy preocupado por el número de nodos en su Trie, es posible que mira a unirse a sus sufijos de palabras también. Me gustaría echar un vistazo a la idea DAWG (Directed Acyclic Word Graph): http://en.wikipedia.org/wiki/Directed_acyclic_word_graph

El inconveniente 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 4

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

Si estás construyendo un árbol de aplicación de prefijo para el pitón entonces sus alfabetos serían cosas como def,: si, si no ... etc

La elección del alfabeto derecha hace una gran diferencia en la construcción de árboles de prefijo eficientes. En cuanto a sus respuestas, puede buscar paquetes PERL en CPAN que hacen el cálculo de subcadena común más largo utilizando trie's. Puede tener algo de suerte allí ya que la mayoría de su implementación es bastante robusta.

Answer 5

Mira: Judy-arrays y la interfaz de pitón en http://www.dalkescientific.com/Python/PyJudy.html