Bagaimana cara Google “Maksud Anda?” Algoritma bekerja?

Saya telah mengembangkan situs web internal untuk alat manajemen portofolio. Ada banyak data teks, nama perusahaan, dll. Saya sangat terkesan dengan beberapa kemampuan mesin pencari untuk dengan cepat menanggapi pertanyaan dengan "Apakah maksud Anda: xxxx".

Saya harus dapat dengan cerdas mengambil kueri pengguna dan merespons dengan tidak hanya hasil pencarian mentah tetapi juga dengan "Apakah maksud Anda?" Menanggapi ketika ada kemungkinan jawaban alternatif dll

[Saya sedang mengembangkan di ASP.NET (VB - jangan menentang saya!)]

UPDATE: Oke, bagaimana saya bisa meniru ini tanpa jutaan 'pengguna yang belum dibayar'?

• Hasilkan kesalahan ketik untuk setiap istilah 'dikenal' atau 'benar' dan melakukan pencarian?
• Beberapa metode lain yang lebih elegan?

Inilah penjelasan langsung dari sumbernya (hampir)

Cari 101!

pada min 22:03

Layak ditonton!

Pada dasarnya dan menurut Douglas Merrill mantan CTO Google itu seperti ini:

1) Anda menulis kata (salah eja) di google

2) Anda tidak menemukan apa yang Anda inginkan (jangan klik pada hasil apa pun)

3) Anda menyadari bahwa Anda salah mengeja kata sehingga Anda menulis ulang kata itu di kotak pencarian.

4) Anda menemukan apa yang Anda inginkan (Anda mengklik tautan pertama)

Pola ini berlipat ganda jutaan kali, menunjukkan kesalahan ejaan yang paling umum dan koreksi "paling umum" apa.

Dengan cara ini Google hampir secara instan, menawarkan koreksi ejaan dalam setiap bahasa.

Ini juga berarti jika dalam semalam semua orang mulai mengeja malam sebagai "nigth" google akan menyarankan kata itu sebagai gantinya.

EDIT

@ThomasRutter: Douglas menggambarkannya sebagai "pembelajaran mesin statistik".

Mereka tahu siapa yang memperbaiki kueri, karena mereka tahu kueri mana yang berasal dari pengguna mana (menggunakan cookies)

Jika pengguna melakukan kueri, dan hanya 10% dari pengguna mengklik hasil dan 90% kembali dan mengetik kueri lain (dengan kata yang dikoreksi) dan kali ini 90% mengklik pada hasil, maka mereka tahu mereka telah menemukan koreksi.

Mereka juga dapat mengetahui apakah itu adalah pertanyaan "terkait" dari dua yang berbeda, karena mereka memiliki informasi tentang semua tautan yang ditampilkan.

Selanjutnya, mereka sekarang memasukkan konteks ke dalam pemeriksaan ejaan, sehingga mereka bahkan dapat menyarankan kata yang berbeda tergantung pada konteksnya.

Lihat demo ini dari google wave (@ 44m 06s) yang menunjukkan bagaimana konteks diperhitungkan untuk secara otomatis memperbaiki ejaan.

Di sini dijelaskan bagaimana pemrosesan bahasa alami itu bekerja.

Dan akhirnya di sini adalah demo luar biasa dari apa yang dapat dilakukan dengan menambahkan terjemahan mesin otomatis (@ 1h 12m 47s) ke dalam campuran.

_{Saya telah menambahkan jangkar menit dan detik ke video untuk melompat langsung ke konten, jika tidak berfungsi, coba muat ulang halaman atau gulir dengan tangan ke tanda.}

Saya menemukan artikel ini beberapa waktu yang lalu: Cara Menulis Korektor Ejaan , ditulis oleh Peter Norvig (Direktur Penelitian di Google Inc.).

Ini bacaan yang menarik tentang topik "koreksi ejaan". Contohnya dalam Python tetapi jelas dan sederhana untuk dipahami, dan saya pikir algoritme dapat dengan mudah diterjemahkan ke bahasa lain.

Berikut ini uraian singkat algoritme. Algoritma ini terdiri dari dua langkah, persiapan dan pengecekan kata.

Langkah 1: Persiapan - menyiapkan basis data kata

Yang terbaik adalah jika Anda dapat menggunakan kata pencarian aktual dan kemunculannya. Jika Anda tidak memiliki itu, sejumlah besar teks dapat digunakan sebagai gantinya. Hitung kemunculan (popularitas) setiap kata.

Langkah 2. Pengecekan kata - menemukan kata yang mirip dengan yang dicentang

Serupa artinya jarak edit rendah (biasanya 0-1 atau 0-2). Jarak edit adalah jumlah minimum sisipan / penghapusan / perubahan / swap yang diperlukan untuk mengubah satu kata ke kata lain.

Pilih kata yang paling populer dari langkah sebelumnya dan sarankan sebagai koreksi (jika selain kata itu sendiri).

Untuk teori algoritma "maksud Anda", Anda dapat merujuk ke Bab 3 Pengantar Pengambilan Informasi. Ini tersedia online secara gratis. Bagian 3.3 (halaman 52) menjawab pertanyaan Anda dengan tepat. Dan untuk secara spesifik menjawab pembaruan Anda, Anda hanya perlu kamus kata-kata dan tidak ada yang lain (termasuk jutaan pengguna).

Hmm ... Saya pikir google menggunakan kumpulan data mereka yang luas (internet) untuk melakukan beberapa NLP (Natural Language Processing) yang serius.

Misalnya, mereka memiliki begitu banyak data dari seluruh internet sehingga mereka dapat menghitung berapa kali urutan tiga kata terjadi (dikenal sebagai trigram ). Jadi jika mereka melihat kalimat seperti: "konser pink frugr", mereka bisa melihat itu memiliki beberapa hits, kemudian menemukan "konser pink *" yang paling mungkin di corpus mereka.

Mereka tampaknya hanya melakukan variasi dari apa yang Davide Gualano katakan, jadi, pasti membaca tautan itu. Google tentu saja menggunakan semua halaman web yang dikenalnya sebagai corpus, sehingga membuat algoritmenya sangat efektif.

Dugaan saya adalah bahwa mereka menggunakan kombinasi algoritma jarak Levenshtein dan massa data yang mereka kumpulkan mengenai pencarian yang dijalankan. Mereka bisa menarik satu set pencarian yang memiliki jarak Levenshtein terpendek dari string pencarian yang dimasukkan, lalu memilih satu dengan hasil terbanyak.

Biasanya koreksi ejaan produksi menggunakan beberapa metodologi untuk memberikan saran ejaan. Beberapa diantaranya adalah:

• Putuskan cara untuk menentukan apakah koreksi ejaan diperlukan. Ini mungkin termasuk hasil yang tidak mencukupi, hasil yang tidak spesifik atau cukup akurat (menurut beberapa ukuran), dll. Kemudian:

• Gunakan badan teks atau kamus yang besar, tempat semua, atau sebagian besar dieja dengan benar. Ini mudah ditemukan online, di tempat-tempat seperti LingPipe . Kemudian untuk menentukan saran terbaik Anda mencari kata yang paling cocok berdasarkan pada beberapa langkah. Yang paling intuitif adalah karakter yang mirip. Apa yang telah ditunjukkan melalui penelitian dan eksperimen adalah bahwa dua atau tiga urutan karakter yang cocok bekerja lebih baik. (bigrams dan trigram). Untuk lebih meningkatkan hasil, timbang skor yang lebih tinggi pada pertandingan di awal, atau akhir kata. Untuk alasan kinerja, indeks semua kata ini sebagai trigram atau bigrams, sehingga ketika Anda melakukan pencarian, Anda mengonversi ke n-gram, dan mencari melalui hashtable atau trie.

• Gunakan heuristik yang terkait dengan potensi kesalahan keyboard berdasarkan lokasi karakter. Jadi "hwllo" harus "halo" karena 'w' dekat dengan 'e'.

• Gunakan kunci fonetik (Soundex, Metaphone) untuk mengindeks kata-kata dan mencari kemungkinan koreksi. Dalam praktiknya ini biasanya mengembalikan hasil yang lebih buruk daripada menggunakan pengindeksan n-gram, seperti dijelaskan di atas.

• Dalam setiap kasus Anda harus memilih koreksi terbaik dari daftar. Ini mungkin metrik jarak seperti levenshtein, metrik keyboard, dll.

• Untuk frasa multi-kata, hanya satu kata yang salah eja, dalam hal ini Anda dapat menggunakan kata-kata yang tersisa sebagai konteks dalam menentukan kecocokan terbaik.

Gunakan jarak Levenshtein , lalu buat Metric Tree (atau Slim tree) untuk mengindeks kata. Kemudian jalankan permintaan 1-Nearest Neighbor, dan Anda mendapatkan hasilnya.

Google tampaknya menyarankan kueri dengan hasil terbaik, bukan dengan yang dieja dengan benar. Tetapi dalam kasus ini, mungkin pembetulan ejaan akan lebih layak, Tentu saja Anda dapat menyimpan beberapa nilai untuk setiap kueri, berdasarkan pada beberapa metrik tentang seberapa baik hasil yang dihasilkannya.

Begitu,

1. Anda memerlukan kamus (bahasa Inggris atau berdasarkan data Anda)

2. Hasilkan kata teralis dan hitung probabilitas untuk transisi menggunakan kamus Anda.

3. Tambahkan decoder untuk menghitung jarak kesalahan minimum menggunakan terali Anda. Tentu saja Anda harus berhati-hati dalam memasukkan dan menghapus ketika menghitung jarak. Hal yang menyenangkan adalah keyboard QWERTY memaksimalkan jarak jika Anda menekan tombol berdekatan satu sama lain (cae akan mengubah mobil, cay akan mengubah kucing)

4. Kembalikan kata yang memiliki jarak minimum.

5. Kemudian Anda bisa membandingkannya dengan database kueri Anda dan memeriksa apakah ada hasil yang lebih baik untuk kecocokan dekat lainnya.

Inilah jawaban terbaik yang saya temukan , pengoreksi ejaan diimplementasikan dan dijelaskan oleh Direktur Penelitian Google Peter Norvig.

Jika Anda ingin membaca lebih lanjut tentang teori di balik ini, Anda dapat membaca bab bukunya .

Ide algoritma ini didasarkan pada pembelajaran mesin statistik.

Saya melihat sesuatu tentang ini beberapa tahun yang lalu, jadi mungkin telah berubah sejak itu, tetapi tampaknya mereka memulainya dengan menganalisis log mereka untuk pengguna yang sama mengirimkan pertanyaan yang sangat mirip dalam waktu singkat, dan menggunakan pembelajaran mesin berdasarkan bagaimana pengguna telah mengoreksi diri.

Sebagai tebakan ... itu bisa

1. mencari kata-kata
2. jika tidak ditemukan gunakan beberapa algoritma untuk mencoba "menebak" kata tersebut.

Bisa berupa sesuatu dari AI seperti jaringan Hopfield atau jaringan propagasi balik, atau sesuatu yang lain "identifikasi sidik jari", memulihkan data yang rusak, atau koreksi ejaan seperti yang disebutkan Davide ...

Sederhana. Mereka punya banyak data. Mereka memiliki statistik untuk setiap istilah yang mungkin, berdasarkan seberapa sering ditanya, dan variasi apa yang biasanya menghasilkan hasil yang diklik pengguna ... jadi, ketika mereka melihat Anda mengetik salah ejaan yang sering untuk istilah pencarian, mereka teruskan dan mengusulkan jawaban yang lebih biasa.

Sebenarnya, jika salah mengeja itu adalah istilah yang paling sering dicari, algorythm akan mengambilnya untuk yang tepat.

mengenai pertanyaan Anda cara meniru perilaku tanpa memiliki banyak data - mengapa tidak menggunakan banyak data yang dikumpulkan oleh google? Unduh hasil google sarch untuk kata yang salah eja dan cari "Apakah maksud Anda:" dalam HTML.

Saya kira itu disebut mashup saat ini :-)

Terlepas dari jawaban di atas, jika Anda ingin mengimplementasikan sesuatu sendiri dengan cepat, berikut adalah saran -

Algoritma

Anda dapat menemukan implementasi dan dokumentasi terperinci dari algoritma ini di GitHub .

• Buat Antrian Prioritas dengan pembanding.
• Buat Pohon Pencarian Ternay dan masukkan semua kata-kata bahasa Inggris (dari posting Norvig ) bersama dengan frekuensinya.
• Mulai melintasi TST dan untuk setiap kata yang ditemukan di TST, hitung Levenshtein Distance ( LD ) -nya dari input_word
• Jika LD ≤ 3 maka masukkan ke dalam Antrian Prioritas.
• Terakhir ekstrak 10 kata dari Antrian Prioritas dan tampilan.

Maksudmu spell checker? Jika itu adalah pemeriksa ejaan daripada seluruh frasa maka saya punya tautan tentang pemeriksa ejaan di mana algoritma dikembangkan dengan python. Periksa tautan ini

Sementara itu, saya juga mengerjakan proyek yang mencakup pencarian basis data menggunakan teks. Saya kira ini akan menyelesaikan masalah Anda

Ini adalah pertanyaan lama, dan saya terkejut bahwa tidak ada yang menyarankan OP menggunakan Apache Solr.

Apache Solr adalah mesin pencarian teks lengkap yang selain banyak fungsi lainnya juga menyediakan saran pemeriksaan ejaan atau permintaan. Dari dokumentasi :

Secara default, pemeriksa ejaan Lucene mengurutkan saran pertama berdasarkan skor dari perhitungan jarak string dan yang kedua berdasarkan frekuensi (jika ada) dari saran dalam indeks.

Ada struktur data khusus - pohon pencarian ternary - yang secara alami mendukung kecocokan sebagian dan kecocokan tetangga.

Cara termudah untuk mengetahuinya adalah dengan pemrograman dinamis Google.

Ini adalah algoritma yang telah dipinjam dari Information Retrieval dan banyak digunakan dalam bioinformatika modern untuk melihat seberapa mirip dua sekuens gen.

Solusi optimal menggunakan pemrograman dinamis dan rekursi.

Ini adalah masalah yang sangat terselesaikan dengan banyak solusi. Hanya google sekitar sampai Anda menemukan beberapa kode sumber terbuka.