Setiap pengguna pernah memiliki kesalahan ketik saat menulis permintaan pencarian. Tidak adanya mekanisme yang memperbaiki kesalahan ketik mengarah pada penerbitan hasil yang tidak relevan, atau bahkan ketidakhadiran mereka. Oleh karena itu, untuk membuat mesin pencari lebih berorientasi pengguna, mekanisme koreksi kesalahan dibangun ke dalamnya.

Tugas memperbaiki kesalahan ketik, pada pandangan pertama, tampaknya agak tidak rumit. Tetapi jika Anda mulai dari berbagai kesalahan, menerapkan solusi bisa sulit. Secara umum, koreksi kesalahan ketik dibagi menjadi konteks-independen dan konteks-sensitif (di mana lingkungan kamus diperhitungkan) . Dalam kasus pertama, kesalahan dikoreksi untuk setiap kata secara terpisah, dalam kasus kedua - dengan mempertimbangkan konteks (misalnya, untuk frasa "dia pulang" dalam kasus konteks independen, koreksi terjadi untuk setiap kata secara terpisah, di mana kita bisa mendapatkan "dia pulang", dan dalam kasus kedua, koreksi yang benar akan memberikan "dia pulang").

Dalam kueri penelusuran pengguna berbahasa Rusia, empat grup utama kesalahan hanya dapat dibedakan untuk koreksi independen konteks [ 1 ]:
1) kesalahan dalam kata-kata itu sendiri (say mr → hai), kategori ini mencakup semua jenis kelalaian, penyisipan dan permutasi huruf - 63,7%,
2) ejaan kata yang terus menerus - 16,9%,
3) tata letak terdistorsi (ghbdtn → hai) - 9,7%,
4) transliterasi (privet → hai) - 1,3%,
5) kesalahan campuran - 8,3%.

Pengguna membuat kesalahan ketik di sekitar 10-15% kasus. Pada saat yang sama, 83,6% permintaan memiliki satu kesalahan, 11,7% - dua, 4,8% - lebih dari tiga. Konteks penting dalam 26% kasus.

Statistik ini disusun berdasarkan sampel acak dari log harian Yandex kembali pada tahun 2013 berdasarkan 10.000 pertanyaan. Dalam domain publik ada presentasi jauh lebih awal dari Yandex untuk 2008, yang menunjukkan distribusi statistik yang serupa [ 2 ]. Dari sini kita dapat menyimpulkan bahwa distribusi varietas kesalahan untuk permintaan pencarian, rata-rata, tidak berubah seiring waktu.

Secara umum, mekanisme koreksi kesalahan ketik didasarkan pada dua model: model kesalahan dan model bahasa. Selain itu, untuk koreksi independen konteks, hanya model kesalahan yang digunakan, dan dalam koreksi tergantung konteks, dua digunakan sekaligus. Model kesalahan biasanya berupa jarak editorial (Levenshtein, jarak Damerau-Levenshtein, berbagai faktor pembobotan, metode yang mirip dengan Soundex, dll. Juga dapat ditambahkan di sini - dalam hal ini, jarak disebut berbobot) , atau model Bril-Moore, yang bekerja pada probabilitas transisi dari satu baris ke yang lain. Bril dan Moore memposisikan model mereka sebagai lebih sempurna, namun, di salah satu kompetisi SpellRuEval terbaru, pendekatan Damerau-Levenshtein menunjukkan hasil yang lebih baik [ 3 ], terlepas dari kenyataan bahwa jarak Damerau-Levenshtein (klarifikasi tidak berbobot) tidak menggunakan informasi apriori tentang statistik off-guard. . Pengamatan ini sangat indikatif jika teks pelatihan yang sama digunakan untuk implementasi yang berbeda dari koreksi otomatis di perpustakaan DeepPavlov.

Jelas, kemungkinan koreksi konteks-sensitif mempersulit konstruksi auto-korektor, karena selain model kesalahan, kebutuhan akan model bahasa ditambahkan. Tetapi jika Anda memperhatikan statistik kesalahan ketik, maka ¾ semua kueri penelusuran yang ditulis secara salah dapat diperbaiki tanpa konteks. Ini menunjukkan bahwa manfaat setidaknya auto-korektor konteks-independen bisa sangat signifikan.

Juga, koreksi konteks-sensitif untuk mengoreksi kesalahan ketik dalam permintaan sangat padat sumber daya. Misalnya, dalam salah satu pidato Yandex, daftar pasangan untuk mengoreksi kesalahan ketik (bigrams) kata berbeda 10 kali dibandingkan dengan jumlah kata (unigrams) , lalu bagaimana dengan trigram? Jelas, ini secara substansial tergantung pada variabilitas kueri. Tampaknya sedikit aneh ketika korektor otomatis mengambil setengah memori dari produk perusahaan yang diusulkan, yang tujuannya tidak berfokus pada pemecahan masalah ejaan. Jadi masalah penerapan koreksi konteks-sensitif di mesin pencari produk perangkat lunak bisa sangat kontroversial.

Pada pandangan pertama, orang mendapat kesan bahwa ada banyak solusi siap pakai untuk bahasa pemrograman apa pun yang dapat digunakan tanpa banyak pencelupan dalam rincian operasi algoritma, termasuk dalam sistem komersial. Namun dalam praktiknya, pengembangan solusi mereka terus berlanjut. Misalnya, relatif baru-baru ini, Joom membuat keputusan sendiri untuk memperbaiki kesalahan ketik menggunakan model bahasa untuk permintaan pencarian [ 4 ]. Apakah situasinya benar-benar sulit dengan ketersediaan solusi turnkey? Sejauh ini, sejauh mungkin, tinjauan luas dari solusi yang ada telah dibuat. Sebelum memulai peninjauan, kami akan memutuskan bagaimana kualitas korektor otomatis diperiksa.

Kontrol kualitas

Masalah memeriksa kualitas korektor otomatis sangat kontroversial. Salah satu pendekatan sederhana untuk validasi adalah melalui Precision and Recall. Sesuai dengan standar ISO, akurasi dan kelengkapan dilengkapi dengan kebenaran (dalam bahasa Inggris "corectness").

Kelengkapan (Pemanggilan Kembali) dihitung sebagai berikut: daftar kata yang benar dikirimkan ke korektor otomatis (Total_list_true), dan jumlah kata yang dianggap korektor otomatis benar (Pemeriksa Ejaan) dibagi dengan jumlah total kata yang benar (Total_list_true) akan dianggap sebagai kelengkapan.

R e c a l l = P e m e r i k s a E j a a n_{t} r u e a t a s T o t a l_{l} i s t_{t} r u e

$Recall = {Pemeriksa Ejaan \ _true \ atas Total \ _list \ _true}$

Untuk menentukan akurasi (Presisi), daftar kata-kata yang salah (Total_list_false) diberikan ke input korektor-otomatis, dan jumlah kata yang dianggap korektor-otomatis salah (Spell_checker_false), dibagi dengan jumlah total kata yang salah (Total_list_false), didefinisikan sebagai akurasi.

P r e c i s i o n = P e m e r i k s a E j a a n_{f} a l s e a t a s T o t a l_{l} i s t_{f} a l s e

$Precision = {Pemeriksa Ejaan \ _false \ atas Total \ _list \ _false}$

Seberapa umum metrik ini informatif dan bermanfaat, masing-masing menentukan sendiri. Sebenarnya, esensi dari tes ini adalah bahwa kata tersebut diperiksa dalam kamus pelatihan. Ketepatan dapat dianggap sebagai metrik yang lebih jelas, yang menurutnya koreksi otomatis untuk setiap kata dari set kata kata yang salah membentuk daftar kandidat pengganti yang kata yang keliru ini dapat diperbaiki (perlu diingat bahwa mungkin ada kata-kata yang tidak ada dalam kamus pelatihan) . Misalkan ukuran daftar kandidat pengganti adalah 5. Berdasarkan fakta bahwa ukuran daftar adalah 5, 6 kelompok akan dibentuk, di mana salah satu dari kami akan memasukkan kata salah asli kami sesuai dengan prinsip berikut: pada kelompok 1 - jika dalam daftar kandidat pengganti, kata yang benar kita seharusnya adalah 1, di 2 jika itu 2, dll, dan di kelompok terakhir jika kata yang benar seharusnya tidak ada dalam daftar kandidat pengganti. Tentu saja, semakin banyak kata yang masuk ke dalam kelompok 1 dan semakin sedikit ke dalam kelompok ke-6, semakin baik korektor otomatis bekerja.

Para penulis mempertimbangkan pendekatan yang dipertimbangkan dalam artikel [ 5 ], di mana auto-koreksi independen konteks dengan bias terhadap standar ISO dibandingkan. Ini juga menyediakan tautan ke metode penilaian kualitas lainnya.

Di satu sisi, pendekatan ini tidak didasarkan pada statistik kotor, yang dapat didasarkan pada model kesalahan Brill - Moore [ 6 ], atau model kesalahan jarak tertimbang Damerau - Levenshtein.

Untuk memeriksa kualitas pekerjaan koreksi otomatis konteks-independen, kami menciptakan generator kesalahan ketik kami sendiri, yang menghasilkan kesalahan ketik tata letak yang salah dan ejaan kesalahan ketik berdasarkan statistik pada kesalahan ketik yang diajukan oleh Yandex. Untuk kesalahan ejaan, penyisipan acak, penggantian, penghapusan, penataan ulang dihasilkan, dan jumlah kesalahan juga bervariasi sesuai dengan statistik ini. Untuk kesalahan dalam tata letak terdistorsi, kata yang benar diubah karakter demi karakter sepenuhnya sesuai dengan tabel terjemahan karakter.

Kemudian serangkaian percobaan dilakukan untuk seluruh daftar kata dalam kamus pelatihan (kata-kata kamus pelatihan dikoreksi untuk yang salah sesuai dengan probabilitas kesalahan ketik tertentu) . Rata-rata, koreksi-otomatis mengoreksi kata dengan benar di 75% kasus. Tanpa ragu, angka ini akan berkurang ketika kamus pembelajaran diisi ulang dengan kata-kata yang dekat dalam jarak editorial, berbagai macam bentuk kata. Masalah ini dapat diselesaikan dengan melengkapi dengan model bahasa, tetapi harus diingat bahwa jumlah sumber daya yang dibutuhkan akan meningkat secara signifikan.

Solusi siap pakai

Pertimbangan solusi siap pakai dilakukan dengan fokus pada penggunaannya sendiri, dan prioritas diberikan kepada koreksi-otomatis yang memenuhi tiga kriteria:
1) bahasa implementasi,
2) jenis lisensi,
3) dapat diperbarui.

Dalam pengembangan produk, Java dianggap sebagai salah satu yang paling populer, jadi prioritas diberikan padanya ketika mencari perpustakaan. Dari lisensi yang relevan: MIT, Publik, Apache, BSD. Pembaruan - tidak lebih dari 2 tahun sejak pembaruan terakhir. Selama pencarian, informasi tambahan dicatat, misalnya, tentang platform yang didukung, program tambahan yang diperlukan, fitur aplikasi, kemungkinan kesulitan selama penggunaan pertama, dll. Tautan dengan sumber daya dasar dan bermanfaat ke sumber diberikan di akhir artikel. Secara umum, jika tidak terbatas pada kriteria di atas, jumlah solusi yang ada adalah besar. Mari kita melihat sekilas yang utama, dan memberikan perhatian lebih hanya pada beberapa.

Secara historis, salah satu koreksi- otomatis tertua adalah Ispell (Mantra Internasional), yang ditulis secara assembler pada tahun 1971, kemudian ditransfer ke C dan menggunakan jarak editorial Damerau-Levenshtein sebagai model kesalahan. Baginya, bahkan ada kamus dalam bahasa Rusia. Selanjutnya, ia digantikan oleh dua koreksi- otomatis HunSpell (sebelumnya MySpell ) dan Aspell . Keduanya diimplementasikan dalam C ++ dan didistribusikan di bawah lisensi GPL. HunSpell juga dicakup oleh GPL / MPL dan digunakan untuk memperbaiki kesalahan ketik di OpenOffice, LibreOffice, Google Chrome, dan alat lainnya.

Ada banyak solusi JS untuk Internet dan browser (ini termasuk: nodehun-kalimat , nspell , node-markdown-spellcheck , Proofreader , Spellcheck-API - sekelompok solusi yang didasarkan pada korektor otomatis Hunspell ; grunt-spell - untuk NodeJS; yaspeller- ci - wrapper untuk korektor otomatis Yandex.Speller , didistribusikan di bawah MIT; rousseau - Korektor pembaca ringan di JS - digunakan untuk mengeja).

Kategori solusi berbayar meliputi: Spellex ; Kode Sumber Pemeriksa Ejaan - sebagai aplikasi desktop; untuk JS: nanospell ; untuk Java: Keyoti RapidSpell Spellchecker , JSpell SDK , WinterTree (WinterTree bahkan dapat membeli kode sumber seharga $ 5000).

Korektor otomatis Peter Norwig banyak digunakan, kode Python yang tersedia untuk umum dalam artikel " Cara Menulis Korektor Ejaan " [ 7 ]. Berdasarkan solusi sederhana ini, auto -corector dibangun dalam bahasa lain, misalnya: Norvig-spell-check , scala-norvig-spell-check (pada Scala), korektor ejaan mainan - Spellcheck mainan Golang (pada GO), pyspellchecker (dengan Python) . Tentu saja, di sini kita tidak berbicara tentang model bahasa dan koreksi konteks-sensitif.

Untuk editor teks, khususnya untuk VIM yang dibuat vim-dialek , vim-ditto - didistribusikan di bawah lisensi publik; untuk Notepad ++ dikembangkan oleh DspellCheck di C ++, lisensi GPL; Emacs memiliki alat untuk mendeteksi bahasa secara otomatis saat mencetak, yang disebut menebak-bahasa , didistribusikan di bawah lisensi publik.

Ada layanan terpisah dari pencarian raksasa: Yandex.Speller - dari Yandex, tentang bungkus untuk itu disebutkan di atas, google-api-ejaan-java (masing-masing, dari Google).

Perpustakaan gratis untuk Java: languagetool (dilisensikan di bawah LGPL), terintegrasi dengan perpustakaan pencarian teks Lucene dan memungkinkan penggunaan model bahasa, diperlukan Java versi 8; Jazzy (analog dari Aspell ) dilisensikan di bawah LGPLv2 dan belum diperbarui sejak 2005, dan pada 2013 porting ke GitHub. Sesuai dengan koreksi otomatis ini, solusi terpisah telah dibuat [ 8 ]; Jortho (Java Orthography) didistribusikan di bawah GPL dan memungkinkan penggunaan gratis secara eksklusif untuk tujuan non-komersial, untuk yang komersial - dengan biaya tambahan; Jaspell (berlisensi di bawah BSD dan belum diperbarui sejak 2005); Open Source Java Suggester - belum diperbarui sejak 2013, didistribusikan oleh SoftCorporation LLC dan memungkinkan penggunaan komersial; LuceneSpellChecker adalah autocorrector Lucene yang ditulis dalam Java dan didistribusikan di bawah lisensi Apache.

Untuk waktu yang lama, Wolf Garbe berurusan dengan kesalahan ketik, ia mengusulkan algoritma SymSpell (di bawah lisensi MIT) dan LinSpell (di bawah LGPL) dengan implementasi C # [ 9 ] yang menggunakan jarak Damerau-Levenshtein untuk model kesalahan. Kekhasan implementasi mereka adalah bahwa pada tahap menghasilkan kemungkinan kesalahan untuk kata input, hanya penghapusan yang digunakan, bukan semua jenis penghapusan, sisipan, penggantian dan permutasi. Dibandingkan dengan penerapan auto-korektor Peter Norwig, kedua algoritma bekerja lebih cepat karena ini, sedangkan peningkatan kecepatan meningkat secara signifikan jika jarak Damerau-Levenshtein menjadi lebih dari dua. Juga, karena fakta bahwa hanya penghapusan yang digunakan, waktu pembentukan kamus berkurang. Perbedaan antara kedua algoritma adalah bahwa LinSpell lebih ekonomis dalam memori dan lebih lambat dalam kecepatan pencarian, SymSpell - sebaliknya. Dalam versi yang lebih baru, SymSpell memperbaiki kesalahan ejaan terpisah. Model bahasa tidak digunakan.

Di antara yang terbaru dan menjanjikan untuk penggunaan koreksi-otomatis yang bekerja dengan model bahasa dan mengoreksi kesalahan ketik konteks termasuk Yandex.Speller , JamSpell [ 10 ], DeepPavlov [ 11 ]. 2 yang terakhir didistribusikan secara bebas: JamSpell (MIT), DeepPavlov (di bawah Apache).

Yandex.Speller menggunakan algoritma CatBoost, bekerja dengan beberapa bahasa dan memperbaiki semua jenis kesalahan, bahkan dengan mempertimbangkan konteksnya. Satu-satunya solusi yang ditemukan adalah memperbaiki kesalahan tata letak dan transliterasi yang salah. Solusinya memiliki fleksibilitas, yang membuatnya populer. Kerugiannya adalah ia adalah layanan jarak jauh, dan tentang batasan serta ketentuan penggunaan dapat ditemukan di sini [ 12 ]. Layanan ini bekerja dengan sejumlah bahasa terbatas, Anda tidak dapat menambahkan kata-kata sendiri dan mengelola proses koreksi. Sesuai dengan sumber daya [ 3 ] sesuai dengan hasil kompetisi RuSpellEval, korektor otomatis ini menunjukkan kualitas koreksi tertinggi. JamSpell adalah korektor otomatis yang paling cepat dikenal (implementasi C ++), ada binder yang sudah jadi untuk bahasa lain. Memperbaiki kesalahan hanya dalam kata-kata itu sendiri dan bekerja dengan bahasa tertentu. Anda tidak dapat menggunakan solusi di tingkat unigrams dan bigrams. Untuk mendapatkan kualitas yang dapat diterima, teks pelatihan yang besar diperlukan.
DeepPavlov memiliki beberapa praktik yang baik, namun, integrasi solusi ini dan dukungan berikutnya dalam produk mereka sendiri dapat menyebabkan kesulitan, karena bekerja dengan mereka memerlukan menghubungkan lingkungan virtual dan menggunakan versi Python 3.6 yang lebih lama. DeepPavlov menyediakan tiga pilihan implementasi koreksi- otomatis yang siap pakai, di mana dua di antaranya model kesalahan Bril-Moore digunakan dan dalam dua model bahasa. Ini hanya memperbaiki kesalahan ejaan, dan opsi dengan model kesalahan berdasarkan jarak Damerau-Levenshtein dapat memperbaiki kesalahan penulisan kontinu.

Saya akan menyebutkan satu lagi pendekatan modern untuk memperbaiki kesalahan ketik, yang didasarkan pada penggunaan representasi kata-kata vektor (Word Embeddings). Keuntungannya adalah dapat digunakan untuk membangun korektor otomatis untuk memperbaiki kata berdasarkan konteks. Rincian lebih lanjut tentang pendekatan ini dapat ditemukan di sini [ 13 ]. Tetapi untuk menggunakannya untuk mengoreksi kesalahan ketik dari permintaan pencarian, Anda harus mengakumulasi log besar permintaan. Selain itu, model itu sendiri bisa sangat luas dalam hal konsumsi memori, yang akan mempengaruhi kompleksitas integrasi ke dalam produk.

Pilihan Naumen

Dari solusi yang sudah jadi untuk Java, sebuah korektor otomatis dari Lucene dipilih (didistribusikan di bawah lisensi dari Apache). Memungkinkan Anda mengoreksi kesalahan ketik dengan kata-kata. Proses pembelajarannya cepat: misalnya, pembentukan struktur data kamus khusus - indeks untuk 3 juta baris - adalah 30 detik pada prosesor Intel Core i5-8500 3.00GHz, 32 Gb RAM, Lucene 8.0.0. Dalam versi sebelumnya, waktunya mungkin 2 kali lebih lama. Ukuran kamus pelatihan adalah 3 juta baris (~ 73 Mb txt-file), struktur indeks ~ 235 Mb. Untuk model kesalahan, Anda dapat memilih jarak Jaro-Winkler, Levenshtein, Damerau-Levenshtein, N-Gram, jika perlu, Anda dapat menambahkan sendiri. Jika perlu, dimungkinkan untuk menghubungkan model bahasa [ 14 ]. Model sudah dikenal sejak 2001, tetapi perbandingannya dengan solusi modern terkenal di domain publik tidak ditemukan. Langkah selanjutnya adalah memeriksa pekerjaan mereka.

Solusi berbasis Lucene yang dihasilkan hanya mengoreksi kesalahan dalam kata-kata itu sendiri. Tidak sulit untuk menambahkan koreksi tata letak keyboard yang terdistorsi ke solusi semacam itu dengan menggunakan tabel terjemahan yang sesuai, sehingga mengurangi kemungkinan output yang tidak relevan menjadi 10% (sesuai dengan statistik kesalahan ketik). Selain itu, mudah untuk menambahkan tulisan terpisah dari 2 kata dan transliterasi.

Kerugian utama dari solusi ini adalah kebutuhan akan pengetahuan tentang Jawa, kurangnya kasus penggunaan yang terperinci dan dokumentasi yang terperinci, yang tercermin dalam penurunan kecepatan pengembangan solusi untuk spesialis Data-Science. Selain itu, kesalahan ketik dengan jarak Damerau-Levenshtein lebih dari 2 tidak diperbaiki. Sekali lagi, jika kita melanjutkan dari statistik keliru, lebih dari 2 kesalahan dalam satu kata terjadi lebih jarang daripada di 5% kasus. Apakah kebutuhan untuk mempersulit algoritma, khususnya, peningkatan konsumsi memori, dibenarkan? Itu sudah tergantung pada kasus pelanggan. Jika ada sumber daya tambahan, mengapa tidak menggunakannya?

Sumber daya utama untuk koreksi-otomatis yang terjangkau :

Tinjauan Umum Solusi Koreksi Typo Terbuka

Kontrol kualitas

Solusi siap pakai

Pilihan Naumen

More articles: