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

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

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

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

4、行的。壓縮不僅進(jìn)步查詢時的效率，還能加快創(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é)標(biāo)識碼，用前面所說的2bits寫下長度指示器。寫下x的二進(jìn)制表示法，如下例：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作為標(biāo)記位arker；取x余數(shù)二進(jìn)制編碼的位。用21bits表示x的值，整數(shù)越小，那么表示它值的位數(shù)就越少。大多數(shù)詞頻相對很校舉個

6、例子：X=22=424x254為2的次冪不超過22的最大值，所以得出4位一元碼unary：1111x-=22-24=6用4位二進(jìn)制數(shù)表示余數(shù)6：0110最后的編碼為：111100110 x123456763100101110001100111,0,1011,0,1111111,0,11111EliasGaaEnding()總結(jié)：Gaa編碼對于一元碼很小的小整數(shù)是有效的，但是對于存儲15個以上的整數(shù)效率就降低。3.3EliasDelta()編碼Delta2編碼實際上是Gaa編碼的延伸，其中整數(shù)x由兩部分表示，1位由Gaa編碼得出，之后標(biāo)記位，接下來是x的二進(jìn)制編碼，其中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得到的。當(dāng)rp時，Glb編碼是由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*ean(a

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

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

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

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

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

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

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

15、效率。不管是那一種方法，都有其優(yōu)點與弊端，但這兩種不同的高效策略并不矛盾，可以綜合應(yīng)用，為進(jìn)一步優(yōu)化索引構(gòu)造、進(jìn)步效率效勞。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