Algoritmo diff? [chiuso]

Question

Sono sembrato pazzo per una spiegazione di un algoritmo diff che funziona ed è efficiente.

Il più vicino che ho ottenuto è questo link a RFC 3284 (da diversi blog di Eric Sink post), che descrive in termini perfettamente comprensibili il formato dei dati in cui sono archiviati i risultati del diff. Tuttavia, non ha alcun riferimento al modo in cui un programma raggiungerebbe questi risultati facendo una diff.

Sto cercando di ricercare questo per curiosità personale, perché sono sicuro che ci devono essere dei compromessi quando si implementa un algoritmo diff, che sono abbastanza chiari a volte quando si guardano le differenze e ci si chiede "perché il programma diff ha scelto questo come un cambiamento invece di quello? " ...

Dove posso trovare una descrizione di un algoritmo efficiente che finirebbe per produrre VCDIFF?
A proposito, se ti capita di trovare una descrizione dell'algoritmo effettivo utilizzato da DiffMerge di SourceGear, sarebbe ancora meglio.

NOTA: la sottosequenza comune più lunga non sembra essere l'algoritmo utilizzato da VCDIFF, sembra che stiano facendo qualcosa di più intelligente, dato il formato dei dati che usano.

Answer 1

Un algoritmo di differenza O (ND) e le sue variazioni è un documento fantastico e potresti volerlo per iniziare lì. Include lo pseudo-codice e una bella visualizzazione degli incroci grafici coinvolti nel fare il diff.

Sezione 4 del documento introduce alcuni perfezionamenti dell'algoritmo che lo rendono molto efficace.

L'implementazione riuscita di questo ti lascerà uno strumento molto utile nella tua cassetta degli attrezzi (e probabilmente anche un'esperienza eccellente).

Generare il formato di output di cui hai bisogno a volte può essere complicato, ma se hai comprensione degli algoritmi interni, dovresti essere in grado di produrre tutto ciò di cui hai bisogno. Puoi anche introdurre l'euristica per influenzare la produzione e fare alcuni compromessi.

Ecco una pagina che include un po 'di documentazione, codice sorgente completo ed esempi di un algoritmo diff che utilizza le tecniche dell'algoritmo sopra menzionato.

Il codice sorgente sembra seguire da vicino l'algoritmo di base ed è facile da leggere.

C'è anche un po 'di preparazione dell'input, che potresti trovare utile. C'è un'enorme differenza nell'output quando si differenzia per carattere o token (parola).

Buona fortuna!

Answer 2

Vorrei iniziare guardando il codice sorgente attuale per diff, che GNU crea disponibile .

Per una comprensione di come funziona effettivamente quel codice sorgente, i documenti in quel pacchetto fanno riferimento ai documenti che lo hanno ispirato:

  

L'algoritmo di base è descritto in "Un algoritmo di differenza O (ND) e sue variazioni", Eugene W. Myers, "Algorithmica" Vol. 1 n. 2, 1986, pagg. 251-266; e in " A File   Programma di confronto " ;, Webb Miller ed Eugene W. Myers, "Software - Practice and Experience" Vol. 15 n. 11, 1985, pagg. 1025-1040. L'algoritmo è stato scoperto indipendentemente come descritto in "Algorithms for Approximate String Matching", E. Ukkonen, "Information and Control" Vol. 64, 1985, pagg. 100-118.

Leggere i documenti e poi guardare il codice sorgente per un'implementazione dovrebbe essere più che sufficiente per capire come funziona.

Answer 3

Vedi https://github.com/google/diff-match-patch

  

" Le librerie Diff Match e Patch   offrire solidi algoritmi per eseguire il   operazioni richieste per la sincronizzazione   testo semplice. ... Attualmente disponibile   in Java, JavaScript, C ++, C # e   Pitone "

Vedi anche la pagina Diff di wikipedia.org e - " Bram Cohen: il problema diff è stato risolto "

Answer 4

Sono venuto qui alla ricerca dell'algoritmo diff e successivamente ho realizzato la mia implementazione. Mi dispiace non so di vcdiff.

Wikipedia : da una sottosequenza comune più lunga è solo un piccolo passo per ottenere diff- come output: se un elemento è assente nella sottosequenza ma presente nell'originale, deve essere stato eliminato. (I segni '& # 8211;', sotto.) Se è assente nella sottosequenza ma presente nella seconda sequenza, deve essere stato aggiunto. (I segni '+'.)

Bella animazione dell'algoritmo LCS qui .

Link a una veloce implementazione di rubini LCS qui .

Il mio adattamento rubino lento e semplice è sotto.

def lcs(xs, ys)
  if xs.count > 0 and ys.count > 0
    xe, *xb = xs
    ye, *yb = ys
    if xe == ye
      return [xe] + lcs(xb, yb)
    end
    a = lcs(xs, yb)
    b = lcs(xb, ys)
    return (a.length > b.length) ? a : b
  end
  return []
end

def find_diffs(original, modified, subsequence)
  result = []
  while subsequence.length > 0
    sfirst, *subsequence = subsequence
    while modified.length > 0
      mfirst, *modified = modified
      break if mfirst == sfirst
      result << "+#{mfirst}"
    end
    while original.length > 0
      ofirst, *original = original
      break if ofirst == sfirst
      result << "-#{ofirst}"
    end
    result << "#{sfirst}"
  end
  while modified.length > 0
    mfirst, *modified = modified
    result << "+#{mfirst}"
  end
  while original.length > 0
    ofirst, *original = original
    result << "-#{ofirst}"
  end
  return result
end

def pretty_diff(original, modified)
  subsequence = lcs(modified, original)
  diffs = find_diffs(original, modified, subsequence)

  puts 'ORIG      [' + original.join(', ') + ']'
  puts 'MODIFIED  [' + modified.join(', ') + ']'
  puts 'LCS       [' + subsequence.join(', ') + ']'
  puts 'DIFFS     [' + diffs.join(', ') + ']'
end

pretty_diff("human".scan(/./), "chimpanzee".scan(/./))
# ORIG      [h, u, m, a, n]
# MODIFIED  [c, h, i, m, p, a, n, z, e, e]
# LCS       [h, m, a, n]
# DIFFS     [+c, h, +i, -u, m, +p, a, n, +z, +e, +e]

Answer 5

Sulla base del link che Emmelaich ha fornito, c'è anche una grande serie di strategie diff su il sito web di Neil Fraser (uno degli autori della biblioteca) .

Copre le strategie di base e verso la fine dell'articolo passa all'algoritmo di Myer e alla teoria dei grafi.