Bagaimana komputer tahu apa yang berubah?

Apa itu diff?

Diff adalah daftar perubahan terkecil yang mengubah satu teks menjadi teks lain. Dua daftar belanja ini hampir sama — hanya satu baris yang berbeda.

Tanda − berarti dihapus, tanda + berarti ditambahkan, sisanya tidak berubah. Pertanyaan sesungguhnya: bagaimana komputer memutuskan bahwa itu satu penggantian, bukan menghapus lima baris lalu menulis lima baris baru?

Cara kerjanya, dalam tiga langkah

Tidak ada matematika di bagian ini. Ini seluruh idenya.

1. 1

   Susun jadi kisi

   Teks lama ditulis mendatar, teks baru menurun. Setiap titik pada kisi berarti "sudah memakai sekian baris lama dan sekian baris baru". Perubahan menjadi soal mencari jalan dari pojok kiri atas ke pojok kanan bawah.

2. 2

   Cari jalan termurah

   Melangkah ke kanan berarti menghapus satu baris lama. Ke bawah berarti menyisipkan satu baris baru. Menyusuri diagonal gratis — itu baris yang sama persis di kedua sisi. Diff terbaik adalah jalur dengan langkah berbayar paling sedikit.

3. 3

   Baca jalurnya

   Jalur yang menang diterjemahkan kembali menjadi daftar − dan + yang biasa Anda lihat. Kanan menjadi baris terhapus, bawah menjadi baris tersisip, diagonal menjadi baris yang dibiarkan.

Untuk yang ingin detailnya

Diberi dua urutan A (panjang N) dan B (panjang M), bentuk sebuah edit graph: kisi (N+1) × (M+1) titik, di mana titik (x, y) berarti "sudah memakai x elemen A dan y elemen B". Diff adalah jalur dari (0,0) ke (N,M). Edit script terpendek adalah jalur dengan langkah non-diagonal paling sedikit.

Kenapa k, dan kenapa itu yang membuatnya cepat

Perhatikan kolom terakhir. Langkah diagonal menambah x dan y sekaligus, jadi k = x − y tidak berubah — gratis dan tetap di jalur yang sama. Hanya langkah berbayar yang memindahkan k, tepat satu ke kanan atau ke kiri. Akibatnya: setelah d suntingan, hanya diagonal −d sampai +d yang bisa dijangkau, dan pada tiap diagonal cukup disimpan satu angka — titik terjauh yang dicapai. Di situlah kisi (N+1)×(M+1) menyusut jadi satu baris berisi paling banyak 2d+1 angka, dan pencarian jadi O((N+M)·D), bukan O(N·M). Myers §2.

Satu pencarian, dengan angkanya

Dua daftar belanja yang tadi, dijalankan sampai selesai. Tidak ada kontrol di bagian ini — hanya nilai yang benar-benar dihasilkan algoritma di tiap tingkat d.

1. d = 0

   (2, 2)

   Mulai dari (0,0). "susu" dan "telur" sama di kedua sisi, jadi keduanya dilalui gratis menuruni diagonal sampai (2,2). Belum ada yang dibayar, dua baris sudah beres.

   V sesudahnyak0 x 2

2. d = 1

   Satu suntingan dibolehkan, jadi dua diagonal terbuka dari (2,2). Ke kanan berarti menghapus "gula" dan mendarat di (3,2); ke bawah berarti menyisipkan "garam" dan mendarat di (2,3). Tidak ada yang cocok sesudahnya, jadi tidak ada yang meluncur, dan tidak satu pun sampai di (5,5).

   V sesudahnyak-1 x 2k0 x 2k1 x 3

3. d = 2

   (5, 5)

   Dua suntingan. Dari (3,2) langkah ke bawah menyisipkan "garam" dan mendarat di (3,3) — di sana "roti" dan "kopi" sama, jadi keduanya gratis sampai (5,5). Selesai.

   V sesudahnyak-2 x 2k-1 x 2k0 x 5k1 x 3

D = 2: satu baris dihapus, satu disisipkan, empat dibiarkan. Itulah diff yang Anda lihat di atas.

Istilah

Istilah algoritma sengaja dibiarkan dalam bahasa Inggris supaya Anda mengenalinya lagi di paper dan di kode. Ini terjemahannya ke bahasa manusia.

diff

Daftar perubahan antara dua teks — baris apa yang dihapus, apa yang ditambah.

edit script

Urutan langkah yang mengubah A menjadi B. Itulah "jawaban" yang dicari.

edit graph

Kisi yang menjadi papan pencariannya. Satu sumbu untuk teks lama, satu untuk teks baru.

D

Berapa banyak langkah berbayar dalam jawaban — jumlah baris yang dihapus ditambah yang disisipkan. Makin kecil makin ringkas.

snake

Deretan baris yang sama persis di kedua sisi, dilalui gratis. Di gambar tampak sebagai garis miring.

frontier

Sejauh mana pencarian sudah sampai. Ia memuai selangkah demi selangkah — itu bagian yang bergerak.

diagonal k

Nomor jalur miring pada kisi, k = x − y. Cara algoritma menyebut "sedang di garis miring yang mana".

array V

Catatan kecil berisi titik terjauh yang dicapai pada setiap diagonal. Ini satu-satunya data yang benar-benar disimpan algoritma.

backtrack

Fase kedua. Setelah pencarian sampai di pojok, jalurnya dibaca mundur dari V yang direkam — itulah yang mengubah "jaraknya sekian" menjadi daftar baris yang sebenarnya.

tie-breaking

Apa yang terjadi ketika dua langkah sama-sama bagus. Aturannya sewenang-wenang tetapi tetap — dan aturan itulah yang menentukan diff mana dari beberapa yang sama pendeknya yang Anda lihat.

hunk

Satu blok perubahan yang berdekatan dalam sebuah diff, beserta beberapa baris konteks di sekitarnya. Diff yang sama bisa muncul sebagai satu hunk atau beberapa; lebih sedikit biasanya lebih enak dibaca.

tokenize

Mengubah teks menjadi daftar angka sebelum dibandingkan — satu angka per baris, kata, atau karakter. Yang dihitung sebagai "elemen" adalah pilihan Anda, dan pilihan itu mengubah jawabannya.

O(...)

Cara ringkas menyebut pertumbuhan biaya seiring membesarnya masukan, mengabaikan konstanta. O(N·M) berarti "sebanding dengan hasil kali kedua panjang"; O((N+M)·D) berarti "sebanding dengan jumlahnya dikali besar perubahan" — jauh lebih kecil bila perubahannya kecil.