Kemungkinan peningkatan Damerau-Levenshtein?

Saya baru-baru ini mengimplementasikan algoritma jarak Damerau-Levenshtein dari pseudocode di Wikipedia. Saya tidak bisa menemukan penjelasan persis bagaimana kerjanya dan pseudocode menggunakan nama variabel yang sama sekali tidak informatif seperti DA, DB, i1, dan j1yang meninggalkan aku menggaruk-garuk kepala.

Inilah implementasi saya dengan Python: https://gist.github.com/badocelot/5327337

Implementasi Python membantu saya menelusuri program dan mencari tahu apa yang terjadi, mengubah nama variabel menjadi nama yang lebih bermanfaat. Saya cukup akrab dengan pendekatan Wagner-Fischer untuk menghitung jarak Levenshtein sehingga saya memiliki kerangka referensi.

Dengan risiko terlalu panjang, inilah cara saya memahami Damerau-Levenshtein:

Variabel misteri:

• DA( last_rowdalam kode saya) adalah semacam peta yang menahan baris terakhir setiap elemen terlihat; dalam kode saya ini adalah kamus Python yang sebenarnya
• DB( last_match_col) memegang kolom terakhir tempat huruf dalam bcocok dengan huruf auntuk baris saat ini
• i1( last_matching_row) adalah nomor baris dari DAuntuk huruf saat ini dib
• j1hanyalah salinan dari nilai DB/ last_match_colsebelum berpotensi diperbarui; dalam kode saya, saya baru saja pindah tempat last_match_coldiperbarui dan dihilangkan variabel ini

Biaya transposisi:

H[i1][j1] + (i-i1-1) + 1 + (j-j1-1)

menghitung biaya pertukaran karakter saat ini bdengan karakter terakhir yang bdiketahui berada a(pertandingan terakhir), memperlakukan semua karakter di antaranya sebagai penambahan atau penghapusan.

Komponen biaya:

• H[i1][j1] mengembalikan biaya pokok ke titik dalam perhitungan sebelum transposisi, karena menemukan transposisi membatalkan pekerjaan sebelumnya
• (i-i1-1) adalah jarak antara baris saat ini dan baris terakhir yang cocok dengan karakter saat ini, yang merupakan jumlah penghapusan yang akan diperlukan
• (j-j1-1) adalah jarak antara kolom saat ini dan kolom terakhir dengan kecocokan, yang merupakan jumlah penambahan
• Ekstra + 1hanyalah biaya transposisi itu sendiri

Jika analisis ini salah, saya ingin tahu di mana kesalahan saya. Seperti yang saya katakan, saya tidak bisa menemukan apapun penjelasan rinci tentang bagaimana algoritma bekerja secara online.

Versi yang ditingkatkan?

Setelah tahu bahwa, meskipun, aku tersadar bahwa dengan menghitung biaya baik penambahan dan penghapusan antara huruf dialihkan tampak cacat: satu tambahan dan satu penghapusan setara dengan substitusi, yang ini tidak memeriksa.

Jika semua itu benar, solusinya harus sepele: biaya huruf antara huruf yang dialihkan harus lebih tinggi dari penambahan dan penghapusan: konversi sebanyak mungkin menjadi substitusi dan tambahkan dalam setiap penambahan atau penghapusan yang tersisa.

Jadi biayanya adalah:

H[i1][j1] + max((i-i1-1), (j-j1-1)) + 1

Ini kode saya untuk versi ini: https://gist.github.com/badocelot/5327427

Dari beberapa tes sederhana, ini tampaknya benar. Misalnya, "abcdef" -> "abcfad" memberikan jarak sunting 2 (ubah "d" dan "f", ubah "e" menjadi "a"), sedangkan algoritma asli memberikan jarak 3 (baik tiga terakhir) huruf adalah substitusi, atau 1 transposisi + 1 penambahan + 1 penghapusan).

Sekarang, saya tidak bisa menjadi orang pertama yang memikirkan hal ini. Jadi, mengapa saya tidak berlari melewatinya? Apakah saya tidak mencari cukup lama? Atau adakah beberapa cacat halus yang mencegah ini bekerja?

Saya harus mencari jarak Damerau-Levenshtein di wikipedia, jadi maafkan saya jika ini salah. Tapi sepertinya itu hanya memungkinkan untuk mentransposisi huruf yang berdekatan dan tidak ada yang sewenang-wenang. Jadi contoh Anda "abcdef" -> "abcfad" dengan transposif dari d dan f tidak bekerja. Menurut saya, Anda telah memodifikasi definisi algoritma dan tidak lagi menghitung jarak Damerau-Levenshtein.