Come posso creare un grafo word aciclico diretto incrementale per archiviare e cercare stringhe?

Question

Sto cercando di memorizzare un elenco di stringhe in modo conciso, in modo che possano essere analizzate/ricercate molto rapidamente.

Un grafico di parola aciclico diretto (DAWG) si adatta a questo scopo meravigliosamente. Tuttavia, non ho un elenco delle stringhe da includere in primo luogo, quindi deve essere incrementabile in modo incrementale. Inoltre, quando cerco attraverso una stringa, ho bisogno di riportare i dati associati al risultato (non solo un booleano che dice se era presente).

Ho trovato informazioni su una modifica del DAWG per il tracciamento dei dati di stringa qui: http://www.pathcom.com/~vadco/adtdawg.html Sembra estremamente, estremamente complesso e non sono sicuro di essere in grado di scriverlo.

Ho anche trovato alcuni documenti di ricerca che descrivono algoritmi di costruzione incrementale, anche se ho trovato che i documenti di ricerca in generale non sono molto utili.

Non credo di essere abbastanza avanzato da poter combinare entrambi questi algoritmi da solo. Esiste già la documentazione di un algoritmo che le include, oppure un algoritmo alternativo con una buona memoria utilizza la velocità &?

Answer 1

Ho scritto la pagina Web ADTDAWG. Aggiungere parole dopo la costruzione non è un'opzione. La struttura non è altro che 4 matrici di tipi interi senza segno. È stato progettato per essere immutabile per l'inclusione totale della cache della CPU e per la complessità minima dell'accesso multi-thread.

La struttura è un automa che forma una funzione hash minima e perfetta. È stato creato per la velocità mentre si attraversa in modo ricorsivo utilizzando uno stack esplicito.

Come pubblicato, supporta fino a 18 caratteri. Compresi tutti i 26 caratteri inglesi richiederanno ulteriori aumenti.

Il mio consiglio è di utilizzare un Trie standard, con un indice di array memorizzato in ciascun nodo. Ya, sembrerà infantile, ma ogni nodo END_OF_WORD rappresenta solo una parola. ADTDAWG è una soluzione per ogni nodo END_OF_WORD in un DAWG tradizionale che rappresenta molte, molte parole.

I tavoli di hash minimi e perfetti non sono il tipo di cosa che puoi semplicemente mettere insieme al volo.

Sto cercando qualcos'altro su cui lavorare, o un lavoro, quindi contattami, e farò quello che posso. Per ora, tutto quello che posso dire è che non è realistico utilizzare l'ottimizzazione pesante su una struttura che è soggetta a modifiche frequenti.

Answer 2

Si consiglia inoltre di esaminare una struttura trie per questo (potenzialmente creando un radix-tree). Sembra una struttura alternativa "semplice" decente.

sto suggerendo questo per un paio di motivi:

1. Io davvero non hanno una piena comprensione del vostro risultato.
2. Definitivamente incrementale da compilare.
3. I nodi foglia possono contenere tutti i dati desiderati.
4. Soggettivamente, un semplice algoritmo.

Answer 3

Java

Per problemi su grafi che richiedono la persistenza, mi piacerebbe prendere uno sguardo al progetto Neo4j graph DB. Neo4j è progettato per archiviare grafici di grandi dimensioni e consentire la costruzione incrementale e la modifica dei dati, che sembra soddisfare i criteri che descrivi.

Hanno alcuni buoni esempi per farti andare rapidamente e di solito c'è un codice di esempio per iniziare con la maggior parte dei problemi.

Hanno un DAG example con un collegamento in basso allo full source code.

C++

Se stai usando C++, una soluzione comune per rappresentare graficamente edificio/analisi è quello di utilizzare il Boost graph library. Per mantenere il tuo grafico puoi mantenere una versione basata su file del grafico in GraphML (per esempio) e leggere e scrivere su quel file mentre il tuo grafico cambia.