Unisci i grafici aciclici diretti riducendo al minimo il numero di nodi

4

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?

    
posta Francesco Frassinelli 14.12.2014 - 01:11
fonte

1 risposta

1

Penso che la tua struttura sia il grafico a linee del DAWG minimo. Li ho generati prima, tre anni fa, costruendo il DAWG minimo, da quello grafico a linee, quindi minimizzando il grafico a linee. Ho cercato la letteratura e Google in modo approfondito e non ho mai trovato questo ultimo passaggio. Ho concluso che il DAWG era più utile, in generale, ma la linea DAWG era migliore per la visualizzazione di quelli non abituati ai DAWG. C'è un altro nome per un DAWG usato nell'elaborazione del linguaggio naturale, un Word Something, il qualcosa che mi ha eluso in questo momento.

Il tuo esempio adc suggerisce un DAWG in cui tutti i nodi hanno un # margine al sink.

    
risposta data 23.03.2015 - 21:39
fonte

Leggi altre domande sui tag