¿Cómo puedo construir un gráfico de palabras acíclica dirigido incremental para almacenar y buscar cadenas?

Question

Estoy tratando de almacenar una gran lista de cadenas de manera concisa para que puedan analizarse/buscarse rápidamente.

Un gráfico de palabras acíclica dirigido (DAWG) se adapta maravillosamente a este propósito. Sin embargo, no tengo una lista de cadenas para incluir en primer lugar, por lo que debe ser incrementalmente compilable. Además, cuando busco una cadena, necesito recuperar los datos asociados con el resultado (no solo un booleano que dice si estaba presente).

He encontrado información sobre una modificación de la DAWG para el seguimiento de datos de cadena aquí: http://www.pathcom.com/~vadco/adtdawg.html Parece extremadamente, extremadamente complejo y no estoy seguro de poder escribirlo.

También he encontrado algunos artículos de investigación que describen algoritmos de construcción incrementales, aunque he encontrado que los artículos de investigación en general no son muy útiles.

No creo que esté lo suficientemente avanzado como para poder combinar ambos algoritmos yo mismo. ¿Existe documentación de un algoritmo que los presente o un algoritmo alternativo con buena memoria que use la velocidad &?

Answer 1

Escribí la página web ADTDAWG. Agregar palabras después de la construcción no es una opción. La estructura no es más que 4 matrices de tipos enteros sin signo. Fue diseñado para ser inmutable para la inclusión total de la memoria caché de la CPU, y la complejidad mínima de acceso a múltiples subprocesos.

La estructura es un autómata que forma una función hash mínima y perfecta. Fue construido para velocidad mientras se recorre recursivamente usando una pila explícita.

Según lo publicado, admite hasta 18 caracteres. Incluir los 26 caracteres en inglés requerirá un aumento adicional.

Mi consejo es usar un Trie estándar, con un índice de matriz almacenado en cada nodo. Ya, va a parecer infantil, pero cada nodo END_OF_WORD representa solo una palabra. ADTDAWG es una solución para cada nodo END_OF_WORD en un DAWG tradicional que representa muchas, muchas palabras.

Las tablas hash minimalistas y perfectas no son el tipo de cosas que puede armar sobre la marcha.

Estoy buscando algo más para trabajar, o un trabajo, así que contáctame, y haré lo que pueda. Por ahora, todo lo que puedo decir es que no es realista usar una gran optimización en una estructura que está sujeta a cambios frecuentes.

Answer 2

Es posible que desee ver una estructura trie para esto (potencialmente la construcción de un radix-tree). Parece una estructura alternativa "simple" decente.

que estoy sugiriendo esto por varias razones:

1. que realmente no tienen una comprensión completa de su resultado.
2. Definitivamente incremental para compilar.
3. Los nodos de hoja pueden contener todos los datos que desee.
4. Subjetivamente, un algoritmo simple.

Answer 3

Java

Para los problemas de gráficos que requieren persistencia, me gustaría echar un vistazo al proyecto Neo4j graph DB. Neo4j está diseñado para almacenar gráficos grandes y permitir construcciones y modificaciones incrementales de los datos, que parecen cumplir los criterios que usted describe.

Tienen algunos buenos ejemplos para que pueda comenzar rápidamente y generalmente hay un código de ejemplo para comenzar con la mayoría de los problemas.

Tienen un DAG example con un enlace en la parte inferior del full source code.

C++

Si estás usando C++, una solución común para representar gráficamente el edificio/el análisis es utilizar el Boost graph library. Para conservar su gráfico, puede mantener una versión del gráfico basada en archivos en GraphML (por ejemplo) y leer y escribir en ese archivo a medida que cambia su gráfica.