Algoritme apa yang memberikan saran dalam pemeriksa ejaan?

Algoritme apa yang biasanya digunakan saat menerapkan pemeriksa ejaan yang disertai dengan saran kata?

Pada awalnya saya pikir mungkin masuk akal untuk memeriksa setiap kata baru yang diketik (jika tidak ditemukan dalam kamus) terhadap jarak Levenshtein itu dari setiap kata lain dalam kamus dan mengembalikan hasil teratas. Namun, ini sepertinya akan sangat tidak efisien, harus mengevaluasi seluruh kamus berulang kali.

Bagaimana ini biasanya dilakukan?

Ada esai bagus dari Peter Norvig bagaimana menerapkan korektor ejaan. Ini pada dasarnya adalah pendekatan brute force yang mencoba string kandidat dengan jarak edit yang diberikan. ( Berikut adalah beberapa tip bagaimana Anda dapat meningkatkan kinerja pengoreksi ejaan menggunakan Filter Bloom dan pencirian kandidat yang lebih cepat .)

Persyaratan untuk pemeriksa ejaan lebih lemah. Anda hanya perlu mengetahui bahwa sebuah kata tidak ada dalam kamus. Anda dapat menggunakan Bloom Filter untuk membuat pemeriksa ejaan yang menghabiskan lebih sedikit memori. Versi kuno dijelaskan dalam Pemrograman Mutiara oleh Jon Bentley menggunakan 64kb untuk kamus bahasa Inggris.

Sebuah BK-Tree adalah pendekatan alternatif. Artikel yang bagus ada di sini .

Jarak Levenshstein bukanlah jarak edit yang tepat untuk pemeriksa ejaan. Ia hanya mengetahui penyisipan, penghapusan dan substitusi. Transposisi hilang dan menghasilkan 2 untuk transposisi 1 karakter (ini 1 penghapusan dan 1 penyisipan). Jarak Damerau – Levenshtein adalah jarak edit yang benar.

Pendekatan untuk menghasilkan saran yang berhasil saya gunakan tetapi belum pernah saya lihat dijelaskan di mana pun adalah dengan menghitung saran sebelumnya (saat membuat kamus) dengan menggunakan fungsi hash yang "buruk".

Idenya adalah untuk melihat jenis kesalahan ejaan yang dilakukan orang, dan merancang fungsi hash yang akan menetapkan ejaan yang salah ke keranjang yang sama dengan ejaan yang benar.

Sebagai contoh, kesalahan umum adalah dengan menggunakan vokal yang salah, seperti definate bukan yang pasti . Jadi Anda mendesain fungsi hash yang memperlakukan semua vokal sebagai huruf yang sama. Cara mudah untuk melakukannya adalah dengan terlebih dahulu "menormalkan" kata masukan dan kemudian memasukkan hasil yang dinormalisasi melalui fungsi hash biasa. Dalam contoh ini, fungsi normalisasi mungkin menghilangkan semua vokal, jadi definitejadilah dfnt. Kata yang "dinormalisasi" kemudian di-hash dengan fungsi hash yang khas.

Masukkan semua kata kamus Anda ke dalam indeks tambahan (tabel hash) menggunakan fungsi hash khusus ini. Bucket dalam tabel ini akan memiliki daftar tabrakan yang panjang karena fungsi hashnya "buruk", tetapi daftar tabrakan tersebut pada dasarnya adalah saran yang telah dihitung sebelumnya.

Sekarang, saat Anda menemukan kata yang salah eja, Anda mencari daftar tabrakan untuk bucket yang dipetakan oleh kesalahan eja tersebut di indeks tambahan. Ta da: Anda memiliki daftar saran! Yang harus Anda lakukan adalah memberi peringkat pada kata-kata itu.

Dalam praktiknya, Anda memerlukan beberapa indeks tambahan dengan fungsi hash lainnya untuk menangani jenis kesalahan lain, seperti huruf yang dialihkan, huruf tunggal / ganda, dan bahkan yang sederhana seperti Soundex untuk menangkap kesalahan ejaan fonetik. Dalam praktiknya, saya menemukan pelafalan sederhana yang berjalan lama dan pada dasarnya sudah usang beberapa yang dirancang untuk menemukan kesalahan ketik yang sepele.

Jadi sekarang Anda mencari kesalahan ejaan di setiap indeks tambahan dan menggabungkan daftar tabrakan sebelum memberi peringkat.

Ingat collision list hanya berisi kata-kata yang ada di kamus. Dengan pendekatan yang mencoba menghasilkan ejaan alternatif (seperti dalam artikel Peter Norvig), Anda bisa mendapatkan (puluhan) ribu kandidat yang harus Anda filter terlebih dahulu dari kamus. Dengan pendekatan yang telah dihitung sebelumnya, Anda mungkin mendapatkan beberapa ratus kandidat, dan Anda tahu bahwa semuanya dieja dengan benar, sehingga Anda dapat langsung beralih ke peringkat.

Pembaruan : Saya telah menemukan satu deskripsi algoritma yang mirip dengan ini, Pencarian Terdistribusi FAROO . Ini masih pencarian terbatas jarak edit, tetapi sangat cepat karena langkah praperhitungan bekerja seperti ide "fungsi hash buruk" saya. FAROO hanya menggunakan konsep terbatas dari fungsi hash yang buruk.

Algoritma

1. Ambil kata yang salah dieja sebagai masukan.
2. Simpan daftar kata dalam bahasa Inggris beserta frekuensinya dalam file teks.
3. Masukkan semua kata bahasa Inggris yang tersedia (disimpan dalam file teks) bersama dengan frekuensinya (ukuran seberapa sering sebuah kata digunakan dalam bahasa Inggris) di Pohon Pencarian Ternary.
4. Sekarang lintasi sepanjang Pohon Pencarian Ternary -
   • Untuk setiap kata yang ditemukan di Pohon Pencarian Ternary, hitung Jarak Levenstheinnya dari kata yang salah eja.
   • Jika Levensthein Distance <= 3, simpan kata dalam Antrian Prioritas.
   • Jika dua kata memiliki jarak edit yang sama, kata yang memiliki frekuensi lebih tinggi akan diparut. Cetak 10 item teratas dari Antrean Prioritas.

Optimasi

5. Anda dapat mengeliminasi kata-kata dalam subpohon simpul saat ini jika jarak edit substring kata masukan dari kata saat ini lebih kecil daripada 3.

   ---

   Anda dapat menemukan penjelasan dan kode sumber yang lebih detail di proyek github .

Anda tidak perlu mengetahui jarak edit yang tepat untuk setiap kata dalam kamus. Anda dapat menghentikan algoritme setelah mencapai nilai batas dan mengecualikan kata tersebut. Ini akan menghemat banyak waktu komputasi.

Pemeriksa ejaan sangat mudah diterapkan seperti pada program ejaan Unix. Kode sumber tersedia untuk umum. Koreksi dapat dilakukan, salah satu tekniknya adalah melakukan pengeditan dan sekali lagi memeriksa apakah kata baru ini ada dalam kamus. Hasil edit baru tersebut dapat dikelompokkan dan ditampilkan kepada pengguna.

Sistem Unix menggunakan program yang ditulis oleh Mc IllRoy. Cara alternatif adalah dengan menggunakan Trie yang dapat berguna dalam kasus file besar.

• Percobaan Trie saya
• Unix seperti eksperimen

Pendekatan unix membutuhkan lebih sedikit ruang untuk kamus besar karena menggunakan algoritma hash pencar.