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

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

1 引 言

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

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

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

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

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

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

圖1 倒排鏈表結構的數據塊和數據段關系圖Fig.1 Inverted lists of data blocks and data chunks

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

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

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

硬編碼和移位方法被廣泛應用在各類倒排索引壓縮算法中以達到算法壓縮和解壓實現性能的提升[7，32].其中，硬編碼是指將壓縮算法的每一種填充模式的各類描述信息直接寫入程序，避免壓縮和解壓過程的循環(huán)和分支判斷開銷.通過硬編碼和移位方法可以避免循環(huán)和分支判斷的開銷.表1和表2是采用硬編碼/移位方法的對5個整數進行壓縮和解壓的例子.對于給定的待壓縮整數序列，通過逐個對整數的最大位寬和可壓縮整數個數進行檢測來確定采用哪種填充模式(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個可單次壓縮的整數(d[1]～d[5])和填充模式的狀態(tài)信息s(s=69).算法依據填充模式的位寬等描述信息將5個整數移位至各自的預分配碼槽(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]，每個整數在壓縮狀態(tài)下的位寬、可壓縮整數個數等信息由硬編碼描述，首先通過對碼字移位獲取碼字中存儲的填充模式的狀態(tài)信息s(s=r[0]?24)，之后選擇對應的硬編碼解壓算法，最后在選定的解壓算法中利用預先設定好的碼字描述信息直接移位就可以得到5個整數.

3 機器字對齊壓縮算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 壓縮倒排索引的隨機訪問策略

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

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

5.1 自索引采樣技術

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

圖2 自索引結構示意圖Fig.2 Example of Self-index Structure

5.2 局部隨機訪問技術

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

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

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

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

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

7 總結與展望

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

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

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

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