Bandingkan Teks Online — Diff Dua Teks

Algoritma diff modern didasarkan pada komputasi LCS (Longest Common Subsequence). Diberikan dua teks A dan B, algoritma menemukan urutan baris terpanjang yang muncul di keduanya dengan urutan yang sama. Baris dari A yang tidak termasuk LCS ditandai sebagai dihapus (merah), sedangkan baris dari B yang tidak termasuk ditandai sebagai ditambahkan (hijau). Algoritma Hunt-McIlroy tahun 1975 yang digunakan pada perintah diff Unix asli memformalkan pendekatan ini.

Hijau menandakan baris yang ditambahkan dalam teks baru yang tidak ada di teks asli. Merah menandakan baris yang dihapus dari teks asli dan tidak lagi ada. Kuning atau tanpa warna menandakan baris yang tidak berubah (konteks). Dalam mode diff per karakter, karakter baru dalam baris yang dimodifikasi disorot dengan hijau tua, sedangkan karakter yang dihapus disorot dengan merah tua, sehingga perubahan tepat dalam baris terlihat jelas.

Diff baris per baris memperlakukan setiap baris sebagai unit atomik: sebuah baris ada atau tidak ada, persis seperti yang dilakukan git diff. Cara ini ideal untuk kode di mana perubahan terjadi di seluruh baris. Diff karakter per karakter beroperasi di dalam setiap baris yang dimodifikasi dan menunjukkan karakter atau kata mana yang berubah. Cara ini lebih berguna untuk prosa, kontrak, atau teks di mana perubahan adalah suntingan kecil di dalam paragraf.

Diff sangat penting dalam kontrol versi seperti git diff yang menampilkan perubahan sebelum commit, tinjauan kode seperti pull request di GitHub, perbandingan dokumen hukum antara versi, jurnalisme dan pemeriksaan fakta dengan membandingkan versi siaran pers, serta debugging dengan membandingkan output yang diharapkan dan aktual dalam pengujian. Diff juga digunakan dalam patch perangkat lunak karena file .patch adalah unified diff yang dapat diterapkan oleh git apply.

LCS (Longest Common Subsequence) adalah masalah menemukan subsequence terpanjang yang dimiliki bersama oleh dua urutan tanpa menyusun ulang elemen. Untuk diff teks, urutannya adalah baris-baris teks. LCS mewakili baris yang tidak berubah; semua yang tidak ada dalam LCS adalah perubahan. Algoritma pemrograman dinamis standar untuk LCS memiliki kompleksitas O(n kali m) di mana n dan m adalah panjang kedua urutan, meski algoritma yang lebih efisien seperti Myers diff tahun 1986 mencapai O(n ditambah d) di mana d adalah jumlah perbedaan.