基于多級(jí)指引索引的高效技術(shù)(1)

1、基于多級(jí)指引索引的高效技術(shù)(1)         1 引言        搜索引擎（Search Engine）是隨著Web信息的迅速增加，從1995年開(kāi)始逐漸 發(fā)展 起來(lái)的技術(shù)。它是一種Web上的 應(yīng)用 軟件 系統(tǒng)，以一定的策略在Web上發(fā)現(xiàn)和收集信息，對(duì)信息進(jìn)行 組織 和處理，為用戶提供Web信息查詢服務(wù)。          一個(gè)搜索引擎由搜索器、索引器

2、、檢索器和用戶接口等四個(gè)部分組成。其中索引器是一個(gè)搜索引擎的核心部分，因此索引的好壞直接影響到整個(gè)搜索引擎的質(zhì)量。采用多級(jí)指引索引數(shù)據(jù)結(jié)構(gòu)，盡管建立時(shí)需要付出一定代價(jià)，但是極大地提高了查詢效率。本文在多級(jí)指引索引的基礎(chǔ)上，介紹了提高效率的策略，其中包括多級(jí)指引索引的壓縮，置入文件閾值（posting list threshold）的方法。 2 多級(jí)指引索引簡(jiǎn)介     圖1 索引多級(jí)指引結(jié)構(gòu)          多級(jí)指引索引是倒排索引的進(jìn)化，既滿足檢索接口的詞語(yǔ)-網(wǎng)頁(yè)

3、結(jié)構(gòu)的需要，又考慮到龐大數(shù)據(jù)量結(jié)構(gòu)組織的可行性。在詞語(yǔ)集設(shè)置網(wǎng)頁(yè)指針，將包含該詞語(yǔ)的網(wǎng)頁(yè)分塊放置，減少存儲(chǔ)相同詞語(yǔ)的空間，根據(jù)詞語(yǔ)標(biāo)識(shí)符直接找到網(wǎng)頁(yè)分塊首位置，并為下一級(jí)指引提供前提；同一個(gè)詞語(yǔ)在不同網(wǎng)頁(yè)中出現(xiàn)的位置是變值，設(shè)置位置指針可以減少存儲(chǔ)相同網(wǎng)頁(yè)號(hào)的空間。 3  多級(jí)指引索引的壓縮       多級(jí)指引索引壓縮的目標(biāo)是通過(guò)減少存儲(chǔ)需求來(lái)降低輸入輸出。需要壓縮的內(nèi)容包括：詞語(yǔ)列表中的詞語(yǔ)名，每一個(gè)置入文件列表記錄（entry）中的詞頻，每一個(gè)置入文件列表記錄文檔標(biāo)識(shí)符。如果多級(jí)指引索引減少存儲(chǔ)量，I/O讀寫(xiě)置入列表（posti

4、ng list）的時(shí)間就會(huì)減少，也就減少了內(nèi)存、磁盤空間的占用。而一個(gè)沒(méi)有被壓縮的多級(jí)指引索引通常需要超過(guò)30的空間來(lái)存儲(chǔ)可壓縮的數(shù)據(jù)，壓縮后的數(shù)據(jù)只占原可壓縮數(shù)據(jù)的1015。但是存在的問(wèn)題是，要對(duì)數(shù)據(jù)編碼解碼，增加了CPU時(shí)間耗用，考慮到I/O是系統(tǒng)的瓶頸，CPU與I/O之間不斷擴(kuò)大的性能差距，以時(shí)間換取空間是可行的。壓縮不僅提高查詢時(shí)的效率，還能加快創(chuàng)建索引，從各方面提升系統(tǒng)性能。         多級(jí)指引索引壓縮的方法有字節(jié)對(duì)齊壓縮，Elias gamma編碼，Elias delta編碼，Golomb編碼，二

5、元插值編碼。 3.1 字節(jié)對(duì)齊壓縮（Byte-Aligned）       字節(jié)對(duì)齊壓縮1即對(duì)于一個(gè)給定的正整數(shù)，用一個(gè)或多個(gè)字節(jié)表示。表示該數(shù)首字節(jié)最左邊的兩位為長(zhǎng)度指示器（length indicator），剩余位可以用來(lái)存儲(chǔ)實(shí)際的數(shù)。文檔ID不同，記為x，文檔ID需要基于x的字節(jié)標(biāo)識(shí)碼，用前面所說(shuō)的2bits寫(xiě)下長(zhǎng)度指示器。寫(xiě)下x的二進(jìn)制表示法，如下例：    0-63         00xxxxxx 

6、60;  64-(16K-1)    01xxxxxx xxxxxxxx    16K-(4M-1)   10xxxxxx xxxxxxxx xxxxxxxx    4M-(1G-1)    11xxxxxx xxxxxxxx xxxxxxxx xxxxxxxx         0    

7、        00000000    1            00000001                   63      &#

8、160;   00111111    64          01000000 01000000    65          01000000 01000001    字節(jié)對(duì)齊壓縮的優(yōu)點(diǎn)是容易編碼和解碼，位操作少，占用CPU時(shí)間少，缺點(diǎn)是對(duì)很小的整數(shù)壓縮率低，每個(gè)整數(shù)最少用一個(gè)

9、字節(jié)的空間。 3.2 Elias gamma（）編碼       用2方法表示文檔ID的x的數(shù)值： 表示2的 次冪不超過(guò)x的最大值；一個(gè)0作為標(biāo)記位（marker）；取x 余數(shù)二進(jìn)制編碼的 位。用2 1bits表示x的值，整數(shù)越小，則表示它值的位數(shù)就越少。大多數(shù)詞頻相對(duì)很小。    舉個(gè)例子：    X=22    =4  24x<25    4為2的  次冪不

10、超過(guò)22的最大值，所以得出4位一元碼（unary）：1111    x- =22-24=6    用4位二進(jìn)制數(shù)表示余數(shù)6：0110    最后的編碼為：1111 0 0110     x    1    2    3    4    5&

11、#160;   6    7        63        0    100    101    11000    11001    11,0,10 

12、60;  11,0,11         11111,0,11111    Elias Gamma Encoding() 總結(jié) ：Gamma編碼對(duì)于一元碼很小的小整數(shù)是有效的，但是對(duì)于存儲(chǔ)15個(gè)以上的整數(shù)效率就降低。 3.3 Elias Delta()編碼       Delta2編碼實(shí)際上是Gamma編碼的延伸，其中整數(shù)x由兩部分表示，1 位由Gamma編碼得出，之后標(biāo)記位，接下來(lái)是x的二進(jìn)制編

13、碼，其中x的最高位取反。Delta編碼在表示小的整數(shù)的時(shí)候需要更多的空間存儲(chǔ)，但對(duì)于壓縮大整數(shù)是有效的。 3.4 Golomb編碼       在Golomb8編碼中，整數(shù)x由兩部分組成：商和余數(shù)。商q是由q= 得出的，余數(shù)r是由r=x-q*k-1計(jì)算出來(lái)的，這里的k是Golomb編碼的基礎(chǔ)。    如果r<p,可被存儲(chǔ)為 位，反之則需要 位，這里的p是一個(gè)中心點(diǎn)（pivot point）,是由 k得到的。        

14、;  當(dāng)r<p時(shí)，Golomb編碼是由q個(gè)0，一個(gè)1，r（用二進(jìn)制表示）組成的；當(dāng)r>=p時(shí)，它是由q個(gè)0，一個(gè)1，r+p（用二進(jìn)制表示）組成的。例如，k=3,整數(shù)9就可由00,1,11表示。    選擇k對(duì)整個(gè)編碼來(lái)講是至關(guān)重要的。如果選的不合適，編碼會(huì)變得很大而且解碼也需要很長(zhǎng)時(shí)間。這里可以考慮0.69*mean(a),a為整型數(shù)組。     值    0    1    

15、;2    3    4        11    12    13    14    15        商    0   &#

16、160;0    0    0    1        2    3    3    3    3        余數(shù)   

17、60;0    1    2    3    0        3    0    1    2    3        

18、;編碼    100    101    110    111    0100        00111    000100    000101    000110   

19、 000111              通過(guò)比較，可以將這三種編碼方式結(jié)合起來(lái)，Golomb編碼用于文檔編號(hào)，Gamma編碼用于詞頻，Delta編碼用于表示偏移量。 3.5 二元插值編碼（Binary Interpolative coding）       二元插值6編碼利用相鄰元素關(guān)系，應(yīng)用于單調(diào)遞增整數(shù)序列。如果在單調(diào)序列X1中，對(duì)于給定的整數(shù)xi，我們知道它的前一個(gè)整數(shù)是xi-1，后一個(gè)整數(shù)是xi+

20、1, 由此我們知道存儲(chǔ)xi所需要的最大位數(shù)。因?yàn)閤i一定是在xi-11，xi+11的范圍內(nèi)，所以需要的最大比特?cái)?shù)為2（xi+1xi-12），編碼需要前面的xi-1和xi+1，所以序列X2可由原始的X1的第二個(gè)數(shù)開(kāi)始與X1序列對(duì)應(yīng)，編碼可以遞歸的方法。          進(jìn)一步優(yōu)化的方法是根據(jù)整數(shù)序列的平均游程長(zhǎng)度（mean run length）,對(duì)位向量編碼增加參數(shù)，稱作局部模式。比較簡(jiǎn)單的一種方法是一個(gè)整數(shù)序列的個(gè)數(shù)是Pw，則它的平均游程長(zhǎng)度是N/Pw，設(shè)b=0.69N/Pw，則取VG=(b,b,b,

21、)作壓縮向量，前綴用一元編碼，后綴是二進(jìn)制編碼（占用個(gè)位）。          在非全文索引當(dāng)中，置入文件由文檔號(hào)d和文檔詞頻f組成，一個(gè)（d,f）平均可以用一個(gè)字節(jié)表示；單詞t的置入文件可以根據(jù)t的IDF(Inverse Document Frequency)推算出來(lái)。          在全文索引中，單詞出現(xiàn)的位置信息占據(jù)索引數(shù)據(jù)的主要部分，所以忽略文檔號(hào)d和文檔詞頻f。用變長(zhǎng)壓縮算法，單詞出現(xiàn)的位置可以用少于8

22、bit的位表示。設(shè)全部文檔分詞后的單詞總數(shù)是TN，那么單詞t總的出現(xiàn)次數(shù)是TN×TF(Term Frequency),它的置入文件的平均長(zhǎng)度小于TN×TF字節(jié)。       其中bpo每個(gè)事件(occurrence)的比特?cái)?shù)，bpr每個(gè)記錄的比特?cái)?shù)，cpo每個(gè)事件的周期數(shù)，cpr每條記錄的周期數(shù)。          我們可以假設(shè)1.4GB的多級(jí)指引文件列表通過(guò)最高效的方案（根據(jù)表1）被壓縮，載入與解壓的總代價(jià)如下：  

23、;        UT+EnA+dn,其中U是總時(shí)間，T是尋道時(shí)間（seek time），EnA是讀需要的時(shí)間，dn是在內(nèi)存中解壓的時(shí)間，n是被讀取的已壓縮整數(shù)的量。         當(dāng)n很大時(shí)，尋道時(shí)間就可以忽略，解壓方案的性能P由讀和解壓時(shí)間來(lái)決定，PEAd；         當(dāng)n趨于0的時(shí)候，性能完全取決于尋道時(shí)間，PT，PT（M-C）*R+C。 &#

24、160;       其中M表示測(cè)量的磁盤平均尋道時(shí)間，C是時(shí)鐘周期固定尋道時(shí)間，R是壓縮后的文件占?jí)嚎s前的比率。        通過(guò)這個(gè)式子計(jì)算可得出當(dāng)編碼的整數(shù)數(shù)目很小的時(shí)候，二元插值編碼性能最好，但是在速度上Golomb編碼要超過(guò)其它的編碼，當(dāng)數(shù)目越來(lái)越大的時(shí)候，變長(zhǎng)字節(jié)編碼是最高效的。如圖4示（其中橫坐標(biāo)表示記錄數(shù)，縱坐標(biāo)表示時(shí)鐘周期數(shù)）。        圖4幾種壓縮方式的比較&

25、#160;         總結(jié)起來(lái)，在多級(jí)指引文件信息檢索的過(guò)程中，處理長(zhǎng)的多級(jí)指引文件是一個(gè)瓶頸，所以隨著多級(jí)指引文件的增加而提高性能是一個(gè)好的解決方法。當(dāng)多級(jí)指引文件小的時(shí)候，吞吐量由磁盤尋道時(shí)間決定，這個(gè)時(shí)間是與磁盤文件的長(zhǎng)度相關(guān)的。減少文件的長(zhǎng)度就會(huì)減少磁盤尋道的長(zhǎng)度，選擇基于最小化文件的壓縮是最好的（例如Golomb）。隨著文件長(zhǎng)度的不斷增加，磁盤尋道時(shí)間變得不那么重要，吞吐量與解壓速度密切相關(guān)，所以變長(zhǎng)字節(jié)編碼最合適。如果磁盤空間需要額外的開(kāi)銷，推薦用Golomb壓縮算法，使用Golomb算法可以使文

26、件壓縮的更小并且解壓速度比gamma和delta算法更快。由Moffat和Zobel提出的使用Golomb算法表示文檔號(hào)gamma算法表示詞頻的方法不如使用Golomb同時(shí)表示文檔號(hào)和詞頻高效。 4 置入文件閾值（Posting list threshold）       置入文件閾值也稱Topdocs，實(shí)際上是一種有損壓縮（lossy compression）,就是說(shuō)有的信息可能被丟棄。          這個(gè)算法的主要思想是，對(duì)多級(jí)指引索引I進(jìn)行修剪，

27、每一個(gè)詞語(yǔ)t對(duì)應(yīng)n個(gè)文檔d，將那些權(quán)值A(chǔ)(d,t)很小并且對(duì)系統(tǒng)準(zhǔn)確性影響很小的文檔進(jìn)行修剪，只保存權(quán)值最高的k篇（TOP K）。    算法描述：          為了評(píng)價(jià)Topdocs算法對(duì)精確率的影響，我們 應(yīng)用 TREC(Text Retrieval Conference)的官方結(jié)果9，下表說(shuō)明了提交給TREC運(yùn)行的準(zhǔn)確度，結(jié)果顯示P10(threshold為10)在索引修剪之后基本上沒(méi)什么變化，并且在平均精確率（MAP）上的差別是可以忽略的。 

28、        索引大小    修剪率(%)    MAP    P10    0    3.53GB    0    0.211    0.362    0.05

29、60;   3.15GB    10.7    0.207    0.362    0.1    2.9GB    17.8    0.205    0.360       

30、60;  TREC實(shí)驗(yàn)結(jié)果說(shuō)明Topdocs方法有可能會(huì)丟掉索引中的一些重要信息，但是卻可以和包括全部索引的查詢效果一樣好。用這種方法， 網(wǎng)絡(luò) 搜索引擎通過(guò)轉(zhuǎn)移那些對(duì)搜索結(jié)果沒(méi)什么影響的數(shù)據(jù)來(lái)減少存儲(chǔ)大量索引的負(fù)擔(dān)，避免了檢索整個(gè)置入文件，顯著的提高了效率。實(shí)驗(yàn)結(jié)果證明可以減少40的索引空間，并且可以達(dá)到相同的P10，只是在MAP上有點(diǎn)降低，同時(shí)也不適用于布爾查詢。 5  總結(jié)       基于多級(jí)指引索引的兩種不同的高效策略，實(shí)際上是有損壓縮與無(wú)損壓縮的包含的兩個(gè)范疇。它們都是為了提高查詢索引效率，也就是提高搜索引擎的檢索

31、效率。不管是那一種方法，都有其優(yōu)點(diǎn)與弊端，但這兩種不同的高效策略并不矛盾，可以綜合應(yīng)用，為進(jìn)一步優(yōu)化索引結(jié)構(gòu)、提高效率服務(wù)。 參考文獻(xiàn) 1 Scholer F,Wiliams H,iannis J.Compression of inverted indexes for fast query evaluation J .ACM Transactions on Information Systems,2002 (8):222 229    2 P. Elias. Universal codeword sets and representations of the integers. IEEE Transactions on Information Theory,IT-21(2):194-203, Mar. 1975.    3 Grossman, Frieder, Goharian. Information Retrieval Compression. 2002.    4 Navarro G, Moura E, Neubert M. Adding compression