Diff teks

Bagaimana diff bekerja

Membandingkan dua teks adalah masalah klasik dalam ilmu komputer: menemukan himpunan perubahan terkecil yang mengubah satu teks menjadi yang lain. Alat ini menyelesaikannya dengan algoritma subsekuens umum terpanjang (LCS): menemukan rangkaian baris (atau kata) terpanjang yang sama di kedua teks dalam urutan yang sama, dan sisanya dilaporkan sebagai penambahan atau penghapusan. Tanpa server, tanpa jaringan: hanya dua teks Anda dan sedikit pemrograman dinamis di browser Anda.

LCS algorithm

Diberi dua sekuens, LCS bertanya: apa subsekuens elemen terpanjang yang ada di keduanya, dengan urutan sama? Diatasi dengan pemrograman dinamis dalam O(n·m): sebuah tabel di mana tiap sel menyimpan jawaban terbaik untuk prefix hingga titik itu. Menelusuri tabel ke belakang menghasilkan perujukan — baris yang sama berpasangan, sisanya adalah penambahan dan penghapusan. Utilitas diff Unix yang terkenal memakai teknik yang sangat mirip.

Level baris vs level kata

Level baris menjalankan satu kali LCS pada baris utuh: cepat dan mudah dibaca, tetapi pengeditan satu kata pada baris panjang akan tampil sebagai "seluruh baris berubah". Level kata menambahkan sekali lagi: pasangan baris yang berubah dibandingkan ulang kata per kata, sehingga sorotan menunjuk tepat kata mana yang bergeser. Anggap ini sebagai zoom pada baris yang ditandai oleh passata pertama.

Pemakaian umum

Meninjau perubahan kode antara dua versi, membandingkan draf dokumen, mendeteksi typo antara dua salinan teks, atau memastikan perubahan file konfigurasi benar-benar sesuai niat. Penghitung (baris ditambahkan / baris dihapus) memberi estimasi cepat ukuran perubahan sebelum membaca detailnya.

Pertanyaan yang sering diajukan