Algoritma Diff? [Tutup]

Saya sudah tampak gila untuk penjelasan tentang algoritma diff yang bekerja dan efisien.

Yang paling dekat yang saya dapatkan adalah tautan ini ke RFC 3284 (dari beberapa posting blog Eric Sink), yang menjelaskan secara termudah dimengerti format data di mana hasil yang berbeda disimpan. Namun, tidak disebutkan sama sekali tentang bagaimana suatu program akan mencapai hasil ini saat melakukan perbedaan.

Saya mencoba untuk meneliti ini karena keingintahuan pribadi, karena saya yakin pasti ada kompromi ketika menerapkan algoritma diff, yang kadang-kadang cukup jelas ketika Anda melihat diffs dan bertanya-tanya "mengapa program diff memilih ini sebagai perubahan bukannya itu? "...

Di mana saya dapat menemukan deskripsi algoritma yang efisien yang pada akhirnya menghasilkan VCDIFF?
Omong-omong, jika Anda menemukan deskripsi algoritma aktual yang digunakan oleh SourceGear's DiffMerge, itu akan lebih baik.

CATATAN: urutan umum terpanjang tampaknya bukan algoritma yang digunakan oleh VCDIFF, sepertinya mereka melakukan sesuatu yang lebih cerdas, mengingat format data yang mereka gunakan.

Algoritma Perbedaan O (ND) dan Variasi-nya adalah makalah yang fantastis dan Anda mungkin ingin memulainya. Ini termasuk pseudo-code dan visualisasi yang bagus dari grafik traversal yang terlibat dalam melakukan diff.

Bagian 4 dari makalah ini memperkenalkan beberapa penyempurnaan pada algoritma yang membuatnya sangat efektif.

Berhasil menerapkan ini akan meninggalkan Anda dengan alat yang sangat berguna di kotak alat Anda (dan mungkin beberapa pengalaman yang sangat baik juga).

Menghasilkan format output yang Anda butuhkan kadang-kadang bisa rumit, tetapi jika Anda memiliki pemahaman tentang algoritma internal, maka Anda harus dapat menampilkan apa pun yang Anda butuhkan. Anda juga dapat memperkenalkan heuristik untuk mempengaruhi output dan melakukan pengorbanan tertentu.

Berikut adalah halaman yang menyertakan sedikit dokumentasi, kode sumber lengkap , dan contoh-contoh algoritma diff menggunakan teknik-teknik dalam algoritma yang disebutkan di atas.

The kode sumber tampaknya mengikuti algoritma dasar dekat dan mudah dibaca.

Ada juga sedikit persiapan input, yang menurut Anda berguna. Ada perbedaan besar dalam output ketika Anda berbeda berdasarkan karakter atau token (kata).

Semoga berhasil!

Saya akan mulai dengan melihat kode sumber aktual untuk diff, yang disediakan oleh GNU .

Untuk pemahaman tentang bagaimana kode sumber itu benar-benar bekerja, dokumen dalam paket itu merujuk makalah yang menginspirasi itu:

Algoritma dasar dijelaskan dalam "Algoritma Perbedaan O (ND) dan Variasi-variasinya", Eugene W. Myers, Vol 'Algorithmica'. 1 No. 2, 1986, hlm. 251-266; dan dalam "Program Perbandingan File", Webb Miller dan Eugene W. Myers, 'Software - Practice and Experience' Vol. 15 No. 11, 1985, hlm. 1025-1040. Algoritma ini ditemukan secara independen seperti yang dijelaskan dalam "Algoritma untuk Pencocokan String Perkiraan", E. Ukkonen, `Information and Control 'Vol. 64, 1985, hlm. 100-118.

Membaca makalah kemudian melihat kode sumber untuk implementasi harus lebih dari cukup untuk memahami cara kerjanya.

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

"Perpustakaan Diff Match dan Patch menawarkan algoritma yang kuat untuk melakukan operasi yang diperlukan untuk menyinkronkan teks biasa. ... Saat ini tersedia di Java, JavaScript, C ++, C #, dan Python"

Juga lihat halaman wikipedia.org Diff dan - " Bram Cohen: Masalah diff telah dipecahkan "

Saya datang ke sini mencari algoritma diff dan kemudian membuat implementasi sendiri. Maaf saya tidak tahu tentang vcdiff.

Wikipedia : Dari urutan umum terpanjang, hanya langkah kecil untuk mendapatkan keluaran seperti-berbeda: jika item tidak ada di bagian berikutnya tetapi ada dalam aslinya, item itu pasti sudah dihapus. (Tanda '-', di bawah.) Jika tidak ada di urutan berikutnya tetapi ada di urutan kedua, harus ditambahkan di. (Tanda '+'.)

Animasi yang bagus dari algoritma LCS di sini .

Tautan ke implementasi ruby ​​LCS cepat di sini .

Adaptasi ruby ​​saya yang lambat dan sederhana ada di bawah ini.

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]

Berdasarkan tautan yang diberikan Emmelaich, ada juga sejumlah besar Diff Strategies di situs web Neil Fraser (salah satu penulis perpustakaan) .

Dia membahas strategi dasar dan menjelang akhir artikel berlanjut ke algoritma Myer dan beberapa teori grafik.