The algorithm parses documents into

The algorithm parses documents into termID–docID pairs and accumulates
the pairs inmemory until a block of a fixed size is full (PARSENEXTBLOCK
in Figure 4.2). We choose the block size to fit comfortably into memory to
permit a fast in-memory sort. The block is then inverted and written to disk.
INVERSION Inversion involves two steps. First, we sort the termID–docID pairs. Next,
we collect all termID–docID pairs with the same termID into a postings list,
POSTING where a posting is simply a docID. The result, an inverted index for the block
we have just read, is thenwritten to disk. Applying this to Reuters-RCV1 and
assuming we can fit 10 million termID–docID pairs into memory, we end up
with ten blocks, each an inverted index of one part of the collection.
In the final step, the algorithm simultaneously merges the ten blocks into
one large merged index. An example with two blocks is shown in Figure 4.3,
where we use di to denote the ith document of the collection. To do the merging,
we open all block files simultaneously, and maintain small read buffers
for the ten blocks we are reading and a write buffer for the final merged index
we are writing. In each iteration, we select the lowest termID that has
not been processed yet using a priority queue or a similar data structure. All
postings lists for this termID are read and merged, and the merged list is
written back to disk. Each read buffer is refilled from its file when necessary.
How expensive is BSBI? Its time complexity is Q(T log T) because the step
with the highest time complexity is sorting and T is an upper bound for the
number of items we must sort (i.e., the number of termID–docID pairs).

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

อัลกอริทึมการวิเคราะห์เอกสารเป็นคู่ termID – docID และสะสมinmemory คู่จนกว่าจะบล็อกขนาดถาวร (PARSENEXTBLOCKในรูปที่ 4.2) เราเลือกขนาดบล็อกสบายเข้าหน่วยความจำอนุญาตให้การเรียงลำดับอย่างรวดเร็วในหน่วยความจำ บล็อคแล้วจะกลับ และการเขียนดิสก์กลับกลับเกี่ยวข้องกับขั้นตอนที่สอง ครั้งแรก เราเรียงลำดับคู่ termID – docID ถัดไปเรารวบรวม termID – docID คู่กับ termID เดียวกันเป็นรายการลงรายการบัญชีลงรายการบัญชีการลงรายการบัญชีอยู่เพียง docID ผล ดัชนีกลับสำหรับบล็อคเราอ่าน เป็น thenwritten ไปยังดิสก์ ใช้นี้รอยเตอร์ส-RCV1 และสมมติว่า เราสามารถแบ่งออกเป็น 10 ล้านคู่ termID – docID หน่วยความจำ เราเอยมี 10 บล็อก แต่ละดัชนีกลับของส่วนหนึ่งของคอลเลกชันในขั้นตอนสุดท้าย อัลกอริทึมพร้อมผสานเป็นบล็อกสิบหนึ่งใหญ่ผสานดัชนี ตัวอย่าง มี 2 บล็อกจะแสดงในรูปที่ 4.3ที่เราใช้ di เพื่อแสดงเอกสารระยะของคอลเลกชัน ทำการผสานเราเปิดบล็อกแฟ้มทั้งหมดพร้อมกัน และรักษาบัฟเฟอร์เล็กอ่านบล็อก 10 ที่เรากำลังอ่านและเขียนบัฟเฟอร์สำหรับดัชนีรวมสุดท้ายเราจะเขียน เนื่อง เราเลือก termID ต่ำที่มีไม่ได้ประมวลผลยัง ใช้คิวลำดับความสำคัญหรือโครงสร้างข้อมูลที่คล้ายกัน ทั้งหมดลงรายการบัญชีรายการใน termID นี้จะอ่านผสาน และรายการรวมเขียนกลับไปยังดิสก์ อ่านเป็นเติมบัฟเฟอร์จากแฟ้มของเมื่อจำเป็นBSBI จะแพงอย่างไร ความซับซ้อนของเวลาเป็น Q (ล็อก T T) เนื่องจากขั้นตอนเรียงลำดับเวลาสูง ซับซ้อน และ T จะเป็นขอบเขตบนสำหรับการหมายเลขของสินค้าที่เราต้องเรียงลำดับ (เช่น จำนวนคู่ termID – docID)

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

ขั้นตอนวิธีการแยกวิเคราะห์เอกสารเป็น termID-docid คู่และสะสม
คู่ inmemory จนกว่าบล็อกของขนาดคงเต็ม (PARSENEXTBLOCK
ในรูปที่ 4.2) เราเลือกบล็อกขนาดเพื่อให้พอดีกับความสะดวกสบายในหน่วยความจำที่จะ
อนุญาตให้มีการจัดเรียงอย่างรวดเร็วในหน่วยความจำ บล็อกจะกลับแล้วและเขียนไปยังดิสก์.
INVERSION ผกผันเกี่ยวข้องกับขั้นตอนที่สอง ครั้งแรกที่เราจัดเรียงคู่ termID-docid ถัดไป
ที่เราเก็บรวบรวมทุกคู่ termID-docid กับ termID เดียวกันลงในรายการโพสต์,
โพสต์ที่โพสต์เป็นเพียง docid ส่งผลให้ดัชนีกลับสำหรับบล็อก
ที่เราได้อ่านเพียงแค่เป็น thenwritten ไปยังดิสก์ ใช้นี้รอยเตอร์-RCV1 และ
สมมติว่าเราสามารถใส่ 10 ล้านคู่ termID-docid ในหน่วยความจำเราท้าย
สิบบล็อกแต่ละดัชนีคว่ำของส่วนหนึ่งของคอลเลกชัน.
ในขั้นตอนสุดท้ายอัลกอริทึมดังกล่าวพร้อมกันสิบช่วงตึก เข้าไปใน
หนึ่งดัชนีที่ผสานขนาดใหญ่ ตัวอย่างเช่นมีสองช่วงตึกแสดงในรูปที่ 4.3
ที่เราใช้ di เพื่อแสดงเอกสาร ith ของคอลเลกชัน การทำเช่นการควบรวมที่
เราเปิดไฟล์บล็อกทั้งหมดพร้อมกัน, และการบำรุงรักษาบัฟเฟอร์อ่านขนาดเล็ก
สำหรับสิบบล็อกเราจะอ่านและการเขียน buffer สำหรับดัชนีที่ผสานสุดท้าย
เรากำลังเขียน ในแต่ละซ้ำเราเลือก termID ต่ำสุดที่ได้
รับการประมวลผลไม่ได้ใช้คิวลำดับความสำคัญหรือโครงสร้างข้อมูลที่คล้ายกัน ทุก
โพสต์รายการสำหรับ termID นี้อ่านและควบรวมกิจการและรายการที่ผสานจะ
เขียนกลับไปยังดิสก์ อ่านแต่ละบัฟเฟอร์เติมจากแฟ้มเมื่อมีความจำเป็น.
วิธีราคาแพง BSBI? ความซับซ้อนของมันคือเวลา Q (log T T) เพราะขั้นตอน
ที่มีความซับซ้อนเวลาสูงสุดคือการเรียงลำดับและ T คือขีด จำกัด บนสำหรับ
จำนวนของรายการที่เราจะต้องจัดเรียง (เช่นจำนวนคู่ termID-docid)

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

วิธีวิเคราะห์เอกสารใน termid – docid คู่และสะสม
คู่ inmemory จนกว่าบล็อกของขนาดคงที่เต็ม ( parsenextblock
ในรูปที่ 4.2 ) เราเลือกบล็อกขนาดเพื่อให้พอดีกับความสะดวกสบายในความทรงจำ

ให้รวดเร็วในการจัดเรียงหน่วยความจำ บล็อกเป็นแล้วเอามาเขียนไปยังดิสก์ .
ผกผันผกผันที่เกี่ยวข้องกับสองขั้นตอน ครั้งแรกที่เราเรียง termid – docid คู่ ต่อไป
เรารวบรวมทั้งหมด termid – docid คู่กับ termid ลงในรายการการโพสต์
โพสต์ที่โพสต์เป็นเพียง docid . ผล กลับดัชนีบล็อก
เราเพิ่งได้อ่าน เป็น thenwritten ไปยังดิสก์ ใช้สิ่งนี้เพื่อ reuters-rcv1 และ
สมมติว่าเราสามารถให้ 10 ล้าน termid – docid คู่เข้าไปในหน่วยความจำ เราสิ้นสุดขึ้น
10 บล็อก แต่ละกลับดัชนีส่วนหนึ่งของคอลเลกชัน .
ในขั้นตอนสุดท้าย ขั้นตอนวิธีการ พร้อมผสานบล็อกสิบใน
ขนาดใหญ่หนึ่งรวมดัชนี ตัวอย่างสองบล็อกจะแสดงในรูปที่ 4.3
ที่เราใช้ ดิ ไปจนถึง ith เอกสารคอลเลกชัน ทำผสาน
เราเปิดไฟล์บล็อกพร้อมกันทั้งหมด และรักษา
บัฟเฟอร์อ่านขนาดเล็กสำหรับสิบบล็อกที่เราอ่านและเขียนบัฟเฟอร์สำหรับขั้นสุดท้ายรวมดัชนี
เรากำลังเขียนในแต่ละซ้ำ เราเลือกที่ถูกที่สุด termid ที่มี
ไม่ได้รับการประมวลผลการใช้แถวคอยลำดับความสำคัญหรือโครงสร้างของข้อมูลที่คล้ายคลึงกัน
ประกาศรายชื่อทั้งหมดนี้ termid จะอ่านและผสานและรวมรายชื่อ
เขียนกลับไปยังดิสก์ อ่านแต่ละบัฟเฟอร์มีอายุจากแฟ้มเมื่อจำเป็น .
bsbi น่ะแพงแค่ไหน เวลาของความซับซ้อนคือ Q ( T
T ) ) เพราะขั้นตอนกับเวลาที่มีความซับซ้อน การเรียงลำดับ และ t คือขอบเขตบน
จำนวนรายการที่เราต้องเรียง ( เช่น จำนวนของ termid – docid คู่ )