信息檢索 第04章 文本搜索技術(shù)專業(yè)課課件

信息檢索

第04章文本搜索技術(shù)軟件學(xué)院教研室陳鄞信息檢索系統(tǒng)的體系結(jié)構(gòu)文本數(shù)據(jù)庫數(shù)據(jù)庫管理建索引索引查詢處理搜索排序排序后的文檔用戶反饋文本處理用戶界面檢出的文檔用戶需求文本提問邏輯視圖倒排文檔引言文本搜索方法全文掃描基于索引的文本搜索什么是索引？索引是一種數(shù)據(jù)結(jié)構(gòu)，它在關(guān)鍵詞與包含關(guān)鍵詞的文檔之間建立了一種映射關(guān)系，從而加快檢索的速度。建立索引的目的加快檢索速度常用的索引技術(shù)倒排文檔后綴數(shù)組簽名文件本章內(nèi)容4.1倒排文檔4.2后綴數(shù)組4.3簽名文件4.4全文掃描4.1倒排文檔4.1.1什么是倒排文檔4.1.2倒排文檔的建立4.1.3倒排文檔的維護(hù)4.1.4倒排文檔的壓縮4.1.5倒排文檔性能分析4.1.1什么是倒排文檔文檔編號題目關(guān)鍵詞1…知識管理，管理信息系統(tǒng)，企業(yè)信息化2…知識管理，知識鏈，學(xué)習(xí)型組織，知識創(chuàng)新3…知識管理，知識創(chuàng)新，知識共享4…知識管理，學(xué)習(xí)型組織5…技術(shù)創(chuàng)新，知識空間，知識創(chuàng)新6…企業(yè)信息化，信息結(jié)構(gòu)，競爭情報7…知識管理，知識創(chuàng)新，競爭情報8…管理信息系統(tǒng)，企業(yè)文化9…管理信息系統(tǒng)，競爭情報10…知識管理，企業(yè)文化，管理創(chuàng)新關(guān)鍵詞目長文檔集合1管理創(chuàng)新1102管理信息系統(tǒng)31;8;93技術(shù)創(chuàng)新154競爭情報36;7;95企業(yè)文化28;106企業(yè)信息化21;67信息結(jié)構(gòu)168學(xué)習(xí)型組織22;49知識創(chuàng)新42;3;5;710知識管理61;2;3;4;7;1011知識共享1312知識空間1513知識鏈12建立索引以記錄集合的某一屬性作為索引對象，記錄該屬性的每一個屬性值在記錄集合中的出現(xiàn)位置倒排文檔的定義倒排文檔是從關(guān)鍵詞快速查詢到文檔的索引結(jié)構(gòu)。文檔正常表示為關(guān)鍵詞的集合，建立倒排文檔是把每個關(guān)鍵詞表示為其所在文檔的集合，這個過程稱為inversion，即倒排。有些書在最后提供的索引（單詞—頁碼列表對），就可以看成是一種倒排文檔倒排文檔的結(jié)構(gòu)倒排文檔組成詞項詞典（dictionary）索引項（詞項）組成的集合倒排記錄表（PostingList）索引項在文檔集合中的位置組成的集合architecturecomputerdatabaseretrieval...D1,a1D1,a2D1,a3詞項詞典全體倒排記錄表Q=term1,term2,term3,...在實際應(yīng)用中，記錄表的組織形式和存儲的內(nèi)容是多種多樣的可以在一個文件內(nèi)部建立倒排文檔文本倒排文檔12345678910111213141516這是一本關(guān)于信息檢索的教材。介紹了檢索的基本技術(shù)?！夹g(shù)教材檢索信息…15,…8,…6,12,…5,……詞匯表記錄表保存句子位置保存段落、句子和詞的位置databasefilesystems...D345,25D348,37D350,8D123,5D128,25D345,25文檔D350第8句databasefilesystems...D345,2,3,5D348,37,5,9D350,8,12,1D123,5,4,3D128,25,1,12D345,2,3,6文檔D350第8段第12句第1個詞在記錄表中存儲關(guān)鍵詞所在的文檔編號段落編號句子編號詞編號所在的特殊單元（如標(biāo)題、小標(biāo)題）保存位置序號的目的：支持上下文條件查詢短語查詢例如：搜索“StanfordUniversity”TheinventorStanfordOvshinskyneverwenttouniversity.近鄰查詢“database”和“systems”之間不能間隔超過3個詞“database”和“architecture”在同一個句子（段落）里databaseD1,2,97,104D3,43systemD1,5D3,44“database”在D1中出現(xiàn)的詞序號在記錄表中存儲指針在記錄表中存儲統(tǒng)計信息頻率權(quán)重databasefilesystems...D345,10D348,20D350,1D123,82D128,8D345,12在D345中，“systems”

比“database”重要1.2倍總結(jié)——記錄表中的內(nèi)容位置信息形式上：序號或指針內(nèi)容上：文檔、段落、句子、詞附加信息特殊位置信息：所在單元（標(biāo)題、小標(biāo)題）統(tǒng)計信息同義詞擴(kuò)展詞匯表同義詞對于提高檢索的召回率很有意義同義詞可以通過指針指向同一個記錄表...databasedatabasessystemsD345,2,3,5D348,37,5,9D350,8,12,1D123,5,4,3D128,25,1,12D345,2,3,6dataset4.1.2詞典的確定詞條化（

Tokenizing）詞條歸一化(TokenNormalization)去除停用詞某些情況下，一些常見詞在文檔和用戶需求進(jìn)行匹配時價值并不大，需要徹底從詞匯表中去除。這些詞稱為停用詞（stopword）預(yù)處理對倒排索引的影響例：Reuters-RCV1語料規(guī)模：1GB文本數(shù)據(jù)內(nèi)容：1996年8月20日到1997年8月19日一年間的路透社新聞180對Reuters-RCV1進(jìn)行預(yù)處理前后詞項、無位置信息倒排記錄及詞條的數(shù)目4.1.3倒排文檔的建立DocidTermpaperreportnovelnovel……1111…reporthuman……22…h(huán)umannovelnovelpaperreportreport……211112…排序歸并human2,1novel1,2paper1,1report1,12,11112在此記錄文檔頻率在此記錄詞項頻率基于排序的索引構(gòu)建方法對于小規(guī)模文檔集來說，上述過程均可在內(nèi)存中完成在大規(guī)模文檔條件下需要引入二級存儲介質(zhì)時的索引方法基于塊排序的索引方法分布式索引構(gòu)建方法為使索引構(gòu)建過程效率更高，將詞項用其ID來代替，每個詞項的ID是唯一的序列編號①基于塊排序的索引方法BSBI(blockedsort-basedindexing)第1步，將文檔集分割成幾個大小相等的部分；第2步，將每個部分的詞項ID—文檔ID對排序；第3步，將中間產(chǎn)生的臨時排序結(jié)果存放到磁盤中；第4步，將所有的中間文件合并成最終的索引。BSBINDEXCONSTRUCTION()1n←02while(alldocumentshavenotbeenprocessed)3don←n+14

block←PARSENEXTBLOCK()5 BSBI-INVERT(block)6 WRITEBLOCKTODISK(block,fn)7MERGEBLOCKS(f1,...,fn;fmerged)MERGEBLOCKS(f1,...,fn;fmerged)合并時，同時打開所有塊對應(yīng)的文件，內(nèi)存中維護(hù)為n個塊準(zhǔn)備的讀緩沖區(qū)和一個為最終合并索引準(zhǔn)備的寫緩沖區(qū)每次迭代中，利用優(yōu)先級隊列或者類似的數(shù)據(jù)結(jié)構(gòu)選擇最小的未處理詞項ID進(jìn)行處理。讀入該詞項的各個倒排記錄表并合并，合并結(jié)果寫回磁盤中②內(nèi)存式單遍掃描索引構(gòu)建方法SPIMI(single-passin-memoryindexing)SPIMI使用詞項而不是其ID，它將每個塊的詞典寫入磁盤，對于下一個塊則重新采用新的詞典只要硬盤空間足夠大，就能夠索引任何大小的文檔集性能分析優(yōu)點：由于不需要排序操作，因此處理的速度更快由于保留了倒排記錄表對詞項的歸屬關(guān)系，因此能夠節(jié)省內(nèi)存，詞項的ID也不需要保存這樣，每次單獨的SPIMI-Invert調(diào)用能夠夠處理的塊大小可以非常大，整個倒排索引的構(gòu)建過程也因此會非常高效。缺點每次當(dāng)空間放滿的時候，就會申請加倍的空間。這意味著一些空間被浪費正好抵消了不用保存詞項ID所省下的空間?？傮w來說，SPIMI所需的內(nèi)存空間仍然比BSBI少③

分布式索引構(gòu)建方法實際當(dāng)中的文檔集通常很大，在單臺計算機(jī)上很難高效的構(gòu)建索引Web搜索引擎通常需要大規(guī)模計算機(jī)集群，使用分布式算法來構(gòu)建索引，其索引結(jié)果也是分布式的，它往往按照詞項或文檔進(jìn)行分割后分布在多臺計算機(jī)上MapReduceMapReduce是一個通用的分布式計算框架，它面向大規(guī)模計算機(jī)集群而設(shè)計集群的關(guān)鍵是，利用價格低廉的日用計算機(jī)（稱為節(jié)點node）來解決大型的計算問題。這些計算機(jī)都采用通用的標(biāo)準(zhǔn)部件（處理器、內(nèi)存和磁盤），而不像超級計算機(jī)那樣采用專用硬件一般來說，MapReduce會通過鍵-值對（key-valuepair）的轉(zhuǎn)換處理，將一個大型的計算問題轉(zhuǎn)化成較小的子問題在索引構(gòu)建中，鍵-值對的形式就是(詞項ID,文檔ID)Map階段將輸入的數(shù)據(jù)片映射成鍵-值對。在索引構(gòu)建中，該階段對應(yīng)于BSBI和SPIMI算法中的文檔分析任務(wù)，因此也將執(zhí)行map過程的機(jī)器稱為分析器（parser）Reduce階段將同一鍵（詞項ID）的所有值（文檔ID）集中存儲在索引構(gòu)建中，對應(yīng)于倒排任務(wù)，因此也將執(zhí)行reduce過程的機(jī)器稱為倒排器（inverter）使用MapReduce進(jìn)行分布式索引構(gòu)建的例子4.1.4倒排文檔的維護(hù)插入文檔刪除文檔更新文檔①插入文檔方法調(diào)用該文檔包含的關(guān)鍵詞所對應(yīng)的記錄表，在后面插入關(guān)鍵詞在該文檔中的位置信息，該表再放回倒排文檔中最壞的情況文檔包含n個關(guān)鍵詞，并且每個關(guān)鍵詞都不重復(fù)，插入時需要調(diào)用并更新n個記錄表批量插入如果每插入一個文檔，都要調(diào)用幾十次或幾百次記錄表，時間上開銷很大事實上，倒排文檔中文檔的插入工作都是成批進(jìn)行的首先為待插入的多個文檔建立輔助索引（臨時內(nèi)存索引）檢索時，同時遍歷主索引和臨時內(nèi)存索引，并將結(jié)果合并當(dāng)輔助索引變得很大時，就將它合并到主索引中批量插入為什么能提高效率？一個詞可能出現(xiàn)在多個文檔中批處理過程從倒排文檔中調(diào)出一個記錄表，可插入若干記錄項批量插入需要注意的問題索引內(nèi)容滯后問題對臨時內(nèi)存索引進(jìn)行檢索使用后臺進(jìn)程在機(jī)器空閑時進(jìn)行插入操作批量插入的規(guī)模批不能太小，否則很少會出現(xiàn)多個文件包含一個詞的情況批不能太大，否則批的生成本身開銷也很大設(shè)計一個新的插入操作時，必須考慮主存和臨時存儲器中可利用的空間大小倒排文檔的插入開銷依賴于更新的頻度，對索引的即時性的要求，以及系統(tǒng)的工作負(fù)荷能力對于圖書館應(yīng)用來說，插入操作不是問題對新聞和互聯(lián)網(wǎng)方面的應(yīng)用而言，就是一個問題②刪除文檔前向索引（ForwardIndex）步驟找到將要被刪除的文檔ID從前向索引中獲得該文檔中包含的詞根據(jù)該文檔中的詞定位倒排文檔中的記錄表，并在這些記錄表中將該文檔ID刪除DocIDword1,word2,….批量刪除保持刪除的及時性維護(hù)一張“刪除文件列表”，在檢索過程中，忽略那些被登記在表中的文檔ID使用后臺進(jìn)程在機(jī)器空閑時進(jìn)行刪除操作③更新文檔代價較高一般不進(jìn)行更新操作，而是使用“刪除+插入”操作代替對于數(shù)據(jù)量不大的應(yīng)用，甚至可以考慮重建索引4.1.5基于倒排文檔的檢索布爾模型中的檢索VSM中的檢索4.1.5.1布爾模型中基于倒排文檔的檢索例：BrutusANDCalpurnia該并發(fā)掃描算法要求倒排記錄表必須按照全局統(tǒng)一的指標(biāo)進(jìn)行排序布爾模型中的查詢優(yōu)化查詢優(yōu)化(queryoptimization)指的是如何通過組織查詢的處理過程來使處理工作量最小對布爾查詢進(jìn)行優(yōu)化要考慮的一個主要因素是倒排記錄表的訪問順序a

AND

b

AND

c按照詞項的文檔頻率（也就是倒排記錄表的長度）從小到大依次進(jìn)行處理(maddingORcrowd)AND(ignobleORstrife)AND(killedORslain)保守地估計出每個OR操作后的結(jié)果大小，然后按照結(jié)果從小到大的順序執(zhí)行AND操作基于跳表的倒排記錄表快速合并算法例

跳表指針個數(shù)多少跳躍的步長短長跳躍的可能性大小指針比較次數(shù)多少存儲空間多少4.1.5.2倒排記錄表在VSM中的應(yīng)用基于倒排文檔的向量相似度計算以文檔為單位的評分方法（document-at-a-time）以詞項為單位的評分方法（term-at-a-time）以文檔為單位的評分方法給定查詢q，并發(fā)掃描q中各詞項的倒排記錄表，得到并集A對A中的文檔進(jìn)行余弦相似度計算該算法要求倒排記錄表必須按照全局統(tǒng)一的指標(biāo)進(jìn)行排序以詞項為單位的評分方法算法要點根據(jù)每個t的貢獻(xiàn)對文檔得分進(jìn)行累加數(shù)組Scores的N個元素也稱為累加器（accumulator）非精確返回前K篇文檔的方法精確返回前K篇得分最高文檔的主要計算開銷源于大量文檔都參與的余弦相似度計算非精確返回前K篇得分最高文檔基本思想：只集中關(guān)注那些可能具有很高最終得分的文檔，減少參與計算的文檔數(shù)目，產(chǎn)生“可能”排名最高的K篇文檔的方法①索引去除技術(shù)只考慮那些詞項的idf值超過一定閾值的文檔只考慮包含多個查詢詞項（一個特例是包含全部查詢詞項）的文檔存在的問題：有可能最后的候選結(jié)果文檔數(shù)目少于K個例：q=“risinginterestrates”解決辦法：層次型索引（tieredindex）risinginterestrates②勝者表（championlist）基本思路對于詞典中的每個詞項t，預(yù)先計算出倒排記錄表中tf值最高的r個文檔構(gòu)成t的勝者表給定查詢q，對查詢q中所有詞項的勝者表求并集，得到集合A。只對A中的文檔進(jìn)行余弦相似度計算如果勝者表按照全局統(tǒng)一的指標(biāo)進(jìn)行排序（如文檔ID），既可以采用以文檔為單位的評分方法，并發(fā)掃描查詢q中所有詞項的勝者表，也可以采用以詞項為單位的評分方法如果勝者表按照tf值降序排列，只可以采用以詞項為單位的評分方法直觀上說，r應(yīng)該比K大沒有必要將所有詞項的r設(shè)成一樣的值，比如對于罕見詞項，r值可以適當(dāng)設(shè)大一些③全局勝者表(globalchampionlist)靜態(tài)質(zhì)量得分（staticqualityscore，簡稱靜態(tài)得分）很多搜索引擎中，每篇文檔d往往都有一個與查詢無關(guān)的靜態(tài)得分g(d)，該得分函數(shù)的取值往往在0到1之間靜態(tài)得分也是一種全局統(tǒng)一的指標(biāo)如果將所有文檔按照其靜態(tài)得分g(d)在倒排記錄表中降序排列，也可以采用并發(fā)掃描的方法進(jìn)行倒排記錄表的合并操作一篇文檔d的最后得分可以定義為靜態(tài)得分g(d)和某個與查詢相關(guān)的得分的某種組合例：score(q,d)=g(d)+cossim(q,d)公式(1)基于靜態(tài)得分的全局勝者表對于詞典中的每個詞項tj，預(yù)先計算出g(di)+

wij得分最高的r個文檔構(gòu)成tj

的勝者表給定查詢q，對查詢q中所有詞項的全局勝者表求并集，得到集合A。利用公式(1)只對集合A中的文檔計算其最后得分勝者表存在的問題并集A中的元素個數(shù)可能會少于K解決辦法對每個詞項t，維持兩個無交集的倒排文件表第一張表稱為高端表，由m篇具有最高tf值的文檔組成；第二張表稱為低端表，由剩下的包含t的文檔組成。

每個表均以g(d)值來排序給定查詢q，對查詢q中所有詞項的高端表求并集，得到集合A。只對集合A中的文檔計算其最后得分如果該過程能夠產(chǎn)生前K篇得分最高的文檔，則處理結(jié)束。否則，需要繼續(xù)掃描低端表并計算其中文檔的得分。④簇剪枝方法（clusterpruning）

簇剪枝方法之變形

b1

=b2=1時是原始簇剪枝方法增加b1

和b2

會增加找到真實的前K篇文檔的可能性，但也會消耗更大的代價4.1.6倒排文檔的壓縮為什么要進(jìn)行壓縮?節(jié)省磁盤空間經(jīng)過適當(dāng)?shù)膲嚎s，索引的大小可以降為原始文檔的25%左右加快數(shù)據(jù)從磁盤到內(nèi)存的傳輸效率將壓縮的數(shù)據(jù)塊傳輸?shù)絻?nèi)存并解壓所需的總時間往往比將未壓縮的數(shù)據(jù)塊傳輸?shù)絻?nèi)存要快提高了倒排文檔的緩存能力，因為壓縮技術(shù)使得內(nèi)存的利用率大大提高。隨著緩存能力的提高，檢索的速度也得到相應(yīng)提高。壓縮技術(shù)的分類有損壓縮會損失一些原文信息大小寫轉(zhuǎn)換、去停用詞、詞干提取、……LSA降維技術(shù)無損壓縮在壓縮文件的同時，其原始信息完全保留，不會缺損倒排文檔壓縮的內(nèi)容詞匯表記錄表（1）詞匯表的壓縮定寬數(shù)組浪費存儲空間不能表示所有的詞字符串表詞匯表關(guān)鍵詞文檔數(shù)鏈接………………檢索3………………計算機(jī)2………………記錄表文檔號……127……29……詞匯表關(guān)鍵詞指針文檔數(shù)鏈接………………3………………2………………記錄表文檔號……127……29…………檢索\0……計算機(jī)\0……既緊湊，又不會出現(xiàn)溢出現(xiàn)象壓縮率可達(dá)50%左右使用定寬數(shù)組表示一個單詞（2）記錄表的壓縮問題一般用16位或32位整數(shù)表示文檔和單詞位置的絕對編號。16位很容易溢出，16位整數(shù)最多可以表示65536個文檔或單詞位置編號，這在實際中是很容易造成溢出的（尤其是文檔編號）。32位又浪費空間對于大多數(shù)文檔和單詞位置編號而言，很難達(dá)到這個數(shù)值①定長整數(shù)描述相對變化用比較少的位數(shù)（如16位）記錄位置間的相對變化僅記錄相鄰位置之間的差異databaseD345,25,34,98,120D348,37,71,85database345,25,9,64,223,37,34,14Wordpositions類似視頻壓縮中僅記錄本幀和上一幀的差異②變長整數(shù)描述變化定長整數(shù)描述相對變化存在的問題有些常用詞（例如“的”），文本編號的相對變化多數(shù)是1，如果仍然使用16位編碼，顯然浪費了太多的空間某些詞可能僅存在于少數(shù)的文本之中，而這些文本編號的相對變化也很有可能超過65,536，即216。這時，如果仍然使用16位整數(shù)表示，就會溢出變長整數(shù)描述相對變化基本原理：使用較少的位數(shù)表示較小的整數(shù)，而較大的整數(shù)，則需要使用較多的位數(shù)表示壓縮技術(shù)帶來的負(fù)面影響在搜索時必須花些時間對壓縮的數(shù)據(jù)進(jìn)行解碼在維護(hù)時，特別是進(jìn)行刪除操作時，由于某些文檔被刪除，所以不得不對剩余的文檔編號進(jìn)行重新編碼但是，以上這些都是處理器的計算問題，在目前的硬件條件下，磁盤的I/O速度過慢才是影響IR的瓶頸。由于索引被壓縮，提高了磁盤的傳輸效率，因此，壓縮技術(shù)仍然是利大于弊的4.1.7倒排文檔的性能分析倒排文檔的優(yōu)點檢索速度較快存儲的信息類型較多，支持復(fù)雜的檢索操作4.1.7倒排文檔的性能分析倒排文檔的優(yōu)點倒排文檔的缺點很大的存儲開銷很高的維護(hù)開銷文本被看作是詞的序列，在某種程度上限制了其應(yīng)用在某些應(yīng)用中，如基因數(shù)據(jù)庫，不存在詞的概念對于中文等東亞語言，詞的概念不明確適合于在相對靜態(tài)的環(huán)境中使用q=人民/生活di:報紙/上/有/一/篇/題/為/“/提高/人/民生/活水/平/”/的/文章但可以壓縮提綱4.1倒排文檔4.2后綴數(shù)組4.3簽名文件4.4全文掃描4.2后綴數(shù)組后綴（Suffix）是指從某個位置i開始到整個串末尾結(jié)束的一個特殊子串。i∈{1,2,…,n}，n為字符串的長度例后綴數(shù)組（SuffixArray）是一個一維數(shù)組，它按“字典順序”保存字符串的n個后綴及其起始位置，即SA[i]<SA[i+1]字符串后綴后綴起始位置iS=s1s2s3s4s5 s1s2s3s4s51s2s3s4s52s3s4s53s4s54s55由n個字符組成的字符串有n個后綴4.2.1后綴數(shù)組的構(gòu)造原始文本文本中的部分后綴后綴數(shù)組（按字典序索引）024681012141618202224262830323436384042444648…這是一本關(guān)于信息檢索的教材。介紹了檢索的基本技術(shù)?！?21216223444…這是…是一…信息…檢索…教材…檢索…技術(shù)……441634222120…技術(shù)…檢索…檢索…教材…是一…信息…這是……在實際構(gòu)造后綴數(shù)組時，其實存放的只是各個后綴的前m個字節(jié)其實質(zhì)是倒排索引文本長度為m的字附串4.2.2基于后綴數(shù)組的檢索原始文本后綴數(shù)組q=“信息檢索”“信息”→“信息檢索” √q=“信息過濾”“信息”→“信息過濾” ×q=“數(shù)據(jù)結(jié)構(gòu)”“數(shù)據(jù)” ×024681012141618202224262830323436384042444648…這是一本關(guān)于信息檢索的教材。介紹了檢索的基本技術(shù)?！?41634222120…技術(shù)…檢索…檢索…教材…是一…信息…這是……在使用后綴數(shù)組進(jìn)行檢索的時候，將每個查詢同樣截取前n個字節(jié)，并于索引中進(jìn)行查找如果沒有找到，則表明不包含所需查詢?nèi)绻檎页晒?，則需要在相應(yīng)的文本位置上，進(jìn)行進(jìn)一步的字符串比較，以確定文本中是否包含查詢4.2.3后綴數(shù)組的性能分析倒排文檔vs.后綴數(shù)組從形式上看，后綴數(shù)組是一種特殊的倒排文檔特指倒排索引文本中長度為n的字符串檢索機(jī)制不同倒排文檔提取完整的查詢詞，即可確定該查詢詞的位置信息后綴數(shù)組只提取查詢詞的前幾個字，然后逐一匹配后面的字符串，以確定查詢詞的位置信息后綴數(shù)組的缺點沒有倒排文檔速度快存儲開銷較大，有重復(fù)信息例如：“提高人民生活水平”占用更多的存儲單元后綴數(shù)組的缺點沒有倒排文檔速度快存儲開銷較大，有重復(fù)信息很難支持排序操作優(yōu)點后綴數(shù)組可以避免部分分詞錯誤造成的影響，從而提高系統(tǒng)的召回率q=人民/生活di:報紙/上/有/一/篇/題/為/“/提高/人/民生/活水/平/”/的/文章提綱4.1倒排索引4.2后綴數(shù)組4.3簽名文件4.4全文掃描4.3簽名文件4.3.1簽名文件的構(gòu)造詞的簽名是一個位向量，由F位組成，其中有m位置1Wordshash(wordsignatures)free001000110010text000010101001information000000011110retrieval101000100001freetextinformationretrieval文本串:F=12m=4一種單詞“簽名”的生成算法輸入：詞W，參數(shù)F和m輸出：詞W的F位“簽名”S算法：1)將W轉(zhuǎn)換為ASCII值（每個字符8位），構(gòu)成整數(shù)i

例如：free=66726565(hex)2)初始化：F位全置0；srandom(i)；

//初始化隨機(jī)種子j=0；3)whilej<m {

p=random();

//生成一個隨機(jī)整數(shù)

y=pmodF；

//

映射到0和F-1之間

if(S[y]==0)

//確保m位置1

{S[y]=1；

j++；

}

}4)結(jié)束，返回Sblocksignatures塊的簽名Block1Block2WordsWordsignaturesfree001000110010text000010101001information000000011110retrieval101000100001101000111111001010111011freetextinformationretrieval文本串:假設(shè)一個塊包含兩個連續(xù)的詞塊的簽名是通過塊中所有詞的簽名按位進(jìn)行“或”操作得到簽名文件按順序存放塊簽名的文件簽名文件指針文件文檔N塊Fbits0010101110111010001111114.3.2簽名文件的使用和維護(hù)對單個詞的查詢q進(jìn)行檢索Step1：使用相同的散列算法生成q的簽名sqStep2：將sq與所有文本塊的簽名si進(jìn)行匹配 匹配條件：sq∩si

=sq

如果si在sq取1的位置上也取1，則該塊被返回000010101001querysignature∩=000010101001√=000000101001×block1

001010111011block2

101000111111blocksignature如果sq與si

匹配成功,就一定能夠確保是一次正確的匹配嗎?4.3.2簽名文件的使用和維護(hù)對單個詞的查詢q進(jìn)行檢索Step1：使用相同的散列算法生成q的簽名sqStep2：將sq與所有文本塊的簽名si進(jìn)行匹配falsedrops產(chǎn)生的原因主要原因：不同詞的簽名重疊次要原因：hash沖突001

000

110

010Query=“free”bitsfrom‘retrieval’signaturebitsfrom‘information’signature誤檢FalseDrop誤檢產(chǎn)生的原因？4.3.2簽名文件的使用和維護(hù)對單個詞的查詢q進(jìn)行檢索Step1：使用相同的散列算法生成q的簽名sqStep2：將sq與所有文本塊的簽名si進(jìn)行匹配Step3：對所有匹配上的文本塊執(zhí)行字符串匹配，確定其是否真正含有要查找的單詞簽名文件的設(shè)計簽名文件的性能指標(biāo)存儲開銷M誤檢率F一個文本塊據(jù)其簽名看包含某個關(guān)鍵詞，但事實上并不包含該關(guān)鍵詞的概率需要確定的參數(shù)塊的大小一般將一個文本看作是一塊Signature的長度經(jīng)驗表明，取文本平均長度的30%~40%為宜每個詞的Signature中多少位置1簽名文件應(yīng)用：作為過濾器排除不包含查詢關(guān)鍵詞的文檔=過濾出的文本匹配的文本QuerySignature文件文檔集合Query

signature4.3.3簽名文件的性能分析優(yōu)點組織簡單，容易生成，維護(hù)費用較低缺點和倒排文檔相比，搜索速度較慢檢索的時間復(fù)雜性與原始文檔集成線性關(guān)系去除Falsedrops需要昂貴的開銷很難支持排序操作很難使用其它查詢函數(shù)，例如同義詞、通配符、分離條件、鄰近操作提綱4.1倒排索引4.2后綴數(shù)組4.3簽名文件4.4全文掃描4.4全文掃描全文掃描不使用任何索引技術(shù)而快速在給定文本或文本集合中查找某一關(guān)鍵詞的技術(shù)。這種技術(shù)通常被稱為單模式匹配某些應(yīng)用中，建立索引的方法并不適用簽名文件的候選塊確認(rèn)過程文本過濾搜索引擎的結(jié)果后處理全文掃描技術(shù)也具有很廣闊的應(yīng)用場合模式匹配問題的定義輸入模式P=p1p2…pm文本S=

s1s2…sn(通常

n>>m)輸出如果文本S包含模式P，則返回匹配位置否則返回不成功常用的單模式匹配算法BruteForce算法（BF）Knuth-Morris-Pratt

算法（KMP

）Boyer-Moore算法（BM

）4.4.1BruteForce算法

{ i:=1

j:=1

while(i

mandj

n) {if(pi==

sj)

{ i:=i+1;

j:=j+1 }

else

{

j:=j-i+2;

i:=1 } }

if(i>m)

returnj

else

returnfalse; }此循環(huán)可以更早地終止:j

n-m+1i=1j=8i=7j=14travelinformationinformingi=1j=9travelinformationinforming模板向右移動算法描述將模式P=p1p2…pm

和文本S的m個字符的子串sksk+1…sk+m-1進(jìn)行匹配(1≤k≤n)如果匹配，則返回匹配的位置如果不匹配，則從sk+1位置開始新的考察BruteForce算法—性能優(yōu)點簡單、直接、容易實現(xiàn)，無需進(jìn)行任何形式的預(yù)處理缺點時間復(fù)雜性較高在模式的末尾發(fā)現(xiàn)不匹配在模式的開頭發(fā)現(xiàn)不匹配4.4.2KMP算法KMP算法是一種改進(jìn)的字符串匹配算法，由D.E.Knuth、V.R.Pratt、J.H.Morris同時發(fā)現(xiàn)位置

12345678文本

abdadefg模式

abdfabdfBruteForce:移動一個字符abdf聰明的做法：移動三個字符在已經(jīng)匹配成功的部分(abd)沒有重復(fù)字串，因此“a”不可能出現(xiàn)在下兩個字符中KMP算法的基本思想每當(dāng)匹配過程中出現(xiàn)字符串比較不等時，不象BF算法那樣僅將模式向右滑動一個位置，而是利用已經(jīng)得到的部分匹配結(jié)果將模式向右滑動盡可能遠(yuǎn)的一段距離后，繼續(xù)進(jìn)行比較。這種方法可以避免對那些能夠推斷出不匹配的位置進(jìn)行徒勞的操作KMP匹配算法–舉例abcabcacab3個字符后發(fā)現(xiàn)不匹配，在已經(jīng)匹配成功的部分(abc)沒有重復(fù)字串將P中的第1個字符與S中不匹配的字符對齊abcabcacab子串a(chǎn)bcabca匹配成功;其中最長的重復(fù)部分是abca;將P向右移動3個位置，

和重復(fù)部分對齊第1個字符不匹配，向右移動1次abcabcacab第1個字符不匹配，向右移動1次P:abcabcacabS:babcbabcabcaabcaabcabcacabKMP–一般原則從匹配成功的子模式中找出“能夠相互匹配的最長的前綴和后綴”如果P中已經(jīng)匹配成功的部分[1..i]首尾有重復(fù)部分，重復(fù)字串的長度為k，則跳過的字符個數(shù)為i-k如果P中已經(jīng)匹配成功的部分[1..i]首尾沒有重復(fù)部分,

則可以直接移動

i個字符ββx模式1ii+1文本ββy1jj+ij+i+1ββx為什么要求“最長”？為什么要求“最長”P:abcabcacababcabcacab3個字符后發(fā)現(xiàn)不匹配，在已經(jīng)匹配成功的部分(abc)沒有重復(fù)字串將P中的第1個字符與S中不匹配的字符對齊abcabcacab子串a(chǎn)bcabca匹配成功;其中最長的重復(fù)部分是abca;將P向右移動3個位置，

和重復(fù)部分對齊第1個字符不匹配，向右移動1次abcabcacab第1個字符不匹配，向右移動1次P:abcabcacabS:babcbabcabca

bcacababcabcacab在不確定的情況下，模板滑動的距離要盡量短，以免錯過可能的匹配Shift表例:模式P=“abcabcacab”匹配失敗的位置(i+1)模式字符重復(fù)子串長度(k)跳過字符數(shù)(i-k)1a012b013c024a035b136c237a338c439a0810b18構(gòu)造Shift表

的時間復(fù)雜度：O(m)課后練習(xí)：編寫分析表構(gòu)造算法4.4.3Boyer-Moore算法S:BANANA^CREAMP:CREAMS:BANANA^CREAMP:CREAMS:BANANA^CREAMP:CREAMN(sm)

和M(pm)不匹配，且N不在P中出現(xiàn);向右移動

m=5

個位置,D1=5E和M不匹配，E(sm)

在p中出現(xiàn);移動P使之相互對齊，D1=2如果有多個E，應(yīng)該和哪個E對齊？Shift表tm

m12345Cφ1234R1φ123E12φ12A123φ1M1234Φα12345最右不匹配的字母位置編號模式P=CREAM=字母表Σ–{C,R,E,A,M}另一個例子模式P=“BANANA”123456Bφ12345A1φ1φ1φN12φ1φ1α123456過程描述先令模式和文本左邊對齊，然后對模式中最右一個字符pm與其在文本中相對應(yīng)的字符tm進(jìn)行比較如果比較的結(jié)果是不匹配第一種情況，tm根本沒有在模式中的任何一個位置出現(xiàn)，那么就可以放心大膽地將模式向后移動m個字符如果tm是模式中的第r個字符（指最后一次出現(xiàn)的位置），那么就可以將模式向后移動m-r個字符如果比較的結(jié)果是匹配對模式中右數(shù)第2個字符pm-1與其在文本中相對應(yīng)的字符tm-1進(jìn)行比較。此過程往復(fù)循環(huán)。BM算法--D2Shift僅基于

D1,移動一個字符abcabdacababcabdacab僅基于D2,移動5個字符S:babcbadcabcaabcaP:abcabdacab根據(jù)模式中是否還包含已經(jīng)匹配上的子模式”cab”來確定模板移動的距離如何計算Δ2？ijD2Shift的實現(xiàn)如果在

p[i]處不匹配，令：

len=m-i

找到最大的j

使p[j..(j+len-1)]=p[(i+1)..m]

則：shift2[i]=i–j+1P:abcabdacabij是否D2

總是大于D1

？

S:babcbadcabcaabcaP:abcabcacababcabcacab

D1=7