ดัชนีผกผัน

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

Definition

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

Scope

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

Core questions

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

Key concepts

• พจนานุกรมคำศัพท์
• รายการเอกสาร
• ตัวระบุเอกสาร
• ดัชนีตำแหน่ง
• การจัดเก็บความถี่ของคำ
• การจัดทำดัชนีแบบบล็อกโดยใช้การเรียงลำดับ (BSBI)
• การจัดทำดัชนีในหน่วยความจำแบบผ่านครั้งเดียว (SPIMI)
• การรวมและการอัปเดตดัชนี

Key theories

การจัดระเบียบพจนานุกรมและรายการเอกสาร

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

การสร้างดัชนีที่ปรับขนาดได้

วิธีการที่ใช้ดิสก์ เช่น การจัดทำดัชนีแบบบล็อกโดยใช้การเรียงลำดับและการจัดทำดัชนีในหน่วยความจำแบบผ่านครั้งเดียว สร้างไฟล์ผกผันสำหรับชุดข้อมูลที่มีขนาดใหญ่กว่าหน่วยความจำมาก โดยการสะสมและรวมดัชนีบางส่วน

Clinical relevance

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

History

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

Key figures

• Justin Zobel
• Alistair Moffat
• Steffen Heinz

Seminal works

• zobel2006
• heinz2003
• manning2008

Frequently asked questions

ทำไมถึงเรียกว่า 'ดัชนีผกผัน'?

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

ดัชนีตำแหน่งใช้สำหรับอะไร?

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