Come realizzare una funzione diff?

Question

Come posso implementare una funzione diff , come la cronologia delle revisioni delle domande di Stack Overflow?

Answer 1

Hai qui un esempio javascript dell'implementazione di un algoritmo diff.

Basato su:

P. Heckel, una tecnica per isolare le differenze tra i file Comm. ACM, 21, (4), 264-268 (1978).

L'implementazione, di per sé, ha due funzioni, una delle quali è consigliata per l'uso:

diffString( String oldFile, String newFile )

Questo metodo prende due stringhe e calcola le differenze in ciascuna. Il risultato finale è il 'newFile' contrassegnato con HTML (per indicare sia le eliminazioni dal vecchio file sia le aggiunte al nuovo file).

Answer 2

Vorrei trovare il codice per l'utility diff di FreeBSD e usarlo come base. Non ha senso reinventare le ruote quando la licenza consente questo tipo di copia.

Answer 3

La maggior parte degli algoritmi si basa su LCS: Sottosequenza comune più lunga . Non è ovvio implementarlo in modo efficiente. Probabilmente troverai varie implementazioni in rete, per varie lingue.

Answer 4

Immagino che l'unico modo sarebbe quello di confrontare ogni personaggio formando le 2 stringhe. Qualcosa del genere:

void diff(String first,String second) {
   int biggest = (first.length() > second.length()) ? first.length() : second.length();
   for(int i = 0;i < biggest;i++) {
      //compare each char from the longest string with each char from the shorter
      // do something with them if they're not equal
   }
}

Questo è solo uno schizzo di come lo farei. Tutto dipende da cosa vuoi fare con i dati.

Answer 5

Se quello che vuoi è la cronologia delle revisioni, non reinventare la ruota a partire da diff. Basta gettare tutto nel controllo della versione e utilizzare le sue funzionalità di diff e registrazione. Per una storia semplice e lineare, qualcosa di semplice come RCS farà. Oppure puoi lanciarci l'ultimo cannone e usare git .

La maggior parte delle utility diff fa una differenza riga per riga. Stack Overflow fa una diff parola per parola. Per questo è necessario qualcosa come wdiff . La maggior parte dei sistemi di controllo versione consente di collegare l'utilità diff. Fuori dalla scatola, git diff --color-words si avvicina notevolmente a ciò che viene fatto qui. Con un po 'di confusione con le impostazioni, puoi probabilmente farlo sputare qualcosa che puoi trasformare in una bella pagina web.