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

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

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

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

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

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

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編碼對(duì)于一元碼很小的小整數(shù)是有效的，但是對(duì)于存儲(chǔ)15個(gè)以上的整數(shù)效率就降低。3.3EliasDelta()編碼Delta2編碼實(shí)際上是Gaa編碼的延伸，其中整數(shù)x由兩部分表示，1位由Gaa編碼得出，之后標(biāo)記位，接下來是x的二進(jìn)制編碼，其中x的最高位取反。Delta

7、編碼在表示小的整數(shù)的時(shí)候需要更多的空間存儲(chǔ)，但對(duì)于壓縮大整數(shù)是有效的。3.4Glb編碼在Glb8編碼中，整數(shù)x由兩部分組成：商和余數(shù)。商q是由q=得出的，余數(shù)r是由r=x-q*k-1計(jì)算出來的，這里的k是Glb編碼的基矗假如rp,可被存儲(chǔ)為位，反之那么需要位，這里的p是一個(gè)中心點(diǎn)pivtpint,是由k得到的。當(dāng)rp時(shí)，Glb編碼是由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è)編碼來講是至關(guān)重要的。假如選的不適宜，編碼會(huì)變得很大而且解碼也需要很長(zhǎng)時(shí)間。這里可以考慮0.69*ean(a

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

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

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

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

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

13、Glb同時(shí)表示文檔號(hào)和詞頻高效。置入文件閾值也稱Tpds，實(shí)際上是一種有損壓縮lssypressin,就是說有的信息可能被丟棄。這個(gè)算法的主要思想是，對(duì)多級(jí)指引索引I進(jìn)展修剪，每一個(gè)詞語t對(duì)應(yīng)n個(gè)文檔d，將那些權(quán)值A(chǔ)(d,t)很小并且對(duì)系統(tǒng)準(zhǔn)確性影響很小的文檔進(jìn)展修剪，只保存權(quán)值最高的k篇TPK。算法描繪：為了評(píng)價(jià)Tpds算法對(duì)準(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實(shí)驗(yàn)結(jié)果說明Tpds方法有可能會(huì)丟掉索引中的一些重要信息，但是卻可以和包括全部索引的查詢效果一樣好。用這種方法，網(wǎng)絡(luò)搜索引擎通過轉(zhuǎn)移那些對(duì)搜索結(jié)果沒什么影響的數(shù)據(jù)來減少存儲(chǔ)大量索引的負(fù)擔(dān)，防止了檢索整個(gè)置入文件，顯著的進(jìn)步了效率。實(shí)驗(yàn)結(jié)果證明可以減少40的索引空間，并且可以到達(dá)一樣的P10，只是在AP上有點(diǎn)降低，同時(shí)也不適用于布爾查詢?；诙嗉?jí)指引索引的兩種不同的高效策略，實(shí)際上是有損壓縮與無損壓縮的包含的兩個(gè)范疇。它們都是為了進(jìn)步查詢索引效率，也就是進(jìn)步搜索引擎的檢索

15、效率。不管是那一種方法，都有其優(yōu)點(diǎn)與弊端，但這兩種不同的高效策略并不矛盾，可以綜合應(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