姜 琨,朱 磊,宋省身,楊岳湘

1(西安理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院， 西安 710048)2(國(guó)防科技大學(xué) 計(jì)算機(jī)學(xué)院， 長(zhǎng)沙 410073)

1 引 言

不斷增長(zhǎng)的網(wǎng)頁(yè)數(shù)量和查詢請(qǐng)求量對(duì)搜索引擎的性能提出非常大的挑戰(zhàn)[1，2].互聯(lián)網(wǎng)中的網(wǎng)頁(yè)數(shù)量呈指數(shù)增長(zhǎng)， 搜索引擎為了保持索引信息的全面性，需要不斷地采集新出現(xiàn)的網(wǎng)頁(yè)和更新已索引的網(wǎng)頁(yè).目前，主流的搜索引擎如Google、百度其網(wǎng)頁(yè)索引量都超過(guò)了百億，但這也只占了整個(gè)互聯(lián)網(wǎng)中不到10%的網(wǎng)頁(yè)信息[3].根據(jù)Netcraft統(tǒng)計(jì)，截至2014年9月份互聯(lián)網(wǎng)上已經(jīng)擁有近10億個(gè)網(wǎng)站[注]Total number of Websites.http://www.internetlivestats.com/total-number-of-websites.2019.05.The size of the world wide web.http://www.worldwidewebsize.com.2019.05..正如《第43次中國(guó)互聯(lián)網(wǎng)網(wǎng)絡(luò)發(fā)展統(tǒng)計(jì)報(bào)告》指出，截至2018年底國(guó)內(nèi)的網(wǎng)頁(yè)總量就達(dá)到2816億個(gè)，較2017年底增長(zhǎng)了8.2%[4].近年來(lái)，互聯(lián)網(wǎng)上更多自媒體如Twitter、Quora、知乎等應(yīng)用的蓬勃發(fā)展使得搜索引擎系統(tǒng)待索引的數(shù)據(jù)規(guī)模進(jìn)一步增加[5，6].面向海量互聯(lián)網(wǎng)網(wǎng)頁(yè)數(shù)據(jù)的磁盤(pán)壓縮倒排索引數(shù)據(jù)非常龐大，擁有僅5千萬(wàn)個(gè)網(wǎng)頁(yè)的Clueweb09(B)數(shù)據(jù)集的壓縮索引就達(dá)到15GB(包含詞典文件和倒排文件)，更不用說(shuō)針對(duì)整個(gè)海量互聯(lián)網(wǎng)網(wǎng)頁(yè)的倒排索引數(shù)據(jù)[7].這些海量互聯(lián)網(wǎng)網(wǎng)頁(yè)數(shù)據(jù)給搜索引擎系統(tǒng)的倒排索引存儲(chǔ)和處理帶來(lái)了持續(xù)的挑戰(zhàn)和研究需求[2-8].此外，搜索引擎每天需要處理數(shù)億次查詢請(qǐng)求，相當(dāng)于每秒處理數(shù)千個(gè)查詢，并且這些查詢請(qǐng)求往往需要實(shí)時(shí)返回查詢結(jié)果[2].海量數(shù)據(jù)、海量查詢、實(shí)時(shí)響應(yīng)的應(yīng)用需求對(duì)搜索引擎的存儲(chǔ)和查詢性能提出了很大挑戰(zhàn)[8].

研究表明，利用倒排索引壓縮技術(shù)可以極大的降低倒排索引數(shù)據(jù)的磁盤(pán)存儲(chǔ)空間開(kāi)銷，并使更多的數(shù)據(jù)可以被加載到內(nèi)存中；通過(guò)結(jié)合高效的解壓操作就能達(dá)到對(duì)海量磁盤(pán)壓縮索引數(shù)據(jù)的快速查詢?cè)L問(wèn)[9].因此，倒排索引壓縮技術(shù)就成為提升海量倒排索引數(shù)據(jù)存儲(chǔ)和查詢性能的必要手段[10]，而研究人員也展開(kāi)了大量針對(duì)倒排索引壓縮算法及其在搜索引擎系統(tǒng)應(yīng)用中的性能優(yōu)化研究[9，11].倒排索引壓縮技術(shù)可以直接提升單個(gè)服務(wù)節(jié)點(diǎn)對(duì)索引數(shù)據(jù)的存儲(chǔ)性能.在磁盤(pán)上，索引壓縮技術(shù)可以使數(shù)據(jù)的存儲(chǔ)更加緊密，這就降低了數(shù)據(jù)訪問(wèn)過(guò)程中的磁盤(pán)尋道延遲[12].更重要的是，索引壓縮使得更多的索引數(shù)據(jù)可以直接加載到內(nèi)存中，現(xiàn)代計(jì)算機(jī)采用存儲(chǔ)器層來(lái)為處理器提供數(shù)據(jù)訪問(wèn)支持，最上層的緩存容量小，速度很快.依次向下層存儲(chǔ)器的容量將變大，但是速度變慢[13].倒排索引壓縮能夠使得更多的索引數(shù)據(jù)存入上層的存儲(chǔ)器中[14].可以看出，倒排索引壓縮技術(shù)實(shí)際上關(guān)系到搜索引擎的索引存儲(chǔ)、更新和查詢性能，因此對(duì)倒排索引壓縮算法的研究在商業(yè)搜索引擎公司和學(xué)術(shù)領(lǐng)域上都屬于熱點(diǎn)與難點(diǎn)問(wèn)題.

本文對(duì)當(dāng)前倒排索引壓縮技術(shù)的發(fā)展動(dòng)態(tài)進(jìn)行綜述，對(duì)倒排索引壓縮算法和應(yīng)用進(jìn)行系統(tǒng)化地總結(jié)，以期望能夠應(yīng)對(duì)這一領(lǐng)域研究面臨的新的挑戰(zhàn)并為進(jìn)一步的研究工作提供幫助.

2 傳統(tǒng)倒排索引壓縮算法

在擁有大規(guī)模索引數(shù)據(jù)的搜索引擎中，倒排索引被證明是一種非常高效的數(shù)據(jù)結(jié)構(gòu)[15，16].基本的倒排索引主要由詞典和倒排鏈表兩部分組成.詞典由大量的詞項(xiàng)組成，主要用來(lái)記錄整個(gè)文檔集合中出現(xiàn)過(guò)的詞項(xiàng)和對(duì)應(yīng)的倒排鏈表指針.倒排鏈表記錄了該詞項(xiàng)在不同文檔中的命中信息、位置信息或者預(yù)計(jì)算分?jǐn)?shù)等信息.在實(shí)際應(yīng)用中，詞典文件比起倒排文件來(lái)說(shuō)通常要小得多，所以當(dāng)前研究人員主要集中于對(duì)倒排鏈表壓縮算法的研究[17，18].倒排鏈表存儲(chǔ)在磁盤(pán)上，每個(gè)從磁盤(pán)讀取的數(shù)據(jù)塊(block)包含一定數(shù)量的倒排鏈表的數(shù)據(jù)段(data chunk，DC).每個(gè)數(shù)據(jù)段作為壓縮算法處理的基本單位，包含著一串被壓縮的整數(shù)序列.每個(gè)數(shù)據(jù)段包含一組docid和對(duì)應(yīng)的一組freq.圖1給出倒排鏈表的數(shù)據(jù)塊和數(shù)據(jù)段的關(guān)系.

在倒排鏈表壓縮過(guò)程中，各個(gè)倒排項(xiàng)都包含文檔號(hào)(docid)信息，并且每個(gè)詞項(xiàng)的倒排鏈表中的倒排項(xiàng)按文檔號(hào)從小到大進(jìn)行排列.這使得在存儲(chǔ)文檔號(hào)docid信息時(shí)，可以存儲(chǔ)文檔號(hào)docid之間的差值d-gap來(lái)提升倒排鏈表的壓縮率.文檔重排技術(shù)可以使得d-gap數(shù)值進(jìn)一步降低而提升倒排索引的壓縮率[19，20].根據(jù)Shannon的分析，分布概率為P(x)的數(shù)字的最優(yōu)壓縮比特長(zhǎng)度為-「log2P(x)?[12]；此外，互聯(lián)網(wǎng)網(wǎng)頁(yè)中詞項(xiàng)的文檔頻率服從Zipf定律(冪定律)[21].因此，倒排索引壓縮的目的就是采用盡可能接近最優(yōu)比特長(zhǎng)度的編碼來(lái)表示一個(gè)原來(lái)以32或64位機(jī)器字表示的d-gap整數(shù).我們稱壓縮狀態(tài)下的編碼為碼字(code word).

圖1 倒排鏈表結(jié)構(gòu)的數(shù)據(jù)塊和數(shù)據(jù)段關(guān)系圖Fig.1 Inverted lists of data blocks and data chunks

傳統(tǒng)的符號(hào)壓縮算法如Huffman編碼、算術(shù)編碼、PPM等半靜態(tài)或者自適應(yīng)壓縮方法需要預(yù)先知道被壓縮符號(hào)的統(tǒng)計(jì)信息并保留其壓縮模型，而互聯(lián)網(wǎng)網(wǎng)頁(yè)較快的更新速度使得d-gap序列不穩(wěn)定且無(wú)法為每個(gè)倒排鏈表d-gap序列保留一個(gè)穩(wěn)定的壓縮模型[22].另外，更加復(fù)雜的詞典方法如LZ77、LZW等也較少應(yīng)用在倒排索引壓縮中，這是因?yàn)榈古沛湵韉-gap序列的語(yǔ)義重復(fù)度要比符號(hào)序列小很多[23].因此，倒排索引壓縮算法的研究主要集中在不需要統(tǒng)計(jì)信息的輕量級(jí)壓縮(light-weighted compression)[24，25].倒排鏈表的壓縮算法按碼字對(duì)齊的方式可以分為：比特對(duì)齊(bit-aligned)壓縮算法和字節(jié)對(duì)齊(byte-aligned)壓縮算法.

比特對(duì)齊壓縮算法為給定每一個(gè)待壓縮整數(shù)分配一個(gè)對(duì)應(yīng)的碼字，而壓縮的過(guò)程就相當(dāng)于對(duì)輸入序列的符號(hào)替換.這些方法根據(jù)壓縮的模型，一般可以分為全局方法和局部方法，全局方法的碼字不依賴于輸入序列，對(duì)所有的輸入都使用同一模型進(jìn)行壓縮，這類算法有Unary、Gamma、Delta、Golomb、Rice等[12,22,26，27]；局部方法則根據(jù)輸入的變化適當(dāng)調(diào)整模型的參數(shù)，如Interpolative Code[28].局部模型在壓縮效果方面要優(yōu)于全局模型，但解壓過(guò)程的性能要比全局模型差.這類壓縮算法具有較高的壓縮率，但在解壓的時(shí)候頻繁的位操作運(yùn)算會(huì)大大地降低效率.

為了加快壓縮和解壓速度，進(jìn)而出現(xiàn)了字節(jié)對(duì)齊壓縮算法，如Varint(又稱為variable byte或者vbyte)、Group Varint等[1,29，30].它們的基本思想是使用字節(jié)的低7位來(lái)存儲(chǔ)數(shù)據(jù)，最高位作為壓縮結(jié)束的標(biāo)識(shí)符.字節(jié)對(duì)齊的壓縮方式可能會(huì)浪費(fèi)一部分空間，但解壓的速度要遠(yuǎn)高于比特對(duì)齊壓縮算法.在字節(jié)對(duì)齊壓縮算法的基礎(chǔ)上，Google公司提出并采用的Group Varint倒排索引壓縮算法可以大大提升Varint的解壓性能[1].它通過(guò)將原來(lái)由Varint壓縮的4個(gè)數(shù)字改為一次性壓縮來(lái)進(jìn)一步減少分支判斷，結(jié)合硬編碼(hard-coding)和移位(shifting)方法可以達(dá)到更好的壓縮/解壓性能.這是因?yàn)镚roup Varint對(duì)多個(gè)字節(jié)的狀態(tài)位進(jìn)行統(tǒng)一存儲(chǔ)，這樣就可以在單次數(shù)據(jù)操作中壓縮多個(gè)數(shù)字.這也表明一次性壓縮多個(gè)整數(shù)能提升壓縮和解壓的性能.此外，研究人員為了提高算法的壓縮率而提出了Nibble Varint壓縮算法，利用4比特作為單位來(lái)避免Varint對(duì)空間的浪費(fèi)[31].比特對(duì)齊壓縮算法能夠達(dá)到較高的壓縮率，而字節(jié)對(duì)齊壓縮算法能夠達(dá)到較好的壓縮/解壓速度[22].這兩類壓縮算法都是針對(duì)單個(gè)整數(shù)進(jìn)行壓縮，壓縮過(guò)程類似于將每個(gè)整數(shù)替換為對(duì)應(yīng)的碼字.

硬編碼和移位方法被廣泛應(yīng)用在各類倒排索引壓縮算法中以達(dá)到算法壓縮和解壓實(shí)現(xiàn)性能的提升[7，32].其中，硬編碼是指將壓縮算法的每一種填充模式的各類描述信息直接寫(xiě)入程序，避免壓縮和解壓過(guò)程的循環(huán)和分支判斷開(kāi)銷.通過(guò)硬編碼和移位方法可以避免循環(huán)和分支判斷的開(kāi)銷.表1和表2是采用硬編碼/移位方法的對(duì)5個(gè)整數(shù)進(jìn)行壓縮和解壓的例子.對(duì)于給定的待壓縮整數(shù)序列，通過(guò)逐個(gè)對(duì)整數(shù)的最大位寬和可壓縮整數(shù)個(gè)數(shù)進(jìn)行檢測(cè)來(lái)確定采用哪種填充模式(padding mode).

表1 compress_69算法偽碼
Table 1 Pseudocode of compress_69

input:5 integers in int array d and status s=691 r[0]=(r[0]<< 14) + d[0]2 r[0]=(r[0]<<10) +(d[1]>>>4)3 r[1]=(r[1]<<4) +((d[1]<<28)>>>28)4 r[1]=(r[1]<<9) + d[2]5 r[1]=(r[1]<<9) + d[3]6 r[1]=(r[1]<<9) + d[4]7 r[0]= s <<24 | r[0]output:2 codewords in int array r

在表1所示的壓縮過(guò)程中，給定的5個(gè)可單次壓縮的整數(shù)(d[1]～d[5])和填充模式的狀態(tài)信息s(s=69).算法依據(jù)填充模式的位寬等描述信息將5個(gè)整數(shù)移位至各自的預(yù)分配碼槽(padding slot)，然后將填充模式狀態(tài)信息s存儲(chǔ)在碼字頭部，這樣在解壓時(shí)通過(guò)移位操作就可以獲得碼字所采用的填充模式.

表2 decompress_69算法偽碼
Table 2 Pseudocode of decompress_69

input:2 integers codewords in array r1 d[0]=(r[0]<<8)>>>182 d[1]=(r[0]<<22)>>>18 |(r[1]>>>27)3 d[2]=(r[1]<<5)>>>234 d[3]=(r[1]<<14)>>>235 d[4]=(r[1]<<23)>>>23output:out_s=5 integers in int array d

在表2所示的解壓過(guò)程中，給定2個(gè)碼字r[0]和r[1]，每個(gè)整數(shù)在壓縮狀態(tài)下的位寬、可壓縮整數(shù)個(gè)數(shù)等信息由硬編碼描述，首先通過(guò)對(duì)碼字移位獲取碼字中存儲(chǔ)的填充模式的狀態(tài)信息s(s=r[0]?24)，之后選擇對(duì)應(yīng)的硬編碼解壓算法，最后在選定的解壓算法中利用預(yù)先設(shè)定好的碼字描述信息直接移位就可以得到5個(gè)整數(shù).

3 機(jī)器字對(duì)齊壓縮算法

目前，倒排索引壓縮算法中被廣泛研究和采用的是字對(duì)齊(word-aligned)壓縮算法，其可以在給定的32位或64位機(jī)器字長(zhǎng)內(nèi)一次處理多個(gè)倒排信息整數(shù).該壓縮算法分為按照單個(gè)機(jī)器字對(duì)齊進(jìn)行壓縮(非固定整數(shù)個(gè)數(shù)進(jìn)行壓縮)和按照固定整數(shù)個(gè)數(shù)進(jìn)行壓縮兩類.按照單個(gè)機(jī)器字對(duì)齊壓縮的主要思想是將盡量多的整數(shù)壓縮在一個(gè)32位或64位機(jī)器字內(nèi)，如Simple系列壓縮算法[33-37].按照固定整數(shù)個(gè)數(shù)進(jìn)行壓縮的主要思想是選取32m(m為正整數(shù))個(gè)整數(shù)進(jìn)行等位寬壓縮，同時(shí)保證碼字末尾是字對(duì)齊的，如FOR系列壓縮算法[32,38-40].兩類字對(duì)齊壓縮算法的解壓過(guò)程均可采用硬編碼方式來(lái)降低CPU分支判斷等操作的次數(shù).下面我們綜述幾種典型的字對(duì)齊壓縮算法.

Simple系列：該系列壓縮算法最初由Anh和Moffat提出，包括Simple-9壓縮算法[33]及其改進(jìn)壓縮算法如Carryover-12、Slide等[34-37]，其基本思想是將盡可能多的整數(shù)壓縮在一個(gè)單一的32位機(jī)器字中.如表3所示，Simple-9壓縮算法使用4比特作為狀態(tài)位來(lái)描述其余28個(gè)數(shù)據(jù)位，形成9種可能的數(shù)據(jù)位填充模式.每種填充模式為每個(gè)被壓縮的整數(shù)分配固定的比特寬度.解壓階段通過(guò)狀態(tài)位確定填充模式來(lái)提取數(shù)據(jù)位存儲(chǔ)的所有整數(shù).壓縮和解壓過(guò)程采用硬編碼方式來(lái)降低循環(huán)的次數(shù).Simple系列壓縮算法中每次可壓縮的整數(shù)個(gè)數(shù)因采用的填充模式不同而不同.因此，Simple系列壓縮方法實(shí)際上是依據(jù)填充模式對(duì)倒排鏈表進(jìn)行“貪心”劃分(left-greedy partition)并分別壓縮.為了將更多的整數(shù)壓縮到一個(gè)機(jī)器字中并降低固定比特寬度帶來(lái)的位寬浪費(fèi)，研究人員提出了眾多具有更為豐富的數(shù)據(jù)填充模式的改進(jìn)算法，包括Carryover-12、Slide、Simple-16、Simple-8b等[33-37].尤其是Simple-8b作為對(duì)Simple-9在64位機(jī)器字上的改進(jìn)，采用4比特的狀態(tài)位來(lái)描述60位數(shù)據(jù)位的不同填充模式[35].Simple-8b因?yàn)椴捎?4位機(jī)器字對(duì)壓縮序列進(jìn)行處理，增加了單次可編碼的整數(shù)個(gè)數(shù).故Simple-8b相比Simple-9能夠明顯減少CPU分支判斷的次數(shù)，所以其壓縮和解壓速度都好于Simple-9算法.

表3 Simple-9中采用的9種填充模式
Table 3 9 padding modes of simple-9

編號(hào)狀態(tài)位(4比特)可壓縮整數(shù)個(gè)數(shù)k比特寬度b位寬浪費(fèi)0#a(0000)28101#b(0001)14202#c(0010)9313#d(0011)7404#e(0100)5535#f(0101)4706#g(0110)3917#h(0111)21408#i(1000)1280

FOR(FrameOfReference)系列：該系列壓縮算法又稱為Binary Packing、PackedBinary或者Null Suppression[7,41]，其主要思想是把待壓縮整數(shù)序列劃分為定長(zhǎng)的數(shù)據(jù)段(一般為一個(gè)磁盤(pán)分頁(yè)，如可能包括216=65536個(gè)整數(shù))，然后用段內(nèi)最大位寬來(lái)標(biāo)示段內(nèi)數(shù)字[38]；PFOR是為了克服在某些分段中出現(xiàn)的異常值會(huì)迫使整個(gè)分段采用過(guò)大位寬的問(wèn)題，把整個(gè)分段分成較小的正常值和較大的異常值兩部分，異常值的個(gè)數(shù)通常取數(shù)據(jù)段長(zhǎng)度的10%.其中，PFOR正常值仍采用定長(zhǎng)壓縮，異常值直接附在分段的尾部，使用32位機(jī)器字來(lái)表示[39]；Zhang等人改進(jìn)了原來(lái)的PFOR(Lemire等人[7]稱該算法為PFOR2008)，使得每次壓縮的數(shù)據(jù)段長(zhǎng)度為128，并且采用8、16或者32比特來(lái)壓縮異常值[34].NewPFD和OptPFD也將數(shù)據(jù)段長(zhǎng)度定為128，并把異常值拆成兩部分，僅把超出正常值的部分移至尾部并采用Simple-16進(jìn)行壓縮；不同的是NewPFD選擇10%的異常值，而OptPFD通過(guò)權(quán)衡正常值和異常值選擇策略來(lái)實(shí)現(xiàn)最優(yōu)壓縮效果[19]；FastPFOR和SimplePFOR則是把多個(gè)分段的數(shù)據(jù)區(qū)分別單獨(dú)壓縮，異常值組合形成一個(gè)分頁(yè)(Page)進(jìn)行壓縮，而通過(guò)在解壓時(shí)一并讀取該分頁(yè)加快解壓速度；不同的是SimplePFOR采用Simple-8b壓縮異常值，而FastPFOR生成32中不同長(zhǎng)度的位寬數(shù)組來(lái)分別存放不同大小的異常值[7].總的來(lái)說(shuō)，F(xiàn)OR系列壓縮算法在每次可壓縮的整數(shù)個(gè)數(shù)是一定的，因此屬于等長(zhǎng)壓縮算法.

OCS(OptimizedChunkSplitting)系列：FOR系列壓縮算法具有較高的解壓性能，正是因?yàn)槠淇梢詥未翁幚磔^長(zhǎng)(如：128或256個(gè))的整數(shù)序列.但是增加單次可壓縮整數(shù)的個(gè)數(shù)可能會(huì)造成該次壓縮的數(shù)據(jù)段中存在較大的異常數(shù)(exception)，從而制約了算法的壓縮率.為了降低異常值給等長(zhǎng)壓縮算法帶來(lái)的位寬浪費(fèi)問(wèn)題，研究人員提出基于倒排鏈表劃分的優(yōu)化壓縮方法.該優(yōu)化方法尋求最優(yōu)的倒排鏈表數(shù)據(jù)段劃分，每個(gè)數(shù)據(jù)段內(nèi)部采用單獨(dú)的等長(zhǎng)壓縮算法進(jìn)行壓縮，同時(shí)保證連續(xù)的多個(gè)數(shù)據(jù)段是字對(duì)齊的[8,42].Rossano Venturini等人提出的VSE針對(duì)整個(gè)倒排鏈表使用動(dòng)態(tài)規(guī)劃方法尋找最優(yōu)數(shù)據(jù)段劃分[32]，但其全局優(yōu)化的計(jì)算代價(jià)太高，使索引構(gòu)建的時(shí)間大大加長(zhǎng).Renaud Delbru等人提出的AFOR采用固定長(zhǎng)度的滑動(dòng)窗口方式來(lái)劃分?jǐn)?shù)據(jù)段，可以說(shuō)是以動(dòng)態(tài)規(guī)劃求解局部最優(yōu)的辦法來(lái)避免過(guò)高的計(jì)算代價(jià)[40].Gonzalo Navarro研究團(tuán)隊(duì)提出的DACs使用了和VSE相同的思想，但其數(shù)據(jù)段內(nèi)采用了與Varint類似的字節(jié)壓縮方式，同時(shí)對(duì)不同長(zhǎng)度的碼字構(gòu)建分層結(jié)構(gòu)來(lái)實(shí)現(xiàn)隨機(jī)訪問(wèn)的效果[43]；Rossano Venturini等人進(jìn)一步提出的PEF和CEF壓縮算法優(yōu)化了Elias-Fano壓縮算法[44]，在劃分時(shí)把整數(shù)序列視作有向無(wú)環(huán)圖(DAG)，并引入了近似計(jì)算的方法在線性時(shí)間內(nèi)完成最優(yōu)劃分[45，46].eBay公司Andrew Trotman等人通過(guò)對(duì)整個(gè)內(nèi)存倒排索引進(jìn)行劃分優(yōu)化來(lái)提升Simple-9壓縮算法的壓縮率，但是該方法未能夠考慮給定同步距離內(nèi)多類倒排信息交錯(cuò)壓縮存儲(chǔ)帶來(lái)的位寬浪費(fèi)問(wèn)題[47].

表4 機(jī)器字對(duì)齊壓縮算法對(duì)比
Table 4 Comparison of word-aligned compressions

壓縮算法單次可壓縮整數(shù)個(gè)數(shù)k壓縮率壓縮速度解壓速度Simple不固定(<128)中快中FOR固定(=64、128、256)低快快OCS不固定高慢快

結(jié)合上述分析和已有文獻(xiàn)實(shí)驗(yàn)，表4給出了三類機(jī)器字對(duì)齊壓縮算法的性能對(duì)比[48].FOR系列壓縮算法雖然每次可壓縮的整數(shù)個(gè)數(shù)是固定的，但是其壓縮的碼字所占用的機(jī)器字長(zhǎng)是不確定的，所以將磁盤(pán)倒排索引分塊載入內(nèi)存IO緩存池(buffer pool)就會(huì)出現(xiàn)碼字在解壓時(shí)的緩沖池跨塊讀寫(xiě)的情況[49，50].在目前多數(shù)搜索引擎系統(tǒng)中海量倒排索引數(shù)據(jù)的存儲(chǔ)和查詢應(yīng)用環(huán)境下，這一問(wèn)題在磁盤(pán)壓縮倒排索引的查詢過(guò)程中會(huì)制約碼字的解壓性能.此時(shí)，Simple系列壓縮算法相比FOR系列壓縮算法的優(yōu)勢(shì)有兩個(gè)方面：

1)其填充模式更加細(xì)化，可以降低較大異常數(shù)對(duì)于序列其他整數(shù)壓縮位寬的浪費(fèi)問(wèn)題[7，32，34]；

2)其壓縮碼字能夠和所設(shè)內(nèi)存IO緩存池的讀寫(xiě)數(shù)據(jù)塊對(duì)齊，可以避免讀寫(xiě)磁盤(pán)壓縮倒排索引數(shù)據(jù)時(shí)的跨數(shù)據(jù)塊解壓?jiǎn)栴}[22，39，51].

然而，Simple系列壓縮算法仍然存在如下的問(wèn)題：

1)在交錯(cuò)壓縮給定長(zhǎng)度的多類倒排信息時(shí)存在過(guò)多的分支判斷和循環(huán)調(diào)用等開(kāi)銷；

2)在連續(xù)壓縮多類交錯(cuò)倒排信息時(shí)存在嚴(yán)重的位寬浪費(fèi)問(wèn)題，其所采用的“貪心”劃分方法無(wú)法達(dá)到最優(yōu)的壓縮效果.

3)在給定機(jī)器字長(zhǎng)內(nèi)可壓縮整數(shù)個(gè)數(shù)的不確定性使得其自索引結(jié)構(gòu)構(gòu)建和優(yōu)化過(guò)程中存在同步距離和地址偏移難以計(jì)算等諸多問(wèn)題[48，52].

4 基于SIMD指令集的壓縮算法

為了更加有效地提升處理器的性能，充分挖掘程序運(yùn)行中可能存在的并行操作，現(xiàn)代處理器中引入了多種并行結(jié)構(gòu).SIMD指令能夠?qū)ο蛄炕臄?shù)據(jù)實(shí)現(xiàn)顯著的性能加速[53].具體來(lái)說(shuō)，單條指令不再只能處理單一數(shù)據(jù)，而能夠在一組向量數(shù)據(jù)上同時(shí)執(zhí)行相同操作.Intel推出的SSE和AVX擴(kuò)展指令為可以向量化的數(shù)據(jù)密集型應(yīng)用帶來(lái)了明顯的性能提升[54].例如，SSE向量指令使用了128位的寄存器，可以一次并行處理多個(gè)32位整數(shù).開(kāi)發(fā)人員僅僅需要調(diào)用提供的C/C++語(yǔ)法格式的內(nèi)建函數(shù)(Intrinsic)就可以實(shí)現(xiàn)基于SIMD指令集的并行化開(kāi)發(fā)[55].當(dāng)前倒排索引壓縮算法的一個(gè)研究方向就是通過(guò)采用SIMD向量指令集來(lái)提升現(xiàn)有各個(gè)類別的倒排索引壓縮算法并行執(zhí)行的速度.

國(guó)外最早對(duì)壓縮算法進(jìn)行SIMD并行化的工作是Willhalm等人[25]提出的在輕量級(jí)內(nèi)存數(shù)據(jù)庫(kù)中將等長(zhǎng)位寬壓縮(如FOR等)的碼字利用SIMD數(shù)據(jù)置換指令進(jìn)行快速解壓算法，其過(guò)程包括加載壓縮數(shù)據(jù)到128位的SIMD寄存器、采用Shuffle數(shù)據(jù)置換指令對(duì)SIMD寄存器中的數(shù)據(jù)進(jìn)行重新存儲(chǔ)、消除冗余的比特位并進(jìn)行并行化的整數(shù)提取.Schlegel等人[56]利用SIMD指令同時(shí)處理k個(gè)整數(shù)的編碼，其中設(shè)計(jì)了壓縮數(shù)據(jù)的垂直布局來(lái)避免解壓過(guò)程中大量的SIMD數(shù)據(jù)置換指令操作，大幅提升了Null Suppression和Elias Gamma兩種編碼的解壓性能.Stepanov等人[57]利用標(biāo)志位的存儲(chǔ)格式和編碼方式對(duì)字節(jié)對(duì)齊壓縮算法進(jìn)行了分類，并在這一分類框架下通過(guò)SIMD數(shù)據(jù)置換指令(Shuffle)設(shè)計(jì)了SIMD-GVB(包括3個(gè)變種SIMD-GB、SIMD-G8IU和SIMD-G8CU)并行壓縮算法.Lemire等人[7]提出了兩種采用碼字垂直布局(Vertical Layout)和SIMD數(shù)據(jù)置換指令進(jìn)行并行化的壓縮算法，其中SIMD-BP128*能夠達(dá)到比未并行化的最優(yōu)壓縮算法varint-G8IU和PFOR近2倍的解壓速度，SIMD-FastPFOR相比Simple-8b能夠在保證較高壓縮率的情況下達(dá)到2倍的解壓速度.隨后，Lemire等人[58]又研究了能同時(shí)處理4個(gè)碼字的基于SIMD的S4-BP128和S4-FastPFOR兩種壓縮算法在4種不同差分編碼策略下的性能，以及在所提出的倒排鏈表求交(Intersection)算法中的性能表現(xiàn).Trotman[59]針對(duì)SIMD-BP128*壓縮率較低的問(wèn)題，提出了一種基于SIMD的壓縮算法QMX，其中設(shè)計(jì)了128比特的各種劃分(Quantities)，指示位的集中存儲(chǔ)格式(eXtractors)，以及通過(guò)游程編碼來(lái)存儲(chǔ)重復(fù)整數(shù)(Multipliers)，最后通過(guò)采用SIMD數(shù)據(jù)置換指令來(lái)實(shí)現(xiàn)對(duì)向量化數(shù)據(jù)的快速處理.

國(guó)內(nèi)對(duì)于基于SIMD的倒排索引壓縮算法研究包括：南開(kāi)大學(xué)張曌華等人[60]以及Ao等人[61]采用SSE指令和AVX指令實(shí)現(xiàn)了Simple-9、Simple-16、PFORDelta和BP的并行解壓算法，其中對(duì)于部分算法考慮了垂直布局來(lái)進(jìn)一步提升算法向量化處理性能，剩余的算法采用SIMD數(shù)據(jù)置換指令來(lái)實(shí)現(xiàn)并行化數(shù)據(jù)訪問(wèn).北京大學(xué)閆宏飛等人[62]通過(guò)SIMD數(shù)據(jù)置換指令和垂直布局兩種方式對(duì)PackedBinary和PFORDelta進(jìn)行了并行化，得到了明顯的解壓性能改進(jìn).最新的研究是Zhao和Zhang等人[63，64]利用SIMD向量指令提出一系列分組壓縮算法：Group-Simple、Group-Scheme、Group-AFOR和Group-PFDelta.這些壓縮算法按照各個(gè)分組中最大數(shù)字的位寬對(duì)所有分組進(jìn)行等位寬垂直存儲(chǔ)，所以雖然其解壓性能得到了提升，但是會(huì)導(dǎo)致部分壓縮算法的壓縮率相比較未并行化的原壓縮算法有一定的損失.

5 壓縮倒排索引的隨機(jī)訪問(wèn)策略

倒排索引壓縮算法最終是要應(yīng)用于搜索引擎系統(tǒng)中的，而為了保證良好的用戶體驗(yàn)，搜索引擎任憑索引規(guī)模的如何增長(zhǎng)，總是優(yōu)先考慮系統(tǒng)的查詢性能指標(biāo)[2,10].Stefan Büttcher等人指出倒排索引壓縮算法的性能評(píng)估不能僅考慮對(duì)倒排鏈表所形成的數(shù)個(gè)整數(shù)序列的壓縮，而必須考慮海量磁盤(pán)倒排索引和構(gòu)建自索引查詢結(jié)構(gòu)等實(shí)際應(yīng)用環(huán)境[65].Jimmy Lin等人研究發(fā)現(xiàn)，在給定同步距離內(nèi)的分段倒排信息交錯(cuò)存儲(chǔ)環(huán)境下，Simple系列壓縮算法的填充模式位寬浪費(fèi)問(wèn)題要比內(nèi)存索引壓縮的理想情況要嚴(yán)重的多，極端情況下可能影響壓縮算法在倒排索引查詢中的作用[66].

前面我們認(rèn)為壓縮算法的解壓速度在一定程度上即代表了搜索引擎的查詢速度，但是在實(shí)際應(yīng)用中并非完全如此.在搜索引擎的查詢過(guò)程中，采用直接在磁盤(pán)尋道的方式對(duì)索引數(shù)據(jù)進(jìn)行訪問(wèn)所需要的時(shí)間是難以忍受的.如果先將存儲(chǔ)在磁盤(pán)上的倒排鏈表全部加載到內(nèi)存中，再對(duì)加載入內(nèi)存的整個(gè)倒排鏈表進(jìn)行完全解壓之后再進(jìn)行查詢操作的話，過(guò)長(zhǎng)的數(shù)據(jù)加載時(shí)間將加劇用戶的查詢等待時(shí)間[67].針對(duì)壓縮倒排索引的隨機(jī)訪問(wèn)問(wèn)題，研究人員從以下兩個(gè)方面進(jìn)行研究：為倒排鏈表構(gòu)建自索引同步點(diǎn)的自索引采樣技術(shù)(Self-Indexes)和可以對(duì)壓縮倒排鏈表進(jìn)行局部解壓的隨機(jī)訪問(wèn)技術(shù)(Random Decoding).

5.1 自索引采樣技術(shù)

為了對(duì)壓縮狀態(tài)的倒排鏈表進(jìn)行高效的隨機(jī)訪問(wèn)，Moffat和Zobel提出對(duì)非壓縮倒排鏈表進(jìn)行等長(zhǎng)采樣并形成自索引結(jié)構(gòu)，之后研究了最優(yōu)的自索引結(jié)構(gòu)層數(shù)[68].圖2所示為一個(gè)自索引結(jié)構(gòu)，這樣就可以在查找過(guò)程中通過(guò)自索引結(jié)構(gòu)定位到倒排鏈表的目標(biāo)數(shù)據(jù)段，并通過(guò)二分查找在數(shù)據(jù)段內(nèi)部定位目標(biāo)文檔號(hào).Strohman和Croft研究了Impact-Ordered索引結(jié)構(gòu)上的自索引結(jié)構(gòu)問(wèn)題[69].Boldi和Vigna提出了一種跳轉(zhuǎn)塔的邏輯結(jié)構(gòu)，該方法通過(guò)對(duì)每個(gè)數(shù)據(jù)段的自索引結(jié)構(gòu)進(jìn)行迭代形成塔狀結(jié)構(gòu)，在查找過(guò)程中可以從上到下逐步比較，準(zhǔn)確定位所需的數(shù)據(jù)段[70].Dimopoulos等人為了研究倒排索引在內(nèi)存中的查詢問(wèn)題，構(gòu)建的自索引結(jié)構(gòu)只是保存每個(gè)壓縮數(shù)據(jù)段的首個(gè)文檔號(hào)，且整個(gè)自索引結(jié)構(gòu)并不進(jìn)行壓縮存儲(chǔ)[71].Jonassen等人研究了PFOR等長(zhǎng)數(shù)據(jù)段壓縮的倒排索引的自索引結(jié)構(gòu)構(gòu)建問(wèn)題[72].對(duì)壓縮存儲(chǔ)的倒排鏈表構(gòu)建自索引結(jié)構(gòu)能夠減少磁盤(pán)讀取的數(shù)據(jù)量.即使大部分索引可以被加載到內(nèi)存中進(jìn)行訪問(wèn)，自索引結(jié)構(gòu)還是可以節(jié)省大量的解壓時(shí)間.Bortnikov等人提出的自適應(yīng)自索引結(jié)構(gòu)能夠在傳統(tǒng)自索引和Treap自索引之間動(dòng)態(tài)切換來(lái)實(shí)現(xiàn)基本的跳轉(zhuǎn)查找操作，從而為T(mén)op-K查詢優(yōu)化提供更好的壓縮索引隨機(jī)訪問(wèn)性能[73].

圖2 自索引結(jié)構(gòu)示意圖Fig.2 Example of Self-index Structure

5.2 局部隨機(jī)訪問(wèn)技術(shù)

前述的壓縮算法大多數(shù)利用文檔號(hào)之間的差值d-gap信息進(jìn)行壓縮.盡管d-gap在提高壓縮率和解壓縮度上效果顯著，但由于它對(duì)前后元素的依賴性，導(dǎo)致解壓過(guò)程必須串行執(zhí)行，無(wú)法實(shí)現(xiàn)對(duì)任意位置的元素訪問(wèn).雖然構(gòu)建倒排鏈表的自索引結(jié)構(gòu)能在一定程度上實(shí)現(xiàn)倒排鏈表的隨機(jī)訪問(wèn)，但是卻無(wú)法對(duì)每個(gè)壓縮數(shù)據(jù)段內(nèi)部的整數(shù)進(jìn)行隨機(jī)訪問(wèn).為了解決這一問(wèn)題，研究人員提出了不利用d-gap信息而直接對(duì)原始整數(shù)序列進(jìn)行處理的壓縮算法.其中，DACs將所有文檔號(hào)(docid)按照位寬不同分層存儲(chǔ)，利用動(dòng)態(tài)規(guī)劃的方式來(lái)決定分層的個(gè)數(shù)以及每個(gè)分層的位寬，因?yàn)槠湮粚挼膯挝粸樽止?jié)，所以其壓縮率仍然較差[43]；Interpolative Code利用序列兩端整數(shù)的差值確定中間整數(shù)的編碼長(zhǎng)度，對(duì)單調(diào)遞增的整數(shù)序列進(jìn)行緊湊的遞歸編碼，該算法是目前壓縮效率最高的算法[28]；劉小珠等人提出使用Interpolative Code壓縮的方法來(lái)對(duì)等長(zhǎng)數(shù)據(jù)段壓縮的倒排鏈表實(shí)現(xiàn)隨機(jī)訪問(wèn)[74，75].最新的Quasi-Succinct Indices[44]和Partitioned Elias-Fano Index[45]都源于Elias-Fano編碼[76]，它們將倒排鏈表所有整數(shù)按照指定的長(zhǎng)度分成高位和低兩層，低位部分以完整形式順序?qū)懭雺嚎s文件，高位則按照大小映射到不同的哈希分段中統(tǒng)計(jì)數(shù)目和位置，最后通過(guò)輔助的Rank/Select信息高效地實(shí)現(xiàn)壓縮整數(shù)的隨機(jī)訪問(wèn).

6 搜索引擎系統(tǒng)中的壓縮算法

隨著倒排索引規(guī)模的不斷增加，索引壓縮算法性能上的任何提升都可以極大降低搜索引擎的硬件建設(shè)成本.雖然倒排索引壓縮算法種類繁多、各具優(yōu)勢(shì)，但是在真實(shí)搜索引擎系統(tǒng)中的實(shí)現(xiàn)和應(yīng)用還需要考慮很多因素，如：硬編碼實(shí)現(xiàn)或者自索引結(jié)構(gòu)等[7,10].不論是商業(yè)還是開(kāi)源搜索引擎，都需要面對(duì)海量數(shù)據(jù)、海量查詢、實(shí)時(shí)響應(yīng)的應(yīng)用需求.倒排索引壓縮算法的選擇需要權(quán)衡壓縮率、壓縮速度和解壓速度三方面的因素.如何權(quán)衡選擇合適的索引壓縮算法在商業(yè)搜索引擎公司和學(xué)術(shù)上都屬于研究的熱點(diǎn)與難點(diǎn)[9].諸多性能優(yōu)良的壓縮算法能在某一性能指標(biāo)上表現(xiàn)突出.搜索引擎選擇壓縮算法的重要原則是希望能夠在各個(gè)性能指標(biāo)之間取得一個(gè)平衡[77].當(dāng)前各大商業(yè)搜索引擎所采用的索引壓縮算法屬于商業(yè)機(jī)密而不公開(kāi)，但是我們可以從大量開(kāi)源搜索引擎系統(tǒng)中得出倒排索引壓縮算法的選擇策略.

3The FastPFOR C++ library:fast integer compression.https://github.com/lemire/FastPFOR.2019.05.

當(dāng)前流行的開(kāi)源搜索引擎系統(tǒng)種類較多，使用Java語(yǔ)言編寫(xiě)的有Lucene、MG4J和Terrier，使用C/C++編寫(xiě)的有Xapian、Zettair、Indri等.Lucene提供了包括Gamma、Delta和Varint等多種算法的支持，默認(rèn)采用了Gamma編碼來(lái)壓縮其索引數(shù)據(jù)[78].原來(lái)MG4J采用Golomb編碼來(lái)壓縮索引數(shù)據(jù)，同時(shí)也提供了其他壓縮算法的實(shí)現(xiàn)接口[79]，而MG4J在5.0版本開(kāi)始使用了Quasi-Succinct Indices實(shí)現(xiàn)倒排索引的隨機(jī)訪問(wèn)[44].Zettair和Galago中對(duì)于倒排鏈表所生成的d-gaps采用解壓性能較好的Varint進(jìn)行壓縮，而采用Gamma或Delta對(duì)詞頻信息進(jìn)行壓縮[80，81].Terrier-v5.1實(shí)現(xiàn)了一個(gè)索引壓縮的插件，其中包括當(dāng)前各種常見(jiàn)的如PFOR、Simple等倒排索引壓縮算法，其默認(rèn)的索引壓縮算法采用了Gamma編碼，同時(shí)提供了進(jìn)行壓縮數(shù)據(jù)轉(zhuǎn)換的功能[82].Lemire等人依據(jù)Moffat等人[35]論文中仿真數(shù)據(jù)生成的方法實(shí)現(xiàn)了一個(gè)索引壓縮算法的Java語(yǔ)言仿真測(cè)試平臺(tái)，其中包括了常用的各類壓縮算法實(shí)現(xiàn)[7].另外Lemire等人還給出了一個(gè)C++語(yǔ)言實(shí)現(xiàn)的基于SIMD的壓縮算法測(cè)試框架3.Catena等人對(duì)常見(jiàn)的倒排索引壓縮算法在Terrier搜索引擎系統(tǒng)中的性能表現(xiàn)進(jìn)行了比較全面的測(cè)試和分析[48].以上倒排索引壓縮算法在開(kāi)源系統(tǒng)中的應(yīng)用可以作為進(jìn)行倒排索引壓縮算法研究和實(shí)驗(yàn)的參照.

7 總結(jié)與展望

互聯(lián)網(wǎng)信息的不斷豐富所帶來(lái)的索引數(shù)據(jù)的持續(xù)增加，為新的倒排索引壓縮技術(shù)的發(fā)展提供了持久的動(dòng)力.綜合國(guó)內(nèi)外研究現(xiàn)狀可以看出，大多數(shù)倒排索引壓縮技術(shù)評(píng)估和優(yōu)化工作主要關(guān)注了對(duì)整數(shù)序列的壓縮，卻忽視了現(xiàn)有倒排索引壓縮算法在搜索引擎系統(tǒng)應(yīng)用中存在的如：倒排鏈表磁盤(pán)分段存儲(chǔ)、多類倒排信息交錯(cuò)壓縮和壓縮數(shù)據(jù)自索引結(jié)構(gòu)等實(shí)際情況.針對(duì)倒排索引壓縮算法在存儲(chǔ)和查詢應(yīng)用中存在的實(shí)際問(wèn)題展開(kāi)理論方法研究與性能測(cè)試.這些問(wèn)題的解決有助于推動(dòng)機(jī)器字對(duì)齊壓縮算法在倒排索引存儲(chǔ)和查詢中的廣泛應(yīng)用，有利于解決海量磁盤(pán)壓縮索引數(shù)據(jù)的快速查詢?cè)L問(wèn)問(wèn)題，對(duì)提升各類搜索引擎的系統(tǒng)性能和服務(wù)質(zhì)量具有重要的實(shí)際意義.綜合國(guó)內(nèi)外研究現(xiàn)狀，倒排索引壓縮算法當(dāng)前正在展開(kāi)和今后的主要研究方向有以下幾個(gè)方面：

1)倒排索引壓縮算法在搜索引擎查詢系統(tǒng)中的實(shí)際應(yīng)用問(wèn)題，如：研究支持倒排鏈表隨機(jī)訪問(wèn)的倒排索引壓縮算法[75].因?yàn)橹С蛛S機(jī)訪問(wèn)的壓縮倒排鏈表可以減少不必要的內(nèi)存數(shù)據(jù)加載，提升搜索引擎中壓縮倒排索引的查詢性能；同時(shí)也可以在倒排鏈表求交操作(如SvS算法)中根據(jù)AND查詢策略來(lái)調(diào)整或者改進(jìn)所使用的壓縮算法[58].搜索引擎查詢中對(duì)不同倒排鏈表或者倒排鏈表數(shù)據(jù)段訪問(wèn)頻率是不同的，對(duì)于不同查詢?cè)L問(wèn)頻率的索引數(shù)據(jù)采用不同的壓縮方式就可以實(shí)現(xiàn)更加細(xì)粒度的性能調(diào)節(jié)，再權(quán)衡索引大小、壓縮速度和解壓速度等性能指標(biāo)，從而達(dá)到更好的時(shí)空效率[77,83].

2)基于新的指令集架構(gòu)優(yōu)化倒排索引壓縮算法的數(shù)據(jù)處理能夠進(jìn)一步提升壓縮和解壓性能.單純采用高級(jí)語(yǔ)言提供的庫(kù)函數(shù)實(shí)現(xiàn)的倒排索引壓縮算法對(duì)數(shù)據(jù)的操作粒度較粗，不利于倒排索引壓縮算法的性能優(yōu)化.隨著處理器技術(shù)的不斷發(fā)展，新的SIMD指令集(SSE或者AVX指令集)或者計(jì)算單元(GPU芯片或者芯片加速器[84])等的更新將會(huì)帶來(lái)新的指令級(jí)并行化策略.例如：基于Intel CPU的SSE、AVX向量指令的如：更大的寄存器寬度、數(shù)據(jù)Shuffle置換指令和垂直布局存儲(chǔ)等優(yōu)勢(shì)[54]，可以從匯編指令級(jí)別來(lái)設(shè)計(jì)整數(shù)序列的存儲(chǔ)布局，并利用內(nèi)存和寄存器載入策略、指令級(jí)的比特位操作等技術(shù)提升倒排索引整數(shù)序列的并行化壓縮和解壓處理性能.

3)基于傳統(tǒng)數(shù)據(jù)壓縮領(lǐng)域的新技術(shù)和新理論提升倒排索引壓縮算法的性能.部分傳統(tǒng)壓縮領(lǐng)域中的新理論和方法可以應(yīng)用于倒排索引的整數(shù)序列壓縮.在這方面的工作包括：Zhang等人提出的基于上下文無(wú)關(guān)文法(Context-free Grammar)的倒排索引壓縮方法[85]；Moffat等人提出的基于不對(duì)稱數(shù)字系統(tǒng)(ANS)的倒排索引壓縮方法[86，87]；Pibiri等人利用復(fù)數(shù)分割(Plurally Parsable)理論提出了基于詞典的倒排索引壓縮方法[88].這類研究需要掌握傳統(tǒng)數(shù)據(jù)壓縮的理論并跟蹤其最新研究動(dòng)態(tài).考慮到倒排索引壓縮中整數(shù)序列也是一類特殊的符號(hào)序列，采用傳統(tǒng)壓縮領(lǐng)域的新技術(shù)和新理論分析文檔號(hào)、詞頻等整數(shù)序列的存儲(chǔ)特性，就可能從新的角度明顯提升倒排索引的壓縮性能.