การทำดัชนีและการประมวลผลข้อคำถาม

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

Definition

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

Scope

สาขาวิชานี้ครอบคลุมถึงวิธีการเปลี่ยนชุดข้อมูลข้อความเป็นโครงสร้างที่สามารถค้นหาได้ และวิธีการประเมินข้อคำถามกับโครงสร้างเหล่านั้น: การสร้างดัชนีผกผัน, การตัดสินใจเกี่ยวกับการแยกคำ (tokenization) และคำศัพท์ (term-vocabulary) ที่อยู่เบื้องหลัง, การบีบอัดรายการปรากฏ (postings) เพื่อประหยัดพื้นที่และเพิ่มความเร็วในการเข้าถึง, การประมวลผลข้อคำถามอย่างมีประสิทธิภาพ รวมถึงการจัดอันดับการเรียกค้น (ranked retrieval) และการยุติการทำงานก่อนกำหนด (early termination), และเทคนิคการเรียกค้นที่ทนทานต่อข้อผิดพลาด เช่น การค้นหาด้วยสัญลักษณ์ตัวแทน (wildcard), การแก้ไขการสะกดคำ (spelling-correction), และการจับคู่เสียง (phonetic matching) โดยจะกล่าวถึงวิศวกรรมระบบของการเรียกค้นที่รวดเร็ว ซึ่งแตกต่างจากแบบจำลองการเรียกค้นที่กำหนดการจัดอันดับและวิธีการประเมินที่ใช้วัดคุณภาพ

Sub-topics

• Index Compression
• Inverted Indexes
• Query Processing and Optimization
• Tolerant and Wildcard Retrieval

Core questions

• ดัชนีผกผันถูกสร้างและอัปเดตสำหรับชุดข้อมูลขนาดใหญ่ที่มีการเปลี่ยนแปลงได้อย่างไร?
• รายการปรากฏ (postings lists) สามารถบีบอัดได้อย่างไรโดยไม่ทำให้การประเมินข้อคำถามช้าลง?
• ข้อคำถามได้รับการประเมินอย่างมีประสิทธิภาพได้อย่างไร โดยเฉพาะอย่างยิ่งข้อคำถามที่จัดอันดับจากเอกสารหลายล้านฉบับ?
• ระบบสามารถเรียกค้นผลลัพธ์ที่ดีได้อย่างไรโดยไม่ต้องให้คะแนนเอกสารทุกฉบับ?
• ระบบจัดการกับการสะกดคำผิด, สัญลักษณ์ตัวแทน (wildcards), และการจับคู่โดยประมาณได้อย่างไร?

Key concepts

• ดัชนีผกผัน (inverted index)
• รายการปรากฏ (postings list)
• การแยกคำ (tokenization) และคำศัพท์ (term vocabulary)
• การสร้างดัชนี (index construction) (BSBI, SPIMI)
• การบีบอัดดัชนี (index compression)
• การประเมินแบบเอกสารต่อครั้ง (document-at-a-time) และคำต่อครั้ง (term-at-a-time)
• การตัดแต่งแบบไดนามิก (dynamic pruning) และการยุติการทำงานก่อนกำหนด (early termination)
• การเรียกค้นที่ทนทานต่อข้อผิดพลาด (tolerant retrieval)

Key theories

ดัชนีผกผันเป็นโครงสร้างข้อมูลหลัก

การจับคู่แต่ละคำศัพท์กับรายการปรากฏของเอกสาร (และตำแหน่ง) ที่คำนั้นปรากฏ ช่วยให้การเรียกค้นสามารถเข้าถึงเฉพาะเอกสารที่มีคำศัพท์ในข้อคำถามเท่านั้น ทำให้เป็นโครงสร้างพื้นฐานสำหรับการค้นหาข้อความที่ปรับขนาดได้

การแลกเปลี่ยนระหว่างการบีบอัดและประสิทธิภาพ

การเข้ารหัสช่องว่างรหัสเอกสาร (document-id gaps) และความถี่ของคำศัพท์ (term frequencies) ด้วยรหัสจำนวนเต็มแบบกระชับช่วยลดขนาดดัชนีได้อย่างมาก และด้วยการลดการรับเข้า/ส่งออก (input/output) และปรับปรุงพฤติกรรมแคช (cache behavior) ยังสามารถเร่งการประมวลผลข้อคำถามได้อีกด้วย

การประเมินข้อคำถามที่จัดอันดับอย่างมีประสิทธิภาพ

กลยุทธ์แบบเอกสารต่อครั้ง (document-at-a-time) และคำต่อครั้ง (term-at-a-time) เมื่อรวมกับเทคนิคการตัดแต่งแบบไดนามิก (dynamic pruning) และการยุติการทำงานก่อนกำหนด (early-termination) ช่วยให้ระบบสามารถส่งคืนผลลัพธ์ที่จัดอันดับสูงสุดโดยไม่ต้องให้คะแนนชุดข้อมูลทั้งหมด

Clinical relevance

ดัชนีผกผันและการประมวลผลข้อคำถามที่มีประสิทธิภาพเป็นหัวใจสำคัญของระบบค้นหาที่ใช้งานจริงทุกระบบ ตั้งแต่เครื่องมือค้นหาบนเว็บและแพลตฟอร์มค้นหาแบบโอเพนซอร์ส ไปจนถึงการค้นหาข้อความเต็มรูปแบบในองค์กรและฐานข้อมูล ประสิทธิภาพของสิ่งเหล่านี้เป็นตัวกำหนดความหน่วงของข้อคำถาม (query latency), ต้นทุนฮาร์ดแวร์, และขนาดของชุดข้อมูลที่สามารถค้นหาแบบโต้ตอบได้โดยตรง

History

ไฟล์ผกผัน (inverted files) ถูกนำมาใช้สำหรับการค้นหาข้อความตั้งแต่ระบบสารสนเทศยุคแรกเริ่ม แต่ทฤษฎีสมัยใหม่ของการสร้างดัชนี การบีบอัด และการประเมินที่มีประสิทธิภาพได้ถูกรวบรวมขึ้นในช่วงทศวรรษ 1990 โดยเฉพาะอย่างยิ่งจากผลงาน Managing Gigabytes ของ Witten, Moffat, และ Bell การสำรวจในปี 2006 ของ Zobel และ Moffat ได้สังเคราะห์งานวิจัยดัชนีผกผันตลอดสองทศวรรษที่ผ่านมา ในขณะที่การค้นหาขนาดเว็บทำให้ประสิทธิภาพเป็นสิ่งสำคัญสูงสุด

Key figures

• Justin Zobel
• Alistair Moffat
• Ian H. Witten
• W. Bruce Croft

Seminal works

• zobel2006
• wittenmgb1999
• manning2008

Frequently asked questions

เหตุใดดัชนีผกผันจึงเป็นที่นิยมมากกว่าการสแกนเอกสาร?

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

การบีบอัดดัชนีทำให้การค้นหาช้าลงหรือไม่?

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