Ho alcuni DAG s (grafici acyllic diretti) e voglio unirli per minimizzare il numero di nodi (potremmo dire che ogni nodo ha un costo, mentre i bordi sono liberi).
Questi quattro DAG diversi (diretti da sinistra a destra) ...
a-b-c
a-d-c
a-c
c-a
... dovrebbe diventare:
/---\
a--b--c-a
\-d-/
Questo non è un vero DAWG (grafico della parola aciclica diretto): non voglio memorizzare informazioni come " è 'adc' incluso? ". La mia struttura poteva solo rispondere a questa domanda: "sarebbe possibile che 'adc' fosse una delle parole?".
Esiste un algoritmo per questo scopo?
Aggiornamento (12/15/14) - Distanza di Levenshtein
Ho provato qualcosa di diverso: ho usato la distanza Levenshtein per trovare il numero minimo di modifiche necessarie per trasformare una stringa in un'altra ( nodo = carattere e catena = sequenza di nodi / caratteri = parola ). Il mio algoritmo ignora la cancellazione e inserisce i caratteri anziché sostituirli. Ecco la parte interessante (codice Python):
current = words[0]
for word in words[1:]:
edit = editops(current, word)
customEdit = [('insert', s, d) for op, s, d in edit if op != 'delete']
current = apply_edit(customEdit, current, word)
A volte ci sono caratteri non necessari, quindi li rimuovo alla fine del processo. Se cambio l'ordine delle parole ottengo risultati diversi, quindi eseguo il mio codice molte volte mescolando parole per trovare una stringa più corta (lo shuffling sembra fornire un risultato migliore con un numero minore di iterazioni rispetto alle permutazioni, anche se le parole sono ordinati per lunghezza).
Se ogni carattere è un nodo e ogni parola è un DAG, posso facilmente ottenere una buona approssimazione del DAG che sto cercando.
Il problema principale di questo approccio è che non so come sarà il risultato migliore, quindi non so quando fermarmi (non posso controllare ogni risultato della mia permutazione: ci vorrà troppo tempo !).
Ecco il mio codice (testato con Python 2; python-Levenshtein è necessario). L'output è simile a questo:
ldoarmilpesouimtr (17) iapmdsoeluiortem (16) diolposarmieutm (15) ^C Original size: 22 Compressed: 15 diolposarmieutm (lorem) diolposarmieutm (ipsum) diolposarmieutm (dolor) diolposarmieutm (sit) diolposarmieutm (amet)
È un buon modo per risolvere questo problema? Cosa potrebbe essere migliorato? Sai se è possibile conoscere il numero minimo di nodi / caratteri necessari per fermare l'algoritmo quando ottengo l'optimum?