Algoritmo di differenza di testo

Question

Ho bisogno di un algoritmo in grado di confrontare due file di testo ed evidenziare la loro differenza e (ancora meglio!) può calcolare la loro differenza in modo significativo (come due file simili dovrebbero avere un punteggio di somiglianza superiore a due file diversi, con la parola "simile" definito nei termini normali). Sembra facile da implementare, ma non lo è.

L'implementazione può essere in c # o python.

Grazie.

Answer 1

In Python c'è difflib , come altri hanno suggerito.

difflib offre la classe SequenceMatcher , che può essere usato per darti un rapporto di somiglianza. Funzione di esempio:

def text_compare(text1, text2, isjunk=None):
    return difflib.SequenceMatcher(isjunk, text1, text2).ratio()

Answer 2

Posso consigliare di dare un'occhiata al codice e agli articoli di Neil Fraser:

google-diff-match-patch-patch

  

Attualmente disponibile in Java,   JavaScript, C ++ e Python. Senza riguardo   di lingua, ogni libreria presenta il   stessa API e stessa funzionalità.   Tutte le versioni hanno anche complete   test imbracature.

Neil Fraser: Diff Strategies - per la teoria e le note di implementazione

Answer 3

Guarda difflib . (Python)

Questo calcolerà le differenze in vari formati. È quindi possibile utilizzare la dimensione del contesto diff come una misura di quanto diversi sono due documenti?

Answer 4

Bazaar contiene un algoritmo di differenza alternativo, chiamato pazience diff (ci sono più informazioni nei commenti su quella pagina) che si dice sia migliore del tradizionale algoritmo diff. Il file "patiencediff.py" nella distribuzione del bazar è un semplice front-end della riga di comando.

Answer 5

La mia attuale comprensione è che la migliore soluzione al problema SES (Shortest Edit Script) è Myers "middle-snake"; metodo con la raffinatezza dello spazio lineare di Hirschberg.

L'algoritmo Myers è descritto in:

  

E. Myers, `` An O (ND) Difference   Algorithm and Its Variations, ''
  Algorithmica 1, 2 (1986), 251-266.

L'utilità diff GNU usa l'algoritmo Myers.

Il "punteggio di somiglianza" di cui parli si chiama "modifica distanza" in letteratura quale è il numero di inserti o eliminazioni necessari per trasformare una sequenza nell'altra.

Nota che un certo numero di persone ha citato l'algoritmo a distanza di Levenshtein ma che, sebbene sia facile da implementare, non è la soluzione ottimale in quanto inefficiente (richiede l'uso di una matrice n * m possibilmente enorme) e non fornisce il " modifica script " che è la sequenza di modifiche che potrebbero essere utilizzate per trasformare una sequenza nell'altra e viceversa.

Per una buona implementazione di Myers / Hirschberg guarda:

http://www.ioplex.com/~miallen /libmba/dl/src/diff.c

La particolare libreria in cui è contenuta non è più mantenuta, ma per quanto ne so il modulo diff.c stesso è ancora corretto.

Mike

Answer 6

Se hai bisogno di una granularità più fine delle linee, puoi usare la distanza di Levenshtein. La distanza di Levenshtein è una misura diretta di come sono simili due testi.
È inoltre possibile utilizzarlo per estrarre i registri di modifica e creare un diff molto dettagliato, simile a quello delle pagine della cronologia delle modifiche di SO. Tieni presente, tuttavia, che la distanza di Levenshtein può essere piuttosto impegnativa per calcolare la CPU e la memoria, quindi l'utilizzo di difflib, come ha suggerito Douglas Leder, molto probabilmente sarà più veloce.

Cf. anche questa risposta .

Answer 7

Esistono diverse metriche di distanza, come ha detto il paradosso, esiste la distanza di Levenshtein, ma esiste anche NYSIIS e Soundex . Per quanto riguarda le implementazioni di Python, ho usato py-editdist e ADVAS prima. Entrambi sono belli nel senso che si ottiene un singolo numero come punteggio. Dai un'occhiata prima a ADVAS, implementa una serie di algoritmi.

Answer 8

Come detto, usa difflib. Una volta che hai l'output diffuso, potresti trovare la Levenshtein distance delle diverse stringhe da dare un "valore" di quanto sono diversi.

Answer 9

È possibile utilizzare la soluzione al problema Longest Common Subsequence (LCS) . Vedi anche la discussione sui possibili modi per ottimizzare questa soluzione.

Answer 10

Un metodo che ho usato per una diversa funzionalità, per calcolare quanti dati erano nuovi in ??un file modificato, potrebbe forse funzionare anche per te.

Ho un'implementazione diff / patch C # che mi permette di prendere due file, presumibilmente vecchia e nuova versione dello stesso file, e calcolare la "differenza", ma non nel solito senso della parola. Fondamentalmente, calcolo una serie di operazioni che posso eseguire sulla vecchia versione per aggiornarla per avere gli stessi contenuti della nuova versione.

Per usarlo per la funzionalità inizialmente descritta, per vedere quanti dati erano nuovi, ho semplicemente eseguito le operazioni e per ogni operazione copiata dal vecchio file alla lettera, che aveva un fattore 0 e ogni operazione che il nuovo testo inserito (distribuito come parte della patch, dato che non era presente nel vecchio file) aveva un fattore 1. A tutti i personaggi è stata data questa fabbrica, che mi ha dato sostanzialmente un lungo elenco di 0 e 1.

Tutto quello che dovevo fare era calcolare gli 0 e gli 1. Nel tuo caso, con la mia implementazione, un basso numero di 1 rispetto a 0 significherebbe che i file sono molto simili.

Questa implementazione gestirà anche i casi in cui il file modificato ha inserito copie del vecchio file fuori servizio o addirittura duplicati (ad esempio, si copia una parte dall'inizio del file e la si incolla nella parte inferiore), poiché sarebbero entrambi copie della stessa parte originale dal vecchio file.

Ho sperimentato la pesatura delle copie, in modo che la prima copia contasse 0, e le successive copie degli stessi caratteri avessero fattori progressivamente più alti, al fine di dare un'operazione di copia / incolla alcuni "nuovi fattori", ma non ho mai finito come il progetto è stato demolito.

Se sei interessato, il mio codice diff / patch è disponibile dal mio repository Subversion.

Answer 11

Dai un'occhiata al modulo Fuzzy . Ha algoritmi veloci (scritti in C) per soundex, NYSIIS e doppio metafono.

Una buona introduzione è disponibile all'indirizzo: http: //www.informit. com / articoli / article.aspx? p = 1848528