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

信息檢索與Web搜索

第2講

布爾檢索BooleanRetrieval

授課人：高曙明

*改編自“現(xiàn)代信息檢索”網(wǎng)上公開課件（/~wangbin）布爾檢索針對布爾查詢的檢索，布爾查詢是指利用

AND,OR或者

NOT操作符將詞項(xiàng)連接起來的查詢信息AND

檢索信息OR

檢索信息AND

檢索ANDNOT教材Google支持布爾檢索2布爾檢索模型檢索模型：查詢與文檔之間的相關(guān)性定義，文檔及查詢的表示布爾檢索模型文檔采用詞項(xiàng)集合表示查詢用詞項(xiàng)的布爾表達(dá)式表示相關(guān)性：整個(gè)查詢的相關(guān)性通過對詞項(xiàng)相關(guān)性進(jìn)行布爾運(yùn)算得到，對于查詢中的每個(gè)詞項(xiàng)，包含則相關(guān)相關(guān)性只有相關(guān)和不相關(guān)兩種3基于掃描的布爾檢索信息需求：確定莎士比亞的哪些劇本包含Brutus及Caesar但是不包含Calpurnia

布爾查詢表示：

BrutusANDCaesarANDNOTCalpurnia簡單直接的方法：從頭到尾掃描所有劇本，對每部劇本判斷它是否包含BrutusANDCaesar，同時(shí)又不包含Calpurnia存在的問題速度超慢(特別是對超大型文檔集)難以支持更復(fù)雜的查詢

(e.g.,findthewordRomansnearcountrymen)不支持檢索結(jié)果的排序(即只返回較好的結(jié)果)4詞項(xiàng)-文檔關(guān)聯(lián)矩陣若某劇本包含某單詞，則該位置上為1，否則為0Brutus

AND

Caesar

BUT

NOT

Calpurnia詞項(xiàng)-文檔關(guān)聯(lián)矩陣：給定一個(gè)詞項(xiàng)集和一個(gè)文檔集，指由其中的詞項(xiàng)和文檔之間的關(guān)聯(lián)關(guān)系形成的矩陣

基于關(guān)聯(lián)向量的布爾檢索關(guān)聯(lián)向量：指關(guān)聯(lián)矩陣的每一行、每一列對應(yīng)的向量給定查詢BrutusANDCaesarANDNOTCalpurnia具體步驟：取出三個(gè)相應(yīng)的行向量

，并對Calpurnia

的行向量求補(bǔ)，最后按位進(jìn)行與操作110100AND110111AND101111=100100檢索結(jié)果：AntonyandCleopatra和Hamlet6一個(gè)更真實(shí)的場景假定N=1百萬篇文檔(1M),每篇有1000個(gè)詞(1K)假定每個(gè)詞平均有6個(gè)字節(jié)(包括空格和標(biāo)點(diǎn)符號)

那么所有文檔將約占6GB空間.假定詞匯表的大小(即詞項(xiàng)個(gè)數(shù))

M=500K7超大的詞項(xiàng)-文檔矩陣矩陣大小為500Kx1M=500G但是該矩陣中最多有10億(1G)個(gè)1詞項(xiàng)-文檔矩陣高度稀疏(sparse).稀疏矩陣不應(yīng)簡單地建立和存儲詞項(xiàng)文檔關(guān)聯(lián)矩陣應(yīng)該有更好的表示方式比如我們僅僅記錄所有1的位置8Why?倒排索引(Invertedindex)9DictionaryPostings按docID排序

PostingBrutusCalpurniaCaesar12456165713223112411314517317454101詞典倒排(記錄)表倒排記錄倒排索引示意圖倒排索引核心思想：對每個(gè)詞項(xiàng)t,記錄所有包含t的文檔列表，其中每篇文檔用docID表示文檔列表的數(shù)據(jù)結(jié)構(gòu)：能否采用定長數(shù)組的方式來存儲docID列表？通常采用變長表方式存儲倒排表磁盤上，順序存儲方式比較好，便于快速讀取內(nèi)存中，采用鏈表或者可變長數(shù)組方式存儲空間/易插入之間需要平衡10Tokenizer詞條流FriendsRomansCountrymen倒排索引構(gòu)建Linguisticmodules與詞項(xiàng)對應(yīng)的詞條friendromancountrymanIndexer倒排索引friendromancountryman24213161待索引文檔Friends,Romans,countrymen.詞條化工具語言分析工具索引構(gòu)建過程:

詞條表生成將每篇文檔轉(zhuǎn)化為<詞條，docID>

二元組列表IdidenactJuliusCaesarIwaskilledi'theCapitol;Brutuskilledme.Doc1SoletitbewithCaesar.ThenobleBrutushathtoldyouCaesarwasambitiousDoc2索引構(gòu)建過程:

排序首先按詞項(xiàng)排序然后對每個(gè)相同詞項(xiàng)按

docID排序

索引構(gòu)建的核心步驟索引構(gòu)建過程:

詞典&倒排表某個(gè)詞項(xiàng)在單篇文檔中的多次出現(xiàn)會被合并拆分成詞典和倒排記錄表兩部分每個(gè)詞項(xiàng)出現(xiàn)的文檔數(shù)目(doc.frequency,DF)會被加入存儲開銷計(jì)算15指針詞項(xiàng)及文檔頻率后續(xù)章節(jié):如何快速構(gòu)建索引?如何減少存儲開銷?倒排索引docID表第一講：布爾檢索布爾查詢的處理:

AND給定一個(gè)布爾查詢:BrutusANDCaesar首先在詞典中定位

Brutus返回其倒排記錄表再在詞典中定位Caesar返回其倒排記錄表合并(Merge)兩個(gè)倒排記錄表，即求交集1612834248163264123581321BrutusCaesar倒排表的合并每個(gè)倒排記錄表都有一個(gè)定位指針，兩個(gè)指針同時(shí)從前往后掃描,每次比較當(dāng)前指針對應(yīng)的倒排記錄，然后移動某個(gè)或兩個(gè)指針。假定表長分別為x和y,那么上述合并算法的復(fù)雜度為O(x+y)關(guān)鍵原因:倒排記錄表按照docID排序173412824816326412358132112834248163264123581321BrutusCaesar28合并算法的偽代碼18布爾查詢的處理:

OR/NOTOR表達(dá)式：BrutusORCaesar兩個(gè)倒排記錄表的并集NOT表達(dá)式：BrutusANDNOTCaesar兩個(gè)倒排記錄表的差集一般的布爾表達(dá)式(BrutusORCaesar)ANDNOT(AntonyORCleopatra)查詢處理依序而行？19查詢處理的效率問題考慮n個(gè)詞項(xiàng)的

AND查詢

對每個(gè)詞項(xiàng)，取出其倒排記錄表，然后兩兩合并BrutusCaesarCalpurnia123581621342481632641281316查詢:

Brutus

AND

CaesarAND

Calpurnia

20查詢處理順序的優(yōu)化優(yōu)化策略：按照表從小到大的順序進(jìn)行處理21這是為什么保存df的原因之一相當(dāng)于處理查詢(Calpurnia

AND

Brutus)

ANDCaesarBrutusCaesarCalpurnia123581621342481632641281316一般化的優(yōu)化處理針對一般的布爾表達(dá)式，首先進(jìn)行形式轉(zhuǎn)化，e.g.,(maddingORcrowd)AND(ignobleORstrife)每個(gè)布爾表達(dá)式都能轉(zhuǎn)換成上述形式(合取范式)然后獲取每個(gè)詞項(xiàng)的df，并通過將詞項(xiàng)的df相加估計(jì)每個(gè)OR表達(dá)式對應(yīng)的倒排記錄表的大小最后從小到大依次處理每個(gè)OR表達(dá)式22布爾檢索的優(yōu)點(diǎn)構(gòu)建簡單，是構(gòu)建IR系統(tǒng)的一種最簡單方式查詢表達(dá)方式直觀清晰，易于理解在30多年中是最主要的檢索工具當(dāng)前許多搜索系統(tǒng)仍然使用布爾檢索模型電子郵件、文獻(xiàn)檢索系統(tǒng)、MacOSXSpotlight工具23布爾檢索系統(tǒng):WestLaw最大的商業(yè)化法律搜索服務(wù)引擎

(1975年開始提供服務(wù);1992年加入排序功能)幾十T數(shù)據(jù)，700,000付費(fèi)用戶大部分用戶仍然使用布爾查詢查詢的例子:有關(guān)對政府侵權(quán)行為進(jìn)行索賠的訴訟時(shí)效(Whatisthestatuteoflimitationsincasesinvolvingthefederaltortclaimsact?）LIMIT!/3STATUTEACTION/SFEDERAL/2TORT/3CLAIM24布爾檢索的不足難以表達(dá)復(fù)雜的用戶信息需求想查關(guān)于2011年快女6進(jìn)5比賽的新聞，用布爾表達(dá)式怎么構(gòu)造查詢？(2011OR二零壹壹)AND(快樂女聲OR

快女OR

快樂女生)AND(6進(jìn)5

OR

六進(jìn)五OR

六AND

進(jìn)AND

五)表達(dá)式相當(dāng)復(fù)雜，構(gòu)造困難！不嚴(yán)格的話結(jié)果過多，而且很多不相關(guān)；非常嚴(yán)格的話結(jié)