Jarak edit (jarak Levenshtein)

Ketik recieve dan ponsel Anda menyarankan receive. Ponsel tahu Anda hampir benar karena kedua kata itu hanya berjarak beberapa edit. Mengukur kedekatan itu, yaitu jarak edit, adalah tugas klasik pemrograman dinamis.

Tabel dengan satu kata menurun di sisi dan kata lain mendatar di atas, angka di sel-selnya, dan jalur edit oranye dari sudut kiri atas ke sudut kanan bawah
Tabel dengan satu kata menurun di sisi dan kata lain mendatar di atas, angka di sel-selnya, dan jalur edit oranye dari sudut kiri atas ke sudut kanan bawah

Masalahnya

Satu edit mengubah kata sebanyak satu huruf: menyisipkan huruf, menghapus huruf, atau mengganti satu huruf dengan huruf lain. Jarak edit antara dua kata adalah jumlah edit paling sedikit untuk mengubah satu kata menjadi kata lainnya. Jarak cat dan cut adalah 1, cat dan cast 1, sedangkan cat dan act 2. Jarak ini juga disebut jarak Levenshtein, dari nama matematikawan Soviet Vladimir Levenshtein yang mempelajarinya pada tahun 1965.

Tabelnya

Misalkan d[i][j] adalah jarak edit antara i huruf pertama satu kata dan j huruf pertama kata lainnya. Mengubah kata menjadi kosong butuh satu penghapusan per huruf, jadi d[i][0] = i, dan membangun kata dari nol butuh satu sisipan per huruf, jadi d[0][j] = j. Jika huruf ke-i sama dengan huruf ke-j, d[i][j] = d[i − 1][j − 1]. Jika tidak, d[i][j] = 1 + yang terkecil dari d[i − 1][j − 1] (ganti), d[i − 1][j] (hapus), dan d[i][j − 1] (sisip).

Sebuah contoh

Untuk kitten dan sitting, tabelnya memiliki 7 baris dan 8 kolom. Sel kanan bawah bernilai 3, dan membaca balik dari sana menghasilkan: ganti k dengan s, pertahankan i, t, dan t, ganti e dengan i, pertahankan n, lalu sisipkan g. Kitten, sitten, sittin, sitting: tiga edit, dan tabel membuktikan bahwa tidak ada daftar yang lebih pendek.

Membaca balik edit

Mulailah dari sel kanan bawah dan tanyakan dari tetangga mana nilainya berasal. Jika hurufnya cocok dan sel itu sama dengan tetangga kiri atasnya, huruf itu dipertahankan: melangkahlah secara diagonal. Jika nilainya satu lebih besar dari tetangga kiri atas, itu penggantian; satu lebih besar dari sel di atas, penghapusan; satu lebih besar dari sel di kiri, sisipan. Beberapa jalur bisa seri, dan masing-masing memberi daftar edit terpendek.

Sejarah dan kegunaan

Levenshtein memperkenalkan jarak ini pada tahun 1965 saat meneliti kode pengoreksi galat. Metode tabelnya diterbitkan oleh beberapa orang, yang paling terkenal oleh Robert Wagner dan Michael Fischer pada tahun 1974, sehingga sering disebut algoritma Wagner–Fischer. Kini jarak edit dipakai untuk mengurutkan saran ejaan, mencocokkan nama yang salah ketik di basis data, membandingkan sekuens DNA dan protein, serta menilai pengenalan suara.

Jelajahi

Buka aplikasinya dan tekan Langkah. Dua huruf yang sedang dibandingkan menyala di judul baris dan kolom; huruf yang sama menyalin sel biru di kiri atas, sedangkan huruf yang berbeda membaca ketiga tetangga biru lalu menambahkan satu pada yang terkecil. Di akhir, jalur oranye berjalan balik dari sudut, dan edit-editnya muncul di bawah tabel.

Pertanyaan yang sering diajukan

Apakah jarak edit merupakan metrik?

Ya. Nilainya tidak pernah negatif, bernilai 0 hanya untuk kata yang sama, sama di kedua arah, dan melewati kata ketiga tidak pernah membuatnya lebih pendek: d(a, c) ≤ d(a, b) + d(b, c). Karena itu jarak edit berguna untuk mencari kecocokan yang dekat.

Apa itu jarak Damerau–Levenshtein?

Jarak edit dengan satu jenis edit tambahan: menukar dua huruf yang bersebelahan. Pada tahun 1964 Frederick Damerau menemukan bahwa sisip, hapus, ganti, dan tukar bersama-sama mencakup lebih dari 80% kesalahan ejaan. Dengan pertukaran, jarak recieve dan receive adalah 1, bukan 2.

Bisakah jarak edit dihitung lebih cepat dari O(m·n)?

Tidak jauh lebih cepat. Pada tahun 2015 Arturs Backurs dan Piotr Indyk menunjukkan bahwa metode yang memerlukan waktu O(n^(2 − ε)) untuk suatu ε > 0 akan mematahkan hipotesis waktu eksponensial kuat, yang diyakini sebagian besar peneliti. Namun, untuk kata-kata yang mirip, hanya diperlukan pita sempit di sekitar diagonal tabel.

Bagaimana jarak edit digunakan dalam perbandingan DNA?

Ahli biologi memakai tabel yang sama dengan skor, bukan hitungan: kecocokan mendapat poin, sedangkan penggantian dan celah mengurangi poin yang bergantung pada hurufnya. Itulah algoritma Needleman–Wunsch tahun 1970 untuk sekuens utuh, dan algoritma Smith–Waterman tahun 1981 untuk bagian yang paling cocok.

Siap mencobanya?

Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.

Coba jarak edit