Pertama, jarak Levenshtein didefinisikan sebagai jumlah minimum pengeditan yang diperlukan untuk mengubah string A ke string B, di mana pengeditan adalah penyisipan, atau penghapusan satu karakter, atau penggantian karakter dengan karakter lain. Jadi ini adalah "perbedaan antara dua string", untuk definisi jarak tertentu. =)
Sepertinya Anda sedang mencari fungsi jarak F(A, B) yang memberikan jarak antara string A dan B dan ambang N di mana string dengan jarak kurang dari N satu sama lain adalah kandidat untuk kesalahan ketik. Selain jarak Levenshtein, Anda juga dapat mempertimbangkan Needleman–Wunsch . Ini pada dasarnya adalah hal yang sama tetapi memungkinkan Anda menyediakan fungsi untuk seberapa dekat karakter tertentu dengan karakter lain. Anda dapat menggunakan algoritme itu dengan serangkaian bobot yang mencerminkan posisi tombol pada keyboard QWERTY untuk melakukan pekerjaan yang cukup baik dalam menemukan kesalahan ketik. Ini akan memiliki masalah dengan keyboard internasional.
Jika Anda memiliki k string dan Anda ingin menemukan kemungkinan kesalahan ketik, jumlah perbandingan yang perlu Anda buat adalah O(k^2). Selain itu, setiap perbandingan adalah O(len(A)*len(B)). Jadi, jika Anda memiliki sejuta string, Anda akan menemukan diri Anda dalam masalah jika Anda melakukan sesuatu dengan naif. Berikut adalah beberapa saran tentang cara mempercepatnya:
- Maaf jika ini jelas, tetapi jarak Levenshtein simetris, jadi pastikan Anda tidak menghitung F(A, B) dan F(B, A).
- abs(len(A) - len(B)) adalah batas bawah pada jarak antara string A dan B. Jadi, Anda dapat melewati pemeriksaan string yang panjangnya terlalu berbeda.
Satu masalah yang mungkin Anda hadapi adalah "1st St." memiliki jarak yang cukup tinggi dari "First Street", meskipun Anda mungkin ingin menganggapnya identik. Cara termudah untuk menangani ini mungkin adalah dengan mengubah string menjadi bentuk kanonik sebelum melakukan perbandingan. Jadi, Anda dapat membuat semua string menjadi huruf kecil, menggunakan kamus yang memetakan "1" ke "pertama", dll. Kamus itu mungkin menjadi cukup besar, tetapi saya tidak tahu cara yang lebih baik untuk menangani masalah ini.
Karena Anda menandai pertanyaan ini dengan php, saya berasumsi Anda ingin menggunakan php untuk ini. PHP memiliki fungsi levenshtein() bawaan tetapi kedua string harus terdiri dari 255 karakter atau kurang. Jika itu tidak cukup lama, Anda harus membuatnya sendiri. Atau, Anda menyelidiki menggunakan difflib Python.
