Comment puis-je créer un graphe de mots acyclique dirigé incrémental pour stocker et rechercher des chaînes?

Question

J'essaie de stocker une grande liste de chaînes de manière concise afin qu'elles puissent être analysées/recherchées très rapidement. Un graphique de mots acycliques dirigés (DAWG) s'adapte merveilleusement bien à cet objectif. Cependant, je n'ai pas de liste de chaînes à inclure en premier lieu, donc il doit être progressivement construit. De plus, lorsque je le cherche dans une chaîne, je dois ramener les données associées au résultat (pas seulement un dicton booléen s'il était présent).

J'ai trouvé des informations sur une modification du DAWG pour le suivi des données de chaîne ici: http://www.pathcom.com/~vadco/adtdawg.html Il semble extrêmement, extrêmement complexe et je ne suis pas sûr que je suis capable de l'écrire.

J'ai également trouvé quelques documents de recherche décrivant des algorithmes de construction incrémentiels, bien que j'ai trouvé que les documents de recherche en général ne sont pas très utiles.

Je ne pense pas que je suis assez avancé pour être capable de combiner ces deux algorithmes moi-même. Existe-t-il déjà la documentation d'un algorithme qui les présente, ou un algorithme alternatif avec une bonne utilisation de la mémoire? & speed?

Answer 1

J'ai écrit la page Web ADTDAWG. Ajouter des mots après la construction n'est pas une option. La structure n'est rien de plus que 4 tableaux de types entiers non signés. Il a été conçu pour être immuable pour l'inclusion totale du cache de l'UC et pour la complexité de l'accès multi-thread minimal.

La structure est un automate qui forme une fonction de hachage minimale et parfaite. Il a été construit pour la vitesse tout en parcourant récursivement en utilisant une pile explicite.

Tel que publié, il prend en charge jusqu'à 18 caractères. Y compris les 26 caractères anglais nécessitera une augmentation supplémentaire.

Mon conseil est d'utiliser un Trie standard, avec un index de tableau stocké dans chaque nœud. Ya, ça va paraître infantile, mais chaque noeud END_OF_WORD ne représente qu'un seul mot. L'ADTDAWG est une solution à chaque noeud END_OF_WORD dans un DAWG traditionnel représentant beaucoup, beaucoup de mots.

Les tables de hachage minimales et parfaites ne sont pas le genre de choses que vous pouvez assembler à la volée. Je cherche quelque chose d'autre à travailler, ou un travail, alors contactez-moi, et je ferai ce que je peux. Pour l'instant, tout ce que je peux dire, c'est qu'il est irréaliste d'utiliser une optimisation lourde sur une structure qui est susceptible d'être changée fréquemment.

Answer 2

Vous pouvez également regarder une structure trie pour cela (potentiellement construire un radix-tree). Il semble être une structure alternative «simple» décente.

Je suggère cela pour quelques raisons:

1. Je n'ai pas vraiment une bonne compréhension de votre résultat.
2. Définitivement incrémentielle à construire.
3. Les nœuds feuille peuvent contenir toutes les données que vous souhaitez.
4. Subjectivement, un algorithme simple.

Answer 3

Java

Pour les problèmes de graphes qui exigent la persistance, je prendrais un coup d'oeil au projet Neo4j graph DB. Neo4j est conçu pour stocker de grands graphiques et permettre la construction incrémentielle et la modification des données, ce qui semble répondre aux critères que vous décrivez.

Ils ont quelques bons exemples pour vous aider à démarrer rapidement et il y a généralement un exemple de code pour vous aider à démarrer avec la plupart des problèmes.

Ils ont un DAG example avec un lien en bas au full source code.

C++

Si vous utilisez C++, une solution commune pour représenter graphiquement la construction/l'analyse est d'utiliser le Boost graph library. Pour conserver votre graphique, vous pouvez conserver une version du graphique basée sur un fichier dans GraphML (par exemple) et lire et écrire dans ce fichier lorsque votre graphique change.