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

1、基于多級指引索引的高效技術(shù)         08-05-02 16:49:00     作者：丁維1 周長勝 2    編輯：studa0714 摘  要 介紹了搜索引擎中基于多級指引索引的高效技術(shù)。包括索引壓縮，置入文件閥值的方法。其中索引壓縮介紹了字節(jié)對齊壓縮、Elias gamma編碼、Elias delta編碼、Golomb編碼、二 元插值編碼，并對其壓縮效率，解壓速度以及相對性能做了比較，敘述了在不同的情況

2、下使用不同的編碼，以便提高搜索效率。       關(guān)鍵詞 搜索引擎，多級指引索引，索引壓縮，置入文件閥值 1 引言       搜索引擎（Search Engine）是隨著Web信息的迅速增加，從1995年開始逐漸發(fā)展起來的技術(shù)。它是一種Web上的應(yīng)用軟件系統(tǒng)，以一定的策略在Web上發(fā)現(xiàn)和收集信息，對信息進(jìn)行組織和處理，為用戶提供Web信息查詢服務(wù)。      一個搜索引擎由搜索器、索引器、檢索器和用戶接口等四個部分組成。其中

3、索引器是一個搜索引擎的核心部分，因此索引的好壞直接影響到整個搜索引擎的質(zhì)量。采用多級指引索引數(shù)據(jù)結(jié)構(gòu)，盡管建立時需要付出一定代價，但是極大地提高了查詢效率。本文在多級指引索引的基礎(chǔ)上，介紹了提高效率的策略，其中包括多級指引索引的壓縮，置入文件閾值（posting list threshold）的方法。2 多級指引索引簡介圖1 索引多級指引結(jié)構(gòu)      多級指引索引是倒排索引的進(jìn)化，既滿足檢索接口的詞語-網(wǎng)頁結(jié)構(gòu)的需要，又考慮到龐大數(shù)據(jù)量結(jié)構(gòu)組織的可行性。在詞語集設(shè)置網(wǎng)頁指針，將包含該詞語的網(wǎng)頁分塊放置，減少存儲相同詞語的空間，根據(jù)詞語標(biāo)識符直

4、接找到網(wǎng)頁分塊首位置，并為下一級指引提供前提；同一個詞語在不同網(wǎng)頁中出現(xiàn)的位置是變值，設(shè)置位置指針可以減少存儲相同網(wǎng)頁號的空間。3  多級指引索引的壓縮      多級指引索引壓縮的目標(biāo)是通過減少存儲需求來降低輸入輸出。需要壓縮的內(nèi)容包括：詞語列表中的詞語名，每一個置入文件列表記錄（entry）中的詞頻，每一個置入文件列表記錄文檔標(biāo)識符。如果多級指引索引減少存儲量，I/O讀寫置入列表（posting list）的時間就會減少，也就減少了內(nèi)存、磁盤空間的占用。而一個沒有被壓縮的多級指引索引通常需要超過30的空間來存儲可壓縮的數(shù)據(jù)，壓縮后

5、的數(shù)據(jù)只占原可壓縮數(shù)據(jù)的1015。但是存在的問題是，要對數(shù)據(jù)編碼解碼，增加了CPU時間耗用，考慮到I/O是系統(tǒng)的瓶頸，CPU與I/O之間不斷擴(kuò)大的性能差距，以時間換取空間是可行的。壓縮不僅提高查詢時的效率，還能加快創(chuàng)建索引，從各方面提升系統(tǒng)性能。     多級指引索引壓縮的方法有字節(jié)對齊壓縮，Elias gamma編碼，Elias delta編碼，Golomb編碼，二元插值編碼。3.1 字節(jié)對齊壓縮（Byte-Aligned）      字節(jié)對齊壓縮1即對于一個給定的正整數(shù)，用一個或多個字節(jié)表示。表示該數(shù)

6、首字節(jié)最左邊的兩位為長度指示器（length indicator），剩余位可以用來存儲實際的數(shù)。文檔ID不同，記為x，文檔ID需要基于x的字節(jié)標(biāo)識碼，用前面所說的2bits寫下長度指示器。寫下x的二進(jìn)制表示法，如下例：0-63         00xxxxxx64-(16K-1)    01xxxxxx xxxxxxxx16K-(4M-1)   10xxxxxx xxxxxxxx xxxxxxxx4M-(1G-1)    11xxxxx

7、x xxxxxxxx xxxxxxxx xxxxxxxx 0            000000001            00000001           63        

8、60; 0011111164          01000000 0100000065          01000000 01000001字節(jié)對齊壓縮的優(yōu)點是容易編碼和解碼，位操作少，占用CPU時間少，缺點是對很小的整數(shù)壓縮率低，每個整數(shù)最少用一個字節(jié)的空間。3.2 Elias gamma（）編碼      用2方法表示文檔ID的x的數(shù)值： 表示2的 次冪不超過x的

9、最大值；一個0作為標(biāo)記位（marker）；取x 余數(shù)二進(jìn)制編碼的 位。用2 1bits表示x的值，整數(shù)越小，則表示它值的位數(shù)就越少。大多數(shù)詞頻相對很小。舉個例子：X=22=4  24x<254為2的  次冪不超過22的最大值，所以得出4位一元碼（unary）：1111x- =22-24=6用4位二進(jìn)制數(shù)表示余數(shù)6：0110最后的編碼為：1111 0 0110x1234567630100101110001100111,0,1011,0,11 11111,0,11111Elias Gamma Encoding()總結(jié)：Gamma編碼對于一元碼很小的小整數(shù)是有效的

10、，但是對于存儲15個以上的整數(shù)效率就降低。3.3 Elias Delta()編碼      Delta2編碼實際上是Gamma編碼的延伸，其中整數(shù)x由兩部分表示，1 位由Gamma編碼得出，之后標(biāo)記位，接下來是x的二進(jìn)制編碼，其中x的最高位取反。Delta編碼在表示小的整數(shù)的時候需要更多的空間存儲，但對于壓縮大整數(shù)是有效的。3.4 Golomb編碼      在Golomb8編碼中，整數(shù)x由兩部分組成：商和余數(shù)。商q是由q= 得出的，余數(shù)r是由r=x-q*k-1計算出來的，這里的k是Golomb

11、編碼的基礎(chǔ)。如果r<p,可被存儲為 位，反之則需要 位，這里的p是一個中心點（pivot point）,是由 k得到的。      當(dāng)r<p時，Golomb編碼是由q個0，一個1，r（用二進(jìn)制表示）組成的；當(dāng)r>=p時，它是由q個0，一個1，r+p（用二進(jìn)制表示）組成的。例如，k=3,整數(shù)9就可由00,1,11表示。選擇k對整個編碼來講是至關(guān)重要的。如果選的不合適，編碼會變得很大而且解碼也需要很長時間。這里可以考慮0.69*mean(a),a為整型數(shù)組。值012341112131415商0000123333余數(shù)01230301

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

13、所需要的最大位數(shù)。因為xi一定是在xi-11，xi+11的范圍內(nèi)，所以需要的最大比特數(shù)為2（xi+1xi-12），編碼需要前面的xi-1和xi+1，所以序列X2可由原始的X1的第二個數(shù)開始與X1序列對應(yīng)，編碼可以遞歸的方法。      進(jìn)一步優(yōu)化的方法是根據(jù)整數(shù)序列的平均游程長度（mean run length）,對位向量編碼增加參數(shù)，稱作局部模式。比較簡單的一種方法是一個整數(shù)序列的個數(shù)是Pw，則它的平均游程長度是N/Pw，設(shè)b=0.69N/Pw，則取VG=(b,b,b,)作壓縮向量，前綴用一元編碼，后綴是二進(jìn)制編碼（占用個位）。      在非全文索引當(dāng)中，置入文件由文檔號d和文檔詞頻f組成，一個（d,f）平均可以用一個字節(jié)表示；單詞t的置入文件可以根據(jù)t的IDF(Inverse