การค้นคืนแบบยืดหยุ่นและแบบไวลด์การ์ด

การค้นคืนแบบยืดหยุ่นช่วยให้ระบบค้นหาสามารถจับคู่คำค้นหาได้ แม้จะมีความแตกต่างในการสะกดคำ, การใช้ไวลด์การ์ด, และความแตกต่างทางสัทวิทยา เพื่อให้ผู้ใช้ยังคงพบเอกสารที่เกี่ยวข้องเมื่อคำค้นหาและข้อความไม่ตรงกันทุกประการ

Definition

การค้นคืนแบบยืดหยุ่นประกอบด้วยเทคนิคระดับพจนานุกรมที่จับคู่คำค้นหากับคำที่จัดทำดัชนีไว้ แม้ว่าข้อมูลที่ป้อนจะไม่สมบูรณ์ สะกดผิด หรือมีความแตกต่างทางสัทวิทยา ซึ่งรวมถึงการขยายไวลด์การ์ด, การแก้ไขการสะกดคำโดยใช้ระยะทางแก้ไข, และการเข้ารหัสทางสัทวิทยา

Scope

หัวข้อนี้ครอบคลุมเทคนิคที่ผ่อนคลายการจับคู่คำที่ตรงกันทุกประการในระดับพจนานุกรม: การประมวลผลคำค้นหาแบบไวลด์การ์ดโดยใช้ดัชนีแบบ permuterm และ k-gram, การแก้ไขการสะกดคำด้วยระยะทางแก้ไข (edit distance) และบริบท, และการจับคู่ทางสัทวิทยา เช่น Soundex โดยจะกล่าวถึงวิธีการเสริมพจนานุกรมคำศัพท์เพื่อรองรับการค้นหาโดยประมาณเหล่านี้ และวิธีการสร้างและจัดอันดับคำศัพท์ที่เป็นไปได้ ซึ่งแตกต่างจากการจับคู่เชิงความหมาย (semantic matching) ที่เน้นความหมายมากกว่ารูปแบบพื้นผิว

Core questions

• คำค้นหาแบบไวลด์การ์ด เช่น รูปแบบคำนำหน้า, คำต่อท้าย, และคำแทรกกลาง ถูกประเมินเทียบกับพจนานุกรมอย่างไร?
• ดัชนีแบบ permuterm และ k-gram สนับสนุนการค้นหาแบบไวลด์การ์ดอย่างไร?
• จะพบคำที่สะกดถูกต้องที่ใกล้เคียงที่สุดสำหรับคำค้นหาที่สะกดผิดได้อย่างไร?
• ระยะทางแก้ไข (Levenshtein) วัดความแตกต่างระหว่างสตริงสองสตริงได้อย่างไร?
• การจับคู่ทางสัทวิทยา เช่น Soundex จัดกลุ่มคำที่ออกเสียงคล้ายกันได้อย่างไร?

Key concepts

• คำค้นหาแบบไวลด์การ์ด
• ดัชนีแบบ permuterm
• ดัชนีแบบ k-gram
• ระยะทางแก้ไข (Levenshtein)
• การแก้ไขการสะกดคำ
• การจับคู่ทางสัทวิทยา (Soundex)
• การจับคู่สตริงโดยประมาณ
• การสร้างคำศัพท์ที่เป็นไปได้

Key theories

การจัดทำดัชนีไวลด์การ์ดด้วยดัชนีแบบ permuterm และ k-gram

การหมุนคำเพื่อให้ไวลด์การ์ดอยู่ท้ายเสมอ (permuterm) หรือการจัดทำดัชนีคำตาม k-gram ของตัวอักษร ช่วยให้ระบบสามารถแปลงรูปแบบไวลด์การ์ดเป็นการค้นหาพจนานุกรมทั่วไปที่เรียกคืนคำศัพท์ที่เป็นไปได้

การแก้ไขการสะกดคำด้วยระยะทางแก้ไข

จำนวนการแทรก, การลบ, และการแทนที่อักขระเดี่ยวขั้นต่ำที่จำเป็นในการแปลงสตริงหนึ่งไปเป็นอีกสตริงหนึ่ง (ระยะทางแก้ไข) เป็นมาตรวัดที่เป็นหลักการสำหรับการเสนอทางเลือกที่สะกดถูกต้องสำหรับคำค้นหา ซึ่งมักจะใช้ร่วมกับความถี่ของคำและบริบท

Clinical relevance

การค้นคืนแบบยืดหยุ่นขับเคลื่อนความสามารถในการค้นหาในชีวิตประจำวัน: คำแนะนำการสะกดคำ 'คุณหมายถึง', การเติมข้อความอัตโนมัติและการค้นหาคำนำหน้า, และการจับคู่ชื่อและคำศัพท์ผลิตภัณฑ์ที่ยืดหยุ่น สิ่งนี้ช่วยปรับปรุงการเรียกคืนข้อมูลและประสบการณ์ผู้ใช้ได้อย่างมากเมื่อคำค้นหามีข้อผิดพลาดในการพิมพ์ หรือเมื่อผู้ใช้ไม่ทราบการสะกดคำที่ถูกต้อง

History

การจับคู่โดยประมาณและการแก้ไขการสะกดคำมีประวัติยาวนานในการคำนวณ โดย Soundex มีมาตั้งแต่การจัดทำดัชนีบันทึกในช่วงต้นศตวรรษที่ยี่สิบ การสำรวจของ Kukich ในปี 1992 ได้รวบรวมเทคนิคการแก้ไขการสะกดคำอัตโนมัติ และการสำรวจของ Navarro ในปี 2001 ได้จัดระบบการจับคู่สตริงโดยประมาณ วิธีการเหล่านี้กลายเป็นส่วนประกอบมาตรฐานของพจนานุกรมการค้นหา เนื่องจากการค้นหาบนเว็บทำให้การจัดการคำค้นหาที่ยืดหยุ่นเป็นสิ่งจำเป็น

Key figures

• Karen Kukich
• Gonzalo Navarro

Seminal works

• manning2008
• kukich1992
• navarro2001

Frequently asked questions

เครื่องมือค้นหาจัดการกับไวลด์การ์ดเช่น 'comput*' อย่างไร?

มันใช้โครงสร้างพจนานุกรมเสริม เช่น ดัชนีแบบ permuterm หรือ k-gram เพื่อค้นหาคำทั้งหมดที่ตรงกับรูปแบบ (computer, computing, computation, และอื่นๆ) จากนั้นประเมินคำค้นหาเดิมราวกับว่าคำเหล่านั้นถูกระบุไว้อย่างชัดเจน

ระยะทางแก้ไขคืออะไร และเหตุใดจึงใช้สำหรับการแก้ไขการสะกดคำ?

ระยะทางแก้ไขนับจำนวนการแทรก, การลบ, และการแทนที่อักขระเดี่ยวขั้นต่ำที่จำเป็นในการเปลี่ยนคำหนึ่งไปเป็นอีกคำหนึ่ง ระยะทางแก้ไขที่น้อยระหว่างคำค้นหาที่สะกดผิดกับคำในพจนานุกรมบ่งชี้ว่าคำในพจนานุกรมนั้นน่าจะเป็นการแก้ไขที่ตั้งใจไว้