Program pembanding teks tidak membaca lalu menilai "apa yang berubah" seperti manusia. Sebaliknya, ia mencari cara mengubah satu daftar menjadi daftar lain dengan jumlah penghapusan dan penambahan sesedikit mungkin. Artikel ini menjelaskan bagaimana diff menghitung jawaban itu, dan mengapa hasilnya kadang berbeda dari yang diharapkan manusia.
Satuan perbandingan: baris, kata, karakter
diff pertama-tama memecah teks menjadi daftar token. diff tradisional dan git menganggap satu baris sebagai satu token. Karena itu, meskipun hanya satu karakter yang berubah dalam sebuah baris, seluruh baris itu ditampilkan sebagai "hapus 1 baris + tambah 1 baris".
Perbandingan per baris cepat dan cocok untuk tinjauan kode, tetapi pada dokumen yang satu paragraf panjangnya ditulis dalam satu baris, sulit menemukan bagian yang berubah. Karena itu banyak alat membandingkan dalam dua tahap.
- Bandingkan per baris untuk menemukan baris yang berubah.
- Pasangkan baris-baris yang berubah, lalu bandingkan isinya sekali lagi per kata atau per karakter.
Situs ini juga memakai cara yang sama. Satuan perbandingan di dalam baris dapat dipilih: kata, potongan antarspasi, atau karakter.
Subbarisan bersama terpanjang (LCS)
Inti matematis diff adalah subbarisan bersama terpanjang (Longest Common Subsequence, LCS). Subbarisan adalah sebagian elemen yang dipilih dengan tetap menjaga urutannya. Misalnya, subbarisan bersama terpanjang dari ABCABBA dan CBABAC panjangnya 4, contohnya CABA atau BABA.
Elemen yang masuk ke LCS adalah "yang tetap", sedangkan sisanya adalah "yang dihapus" (hanya ada di kiri) atau "yang ditambah" (hanya ada di kanan). Makin panjang LCS, makin sedikit penghapusan dan penambahan. Jika panjang kedua daftar adalah N dan M, dan panjang LCS adalah L, jumlah penghapusan dan penambahan D adalah sebagai berikut.
D = (N - L) + (M - L)Pada contoh di atas N=7, M=6, L=4, sehingga D = 3 + 2 = 5. D ini disebut jarak edit (jika hanya penyisipan dan penghapusan yang diizinkan), dan daftar penghapusan serta penambahannya disebut skrip edit (edit script).
Graf edit dan algoritma Myers
Jika LCS dicari dengan cara buku teks (pemrograman dinamis), dibutuhkan tabel berukuran N×M. Membandingkan dua file masing-masing 10.000 baris berarti 100 juta sel — lambat dan boros memori. Pada 1986, Eugene W. Myers dalam makalah "An O(ND) Difference Algorithm and Its Variations" mengajukan cara yang lebih cepat, yang menjadi dasar algoritma bawaan GNU diff dan git saat ini.
Myers mengubah perbandingan menjadi pencarian jalur terpendek pada sebuah kisi.
- Jalur bergerak dari pojok kiri atas (0,0) ke pojok kanan bawah (N,M).
- Satu langkah ke kanan = menghapus satu elemen teks kiri, satu langkah ke bawah = menambah satu elemen teks kanan. Biayanya 1.
- Pada sel tempat kedua elemen sama, Anda bisa bergerak diagonal tanpa biaya. Ruas diagonal yang bersambung seperti ini disebut snake.
Jalur dengan biaya terkecil adalah skrip edit terpendek. Algoritma Myers berturut-turut memperluas "titik terjauh yang bisa dicapai dengan biaya 0", "titik terjauh dengan biaya 1", dan seterusnya, lalu berhenti saat mencapai titik akhir. Di setiap tahap cukup mengingat satu posisi terjauh untuk tiap diagonal, sehingga waktu yang dibutuhkan kira-kira sebanding dengan (N+M)×D. Jika kedua teks hampir sama, D kecil dan algoritmanya sangat cepat; jika sama sekali berbeda, algoritmanya melambat.
Memori linear dan middle snake
Untuk menelusuri kembali jalurnya, catatan setiap tahap harus disimpan, sehingga memori bisa bertambah sebanding dengan D². Dalam makalah yang sama, Myers juga mengajukan varian yang menjalankan pencarian dari depan dan dari belakang secara bersamaan hingga keduanya bertemu di sebuah ruas diagonal (middle snake). Dengan membagi masalah di titik itu menjadi dua masalah yang lebih kecil dan mengulanginya, memori yang dipakai hanya sebanding dengan ukuran masukan.
Saat biayanya terlalu mahal: heuristik perkiraan
Jika kedua masukan berisi puluhan ribu baris dan sangat berbeda, D juga besar sehingga (N+M)×D bisa mencapai miliaran. Untuk mengantisipasinya, GNU diff memiliki heuristik yang, bila tahap pencarian melewati batas tertentu, memotong masalah di diagonal yang sejauh ini paling jauh majunya. Hasilnya tetap skrip edit yang benar, tetapi tidak ada jaminan bahwa itu yang terpendek. Opsi --minimal pada GNU diff maupun git memaksa pencarian hasil minimal meskipun memakan waktu lebih lama.
Minimal tidak selalu enak dibaca
Bisa ada beberapa jalur dengan jarak edit yang sama. Misalnya, jika Anda menambahkan satu fungsi ke kode, kurung kurawal penutup } dan baris kosong ada di banyak tempat, sehingga algoritma bisa memasangkan "} milik fungsi baru" dengan "} milik fungsi lama". Hasilnya minimal, tetapi terlihat janggal bagi manusia. Inilah alasan git secara bawaan memakai heuristik yang menggeser batas perubahan berdasarkan indentasi, dan menyediakan algoritma lain seperti patience dan histogram. Perbandingan lengkapnya dibahas di Perbandingan algoritma diff.
Di alat ini
Mesin perbandingan di situs ini mengimplementasikan varian memori linear dari algoritma Myers dengan JavaScript, dan beralih ke pembagian perkiraan dengan cara yang sama seperti GNU diff jika masukannya besar. Perhitungan berjalan di Web Worker, jadi layar tidak macet meskipun file besar dimasukkan. Setelah hasil per baris keluar, baris berubah yang isinya mirip dipasangkan dan ditandai sebagai "diubah", lalu isinya dibandingkan sekali lagi dengan satuan yang dipilih (kata, potongan, atau karakter) dan disorot.
Coba masukkan dua teks di Pembanding Teks dan ubah satuan perbandingan dalam baris untuk melihat bagaimana hasilnya berubah. Untuk membaca hasil dalam format git, lihat Cara membaca unified diff.