Qual è l'algoritmo di diff (basato sulla parola o il carattere) migliore là fuori?

Question

Quindi, voglio essere in grado di trovare il diff tra due stringhe su una parola per parola (forse più veloce di per carattere, però, se per carattere è più veloce allora vorrei farlo in quel modo).

Ecco un esempio di quello che voglio raggiungere: Testo Fonte:

Hello there! 

testo modificato:

Helay scere? 

diff:

Hel[lo](ay) [th](sc)ere[!](?) 

• il testo tra parentesi quadre è ciò che è stato rimosso, il parentetico il testo è quello che è stato aggiunto

non è una specie di un modo super hacker per farlo utilizzando uno strumento a riga di comando, come ad esempio opendiff, ma richiede un carattere di nuova riga inbetween ogni personaggio, come opendiff è la linea-based.

Sto usando ruby ​​e non ho trovato alcuno strumento per farlo ... ma il linguaggio non è terribilmente importante, dato che gli algoritmi possono essere facilmente trasferiti.

grazie.

Answer 1

Ecco una gemma rubino che non diffing di stringhe: http://rubydoc.info/gems/diff-lcs/1.1.3/frames

Prima mano, ho appena fatto (in IRB)

require 'rubygems' 
require 'diff/lcs' 
require 'diff/lcs/array' 
require 'diff/lcs/string' 

Così, scrivendo la logica per inserire, i marcatori inline rimossi e inseriti diventano banali grazie a questo array di modifiche 2D.

Anche se non sono sicuro se questo è il modo migliore.

Answer 2

Si consiglia di controllare questo: http://en.wikipedia.org/wiki/Longest_common_subsequence_problem. Non è difficile da implementare.

Answer 3

Una soluzione sarà trovare la distanza di modifica tra le stringhe.

Answer 4

Quindi quello che puoi fare ripetutamente usa l'LCS (come collegato sopra) per trovare tutte le stringhe comuni, e rimuoverle da entrambe le tue stringhe, sostituendole con qualche altra stringa - diciamo solo un "*". Quindi esegui l'iterazione su entrambe le stringhe contemporaneamente e riordina le parti comuni e distinte.

Esempio

A) Hello there! 
B) Helay scere? 

LCS detection gives us ["Hel"," ","ere"], and after replacement we have 
A) *lo*th*! 
B) *ay*sc*? 

Now you split on the delimiter ("*") giving you 
A) ["lo","th","!"] 
B) ["ay","sc","?"] 

E da qui che hai basta andare a fare semplice meshing. Qualcosa chiave da notare è che ci possono essere voci nulli, per esempio se si sta facendo questo metodo su "Hell" e "Hel" Avrai finalmente ottenere

Common LCS) ["Hel"] 
A) ["l"] 
B) [""] 

meaning your result will be Hel[l]() 

Speriamo che sia accettabile.

Answer 5

Dai un'occhiata a https://github.com/pvande/differ.Questo gioiello fa quello che stai cercando