（1.西安理工大學計算機科學與工程學院，西安 710048；2.陜西省網(wǎng)絡(luò)計算與安全技術(shù)重點實驗室（西安理工大學），西安 710048；3.中國人民解放軍63785部隊，西安 710043）

0 引言

不斷增長的互聯(lián)網(wǎng)網(wǎng)頁規(guī)模給搜索引擎系統(tǒng)的倒排索引存儲帶來了持續(xù)的挑戰(zhàn)和研究需求［1-2］。近年來，大量互聯(lián)網(wǎng)應用的蓬勃發(fā)展更使搜索引擎系統(tǒng)待索引的數(shù)據(jù)規(guī)模進一步增加［3］。一般來說，倒排索引包括倒排文件和詞典文件，倒排文件包含著一串被壓縮的倒排項信息：文檔號（docid）和詞頻（freq），其中文檔號可以轉(zhuǎn)換為更小的d-gap 整數(shù)序列。倒排索引壓縮的目的就是采用盡可能接近最優(yōu)位（bits）數(shù)的碼字存儲原來以一個機器字長表示的倒排信息整數(shù)，同時保證對碼字解壓的無歧義和高效性。倒排索引壓縮技術(shù)的優(yōu)勢在于可以降低壓縮數(shù)據(jù)的存儲開銷和傳輸開銷，從而實現(xiàn)對海量壓縮倒排索引數(shù)據(jù)的快速內(nèi)存查詢訪問［4-5］。因此，倒排索引壓縮技術(shù)一直以來都是提升海量倒排索引數(shù)據(jù)存儲和查詢性能的必要手段和研究熱點。

目前，倒排索引壓縮算法中被廣泛研究和采用的是字對齊壓縮算法，該類型算法又可以分為參照框架（Frame Of Reference，F(xiàn)OR）類型壓縮（如：FOR、PFOR（Patched FOR）、OPT-P4D（OPTimzed PForDelta）等算法）和等字長（Fixed Word-Aligned，F(xiàn)WA）類型壓縮（如：S9、S16、S8b 等）兩類［6-7］。本文所研究的FWA 類型壓縮算法在保證每個被壓縮整數(shù)位寬小于其填充模式的限制條件下，所采用的整數(shù)序列“貪心”劃分策略將盡可能多的相鄰整數(shù)存儲在32q（q為正整數(shù)）位的機器字內(nèi)。研究表明，F(xiàn)WA 類型算法的優(yōu)勢在于：1）在給定的機器字長內(nèi)存儲模式更加細化，可以緩解倒排鏈中異常數(shù)字導致的分塊位寬的浪費問題；2）其壓縮碼字能夠和搜索引擎系統(tǒng)的IO 緩存池的讀寫數(shù)據(jù)塊對齊，可以避免讀寫磁盤壓縮倒排索引數(shù)據(jù)時的跨數(shù)據(jù)塊解壓問題［4］。然而，現(xiàn)有FWA 類型算法的指示位和數(shù)據(jù)位是交錯存儲的，這使得解壓過程必須對每個機器字進行指示位提取處理，從而制約了解壓性能。此外，F(xiàn)WA 類型算法的相鄰填充模式的可壓縮整數(shù)個數(shù)是不連續(xù)的，在相鄰整數(shù)差距較大、序列長度較短時，如果多壓縮一個整數(shù)可能會導致下次存儲模式存在嚴重的位寬損失問題，因此，現(xiàn)有FWA 類型算法采用的“貪心”分塊劃分策略無法達到最優(yōu)的壓縮率。實際上，在FWA 類型算法的存儲模式限制下使最終的劃分分塊總數(shù)最少才能達到最優(yōu)的壓縮效果。如何選擇有效的倒排鏈劃分方法是提升FWA 類型算法壓縮性能的關(guān)鍵。

針對傳統(tǒng)FWA 類型算法中存在的碼字信息交錯存儲和分塊劃分策略空間損失問題，本文研究FWA 類型算法壓縮下的倒排鏈存儲策略和分塊劃分和問題。首先，設(shè)計了一種指示位和數(shù)據(jù)位單獨存儲的新型FWA 類型壓縮算法；然后，提出了一種基于有向無環(huán)圖（Directed Acyclic Graph，DAG）描述的倒排鏈FWA 劃分壓縮方法——固定字對齊劃分（Word-Aligned Partition，WAP）算法；之后，采用動態(tài)規(guī)劃方法求解基于DAG 的最優(yōu)劃分問題；最后，通過仿真整數(shù)序列數(shù)據(jù)和文本檢索會議（Text REtrieval Conference，TREC）GOV2索引數(shù)據(jù)對本文所提WAP 壓縮算法進行實驗分析。實驗結(jié)果表明，本文所提基于DAG 的倒排鏈劃分優(yōu)化算法相較FWA 類型算法和FOR類型算法在壓縮率和解壓速度指標上有優(yōu)勢。

1 相關(guān)工作

倒排索引壓縮算法中的字對齊壓縮算法可以按照每次壓縮的碼字大小是否相等分為FOR類型算法和FWA類型算法。FOR 類型算法的主要思想是選取32q（q為正整數(shù)）個整數(shù)作為一個分塊進行等位寬壓縮，頭部指示位中需要包含壓縮分塊的空間占用信息，只保證了數(shù)據(jù)位的碼字末尾是字對齊的，如：FOR、PFOR 等算法［8-10］。FOR 類型算法的性能優(yōu)勢在于針對較長倒排鏈的壓縮，在倒排鏈長度較短時其壓縮率受異常值影響較大。OPT-P4D算法通過權(quán)衡分塊內(nèi)位寬和壓縮異常值的開銷，從而在不影響解壓性能的條件下提升算法的壓縮率［10］。

FWA 類型算法在給定的機器字長內(nèi)存儲模式更加細化，可以降低異常數(shù)導致的序列中其他整數(shù)壓縮位寬的浪費。Anh等［11］提出的S9壓縮算法使用4位作為指示位描述其余28個數(shù)據(jù)位，形成9 種可能的數(shù)據(jù)位存儲模式。每種存儲模式為每個被壓縮的整數(shù)分配固定的位寬，但存在一定的比特位寬浪費。S9 算法在壓縮過程中將盡可能多的相鄰整數(shù)壓縮在給定的32 位機器字長內(nèi)，這實際上就是對整數(shù)序列的一種向左的“貪心”劃分策略。解壓階段通過指示位所確定的存儲模式來提取數(shù)據(jù)位存儲的所有整數(shù)。當FWA 類型算法所剩的待壓縮整數(shù)個數(shù)較少時會導致存儲模式不匹配，此時存儲模式的位寬浪費問題就比較明顯。為了降低存儲模式的位寬浪費，研究人員提出了具有更為豐富存儲模式的FWA 類型算法，其中包括S16 算法以及Carryover-12、Slide、S8b、Slide8b、Carry8b 等算法［9，11-12］。FWA 類型算法中存儲模式的可壓縮整數(shù)個數(shù)和位寬的非連續(xù)性，以及整數(shù)序列分塊劃分的不合理性，使得整數(shù)序列分塊內(nèi)的異常值提升了塊內(nèi)其他整數(shù)的存儲位寬［13］。

為了降低倒排鏈中的異常值給壓縮算法帶來的位寬浪費，研究人員提出了基于倒排鏈分塊劃分的優(yōu)化壓縮方法［14-15］。該類優(yōu)化方法首先尋求最優(yōu)的倒排鏈分塊劃分，然后在每個分塊內(nèi)部進行等位寬存儲，同時保證連續(xù)的多個分塊是字對齊的。針對FOR類型壓縮算法，Silvestri等［14］提出的VSE（Vector of Splits Encoding）算法針對整個倒排鏈使用動態(tài)規(guī)劃方法尋找最優(yōu)分塊劃分，并采用再壓縮技術(shù)提升算法的壓縮率，形成VSE-R（VSE-Recoding）算法；該類算法難以構(gòu)建字對齊的自索引結(jié)構(gòu)，且采用的全局優(yōu)化的計算代價太高，使索引構(gòu)建的時間大大加長。Delbru 等［15］提出的AFOR（Adaptive Frame Of Reference）算法采用固定長度的滑動窗口方式來劃分分塊，且分塊長度僅可取8、16、32 三種；該方法可以說是采用動態(tài)規(guī)劃技術(shù)求解倒排鏈的局部最優(yōu)劃分來避免過高的計算代價。Brisaboa 等［16］提出的DACs（Directly Addressable Codes）算法使用了和VSE 算法相同的思想，但其分塊內(nèi)采用了與VByte（Variable Byte）算法類似的字節(jié)壓縮方式，同時對不同長度的碼字構(gòu)建分層結(jié)構(gòu)來實現(xiàn)隨機訪問的效果。Pibiri 等［17］提出的PEF（Partitioned Elias-Fano）和CEF（Clustered Elias-Fano）壓縮算法也構(gòu)建分層壓縮結(jié)構(gòu)，在劃分時把整數(shù)序列視作有向無環(huán)圖（DAG），并引入近似計算的方法完成整數(shù)序列的最優(yōu)劃分。針對FWA 類型壓縮算法，Trotman 等［18］通過對倒排索引進行劃分來提升S9 算法的壓縮率，但是該方法未能深入分析FWA 類型算法的存儲模式局限對最優(yōu)劃分結(jié)果的影響。

2 問題定義

假設(shè)L[0，n]（記為L）表示一個長度為n的嚴格遞增的正整數(shù)序列（如：倒排鏈中的d-gap 或者freq序列），L[i]表示序列的第i個元素，L[i，j](0 ≤i≤j＜n)表示序列L的從位置i到位置j的分塊。倒排鏈中的整數(shù)序列L的壓縮是在分塊上進行的，每個分塊的位寬和長度是不同的，如何劃分分塊影響著倒排索引的壓縮率。實際上，序列L[0，n]可以被視作一個有n個節(jié)點的有向無環(huán)圖（DAG）G，其中每個節(jié)點vi(i∈[0，n-1])代表序列L中的一個數(shù)值，vn表示空節(jié)點。圖G是一個完全圖，即對任意i和j滿足0 ≤i≤j＜n，就會存在一條邊連接vi和vj，表示為(vi，vj)。這條邊對應序列L中的一個劃分分塊L[i，j]，每條邊的權(quán)重ω(vi，vj)=C(L[i，j-1])，C為對分塊L[i，j-1]進行壓縮的算法。此時，序列L的劃分問題就轉(zhuǎn)化成了在圖G中規(guī)劃一條從節(jié)點v0到vn的路徑π。比如，路徑（i0=0 且im=n）即對應了序列L的一種有效劃分方案L[0，i1-1]L[i1，i2-1]…L[im-1，n-1]，其中m表示路徑π包含的邊的個數(shù)；記劃分向量S={0，i1，i2，…，im-1}中的元素為每一個劃分分塊在序列L中的起始下標。

在DAG 理論的描述下，倒排鏈的最優(yōu)劃分問題就歸約成為了一個單源最短路徑（Single-Source Shortest-Path，SSSP）計算問題。如圖1所示為含有5個文檔號的DAG描述示意圖（v0到v4，v5為空節(jié)點），其中每個節(jié)點代表一個d-gap，每條邊代表一個分塊的起止位置。邊下面的數(shù)字表示壓縮對應分塊作為節(jié)點之間路徑的代價E（位），由固定代價（本文算法為4位）加編碼分塊的位寬得出。虛線表示當前的最短路徑，即當前倒排鏈的最優(yōu)分塊劃分。圖G中每條路徑π都對應著一種可行的分塊劃分方案，而路徑的權(quán)重之和就是倒排鏈中序列L壓縮后的空間大小。所需要計算的就是在所有對序列L的劃分向量中找出使得壓縮空間開銷|FWA(L，S)|=最小的向量S，即：

圖1 倒排鏈劃分的DAG描述示意圖Fig.1 DAG description of inverted list partitioning

另外，本文在研究網(wǎng)頁d-gap 整數(shù)序列分布情況和現(xiàn)有FWA 類型算法的基礎(chǔ)上，為了降低FWA 類型算法在對小數(shù)字序列壓縮時可壓縮整數(shù)個數(shù)和位寬的非連續(xù)性，設(shè)計了一種64 位機器字對齊壓縮算法，并結(jié)合最優(yōu)劃分技術(shù)實現(xiàn)壓縮性能的提升，稱之為固定字對齊劃分（WAP）算法。如表1 所示，該算法設(shè)計了16種64位的存儲模式p，每種存儲模式可壓縮k個整數(shù)，分塊內(nèi)每個整數(shù)的位寬b是不變的。該算法將指示位和數(shù)據(jù)位單獨存儲，可以保證較高的解壓性能，即將4 位的指示區(qū)單獨存儲于整數(shù)序列的壓縮碼字頭部，并硬編碼實現(xiàn)16種64位數(shù)據(jù)區(qū)的存儲模式。另外，將部分存儲模式的損失位加入該模式的其他位寬中，這樣該存儲模式的位寬將是不固定的，在不影響算法的劃分優(yōu)化性能的情況下可以提升算法的壓縮率。因為WAP 算法的位寬從1～10 是連續(xù)的，所以這一算法適合處理連續(xù)的小數(shù)字序列壓縮。

表1 WAP壓縮算法的存儲模式Tab.1 Storage modes of WAP compression algorithm

對于擬采用WAP算法壓縮的倒排索引，給定劃分向量S，假設(shè)bi是可以表示分塊L[i，j-1]中最大元素的最少位數(shù)，即假設(shè)ki是分塊L[i，j-1]中的元素個數(shù)，即ki=j-i，則0 ＜ki≤K′，其中K′為最大分塊長度。此外，如果采用WAP 算法的某一個存儲模式p(0 ≤p＜P′)（P′是存儲模式的個數(shù)）對分塊L[i，j-1]進行壓縮，那么求解SSSP 問題還必須滿足存儲模式的3 個隱含限制條件：bi≤bwidth[p]、ki=gsize[p]和ki*bwidth[p]=機器字長。

3 動態(tài)規(guī)劃求解方法

本章利用動態(tài)規(guī)劃方法來求解式（1）所定義的DAG 的SSSP問題。首先把圖G中所有節(jié)點的最優(yōu)路徑代價E初始化為+∞，然后從v0到vn迭代，當?shù)竭_節(jié)點vj(0 ≤j＜n)時，所有從v0到vi(i＜j)之間的最優(yōu)路徑代價E[i]已經(jīng)計算。從v0到vj之間的新的路徑代價E'[j]為從v0到vi的最優(yōu)路徑代價E[i]與從vi到vj之間的最優(yōu)路徑代價C(L[i，j-1])之和。優(yōu)化過程需要根據(jù)WAP 算法存儲模式的3 個限制條件尋找最優(yōu)的節(jié)點(i*＜j)，并計算從到vj之間的新路徑的代價C(L[i*，j-1])。當新計算的路徑代價E[j]變小時，更新節(jié)點vj的代價E[j]，其轉(zhuǎn)移狀態(tài)定義如下：

其中：對序列L，E[i]也指從節(jié)點v0到vi之間的子序列L[0：i-1]的最優(yōu)壓縮開銷；C(L[i，j-1])是子序列L[i：j-1]的壓縮開銷。

算法1 給出了動態(tài)規(guī)劃求解的最優(yōu)劃分問題的偽碼。令E[1]=0作為循環(huán)的起始值，因為這代表空序列的編碼開銷。當對式（2）循環(huán)求解后，E[n+1]的值就是整個序列L的最優(yōu)劃分。算法1 中，首先設(shè)E[1]=0，然后從左至右計算E的每一種情況（第2）～12）行）。每一次E[j]的計算中，通過確定某個下標i*＜j使得E[i*]+C(L[i，j-1])的值最小。對于WAP 壓縮算法，每個分塊的壓縮開銷為C(L[i，j-1])=1。這一位置i*是通過對位于j-K′和j-1 之間的所有有效位置（需要從WAP算法的P′個有效位置中確定最優(yōu)存儲模式的下標p*）進行計算得到的（第4）～12）行）。在算法執(zhí)行過程中，還需要將每次計算的存儲模式下標p*保存在存儲模式數(shù)組P中，并將以當前節(jié)點vj為右邊界的分塊的左邊界i*存儲在劃分節(jié)點數(shù)組V中（第11）～12）行）。在計算結(jié)束后，E[n+1]表示壓縮序列L的分塊個數(shù)。此時，就可以通過數(shù)組V中的值來恢復最優(yōu)劃分向量，即從下標n+1 逆向獲得值V[n+1]、V[V[n+1]]、V[V[V[n+1]]]等（第13）～16）行）。

算法1 倒排鏈的最優(yōu)分塊劃分算法。

本文所提出的WAP 算法壓縮過程的計算復雜度為O(n?P′?K′)。目前針對FOR 類型算法的優(yōu)化工作中：OPT-P4D 壓縮優(yōu)化過程的計算復雜度為O(n?P′)，P′為算法所有可能的壓縮模式個數(shù)；AFOR 壓縮優(yōu)化過程的計算復雜度為VSE 壓縮優(yōu)化的計算復雜度為O(n?K′)，不同算法的最大分塊長度K′不同。因此，本文優(yōu)化方法和上述兩種方法具有類似的計算復雜度。WAP 壓縮算法雖然因為壓縮優(yōu)化而降低了壓縮速度，但是能夠在保持解壓速度的前提下明顯提升壓縮算法的壓縮率。

4 實驗測試與結(jié)果分析

實驗部分通過仿真整數(shù)序列數(shù)據(jù)和TREC 網(wǎng)頁索引數(shù)據(jù)對基于DAG 的FWA 類型優(yōu)化算法進行性能測試。考慮到互聯(lián)網(wǎng)網(wǎng)頁索引數(shù)據(jù)的文檔號是聚類分布的，因此實驗采用聚類數(shù)據(jù)分布模型生成仿真測試數(shù)據(jù)［12］。假如需要生成的整數(shù)數(shù)組A[l，l+1，…，s]長度為f，當f＜10 時，按照均勻分布生成數(shù)據(jù)，即在給定整數(shù)大小區(qū)間內(nèi)按照均勻分布生成f個遞增整數(shù)數(shù)據(jù)；當f≥10 時，將整數(shù)數(shù)組分為兩個子數(shù)組A[l，l+1，…，r]和A[r+1，r+2，…，s]（m按照某一策略選定）。這兩個子數(shù)組又依據(jù)一定概率（0 ＜λ＜1）按照下面三種情況迭代：第一種情況子數(shù)組A[l，l+1，…，r]按照均勻分布生成，子數(shù)組A[r+1，r+2，…，s]按照聚類分布生成；第二種情況子數(shù)組A[l，l+1，…，r]按照聚類分布生成，子數(shù)組A[r+1，r+2，…，s]按照均勻分布生成；第三種情況子數(shù)組A[l，l+1，…，r]按照聚類分布生成，子數(shù)組A[r+1，r+2，…，s]也按照聚類分布生成。這三種情況的概率λ分布為0 ＜λ＜0.25、0.25 ≤λ＜0.5 和0.5 ≤λ＜1。這樣，迭代的過程都是小范圍的短整數(shù)序列，從而實現(xiàn)了數(shù)據(jù)的聚類分布。

TREC 網(wǎng)頁壓縮性能測試需要在搜索引擎索引平臺上進行。本文利用GOV2 網(wǎng)頁標準數(shù)據(jù)集構(gòu)建基于文檔號排序的倒排索引。GOV2 數(shù)據(jù)集是TREC 組織提供的基于2004 年互聯(lián)網(wǎng)上.gov域名下的約2 520萬個網(wǎng)頁構(gòu)成的數(shù)據(jù)集，未壓縮狀態(tài)下的大小為426 GB。該數(shù)據(jù)集作為2004—2006 年Terabyte Tracks任務的測試數(shù)據(jù)集，一般用于對搜索引擎系統(tǒng)架構(gòu)的性能測試和評價。本文采用開源檢索系統(tǒng)Terrier4.0平臺構(gòu)建GOV2 網(wǎng)頁的倒排索引數(shù)據(jù)。首先，對網(wǎng)頁數(shù)據(jù)進行預處理：網(wǎng)頁數(shù)據(jù)集在去除超文本標記語言（HyperText Markup Language，HTML）標簽后待索引的內(nèi)容包括網(wǎng)頁標題、正文與錨文本等內(nèi)容；這些內(nèi)容分別除去標準的英語停用詞，并用Porter 詞干分析器進行詞干提取。然后，采用基于合并的索引構(gòu)建法進行倒排索引的構(gòu)建，默認壓縮算法為Eliasγ。最后，采用索引轉(zhuǎn)換方式生成各種壓縮算法壓縮的索引數(shù)據(jù)。本文僅考慮倒排信息中包含d-gap和freq的倒排文件。

為了測試WAP 算法的存儲模式的關(guān)聯(lián)性優(yōu)勢，實驗對比算法包括S9、S16 和S8b 以及本文所提基于DAG 的劃分優(yōu)化（OPT）算法：OPT-S9、OPT-S16 和OPT-S8b。另外，對比實驗還選取FOR 類型的OPT-P4D、AFOR 和VSE 三種優(yōu)化算法。實驗是在擁有Intel（R）Core（TM）雙核i7-7500U、主頻為2.70 GHz 和2.90 GHz、8 GB RAM 的處理器上完成。實驗軟件測試平臺運行于版本為1.7.0_71 的Java 虛擬機之上。本實驗采用壓縮率、壓縮速度和解壓速度3 個指標評估算法的壓縮性能，壓縮率單位為bpi（每個整數(shù)占用比特位），壓縮速度和解壓速度單位為mis（每秒百萬整數(shù)）指標［14］。壓縮測試實驗進行3 次并取平均值。本文所有的實現(xiàn)代碼（包括索引結(jié)構(gòu)、壓縮算法和仿真平臺等）可以訪問GitHub（http：//github.com/deeper2/web-index-bench）來獲取。

4.1 仿真數(shù)據(jù)壓縮實驗

本節(jié)采用仿真系統(tǒng)模擬的倒排鏈整數(shù)序列進行內(nèi)存壓縮測試。生成的隨機測試數(shù)據(jù)的分布范圍為［0，229）。生成較長整數(shù)序列數(shù)據(jù)共1 024 個，每個包含225個整數(shù)（也可以生成更多的整數(shù)，如228），因此連續(xù)整數(shù)之間的差值d-gap 為229-25=24，壓縮數(shù)據(jù)平均至少需要4位，結(jié)果如表2所示。

由表2 可以看出，本文所提出的優(yōu)化算法可以獲得一定的壓縮率提升，雖然壓縮速度因計算最優(yōu)劃分向量而降低，但是作為搜索引擎查詢過程重要的解壓速度指標是基本保持不變的。從實驗結(jié)果可以看出，本文所提出的基于動態(tài)規(guī)劃求解最優(yōu)整數(shù)序列最優(yōu)劃分的方法，在對解壓速度沒有明顯影響的前提下能夠提升FWA 類型算法的壓縮率。此外，由于本文為了單獨測試最優(yōu)劃分的效果，對于VSE 算法并沒有考慮再壓縮的情況（即VSE-R 算法），可以看出WAP優(yōu)化算法相較于AFOR 和VSE 壓縮算法也有一定的優(yōu)勢。這是因為WAP算法對于較長的d-gap序列具有較多的存儲模式，而且存儲模式的指示位開銷較少，所以對于符合網(wǎng)頁聚集特性的連續(xù)小數(shù)字整數(shù)序列，其壓縮性能并不弱于AFOR和VSE算法。

表2 聚類仿真數(shù)據(jù)上壓縮算法的性能對比結(jié)果Tab.2 Performance comparison results of compression algorithms on clustering simulation data

4.2 TREC索引壓縮實驗

本節(jié)對由Terrier4.0索引系統(tǒng)生成的TREC GOV2網(wǎng)頁索引數(shù)據(jù)格式轉(zhuǎn)換，并采用新的壓縮算法進行磁盤數(shù)據(jù)的壓縮和解壓性能測試，選擇長度大于128 的倒排鏈以降低解壓過程中頻繁的解壓函數(shù)調(diào)用開銷，實驗結(jié)果如表3所示。

表3 TERC索引數(shù)據(jù)上壓縮算法的性能對比結(jié)果Tab.3 Performance comparison results of compression algorithms on TREC index data

實驗結(jié)果表明，本文所提出的劃分優(yōu)化能夠提升FWA 類型算法的性能，而且重新設(shè)計的WAP 算法的壓縮率達到最好的效果。各種劃分優(yōu)化壓縮算法因為壓縮過程需要進行動態(tài)規(guī)劃算法求解，所以其壓縮速度要低于傳統(tǒng)非優(yōu)化壓縮算法。對于海量磁盤索引數(shù)據(jù)的解壓性能基本比較穩(wěn)定?？紤]到FWA 類型算法的存儲模式僅有16 種，AFOR 算法的存儲模式有96種，VSE算法的存儲模式有256種，而壓縮算法的實現(xiàn)代碼量和其存儲模式的硬編碼成正比。因此，如果為FWA 類型算法增加有效的存儲模式，并輔以VSE 算法所采用的格式重排技術(shù)，可以預計其壓縮率和解壓速度會有一定程度的提升。

從表3和表2的實驗結(jié)果可以發(fā)現(xiàn)，在仿真數(shù)據(jù)壓縮實驗中WAP 算法的壓縮性能要明顯優(yōu)于OPT-S8b，但是在TREC索引壓縮實驗中WAP 算法的壓縮性能僅略優(yōu)于OPT-S8b。主要的原因是互聯(lián)網(wǎng)相同主題網(wǎng)頁的聚類效果不明顯，而網(wǎng)頁的采集過程有一定的隨機性，導致倒排鏈的相鄰文檔號之間的差值d-gap較大，從而影響壓縮算法的性能。而依據(jù)聚類模型生成的仿真數(shù)據(jù)的聚類效果較好，使得適合于處理小數(shù)字序列的WAP 算法的性能優(yōu)勢更加明顯。從第3 章所述的WAP 算法的計算復雜度可以看出，如果大量的倒排鏈劃分結(jié)果無法達到較長的分塊，求解最優(yōu)劃分過程將使得K′較小，所以隨著索引規(guī)模的增加采用WAP 或者OPT-S8b 算法劃分出的分塊長度可能相同（如：塊長都為1 或者2），兩種算法都會生成大量的較短分塊，因此，WAP 和OPT-S8b 的壓縮速度差距變小。

圖2 是WAP 算法的存儲模式的調(diào)用累積分布圖?？梢钥闯觯古沛湁嚎s中調(diào)用的位寬較大的存儲模式要多于仿真數(shù)據(jù)壓縮，這進一步說明倒排鏈中待壓縮整數(shù)序列中存在較多的大整數(shù)，而仿真數(shù)據(jù)中待壓縮整數(shù)序列中生成的大整數(shù)較少。另外，從圖2中可以看出，仿真數(shù)據(jù)和索引數(shù)據(jù)在WAP算法壓縮過程中對于小數(shù)字分塊的壓縮次數(shù)要高于大數(shù)字分塊的壓縮。這也就是本文所提WAP 算法所設(shè)計的存儲模式的優(yōu)勢，結(jié)合最優(yōu)劃分技術(shù)實現(xiàn)FWA 類型算法壓縮率的提升。因此，如果按照TREC 網(wǎng)頁的鏈接對倒排索引的文檔號進行重排［19］，會使倒排鏈的d-gap 序列中的小數(shù)字增多，從而能夠進一步體現(xiàn)WAP 壓縮算法處理小數(shù)字的優(yōu)勢。另外，實驗結(jié)果表明，在單個機器字長僅為固定的64 位時，設(shè)計更為精巧的存儲模式對壓縮率的提升空間有限。后續(xù)的研究工作應該針對FWA 類型算法進行可變字長的分塊劃分來增加有效的存儲模式數(shù)量。

圖2 WAP算法的存儲模式的調(diào)用累積分布Fig.2 Distribution of calling accumulation of storage modes of WAP algorithm

5 結(jié)語

在搜索引擎系統(tǒng)的海量倒排索引壓縮存儲中，F(xiàn)WA 類型算法中存儲模式的可壓縮整數(shù)個數(shù)和位寬的非連續(xù)性，以及整數(shù)序列分塊劃分的不合理性，使得整數(shù)序列分塊內(nèi)的異常值提升了塊內(nèi)其他整數(shù)的存儲位寬。本文設(shè)計了一種指示位和數(shù)據(jù)位單獨存儲的新型FWA 類型壓縮算法，提出了一種基于DAG 描述的倒排鏈WAP 劃分壓縮算法，其核心是利用DAG進行倒排索引分塊劃分問題的描述，結(jié)合WAP算法的各種存儲模式的位寬限制來確定最優(yōu)劃分問題的結(jié)構(gòu)形式和遞歸定義，并利用動態(tài)規(guī)劃技術(shù)求解基于DAG 的倒排鏈最優(yōu)劃分問題。本文對S9、S16 和S8b 三個FWA 類型算法及其優(yōu)化算法以及WAP 算法進行了實現(xiàn)和分析。仿真和網(wǎng)頁壓縮實驗驗證了本文方法在壓縮率和解壓速度指標上較傳統(tǒng)FWA類型算法和FOR類型算法的性能優(yōu)勢。

FWA 類型算法在壓縮和解壓時存在大量的存儲模式切換開銷，一些現(xiàn)有的倒排索引壓縮算法如VSE 采用格式重排（Layout Permute）提升解壓性能，即將其中相同存儲模式的碼字按照分塊的位寬進行分類存儲并批量處理。未來的研究工作可利用格式重排技術(shù)等優(yōu)化實現(xiàn)方法來提高WAP 算法的解壓性能，也可以采用再壓縮或者文檔重排技術(shù)進一步提升WAP算法的壓縮率［19］。