Pengambilan Toleran dan Wildcard

Pengambilan toleran memungkinkan sistem pencarian untuk mencocokkan kueri meskipun ada variasi ejaan, wildcard, dan perbedaan fonetik, sehingga pengguna tetap menemukan dokumen yang relevan ketika kueri dan teks tidak cocok persis.

Definition

Pengambilan toleran meliputi teknik tingkat kamus yang mencocokkan istilah kueri dengan istilah terindeks meskipun ada masukan yang tidak lengkap, salah eja, atau bervariasi secara fonetik, termasuk ekspansi wildcard, koreksi ejaan berbasis jarak edit, dan pengkodean fonetik.

Scope

Topik ini mencakup teknik-teknik yang melonggarkan pencocokan istilah yang tepat pada tingkat kamus: pemrosesan kueri wildcard menggunakan indeks permuterm dan k-gram, koreksi ejaan berdasarkan jarak edit dan konteks, serta pencocokan fonetik seperti Soundex. Ini membahas bagaimana kamus istilah diperkaya untuk mendukung pencarian perkiraan ini dan bagaimana istilah kandidat dihasilkan dan diberi peringkat, berbeda dari pencocokan semantik, yang membahas makna daripada bentuk permukaan.

Core questions

• Bagaimana kueri wildcard seperti pola awalan, akhiran, dan sisipan dievaluasi terhadap kamus?
• Bagaimana indeks permuterm dan k-gram mendukung pencarian wildcard?
• Bagaimana istilah yang dieja dengan benar terdekat ditemukan untuk istilah kueri yang salah eja?
• Bagaimana jarak edit (Levenshtein) mengukur perbedaan antara dua string?
• Bagaimana pencocokan fonetik seperti Soundex mengelompokkan istilah yang terdengar serupa?

Key concepts

• kueri wildcard
• indeks permuterm
• indeks k-gram
• jarak edit (Levenshtein)
• koreksi ejaan
• pencocokan fonetik (Soundex)
• pencocokan string perkiraan
• pembuatan istilah kandidat

Key theories

Pengindeksan wildcard dengan indeks permuterm dan k-gram

Memutar istilah sehingga wildcard selalu jatuh di akhir (permuterm) atau mengindeks istilah berdasarkan k-gram karakternya memungkinkan sistem mengubah pola wildcard menjadi pencarian kamus biasa yang mengambil istilah kandidat.

Koreksi ejaan jarak edit

Jumlah minimum penyisipan, penghapusan, dan substitusi satu karakter yang diperlukan untuk mengubah satu string menjadi string lain (jarak edit) memberikan ukuran berprinsip untuk mengusulkan alternatif ejaan yang benar untuk istilah kueri, seringkali dikombinasikan dengan frekuensi istilah dan konteks.

Clinical relevance

Pengambilan toleran mendukung kemampuan pencarian sehari-hari: saran ejaan 'apakah maksud Anda', pelengkapan otomatis dan pencarian awalan, serta pencocokan nama dan istilah produk yang memaafkan. Ini secara substansial meningkatkan perolehan kembali (recall) dan pengalaman pengguna ketika kueri mengandung kesalahan ketik atau ketika pengguna tidak mengetahui ejaan yang tepat.

History

Pencocokan perkiraan dan koreksi ejaan memiliki sejarah panjang dalam komputasi, dengan Soundex berasal dari pengindeksan catatan awal abad kedua puluh. Survei Kukich tahun 1992 mengonsolidasikan teknik koreksi ejaan otomatis, dan survei Navarro tahun 2001 mensistematisasi pencocokan string perkiraan. Metode-metode ini menjadi komponen standar kamus pencarian karena pencarian web menjadikan penanganan kueri yang memaafkan sebagai hal yang esensial.

Key figures

• Karen Kukich
• Gonzalo Navarro

Seminal works

• manning2008
• kukich1992
• navarro2001

Frequently asked questions

Bagaimana mesin pencari menangani wildcard seperti 'comput*'?

Ini menggunakan struktur kamus tambahan, seperti indeks permuterm atau k-gram, untuk menemukan semua istilah yang cocok dengan pola tersebut (computer, computing, computation, dan sebagainya), kemudian mengevaluasi kueri asli seolah-olah istilah-istilah tersebut telah dicantumkan secara eksplisit.

Apa itu jarak edit dan mengapa digunakan untuk koreksi ejaan?

Jarak edit menghitung minimum penyisipan, penghapusan, dan substitusi satu karakter yang diperlukan untuk mengubah satu kata menjadi kata lain. Jarak edit yang kecil antara istilah kueri yang salah eja dan istilah kamus menunjukkan bahwa istilah kamus kemungkinan merupakan koreksi yang dimaksud.