基于多級指引索引的高效技術

1、基于多級指引索引的高效技術摘要介紹了搜索引擎中基于多級指引索引的高效技術。包括索引壓縮，置入文件閥值的方法。其中索引壓縮介紹了字節(jié)對齊壓縮、Eliasgaa編碼、Eliasdelta編碼、Glb編碼、二元插值編碼，并對其壓縮效率，解壓速度以及相對性能做了比擬，表達了在不同的情況下使用不同的編碼，以便進步搜索效率。關鍵詞搜索引擎，多級指引索引，索引壓縮，置入文件閥值搜索引擎SearhEngine是隨著eb信息的迅速增加，從1995年開場逐漸開展起來的技術。它是一種eb上的應用軟件系統(tǒng)，以一定的策略在eb上發(fā)現(xiàn)和搜集信息，對信息進展組織和處理，為用戶提供eb信息查詢效勞。一個搜索引擎由搜索器、索引

2、器、檢索器和用戶接口等四個部分組成。其中索引器是一個搜索引擎的核心部分，因此索引的好壞直接影響到整個搜索引擎的質量。采用多級指引索引數(shù)據(jù)構造，盡管建立時需要付出一定代價，但是極大地進步了查詢效率。本文在多級指引索引的根底上，介紹了進步效率的策略，其中包括多級指引索引的壓縮，置入文件閾值pstinglistthreshld的方法。圖1索引多級指引構造多級指引索引是倒排索引的進化，既滿足檢索接口的詞語-網(wǎng)頁構造的需要，又考慮到龐大數(shù)據(jù)量構造組織的可行性。在詞語集設置網(wǎng)頁指針，將包含該詞語的網(wǎng)頁分塊放置，減少存儲一樣詞語的空間，根據(jù)詞語標識符直接找到網(wǎng)頁分塊首位置，并為下一級指引提供前提；同一個詞語

3、在不同網(wǎng)頁中出現(xiàn)的位置是變值，設置位置指針可以減少存儲一樣網(wǎng)頁號的空間。多級指引索引壓縮的目的是通過減少存儲需求來降低輸入輸出。需要壓縮的內容包括：詞語列表中的詞語名，每一個置入文件列表記錄entry中的詞頻，每一個置入文件列表記錄文檔標識符。假如多級指引索引減少存儲量，I/讀寫置入列表pstinglist的時間就會減少，也就減少了內存、磁盤空間的占用。而一個沒有被壓縮的多級指引索引通常需要超過30的空間來存儲可壓縮的數(shù)據(jù)，壓縮后的數(shù)據(jù)只占原可壓縮數(shù)據(jù)的1015。但是存在的問題是，要對數(shù)據(jù)編碼解碼，增加了PU時間耗用，考慮到I/是系統(tǒng)的瓶頸，PU與I/之間不斷擴大的性能差距，以時間換取空間是可

4、行的。壓縮不僅進步查詢時的效率，還能加快創(chuàng)立索引，從各方面提升系統(tǒng)性能。多級指引索引壓縮的方法有字節(jié)對齊壓縮，Eliasgaa編碼，Eliasdelta編碼，Glb編碼，二元插值編碼。3.1字節(jié)對齊壓縮Byte-Aligned字節(jié)對齊壓縮1即對于一個給定的正整數(shù)，用一個或多個字節(jié)表示。表示該數(shù)首字節(jié)最左邊的兩位為長度指示器lengthindiatr，剩余位可以用來存儲實際的數(shù)。文檔ID不同，記為x，文檔ID需要基于x的字節(jié)標識碼，用前面所說的2bits寫下長度指示器。寫下x的二進制表示法，如下例：0-6300 xxxxxx64-(16K-1)01xxxxxxxxxxxxxx16K-(4-1)1

5、0 xxxxxxxxxxxxxxxxxxxxxx4-(1G-1)11xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx0000000001000000016300111111640100000001000000650100000001000001字節(jié)對齊壓縮的優(yōu)點是容易編碼和解碼，位操作少，占用PU時間少，缺點是對很小的整數(shù)壓縮率低，每個整數(shù)最少用一個字節(jié)的空間。3.2Eliasgaa編碼用2方法表示文檔ID的x的數(shù)值：表示2的次冪不超過x的最大值；一個0作為標記位arker；取x余數(shù)二進制編碼的位。用21bits表示x的值，整數(shù)越小，那么表示它值的位數(shù)就越少。大多數(shù)詞頻相對很校舉個

6、例子：X=22=424x254為2的次冪不超過22的最大值，所以得出4位一元碼unary：1111x-=22-24=6用4位二進制數(shù)表示余數(shù)6：0110最后的編碼為：111100110 x123456763100101110001100111,0,1011,0,1111111,0,11111EliasGaaEnding()總結：Gaa編碼對于一元碼很小的小整數(shù)是有效的，但是對于存儲15個以上的整數(shù)效率就降低。3.3EliasDelta()編碼Delta2編碼實際上是Gaa編碼的延伸，其中整數(shù)x由兩部分表示，1位由Gaa編碼得出，之后標記位，接下來是x的二進制編碼，其中x的最高位取反。Delta

7、編碼在表示小的整數(shù)的時候需要更多的空間存儲，但對于壓縮大整數(shù)是有效的。3.4Glb編碼在Glb8編碼中，整數(shù)x由兩部分組成：商和余數(shù)。商q是由q=得出的，余數(shù)r是由r=x-q*k-1計算出來的，這里的k是Glb編碼的基矗假如rp,可被存儲為位，反之那么需要位，這里的p是一個中心點pivtpint,是由k得到的。當rp時，Glb編碼是由q個0，一個1，r用二進制表示組成的；當r=p時，它是由q個0，一個1，r+p用二進制表示組成的。例如，k=3,整數(shù)9就可由00,1,11表示。選擇k對整個編碼來講是至關重要的。假如選的不適宜，編碼會變得很大而且解碼也需要很長時間。這里可以考慮0.69*ean(a

8、),a為整型數(shù)組。值12341112131415商123333余數(shù)1233123編碼100101110111010000111000100000101000110000111通過比擬，可以將這三種編碼方式結合起來，Glb編碼用于文檔編號，Gaa編碼用于詞頻，Delta編碼用于表示偏移量。3.5二元插值編碼BinaryInterplativeding二元插值6編碼利用相鄰元素關系，應用于單調遞增整數(shù)序列。假如在單調序列X1中，對于給定的整數(shù)xi，我們知道它的前一個整數(shù)是xi-1，后一個整數(shù)是xi+1,由此我們知道存儲xi所需要的最大位數(shù)。因為xi一定是在xi-11，xi+11的范圍內，所以需要的

9、最大比特數(shù)為2xi+1xi-12，編碼需要前面的xi-1和xi+1，所以序列X2可由原始的X1的第二個數(shù)開場與X1序列對應，編碼可以遞歸的方法。進一步優(yōu)化的方法是根據(jù)整數(shù)序列的平均游程長度eanrunlength,對位向量編碼增加參數(shù)，稱作部分形式。比擬簡單的一種方法是一個整數(shù)序列的個數(shù)是P，那么它的平均游程長度是N/P，設b=0.69N/P，那么取VG=(b,b,b,)作壓縮向量，前綴用一元編碼，后綴是二進制編碼占用個位。在非全文索引當中，置入文件由文檔號d和文檔詞頻f組成，一個d,f平均可以用一個字節(jié)表示；單詞t的置入文件可以根據(jù)t的IDF(InverseDuentFrequeny)推算出

10、來。在全文索引中，單詞出現(xiàn)的位置信息占據(jù)索引數(shù)據(jù)的主要部分，所以忽略文檔號d和文檔詞頻f。用變長壓縮算法，單詞出現(xiàn)的位置可以用少于8bit的位表示。設全部文檔分詞后的單詞總數(shù)是TN，那么單詞t總的出現(xiàn)次數(shù)是TNTF(TerFrequeny),它的置入文件的平均長度小于TNTF字節(jié)。3.6多級指引索引壓縮總結根據(jù)文獻10這幾種壓縮方法的壓縮效率，解壓速度以及相對性能的比擬如表一所示：圖3其中bp每個事件(urrene)的比特數(shù)，bpr每個記錄的比特數(shù)，p每個事件的周期數(shù)，pr每條記錄的周期數(shù)。我們可以假設1.4GB的多級指引文件列表通過最高效的方案根據(jù)表1被壓縮，載入與解壓的總代價如下：UT+E

11、nA+dn,其中U是總時間，T是尋道時間seektie，EnA是讀需要的時間，dn是在內存中解壓的時間，n是被讀取的已壓縮整數(shù)的量。當n很大時，尋道時間就可以忽略，解壓方案的性能P由讀和解壓時間來決定，PEAd；當n趨于0的時候，性能完全取決于尋道時間，PT，PT-*R+。其中表示測量的磁盤平均尋道時間，是時鐘周期固定尋道時間，R是壓縮后的文件占壓縮前的比率。通過這個式子計算可得出當編碼的整數(shù)數(shù)目很小的時候，二元插值編碼性能最好，但是在速度上Glb編碼要超過其它的編碼，當數(shù)目越來越大的時候，變長字節(jié)編碼是最高效的。如圖4示其中橫坐標表示記錄數(shù)，縱坐標表示時鐘周期數(shù)。圖4幾種壓縮方式的比擬總結起

12、來，在多級指引文件信息檢索的過程中，處理長的多級指引文件是一個瓶頸，所以隨著多級指引文件的增加而進步性能是一個好的解決方法。當多級指引文件小的時候，吞吐量由磁盤尋道時間決定，這個時間是與磁盤文件的長度相關的。減少文件的長度就會減少磁盤尋道的長度，選擇基于最小化文件的壓縮是最好的例如Glb。隨著文件長度的不斷增加，磁盤尋道時間變得不那么重要，吞吐量與解壓速度親密相關，所以變長字節(jié)編碼最適宜。假如磁盤空間需要額外的開銷，推薦用Glb壓縮算法，使用Glb算法可以使文件壓縮的更小并且解壓速度比gaa和delta算法更快。由ffat和Zbel提出的使用Glb算法表示文檔號gaa算法表示詞頻的方法不如使用

13、Glb同時表示文檔號和詞頻高效。置入文件閾值也稱Tpds，實際上是一種有損壓縮lssypressin,就是說有的信息可能被丟棄。這個算法的主要思想是，對多級指引索引I進展修剪，每一個詞語t對應n個文檔d，將那些權值A(d,t)很小并且對系統(tǒng)準確性影響很小的文檔進展修剪，只保存權值最高的k篇TPK。算法描繪：為了評價Tpds算法對準確率的影響，我們應用TRE(TextRetrievalnferene)的官方結果9，下表說明了提交給TRE運行的準確度，結果顯示P10(threshld為10)在索引修剪之后根本上沒什么變化，并且在平均準確率AP上的差異是可以忽略的。索引大小修剪率(%)APP103.

14、53GB0.2110.3620.053.15GB10.70.2070.3620.12.9GB17.80.2050.360TRE實驗結果說明Tpds方法有可能會丟掉索引中的一些重要信息，但是卻可以和包括全部索引的查詢效果一樣好。用這種方法，網(wǎng)絡搜索引擎通過轉移那些對搜索結果沒什么影響的數(shù)據(jù)來減少存儲大量索引的負擔，防止了檢索整個置入文件，顯著的進步了效率。實驗結果證明可以減少40的索引空間，并且可以到達一樣的P10，只是在AP上有點降低，同時也不適用于布爾查詢?；诙嗉壷敢饕膬煞N不同的高效策略，實際上是有損壓縮與無損壓縮的包含的兩個范疇。它們都是為了進步查詢索引效率，也就是進步搜索引擎的檢索

15、效率。不管是那一種方法，都有其優(yōu)點與弊端，但這兩種不同的高效策略并不矛盾，可以綜合應用，為進一步優(yōu)化索引構造、進步效率效勞。1ShlerF,iliasH,iannisJ.pressinfinvertedindexesfrfastqueryevaluatinJ.ATransatinsnInfratinSystes,2002(8):2222292P.Elias.Universalderdsetsandrepresentatinsftheintegers.IEEETransatinsnInfratinThery,IT-21(2):194-203,ar.1975.3Grssan,Frieder,Gha

16、rian.InfratinRetrievalpressin.2002.4NavarrG,uraE,Neubert.AddingpressintblkaddressinginvertedindexesJ.InfratinRetrieval,2000,3(1):49-775VNgAnhandAlistairffatinthepaperInvertedIndexpressinusingrd-AlignedBinarydes,InfratinRetrieval8(1):151-166,January20226ffatandL.Stuiver.Binaryinterplativedingfreffetiveindexpressin.InfratinRetrieval,3(1):2547,July2000.7PeterFenik.PunturedEliasdesfrvariable-lengthdingftheintegers.1996(12)8Jieany.GlydingNtes.2022(10)9Davidarel,EinatAitay,ikiHers