信息檢索與web搜索課件 05學(xué)習(xí)資料

信息檢索與Web搜索

第5講索引構(gòu)建Indexconstruction授課人：高曙明

*改編自“現(xiàn)代信息檢索”網(wǎng)上公開(kāi)課件（/~wangbin）相關(guān)硬件基礎(chǔ)知識(shí)在內(nèi)存中訪(fǎng)問(wèn)數(shù)據(jù)會(huì)比從硬盤(pán)訪(fǎng)問(wèn)數(shù)據(jù)快很多(大概10倍左右)硬盤(pán)尋道需要時(shí)間，即尋道時(shí)間，期間不發(fā)生數(shù)據(jù)傳輸硬盤(pán)I/O是基于塊的:讀寫(xiě)時(shí)是整塊進(jìn)行的。塊大?。?KB到256KB不等IR系統(tǒng)的服務(wù)器的典型配置是內(nèi)存幾個(gè)GB或幾十GB，硬盤(pán)數(shù)百G或者上T容錯(cuò)處理的代價(jià)非常昂貴：采用多臺(tái)普通機(jī)器會(huì)比一臺(tái)提供容錯(cuò)的機(jī)器的價(jià)格更便宜23一些統(tǒng)計(jì)數(shù)據(jù)(ca.2008)符號(hào)含義值sbP平均尋道時(shí)間每個(gè)字節(jié)的傳輸時(shí)間處理器時(shí)鐘頻率底層操作時(shí)間(e.g.,如word的比較和交換)內(nèi)存大小磁盤(pán)大小5ms=5×10?3s0.02μs=2×10?8sHz0.01μs=10?8s幾GB1TB或更多

ReutersRCV1語(yǔ)料庫(kù)路透社1995到1996年一年的英語(yǔ)新聞報(bào)道文檔集，包括政治、貿(mào)易、體育、科技等話(huà)題45ReutersRCV1語(yǔ)料庫(kù)的統(tǒng)計(jì)信息一個(gè)詞項(xiàng)的平均出現(xiàn)次數(shù)是多少？即一個(gè)詞項(xiàng)平均對(duì)應(yīng)幾個(gè)詞條？每個(gè)詞條字節(jié)數(shù)為4.5vs.每個(gè)詞項(xiàng)平均字節(jié)數(shù)7.5，為什么有這樣的區(qū)別？NLMT文檔數(shù)目每篇文檔的詞條數(shù)目詞項(xiàng)數(shù)目(=詞類(lèi)數(shù)目)每個(gè)詞條的字節(jié)數(shù)(含空格和標(biāo)點(diǎn))每個(gè)詞條的字節(jié)數(shù)(不含空格和標(biāo)點(diǎn))每個(gè)詞項(xiàng)的字節(jié)數(shù)無(wú)位置信息索引中的倒排記錄數(shù)目800,000200400,00064.57.5100,000,0006回顧:倒排索引組成

詞典

倒排記錄表

7回顧:倒排索引構(gòu)建的基本步驟掃描一遍文檔集合得到所有的詞項(xiàng)——文檔二元組以詞項(xiàng)為主鍵，以文檔ID為次鍵進(jìn)行排序?qū)⒚總€(gè)詞項(xiàng)對(duì)應(yīng)的所有文檔ID組織成倒排記錄表計(jì)算文檔頻率等統(tǒng)計(jì)量該方法對(duì)大規(guī)模文檔集不適用，為此，需要找到基于磁盤(pán)的方法圖1-4基本思想：對(duì)大規(guī)模文檔集的索引構(gòu)建進(jìn)行分而治之算法步驟：將文檔集分割成若干大小相當(dāng)?shù)牟糠謱⒚總€(gè)部分的詞項(xiàng)ID-文檔ID二元組排序?qū)⒚總€(gè)部分的倒排記錄表寫(xiě)到磁盤(pán)中將所有的中間結(jié)果合并成整個(gè)文檔集的倒排索引基于排序的分塊索引構(gòu)建BSBI89BSBI算法

一個(gè)關(guān)鍵決策：如何確定塊的大小能夠方便加載到內(nèi)存能夠在內(nèi)存中進(jìn)行快速排序10兩個(gè)塊的合并過(guò)程逐步讀入與寫(xiě)出，故內(nèi)存不需太大11基于BSBI的RCV1索引構(gòu)建需要對(duì)T=100,000,000條無(wú)位置信息的倒排記錄進(jìn)行排序每條倒排記錄需要12字節(jié)(4+4+4:termID,docID,df)定義一個(gè)能夠包含10,000,000條上述倒排記錄的數(shù)據(jù)塊這個(gè)數(shù)據(jù)塊很容易放入內(nèi)存中(12*10M=120M)對(duì)于RCV1有10個(gè)數(shù)據(jù)塊基本過(guò)程:對(duì)每個(gè)塊:(i)倒排記錄累積到10,000,000條,(ii)在內(nèi)存中排序,(iii)寫(xiě)回磁盤(pán)最后將所有的塊合并成一個(gè)大的有序的倒排索引內(nèi)存式單遍掃描索引構(gòu)建SPIMI基本思想：對(duì)大規(guī)模文檔集的索引構(gòu)建進(jìn)行分而治之算法特點(diǎn)對(duì)每個(gè)塊都產(chǎn)生一個(gè)獨(dú)立的詞典，使用詞項(xiàng)而不是其ID，不需要統(tǒng)一的詞典增量式動(dòng)態(tài)形成倒排記錄表，避免對(duì)所有詞項(xiàng)—文檔ID二元組進(jìn)行排序在處理過(guò)程中形成塊，而不是一開(kāi)始分塊，使分塊更合理1213SPIMI算法14課堂練習(xí):計(jì)算1臺(tái)機(jī)器下采用BSBI方法對(duì)Google級(jí)規(guī)模數(shù)據(jù)構(gòu)建索引的時(shí)間分布式索引構(gòu)建分布式計(jì)算環(huán)境：計(jì)算機(jī)集群，由很多臺(tái)日用計(jì)算機(jī)組成，每臺(tái)計(jì)算機(jī)隨時(shí)可能出故障基本思想維持一臺(tái)主機(jī)(Master)來(lái)指揮索引構(gòu)建任務(wù)-這臺(tái)主機(jī)被認(rèn)為是安全的將索引構(gòu)建劃分成多組并行任務(wù)主機(jī)將把每個(gè)任務(wù)分配給空閑機(jī)器來(lái)執(zhí)行當(dāng)發(fā)現(xiàn)某臺(tái)計(jì)算機(jī)有問(wèn)題時(shí)，將其任務(wù)重新分配分布式策略：基于詞項(xiàng)分割；基于文檔分割15Google數(shù)據(jù)中心(2007Gartner)Google數(shù)據(jù)中心主要都是普通機(jī)器數(shù)據(jù)中心均采用分布式架構(gòu)，在世界各地分布100萬(wàn)臺(tái)服務(wù)器，300個(gè)處理器/核Google每15分鐘裝入100,000個(gè)服務(wù)器每年的支出大概是每年2-2.5億美元這可能是世界上計(jì)算能力的10%!在一個(gè)1000個(gè)節(jié)點(diǎn)組成的無(wú)容錯(cuò)系統(tǒng)中，每個(gè)節(jié)點(diǎn)的正常運(yùn)行概率為99.9%，整個(gè)系統(tǒng)的正常運(yùn)行概率是多少？63%假定一臺(tái)服務(wù)器3年后會(huì)失效，對(duì)于100萬(wàn)臺(tái)服務(wù)器，機(jī)器失效的平均間隔大概是多少？不到2分鐘1617并行任務(wù)文檔集分割：將輸入的文檔集分片(split)(對(duì)應(yīng)于BSBI/SPIMI算法中的塊)兩類(lèi)并行任務(wù)分析器(Parser)主節(jié)點(diǎn)將一個(gè)數(shù)據(jù)片分配給一臺(tái)空閑的分析器分析器逐篇處理文檔產(chǎn)生

(term,docID)二元組分析器將所有二元組分成j個(gè)詞項(xiàng)分區(qū)，寫(xiě)入j個(gè)分區(qū)文件倒排器(Inverter)主控節(jié)點(diǎn)將每一term分區(qū)(e.g.,a-f分區(qū))分配給一個(gè)倒排器，倒排器收集其所有的(term,docID)二元組對(duì)每個(gè)分區(qū)的所有二元組排序，輸出倒排記錄表（分布式存放）18數(shù)據(jù)流裂片分析器分析器分析器a-fg-pq-z倒排器倒排器倒排器a-fg-pq-za-fg-pq-za-fg-pq-z主控節(jié)點(diǎn)分配分配倒排記錄表Map階段分區(qū)文件Reduce階段MapReduceMapReduce是一個(gè)魯棒的簡(jiǎn)單分布式計(jì)算框架，由Google提出和推廣Hadoop是MapReduce的一個(gè)實(shí)現(xiàn)Google索引構(gòu)建系統(tǒng)(ca.2002)由多個(gè)步驟組成，每個(gè)步驟都采用MapReduce實(shí)現(xiàn)需要根據(jù)具體問(wèn)題編寫(xiě)Map和Reduce函數(shù)前面介紹的索引構(gòu)建過(guò)程實(shí)際上是MapReduce的一個(gè)實(shí)例19基于MapReduce的索引構(gòu)建排好序的倒排記錄表（k，list(v))20動(dòng)態(tài)索引構(gòu)建背景：文檔集是變化的，文檔會(huì)增加、刪除和修改，因此索引應(yīng)該是動(dòng)態(tài)更新的一種解決方案：周期性重構(gòu)一個(gè)全新的索引能夠接受對(duì)新文檔檢索的一定延遲具有足夠的資源動(dòng)態(tài)索引構(gòu)建：能夠及時(shí)更新變化文檔集索引的方法2122動(dòng)態(tài)索引構(gòu)建:主輔索引法在磁盤(pán)上維護(hù)一個(gè)大的主索引(Mainindex)在內(nèi)存中構(gòu)建新文檔的索引，稱(chēng)輔助索引（Auxiliaryindex）查詢(xún)處理時(shí)，同時(shí)搜索兩個(gè)索引，然后合并結(jié)果定期將輔助索引合并到主索引中刪除文檔的處理：采用無(wú)效位向量(Invalidationbit-vector)來(lái)表示刪除的文檔利用該維向量過(guò)濾返回的結(jié)果，以去掉已刪除文檔23主輔索引合并中的問(wèn)題合并可能過(guò)于頻繁（因內(nèi)存有限）合并時(shí)如果正好在搜索，那么搜索的性能將很低，？合并耗時(shí)分析:如果每個(gè)倒排記錄表都采用一個(gè)單獨(dú)的文件來(lái)存儲(chǔ)的話(huà)，那么將輔助索引合并到主索引的代價(jià)并沒(méi)有那么高此時(shí)合并等同于一個(gè)簡(jiǎn)單的添加操作但是這樣做將需要大量的文件，造成文件系統(tǒng)效率不高另一種方法是將索引整體存入一個(gè)大文件中現(xiàn)實(shí)當(dāng)中常常介于上述兩者之間(例如：將大的倒排記錄表分割成多個(gè)獨(dú)立的文件，將多個(gè)小倒排記錄表一并存放在一個(gè)文件當(dāng)中……)24對(duì)數(shù)合并(Logarithmicmerge)對(duì)數(shù)合并算法能夠緩解(隨時(shí)間增長(zhǎng))索引合并的開(kāi)銷(xiāo)→用戶(hù)并不感覺(jué)到響應(yīng)時(shí)間上有明顯延遲維護(hù)一系列索引，其中每個(gè)索引是前一個(gè)索引的兩倍大小將最小的索引(Z0)置于內(nèi)存其他更大的索引(I0,I1,...)置于磁盤(pán)如果

Z0

變得太大(>n),則將它作為I0寫(xiě)到磁盤(pán)中(如果

I0

不存在)或者和

I0

合并(如果

I0

已經(jīng)存在)，并將合并結(jié)果作為I1寫(xiě)到磁盤(pán)中(如果

I1

不存在)，或者和I1合并(如果

I0

已經(jīng)存在)，依此類(lèi)推……25對(duì)數(shù)合并算法26對(duì)數(shù)合并的復(fù)雜度索引數(shù)目的上界：

O(logT)(T

是所有倒排記錄的個(gè)數(shù))對(duì)數(shù)合并索引構(gòu)建時(shí)間：

O(TlogT)這是因?yàn)槊總€(gè)倒排記錄需要合并O(logT)次輔助索引方式：

索引構(gòu)建時(shí)間為O(T2)，因?yàn)槊看魏喜⒍夹枰幚砻總€(gè)倒排記錄因此，對(duì)數(shù)合并的復(fù)雜度比輔助索引方式要低一個(gè)數(shù)量級(jí)查