- Sedang diisi
- Dibaca
- Jawaban
Jarak edit (jarak Levenshtein)
Berapa banyak perubahan satu huruf untuk mengubah kitten menjadi sitting? Tiga: ganti k dengan s, ganti e dengan i, dan tambahkan g. Angka itu adalah jarak edit, cara pemeriksa ejaan mengurutkan saran dan cara ahli biologi membandingkan gen. Ketik dua kata dan lihat sebuah tabel menemukannya. Tekan Putar untuk melihat tabel terisi, atau Langkah dan Mundur untuk maju satu langkah demi satu langkah. Geser penggeser langkah untuk melompat ke mana saja. Ketik dua kata: kata pertama tersusun menurun di sisi tabel, kata kedua mendatar di bagian atas. Setiap sel menyimpan jumlah edit paling sedikit untuk mengubah huruf-huruf sampai barisnya menjadi huruf-huruf sampai kolomnya. Di akhir, edit-editnya dibaca balik dari sel kanan bawah. Contoh baru memilih pasangan kata lain. Saat papan dipilih, tombol panah melangkah, spasi memutar dan menjeda, serta Home dan End melompat ke awal dan akhir.
Cara kerjanya
- Ketik dua kata: kata pertama tersusun menurun di sisi tabel, kata kedua mendatar di bagian atas.
- Tekan Putar, atau gunakan Langkah dan Mundur untuk maju satu langkah demi satu langkah. Geser penggeser langkah untuk melompat ke mana saja.
- Lihat setiap sel mengambil yang termurah dari tiga tetangganya, lalu lihat edit-editnya dibaca balik dengan warna oranye.
Cara kerja tabel
Sebuah sel menyimpan jumlah edit paling sedikit untuk mengubah huruf-huruf kata pertama sampai barisnya menjadi huruf-huruf kata kedua sampai kolomnya. Baris pertama menghitung sisipan, membangun kata kedua dari nol, dan kolom pertama menghitung penghapusan. Jika dua huruf sebuah sel sama, sel itu menyalin sel di kiri atas: tidak perlu edit. Jika tidak, nilainya satu lebih besar dari yang terkecil di antara tiga tetangga: kiri atas untuk ganti, atas untuk hapus, dan kiri untuk sisip.
Membaca balik edit
Sel kanan bawah adalah jarak edit. Mulai dari sana, aplikasi mencari tetangga asal nilai sel itu lalu melangkah ke sana: diagonal untuk huruf yang dipertahankan atau diganti, ke atas untuk huruf yang dihapus, ke kiri untuk huruf yang disisipkan. Jika dibaca dari kiri atas, langkah-langkah itu adalah daftar edit terpendek, yang ditampilkan di bawah tabel: huruf biasa berarti dipertahankan, k→s berarti ganti, −e berarti hapus, dan +g berarti sisip.
Pertanyaan yang sering diajukan
Apa itu jarak Levenshtein?
Nama lain untuk jarak edit ini: jumlah paling sedikit sisipan, penghapusan, dan penggantian satu huruf untuk mengubah satu string menjadi string lain. Namanya diambil dari Vladimir Levenshtein, yang menjelaskannya pada tahun 1965.
Berapa jarak edit antara kitten dan sitting?
3: ganti k dengan s, ganti e dengan i, dan sisipkan g di akhir. Tabel menunjukkan bahwa tidak ada daftar edit yang lebih pendek.
Seberapa cepat algoritma jarak edit?
Untuk kata sepanjang m dan n, tabel memiliki (m + 1)·(n + 1) sel, masing-masing diisi dalam satu langkah, sehingga waktunya O(m·n). Jika hanya jaraknya yang diperlukan, dua baris tabel sudah cukup.
Ada jarak edit apa lagi?
Jarak Damerau–Levenshtein juga menghitung pertukaran dua huruf bersebelahan sebagai satu edit, yang cocok untuk salah ketik. Jarak Hamming hanya mengizinkan penggantian dan berlaku untuk string yang sama panjang. Jarak LCS hanya mengizinkan sisipan dan penghapusan.
Apakah ada data yang dikirim ke mana pun?
Tidak. Semuanya dihitung di browser Anda, dan pengaturan terakhir Anda tersimpan di penyimpanan lokal browser ini.
Siap mencobanya?
Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.
Ke Editor