Dove posso trovare l'algoritmo diff?

Question

Dove posso trovare una spiegazione e l'implementazione dell'algoritmo di diff?

Prima di tutto devo riconoscere che non sono sicuro se questo è il nome corretto dell'algoritmo. Ad esempio, in che modo Overflow dello stack contrassegna le differenze tra due modifiche della stessa domanda?

PS: conosco i linguaggi di programmazione C e PHP.

Answer 1

Non esiste realmente "l'algoritmo di diff". Esistono molti algoritmi di diff differenti e in effetti i particolari algoritmi di diff usati in alcuni casi sono considerati un vantaggio commerciale del particolare strumento diff.

In generale, molti algoritmi di diff sono basati sul problema LCS (Longest Common Successive).

Il programma originale Unix diff degli anni '70 è stato scritto da Doug McIllroy e utilizza il cosiddetto algoritmo Hunt-McIllroy. Quasi 40 anni dopo, le estensioni e i derivati ​​di quell'algoritmo sono ancora molto comuni.

Un paio di anni fa, Bram Cohen (creatore del programma di filesharing di maggior successo e il sistema di controllo versione meno riuscito) ha creato il Patience Diff algorithm che è stato progettato per dare risultati più leggibili rispetto LCS. È stato originariamente implementato nel Bazar VCS e anche aggiunto a Git come opzione.

Tuttavia, a meno che tu non sia interessato alla ricerca sugli algoritmi di diff, la tua migliore scommessa sarebbe probabilmente quella di usare solo una libreria diff esistente come Davide Libenzi's LibXDiff, che è ad esempio ciò che Git usa. Non sarei troppo sorpreso se ci fosse già un'estensione PHP che lo avvolge. Una buona alternativa è Google's Diff-Match-Patch library, che viene utilizzata in Bespin o WhiteRoom, ad esempio e che è disponibile per molte lingue. Utilizza l'algoritmo Diff Meyers più alcuni pre e post-elaborazione per ulteriori accelerazioni.

Un approccio completamente diverso, se si è più interessati alla fusione rispetto alla diffusione, si chiama Trasformazioni operative. L'idea di OT è che invece di capire le differenze tra due documenti, provi a "decodificare" le operazioni che hanno portato a queste differenze. Ciò consente una fusione molto migliore, perché è quindi possibile "riprodurre" tali operazioni. Questi sono più utili per editor collaborativi in ​​tempo reale come EtherPad, Google Wave o SubEthaEdit.

Answer 2

Cosa c'è che non va con wikipedia dove si afferma che è Hunt-McIlroy algorithm?

C'è l'OCR paper che descrive l'algoritmo (spiegazione) ed è possibile ispezionare source (implementazione).

Le domande in modo connesse anche l'elenco (tra gli altri):
'Best' Diff Algorithm
How do document diff algorithms work?
Diff Algorithm
cui tutti sembrano essere utile.