Myers Visualizer

Masalahnya

Developer menjalankan git diff hampir setiap hari kerja, tapi hanya sedikit yang tahu cara kerjanya. Diff hanya terlihat sebagai hasil akhir. Tidak ada yang menunjukkan bahwa hasil itu lahir dari pencarian jalur terpendek di sebuah kisi.

Bagian yang membingungkan juga tidak pernah dijelaskan. Semua orang pernah melihat diff menempelkan kurung kurawal penutup ke fungsi yang salah, atau menampilkan "tambah 2 baris" sebagai "hapus 5, tambah 7". Orang menganggapnya keanehan biasa. Penyebab sebenarnya: kumpulan suntingan terpendek biasanya tidak tunggal, dan aturan pemecah seri di algoritma memilih salah satunya tanpa peduli mana yang enak dibaca. Itu juga alasan git menyertakan algoritma diff lain, seperti patience.

Saya membuat Myers Visualizer untuk developer, untuk mahasiswa dan pengajar pencarian graf, dan untuk siapa pun yang membaca makalah Eugene Myers tahun 1986 dan ingin diagramnya bergerak.

Yang saya bangun

Mesin diff saya tulis langsung dari makalahnya

Saya mengimplementasikan empat algoritma diff sendiri: Myers greedy, Myers versi hemat memori (linear-space), patience, dan histogram. Tidak ada pustaka diff di proyek ini. Mesinnya menerima dua teks dan opsi, lalu mengembalikan daftar suntingan, rekaman lengkap pencariannya, dan statistik. Tidak ada jam atau unsur acak, jadi input yang sama selalu memberi hasil yang sama. Karena pencarian direkam sekali, mundur selangkah tidak memakan biaya apa pun.

Pemeriksanya saya tulis sebelum algoritmanya

Sebelum kode Myers ditulis, saya menulis dua pemeriksa yang berdiri sendiri. Yang pertama menerapkan daftar suntingan ke teks pertama dan memastikan hasilnya sama dengan teks kedua. Yang kedua adalah pencarian brute-force yang lambat untuk menemukan jumlah suntingan minimum yang sebenarnya. Setiap algoritma, di setiap input, harus lolos keduanya. Tesnya tidak pernah menuntut dua algoritma menghasilkan suntingan yang sama, cukup jumlahnya yang sama, karena beberapa jawaban minimal bisa sama-sama benar.

Kisi digambar di canvas, pencarian jalan di latar

Graf suntingan adalah produknya, jadi uji gambar kisi 300×300 saya kerjakan sebelum kode algoritma apa pun. Kisi digambar di canvas, sehingga halaman tidak membuat satu elemen per sel. Setiap frame hanya menggambar ulang garis depan pencarian. Pencariannya sendiri jalan di worker latar dengan batas langkah, jadi preset kasus terburuk pun tidak bisa membekukan halaman.

Klaim setiap preset diuji

Dua klaim preset pertama saya ternyata salah saat saya periksa. Aturan pemecah seri di implementasi saya tidak menempelkan kurung ke fungsi yang salah pada input pertama yang saya coba. Keduanya saya ganti dengan input yang memang menunjukkan fenomenanya, dan sekarang kedelapan preset membuktikan klaimnya lewat tes. Aturan itu juga saya tulis di panduan kerja repo.

Situsnya saya susun ulang untuk orang yang belum pernah menjalankan git diff

Menjelang akhir, saya menyusun ulang halaman depan untuk pendatang baru. Halaman dibuka dengan pertanyaan, lalu contoh tanpa istilah teknis, gagasannya dalam tiga langkah, dan alasan diff bisa salah menunjuk baris. Notasi dan glosarium baru muncul di akhir. Kisinya juga diberi label sumbu, karena pendatang baru yang salah menebaknya akan membaca seluruh gambar secara terbalik.

Hasilnya

Myers Visualizer sudah live, publik, dan open source. Situs ini bisa dipasang seperti aplikasi dan tetap jalan offline setelah kunjungan pertama. Situs menampilkan graf suntingan saat terisi, memori kerja algoritma di sebelahnya, berapa banyak jawaban yang sama-sama minimal, dan perbandingan keempat algoritma. Di contoh situsnya sendiri, keempatnya butuh 5 suntingan, dan patience tetap memangkas jumlah blok perubahan menjadi separuh.

Kisi 300×300 berjalan di 59,9 frame per detik. Di batas input, kasus terburuk butuh 135.152 langkah pencarian dan halaman tetap responsif. Tersedia dalam bahasa Inggris dan Indonesia. Saya membangunnya dalam dua hari pada Agustus 2026.