1 System DesignWe followed the stru

1 System Design
We followed the structure of the starter code and kept the predefined interface. To summarize: • Index class implements the BSBI indexing algorithm
• Query class implements boolean conjunctive query processing algorithm
• BaseIndex defines the interface for writing/reading posting lists
• BasicIndex class writes uncompressed posting lists to/reads posting lists from disk • VBIndex writes/reads posting lists with variable byte encoding for gaps
• GammaIndex writes/reads posting lists with gamma encoding for gaps
There are also some helper classes, e.g. ListLengthComparator which is used for sorting posting lists when processing the query.
Some key algorithm are explained in detail as follows.
1.1 Indexing Algorithm
Key steps in the indexing algorithm are: 1. Process blocks one by one:
(a) For each block, traverse each file and generate pairs
(b) After processing all files in the block, sort the pairs first by Term
ID then by Doc ID and organize pairs with the same Term ID into a posting list
(c) Create a file and store the posting lists with specified posting list writing algorithm
(d) Push the file into the merge queue
2. Merge blocks into a unified index:
(a) Pop two block files from the queue
(b) Merge the postings lists with the same Term ID (if possible) into a single one with standard merging algorithm
1
(c) Write merged posting lists into a merged file (d) Push the merged file into the merge queue
(e) Proceed until the size of queue is 1
3. Write supplemental information (Term to Term ID mapping, Doc Name to Doc ID mapping, posting list positions) out to files
The indexing algorithm guarantees that:
1. Term ID and Doc ID are always greater than 0 (so there’s no problem for γ encoding)
2. When indexing the blocks, only one block is loaded into memory at a time
3. When merging two blocks, the indexes are loaded in in a stream fashion. That is, for each index to merge, only a posting list is loaded at a time.

ผลลัพธ์ (ไทย) 1:

ออกแบบระบบ 1เราตามโครงสร้างของรหัสเริ่มต้น และอินเทอร์เฟซที่กำหนดไว้ล่วงหน้าเก็บไว้ สรุป: •ระดับดัชนีที่ใช้อัลกอริทึมการทำดัชนี BSBI•สอบถามคลาสได้ถาม conjunctive boolean อัลกอริธึมการประมวลผล• BaseIndex กำหนดอินเทอร์เฟซสำหรับการเขียน/อ่านรายการลงรายการบัญชี• BasicIndex ชั้นเขียนรายการเพื่อลงรายการบัญชีการบีบอัด / อ่านลงรายการบัญชีรายการจากดิสก์•เขียน VBIndex/ลง รายการบัญชีรายการที่ มีตัวแปรไบต์ที่เข้ารหัสสำหรับช่องว่างอ่าน• GammaIndex เขียน/อ่านลงรายการบัญชีรายการที่ มีแกมมาเข้ารหัสสำหรับช่องว่างมีผู้ช่วยบางประเภท เช่น ListLengthComparator ซึ่งใช้สำหรับการเรียงลำดับรายการบัญชีเมื่อการประมวลผลแบบสอบถามอัลกอริทึมคีย์บางจะอธิบายในรายละเอียดดังนี้1.1 การจัดทำดัชนีอัลกอริทึมกุญแจสำคัญอัลกอริทึมการจัดทำดัชนีมี: 1. กระบวนการบล็อกหนึ่งโดยหนึ่ง:(ก) สำหรับแต่ละบล็อก เคลื่อนที่แต่ละไฟล์ และสร้าง คู่(ข) หลังจากการประมวลผลแฟ้มทั้งหมดในบล็อก เรียงความ คู่ โดยระยะแรกแล้วรหัส โดยรหัสเอกสาร และจัดระเบียบคู่กับ ID ระยะเดียวกันเป็นรายการลงรายการบัญชี(ค) สร้างแฟ้ม และจัดเก็บรายการลงรายการบัญชี ด้วยรายการบัญชีที่ระบุเขียนอัลกอริทึม(ง) ดันแฟ้มเข้าไปในคิวเวียน2. ผสานบล็อกดัชนีที่รวม:(ก) ป๊อปสองบล็อกแฟ้มจากคิว(ข) ผสานรายการลงรายการบัญชี ด้วย ID ที่ระยะเดียวกัน (ถ้าทำได้) เป็นหนึ่งเดียวกับอัลกอริทึมการผสานมาตรฐาน1(ค) เขียนถูกผสานลงรายการลงในแฟ้มรวม (d) ดันผสานแฟ้มเข้าไปในคิวเวียน(จ) ดำเนินต่อจนกว่าขนาดของคิวคือ 13. เขียนข้อมูลเพิ่มเติม (ระยะระยะ ID แผนที่ ชื่อเอกสารรหัสเอกสารแมป การลงรายการบัญชีรายการตำแหน่ง) ออกไปยังแฟ้มอัลกอริทึมการทำดัชนีรับประกันที่:1. ระยะ ID และรหัสเอกสารมักมากกว่า 0 (เพื่อให้ไม่มีปัญหาสำหรับการเข้ารหัสγ)2. เมื่อดัชนีบล็อก บล็อกเดียวเท่านั้นจะถูกโหลดลงในหน่วยความจำครั้ง3. เมื่อรวมสองบล็อก ดัชนีถูกโหลดในในกระแสแฟชั่น นั่นคือ สำหรับแต่ละดัชนีการผสาน เฉพาะรายการลงรายการบัญชีถูกโหลดในเวลา

ผลลัพธ์ (ไทย) 2:

1 การออกแบบระบบ
เราตามโครงสร้างของรหัสเริ่มต้นและเก็บไว้อินเตอร์เฟซที่กำหนดไว้ล่วงหน้า เพื่อสรุป: •ระดับดัชนีดำเนิน BSBI การจัดทำดัชนีอัลกอริทึม
ระดับ•แบบสอบถามการดำเนินการขั้นตอนวิธีการประมวลผลแบบสอบถามแบบบูลที่เชื่อมต่อ
• BaseIndex กำหนดอินเตอร์เฟซสำหรับการเขียน / อ่านรายการโพสต์
•ระดับ BasicIndex เขียนรายการโพสต์ไม่มีการบีบอัดไป / อ่านโพสต์รายการจากดิสก์• VBIndex เขียน / อ่าน โพสต์รายการที่มีการเข้ารหัสไบต์ตัวแปรสำหรับช่องว่าง
• GammaIndex เขียน / อ่านโพสต์รายการที่มีการเข้ารหัสแกมมาช่องว่าง
นอกจากนี้ยังมีบางชั้นเรียนผู้ช่วยเช่น ListLengthComparator ซึ่งจะใช้สำหรับการเรียงลำดับการโพสต์รายชื่อเมื่อการประมวลผลแบบสอบถาม.
อัลกอริทึมที่สำคัญบางอย่างมีการอธิบายในรายละเอียดดังต่อไปนี้ .
1.1 การจัดทำดัชนีขั้นตอนวิธีการ
ขั้นตอนสำคัญในขั้นตอนวิธีการจัดทำดัชนีมีดังนี้ 1 บล็อกกระบวนการหนึ่งโดยหนึ่ง:
(ก) สำหรับแต่ละบล็อกสำรวจแต่ละไฟล์และสร้างคู่
(ข) หลังจากการประมวลผลไฟล์ทั้งหมดในบล็อกเรียงลำดับคู่เป็นครั้งแรกโดยมีระยะเวลา
ID แล้วตามด้วยรหัสเอกสารและจัดระเบียบคู่กับ ID ระยะเวลาเดียวกันในรายการโพสต์
(ค) สร้างไฟล์และเก็บรายการโพสต์โพสต์ที่มีรายชื่อที่ระบุขั้นตอนวิธีการเขียน
(ง) กดไฟล์ลงในการผสานคิว
2 ผสานบล็อกเป็นดัชนีแบบครบวงจร:
(ก) Pop สองไฟล์บล็อกจากคิว
(ข) ผสานรายการโพสต์ที่มี ID ระยะเดียวกัน (ถ้าเป็นไปได้) เป็นหนึ่งเดียวกับการรวมขั้นตอนวิธีการมาตรฐาน
1
(ค) เขียนรวมการโพสต์รายชื่อลงใน ไฟล์ที่ผสาน (ง) กดไฟล์รวมเข้าไปในคิวผสาน
(จ) ดำเนินการจนมีขนาดของคิวเป็น 1
3. เขียนข้อมูลเสริม (คำที่จะทำแผนที่ระยะ ID หมอชื่อหมอทำแผนที่ ID โพสต์ตำแหน่งรายการ) ออกไป ไฟล์
ค้ำประกันขั้นตอนวิธีการจัดทำดัชนีที่:
1 ID และรหัสระยะหมอมักจะมากกว่า 0 (เพื่อให้มีปัญหาสำหรับการเข้ารหัสγ No)
2 เมื่อจัดทำดัชนีบล็อกเพียงหนึ่งช่วงตึกถูกโหลดลงในหน่วยความจำในเวลา
3 เมื่อผสานสองช่วงตึกดัชนีมีการโหลดในในแฟชั่นสตรีม นั่นคือสำหรับแต่ละดัชนีจะผสานเพียงรายการโพสต์มีการโหลดในเวลา

ผลลัพธ์ (ไทย) 3:

แบบที่ 1 ระบบเราตามโครงสร้างของรหัสเริ่มต้นและเก็บไว้ที่กำหนดอินเตอร์เฟซ สรุป : คลาส - ดัชนีการใช้ bsbi ขั้นตอนวิธีบริการค้นหาชั้นใช้ตรรกะขั้นตอนวิธีการประมวลผลการสอบถามบริการ baseindex กำหนดอินเตอร์เฟซสำหรับการเขียน / อ่านโพสต์รายการ- ระดับการบีบอัด basicindex เขียนโพสต์รายการ / อ่านโพสต์รายชื่อจาก vbindex แต่ละดิสก์เขียน / อ่านโพสต์รายการกับตัวแปรไบต์เข้ารหัสช่องว่างบริการ gammaindex เขียน / อ่านโพสต์รายการและการเข้ารหัสสำหรับช่องว่างนอกจากนี้ยังมีบางชั้นเรียน ผู้ช่วยเหลือ เช่น listlengthcomparator ซึ่งใช้สำหรับการเรียงลำดับการโพสต์รายการเมื่อการประมวลผลแบบสอบถามที่สำคัญบางขั้นตอนวิธีที่อธิบายในรายละเอียดดังนี้ขั้นตอนวิธีการทำดัชนีขั้นตอนสำคัญในการสร้างดัชนีขั้นตอน : 1 . กระบวนการบล็อกหนึ่งโดยหนึ่ง :( ก ) สำหรับแต่ละบล็อก เข้าไปแต่ละไฟล์และสร้าง < เทอม ID ID > คู่หมอ( ข ) หลังจากประมวลผลไฟล์ทั้งหมดในบล็อก เรียง < เทอม ID หมอ ID > คู่แรก โดยระยะID แล้ว โดยหมอประจำตัวและจัดคู่กับระยะเดียวกัน ID เป็นโพสต์รายการ( c ) สร้างไฟล์และจัดเก็บการโพสต์รายการที่มีระบุโพสต์รายการเขียนอัลกอริทึม( ง ) ดันแฟ้มลงในคิว ผสาน2 . ผสานลงในบล็อกรวมดัชนี :( ก ) ปรากฏสองบล็อกไฟล์จากคิว( ข ) ผสานการโพสต์รายการกับ ID ในระยะเดียวกัน ( ถ้าเป็นไปได้ ) เป็นหนึ่งในขั้นตอนวิธีการเดียวกับมาตรฐาน1( ค ) เขียนรายการลงในการโพสต์ที่ผสานรวมไฟล์ ( D ) กดรวมไฟล์ลงในคิว ผสาน( จ ) ดำเนินการจนถึงขนาดของคิวที่ 13 . เขียนข้อมูลเพิ่มเติม ( คำ ) , ID ในระยะหมอชื่อแผนที่ , ID หมอโพสต์ตำแหน่งรายการ ) เพื่อไฟล์ขั้นตอนวิธีการรับประกันว่า :1 . รหัส ID ระยะยาวและหมอมักจะมากกว่า 0 ( ไม่มีปัญหาสำหรับγการเข้ารหัส )2 . เมื่อดัชนีบล็อก บล็อกหนึ่งเท่านั้นจะโหลดลงในหน่วยความจำในเวลา3 . เมื่อผสานสองบล็อกดัชนีโหลดในกระแสแฟชั่น นั่นคือสำหรับแต่ละดัชนีผสานเพียงโพสต์รายการที่มีการโหลดในเวลา