list belongs to, so the termIDs of

list belongs to, so the termIDs of postings need not be stored. As a result, the
blocks that individual calls of SPIMI-INVERT can process are much larger
and the index construction process as a whole is more efficient.
Becausewe do not know how large the postings list of a termwill be when
we first encounter it, we allocate space for a short postings list initially and
double the space each time it is full (lines 8–9). This means that some memory
is wasted, which counteracts the memory savings from the omission of
termIDs in intermediate data structures. However, the overall memory requirements
for the dynamically constructed index of a block in SPIMI are
still lower than in BSBI.
Whenmemory has been exhausted,we write the index of the block (which
consists of the dictionary and the postings lists) to disk (line 12). We have to
sort the terms (line 11) before doing this because we want to write postings
lists in lexicographic order to facilitate the final merging step. If each block’s
postings lists were written in unsorted order, merging blocks could not be
accomplished by a simple linear scan through each block.
Each call of SPIMI-INVERT writes a block to disk, just as in BSBI. The last
step of SPIMI (corresponding to line 7 in Figure 4.2; not shown in Figure 4.4)
is then to merge the blocks into the final inverted index.
In addition to constructing a new dictionary structure for each block and
eliminating the expensive sorting step, SPIMI has a third important component:
compression. Both the postings and the dictionary terms can be stored
compactly on disk if we employ compression. Compression increases the efficiency
of the algorithm further because we can process even larger blocks,
and because the individual blocks require less space on disk. We refer readers
to the literature for this aspect of the algorithm (Section 4.7).

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

รายชื่อสมาชิก เพื่อ termIDs การลงรายการต้องไม่เก็บไว้ ดังนั้น การบล็อกที่สามารถประมวลผลแต่ละสายของ SPIMI กลับมีขนาดใหญ่กว่าและการสร้างดัชนี โดยรวมมีประสิทธิภาพมากขึ้นไม่ทราบ Becausewe ขนาด termwill เป็นรายการลงรายการบัญชีได้เมื่อเราแรกพบมัน เราจัดสรรพื้นที่สำหรับลงสั้นรายการขั้นต้น และคู่ว่างแต่ละครั้งเต็ม (บรรทัดที่ 8 – 9) นี้หมายความ ว่า หน่วยความจำสิ้นเปลือง ที่ counteracts ประหยัดหน่วยความจำจากการละเลยของกิจกรtermIDs ในโครงสร้างข้อมูลระดับกลาง อย่างไรก็ตาม ความต้องการหน่วยความจำทั้งหมดสำหรับดัชนีสร้างขึ้นแบบไดนามิกของบล็อกใน SPIMIยังคงต่ำกว่าใน BSBIเรา Whenmemory ได้แล้ว เขียนดัชนีของบล็อก (ซึ่งประกอบด้วยพจนานุกรมและรายการที่ลงรายการบัญชี) ดิสก์ (บรรทัด 12) เราต้องเรียงลำดับเงื่อนไข (บรรทัด 11) ก่อนที่จะทำนี้เนื่องจากเราต้องการเขียนลงรายการในใบสั่ง lexicographic เพื่อความสะดวกในขั้นตอนสุดท้ายรวม ถ้าแต่ละบล็อคเขียนรายการลงรายการบัญชีในใบสั่ง unsorted ไม่สามารถบล็อกรวมทำได้ โดยการสแกนเชิงเส้นอย่างง่ายโดยแต่ละบล็อคแต่ละการเรียกกลับ SPIMI เขียนบล็อกในดิสก์ เช่นเดียวกับ BSBI สุดท้ายขั้นตอนของ SPIMI (ที่ตรงกับบรรทัดที่ 7 ในรูป 4.2 ไม่แสดงในรูปที่ 4.4)จากนั้นจะต้อง ผสานบล็อกดัชนีกลับสุดท้ายนอกจากการสร้างโครงสร้างพจนานุกรมใหม่สำหรับแต่ละบล็อค และSPIMI ตัดขั้นตอนเรียงลำดับราคาแพง มีสามส่วนประกอบสำคัญ:อัด การลงรายการบัญชีและเงื่อนไขพจนานุกรมสามารถเก็บcompactly บนดิสก์ถ้าเราใช้การบีบอัด อัดเพิ่มประสิทธิภาพของอัลกอริทึมการเพิ่มเติมเนื่องจากเราสามารถประมวลผลขนาดใหญ่กว่าบล็อกและเนื่อง จากแต่ละบล็อกต้องน้อยกว่าเนื้อที่ว่างบนดิสก์ เราอ้างอิงผู้อ่านเอกสารประกอบการในด้านนี้ของอัลกอริทึม (หัวข้อ 4.7)

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

รายการเป็นดังนั้น termIDs โพสต์ไม่จำเป็นต้องเก็บไว้ เป็นผลให้
บล็อกที่โทรแต่ละ SPIMI-INVERT สามารถประมวลผลมีขนาดใหญ่
และการดำเนินการก่อสร้างดัชนีโดยรวมมีประสิทธิภาพมากขึ้น.
Becausewe ไม่ทราบวิธีการที่มีขนาดใหญ่โพสต์รายชื่อของ termwill จะเป็นเมื่อ
ครั้งแรกที่เราพบมันเรา จัดสรรพื้นที่สำหรับการโพสต์รายชื่อสั้น ๆ ในตอนแรกและ
สองเท่าของพื้นที่ในแต่ละครั้งที่มันเต็ม (เส้น 8-9) ซึ่งหมายความว่าหน่วยความจำบางส่วน
จะเสียซึ่งต่อต้านการออมที่มีหน่วยความจำจากการละเลยของ
termIDs ในโครงสร้างข้อมูลกลาง แต่ต้องการหน่วยความจำโดยรวม
สำหรับดัชนีที่สร้างขึ้นแบบไดนามิกของบล็อกใน SPIMI มี
ยังคงต่ำกว่าใน BSBI.
Whenmemory ได้หมดเราเขียนดัชนีของบล็อก (ซึ่ง
ประกอบด้วยพจนานุกรมและรายการโพสต์) ไปยังดิสก์ (สาย 12) เราต้อง
จัดเรียงเงื่อนไข (สาย 11) ก่อนที่จะทำเช่นนี้เพราะเราต้องการที่จะเขียนโพสต์
รายชื่อในการสั่งซื้อพจนานุกรมเพื่ออำนวยความสะดวกในขั้นตอนการควบรวมครั้งสุดท้าย ถ้าบล็อกของแต่ละคน
โพสต์รายชื่อที่ถูกเขียนขึ้นในลำดับที่ไม่ได้เรียงลำดับกลมกลืนบล็อกไม่สามารถ
ทำได้โดยการสแกนเชิงเส้นอย่างง่ายผ่านแต่ละบล็อก.
เรียกร้องของแต่ละ SPIMI-INVERT เขียนบล็อกไปยังดิสก์เช่นเดียวกับใน BSBI ที่ผ่าน
ขั้นตอนของการ SPIMI (ตรงกับสายที่ 7 ในรูปที่ 4.2; ไม่ได้แสดงในรูปที่ 4.4)
. เป็นแล้วจะผสานลงในบล็อกดัชนีคว่ำสุดท้าย
นอกเหนือจากการสร้างโครงสร้างพจนานุกรมใหม่สำหรับแต่ละบล็อกและ
ขจัดขั้นตอนการคัดแยกที่มีราคาแพง SPIMI มีองค์ประกอบที่สำคัญที่สาม:
การบีบอัด ทั้งการโพสต์และเงื่อนไขพจนานุกรมสามารถเก็บไว้
ดานบนดิสก์ถ้าเราใช้การบีบอัด การบีบอัดเพิ่มประสิทธิภาพ
ของขั้นตอนวิธีต่อไปเพราะเราสามารถดำเนินการบล็อกได้ขนาดใหญ่
และเนื่องจากบล็อกบุคคลที่จำเป็นต้องใช้พื้นที่น้อยลงในดิสก์ เราเรียกผู้อ่าน
วรรณกรรมสำหรับทุกแง่มุมของอัลกอริทึมนี้ (มาตรา 4.7)

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

รายการของ ดังนั้น termids โพสต์ไม่ต้องเก็บไว้ เป็นผลให้ ,
บล็อกแต่ละสายของ spimi-invert สามารถประมวลผลมีขนาดใหญ่มาก
และกระบวนการก่อสร้าง ดัชนีโดยรวมมีประสิทธิภาพมากขึ้น .
becausewe ไม่ทราบว่าขนาดใหญ่รายการโพสต์ของ termwill เมื่อ
แรกที่เราพบ เราจัดสรรพื้นที่สำหรับการเริ่มต้นและ
รายการสั้น ๆเพิ่มพื้นที่ในแต่ละครั้งมันเต็ม ( สาย 8 – 9 ) นี้หมายความว่าบางความทรงจำ
สูญเปล่า ซึ่งช่วยประหยัดหน่วยความจำจากการละเลยของ
termids โครงสร้างข้อมูลระดับกลาง อย่างไรก็ตาม ความต้องการหน่วยความจำโดยรวม
สำหรับแบบไดนามิกสร้างดัชนีของบล็อกใน spimi จะยังต่ำกว่าใน bsbi
.
whenmemory ได้หมด เราเขียนบล็อก ( ซึ่ง
ดัชนีของประกอบด้วยพจนานุกรมและการโพสต์รายการ ) ไปยังดิสก์ ( สาย 12 ) เราต้อง
เรียงแง่ ( สาย 11 ) ก่อนทำอย่างนี้เพราะเราต้องการเขียนรายการโพสต์
เพื่อ lexicographic านสุดท้ายรวมขั้นตอน ถ้าเป็นบล็อกโพสต์แต่ละรายการ
เขียนเพื่อเรียงผสานบล็อกได้สำเร็จโดยง่าย เส้น

สแกนผ่านแต่ละบล็อกโทรแต่ละครั้งของ spimi-invert เขียนบล็อกดิสก์ เช่นเดียวกับใน bsbi . ขั้นตอนสุดท้ายของ spimi
( ตรงกับบรรทัดที่ 7 ในรูปที่ 4.2 ; ไม่แสดงในรูปที่ 4.4 )
ถึงผสานลงในบล็อกสุดท้ายคว่ำดัชนี
นอกจากการสร้างโครงสร้างพจนานุกรมใหม่สำหรับแต่ละบล็อก และไม่แพง คัดแยก
ขั้นตอน spimi มี 3 ส่วนประกอบสำคัญ :
การบีบอัดทั้งการโพสต์และพจนานุกรมศัพท์สามารถเก็บไว้บนดิสก์
แบบกะทัดรัด ถ้าเราจ้างการบีบอัด การเพิ่มประสิทธิภาพของขั้นตอนวิธีต่อไป
เพราะเราสามารถกระบวนการบล็อกแม้แต่ใหญ่
และเนื่องจากแต่ละบล็อกต้องใช้พื้นที่น้อยบนดิสก์ เราหมายถึงผู้อ่าน
กับวรรณกรรมสำหรับด้านนี้ของขั้นตอนวิธี ( มาตรา 5 )