Diffusione più veloce

Question

Sto lavorando alla diffusione di file binari di grandi dimensioni. Ho implementato il celebre algoritmo Myers Diff, che produce una diff minima. Tuttavia, è O (ND), quindi per diff due molto diversi file da 1 MB, mi aspetto di prendere tempo 1 milione quadrato = 1 trilione. Questo non è buono!

Quello che mi piacerebbe è un algoritmo che produce un diff potenzialmente non minimale, ma lo fa molto più velocemente. So che uno deve esistere, perché Beyond Compare lo fa. Ma non so come!

Per essere sicuri: ci sono strumenti come xdelta o bdiff, ma questi producono una patch destinata al consumo del computer, che è diverso da un diff consumabile dall'uomo. Una patch riguarda la trasformazione di un file in un altro, quindi può fare cose come copiare da parti precedenti del file. Un diff umano consumabile è lì per mostrare visivamente le differenze e può solo inserire ed eliminare. Ad esempio, questa trasformazione:

"puddi" -> "puddipuddipuddi"

produrrebbe una piccola macchia di "copia [0,4] a [5,9] e [10, 14]", ma una differenza maggiore di "append 'puddipuddi'". Sono interessato ad algoritmi che producono il diff più grande.

Grazie!

Answer 1

La diffusione è fondamentalmente lo stesso algoritmo utilizzato in bioinformatica per allineare le sequenze di DNA. Queste sequenze sono spesso di grandi dimensioni (milioni o miliardi di nucleotidi di lunghezza), e una strategia che funziona bene lì sul genoma è più utilizzato dal programma MUMmer:

1. trovare rapidamente tutti Maximal Unico Partite (sottostringhe che appaiono in entrambi i file e che non possono essere estesi in entrambe le direzioni con quella condizione ancora in attesa) utilizzando un suffisso albero
2. Trova rapidamente il sottoinsieme più lungo di MUM visualizzati in ordine consecutivo in entrambi i file utilizzando un algoritmo di programmazione dinamica a più lunga progressione
3. Correggi questo sottoinsieme di MOM nell'allineamento (es. Segna quelle regi come corrispondente)
4. Se ritenuto necessario, eseguire più lentamente (ad es. Myers) diffondendo le regioni inter-MUM. Nel tuo caso, probabilmente tralasceresti questo passaggio interamente se scoprissi che la lunghezza della MUM più lunga era al di sotto di una soglia (che dovresti prendere per dimostrare che i 2 file non sono correlati).

Questo tende a fornire un insieme molto buono (sebbene non garantito-ottimale) di regioni allineate (o equivalentemente, un insieme molto piccolo di differenze) ogni volta che non ci sono troppe differenze. Non sono certo dei limiti di tempo esatti per ogni passaggio, ma so che non ci sono termini n^2 o superiori.

Credo che il programma MUMmer richieda sequenze di DNA o proteine, quindi potrebbe non funzionare per voi, ma i concetti si applicano certamente alle stringhe generali (ad esempio i file), quindi se siete pronti a reimplementarlo voi stessi raccomanderei questo approccio.

Answer 2

Dal punto di vista delle prestazioni in quanto le dimensioni dei file aumentano, l'opzione GNU Diffutils è probabilmente l'opzione più affidabile. Per la tua situazione probabilmente userò il suo side-by-side comparison format, che è probabilmente il più umano del lotto. Altrimenti si sta scaricando il suo output in un altro formato e facendo del lavoro per renderlo carino.

Un buon contendente, le cui prestazioni sono migliorate costantemente, compresi numerosi aumenti di velocità, è diff-match-patch. Implementa l'algoritmo di Myers Diff in diversi linguaggi, tra cui Java e JavaScript. Vedere lo online demo per un esempio di quest'ultimo con risultati piuttosto stampati. Se vuoi fare una linea di diffusione, studia il wiki per suggerimenti su come usarlo a tale scopo.