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

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

1 引 言

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

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

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

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

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

在倒排鏈表壓縮過程中，各個倒排項(xiàng)都包含文檔號(docid)信息，并且每個詞項(xiàng)的倒排鏈表中的倒排項(xiàng)按文檔號從小到大進(jìn)行排列.這使得在存儲文檔號docid信息時，可以存儲文檔號docid之間的差值d-gap來提升倒排鏈表的壓縮率.文檔重排技術(shù)可以使得d-gap數(shù)值進(jìn)一步降低而提升倒排索引的壓縮率[19，20].根據(jù)Shannon的分析，分布概率為P(x)的數(shù)字的最優(yōu)壓縮比特長度為-「log2P(x)?[12]；此外，互聯(lián)網(wǎng)網(wǎng)頁中詞項(xiàng)的文檔頻率服從Zipf定律(冪定律)[21].因此，倒排索引壓縮的目的就是采用盡可能接近最優(yōu)比特長度的編碼來表示一個原來以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)的符號壓縮算法如Huffman編碼、算術(shù)編碼、PPM等半靜態(tài)或者自適應(yīng)壓縮方法需要預(yù)先知道被壓縮符號的統(tǒng)計(jì)信息并保留其壓縮模型，而互聯(lián)網(wǎng)網(wǎng)頁較快的更新速度使得d-gap序列不穩(wěn)定且無法為每個倒排鏈表d-gap序列保留一個穩(wěn)定的壓縮模型[22].另外，更加復(fù)雜的詞典方法如LZ77、LZW等也較少應(yīng)用在倒排索引壓縮中，這是因?yàn)榈古沛湵韉-gap序列的語義重復(fù)度要比符號序列小很多[23].因此，倒排索引壓縮算法的研究主要集中在不需要統(tǒng)計(jì)信息的輕量級壓縮(light-weighted compression)[24，25].倒排鏈表的壓縮算法按碼字對齊的方式可以分為：比特對齊(bit-aligned)壓縮算法和字節(jié)對齊(byte-aligned)壓縮算法.

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

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

硬編碼和移位方法被廣泛應(yīng)用在各類倒排索引壓縮算法中以達(dá)到算法壓縮和解壓實(shí)現(xiàn)性能的提升[7，32].其中，硬編碼是指將壓縮算法的每一種填充模式的各類描述信息直接寫入程序，避免壓縮和解壓過程的循環(huán)和分支判斷開銷.通過硬編碼和移位方法可以避免循環(huán)和分支判斷的開銷.表1和表2是采用硬編碼/移位方法的對5個整數(shù)進(jìn)行壓縮和解壓的例子.對于給定的待壓縮整數(shù)序列，通過逐個對整數(shù)的最大位寬和可壓縮整數(shù)個數(shù)進(jìn)行檢測來確定采用哪種填充模式(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所示的壓縮過程中，給定的5個可單次壓縮的整數(shù)(d[1]～d[5])和填充模式的狀態(tài)信息s(s=69).算法依據(jù)填充模式的位寬等描述信息將5個整數(shù)移位至各自的預(yù)分配碼槽(padding slot)，然后將填充模式狀態(tài)信息s存儲在碼字頭部，這樣在解壓時通過移位操作就可以獲得碼字所采用的填充模式.

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

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

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

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

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

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

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

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

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

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

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

2)其壓縮碼字能夠和所設(shè)內(nèi)存IO緩存池的讀寫數(shù)據(jù)塊對齊，可以避免讀寫磁盤壓縮倒排索引數(shù)據(jù)時的跨數(shù)據(jù)塊解壓問題[22，39，51].

然而，Simple系列壓縮算法仍然存在如下的問題：

1)在交錯壓縮給定長度的多類倒排信息時存在過多的分支判斷和循環(huán)調(diào)用等開銷；

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

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

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

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

國外最早對壓縮算法進(jìn)行SIMD并行化的工作是Willhalm等人[25]提出的在輕量級內(nèi)存數(shù)據(jù)庫中將等長位寬壓縮(如FOR等)的碼字利用SIMD數(shù)據(jù)置換指令進(jìn)行快速解壓算法，其過程包括加載壓縮數(shù)據(jù)到128位的SIMD寄存器、采用Shuffle數(shù)據(jù)置換指令對SIMD寄存器中的數(shù)據(jù)進(jìn)行重新存儲、消除冗余的比特位并進(jìn)行并行化的整數(shù)提取.Schlegel等人[56]利用SIMD指令同時處理k個整數(shù)的編碼，其中設(shè)計(jì)了壓縮數(shù)據(jù)的垂直布局來避免解壓過程中大量的SIMD數(shù)據(jù)置換指令操作，大幅提升了Null Suppression和Elias Gamma兩種編碼的解壓性能.Stepanov等人[57]利用標(biāo)志位的存儲格式和編碼方式對字節(jié)對齊壓縮算法進(jìn)行了分類，并在這一分類框架下通過SIMD數(shù)據(jù)置換指令(Shuffle)設(shè)計(jì)了SIMD-GVB(包括3個變種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]又研究了能同時處理4個碼字的基于SIMD的S4-BP128和S4-FastPFOR兩種壓縮算法在4種不同差分編碼策略下的性能，以及在所提出的倒排鏈表求交(Intersection)算法中的性能表現(xiàn).Trotman[59]針對SIMD-BP128*壓縮率較低的問題，提出了一種基于SIMD的壓縮算法QMX，其中設(shè)計(jì)了128比特的各種劃分(Quantities)，指示位的集中存儲格式(eXtractors)，以及通過游程編碼來存儲重復(fù)整數(shù)(Multipliers)，最后通過采用SIMD數(shù)據(jù)置換指令來實(shí)現(xiàn)對向量化數(shù)據(jù)的快速處理.

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

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

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

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

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

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

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

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

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

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

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

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

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

7 總結(jié)與展望

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

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

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

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