信息檢索

第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什么是倒排文檔文檔編號(hào)題目關(guān)鍵詞1…知識(shí)管理，管理信息系統(tǒng)，企業(yè)信息化2…知識(shí)管理，知識(shí)鏈，學(xué)習(xí)型組織，知識(shí)創(chuàng)新3…知識(shí)管理，知識(shí)創(chuàng)新，知識(shí)共享4…知識(shí)管理，學(xué)習(xí)型組織5…技術(shù)創(chuàng)新，知識(shí)空間，知識(shí)創(chuàng)新6…企業(yè)信息化，信息結(jié)構(gòu)，競爭情報(bào)7…知識(shí)管理，知識(shí)創(chuàng)新，競爭情報(bào)8…管理信息系統(tǒng)，企業(yè)文化9…管理信息系統(tǒng)，競爭情報(bào)10…知識(shí)管理，企業(yè)文化，管理創(chuàng)新關(guān)鍵詞目長文檔集合1管理創(chuàng)新1102管理信息系統(tǒng)31;8;93技術(shù)創(chuàng)新154競爭情報(bào)36;7;95企業(yè)文化28;106企業(yè)信息化21;67信息結(jié)構(gòu)168學(xué)習(xí)型組織22;49知識(shí)創(chuàng)新42;3;5;710知識(shí)管理61;2;3;4;7;1011知識(shí)共享1312知識(shí)空間1513知識(shí)鏈12建立索引以記錄集合的某一屬性作為索引對(duì)象，記錄該屬性的每一個(gè)屬性值在記錄集合中的出現(xiàn)位置倒排文檔的定義倒排文檔是從關(guān)鍵詞快速查詢到文檔的索引結(jié)構(gòu)。文檔正常表示為關(guān)鍵詞的集合，建立倒排文檔是把每個(gè)關(guān)鍵詞表示為其所在文檔的集合，這個(gè)過程稱為inversion，即倒排。有些書在最后提供的索引（單詞—頁碼列表對(duì)），就可以看成是一種倒排文檔倒排文檔的結(jié)構(gòu)倒排文檔組成詞項(xiàng)詞典（dictionary）索引項(xiàng)（詞項(xiàng)）組成的集合倒排記錄表（PostingList）索引項(xiàng)在文檔集合中的位置組成的集合architecturecomputerdatabaseretrieval...D1,a1D1,a2D1,a3詞項(xiàng)詞典全體倒排記錄表Q=term1,term2,term3,...在實(shí)際應(yīng)用中，記錄表的組織形式和存儲(chǔ)的內(nèi)容是多種多樣的可以在一個(gè)文件內(nèi)部建立倒排文檔文本倒排文檔12345678910111213141516這是一本關(guān)于信息檢索的教材。介紹了檢索的基本技術(shù)。…技術(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個(gè)詞在記錄表中存儲(chǔ)關(guān)鍵詞所在的文檔編號(hào)段落編號(hào)句子編號(hào)詞編號(hào)所在的特殊單元（如標(biāo)題、小標(biāo)題）保存位置序號(hào)的目的：支持上下文條件查詢短語查詢例如：搜索“StanfordUniversity”TheinventorStanfordOvshinskyneverwenttouniversity.近鄰查詢“database”和“systems”之間不能間隔超過3個(gè)詞“database”和“architecture”在同一個(gè)句子（段落）里databaseD1,2,97,104D3,43systemD1,5D3,44“database”在D1中出現(xiàn)的詞序號(hào)在記錄表中存儲(chǔ)指針在記錄表中存儲(chǔ)統(tǒng)計(jì)信息頻率權(quán)重databasefilesystems...D345,10D348,20D350,1D123,82D128,8D345,12在D345中，“systems”

比“database”重要1.2倍總結(jié)——記錄表中的內(nèi)容位置信息形式上：序號(hào)或指針內(nèi)容上：文檔、段落、句子、詞附加信息特殊位置信息：所在單元（標(biāo)題、小標(biāo)題）統(tǒng)計(jì)信息同義詞擴(kuò)展詞匯表同義詞對(duì)于提高檢索的召回率很有意義同義詞可以通過指針指向同一個(gè)記錄表...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)行匹配時(shí)價(jià)值并不大，需要徹底從詞匯表中去除。這些詞稱為停用詞（stopword）預(yù)處理對(duì)倒排索引的影響例：Reuters-RCV1語料規(guī)模：1GB文本數(shù)據(jù)內(nèi)容：1996年8月20日到1997年8月19日一年間的路透社新聞180對(duì)Reuters-RCV1進(jìn)行預(yù)處理前后詞項(xiàng)、無位置信息倒排記錄及詞條的數(shù)目4.1.3倒排文檔的建立DocidTermpaperreportnovelnovel……1111…reporthuman……22…h(huán)umannovelnovelpaperreportreport……211112…排序歸并human2,1novel1,2paper1,1report1,12,11112在此記錄文檔頻率在此記錄詞項(xiàng)頻率基于排序的索引構(gòu)建方法對(duì)于小規(guī)模文檔集來說，上述過程均可在內(nèi)存中完成在大規(guī)模文檔條件下需要引入二級(jí)存儲(chǔ)介質(zhì)時(shí)的索引方法基于塊排序的索引方法分布式索引構(gòu)建方法為使索引構(gòu)建過程效率更高，將詞項(xiàng)用其ID來代替，每個(gè)詞項(xiàng)的ID是唯一的序列編號(hào)①基于塊排序的索引方法BSBI(blockedsort-basedindexing)第1步，將文檔集分割成幾個(gè)大小相等的部分；第2步，將每個(gè)部分的詞項(xiàng)ID—文檔ID對(duì)排序；第3步，將中間產(chǎn)生的臨時(shí)排序結(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)合并時(shí)，同時(shí)打開所有塊對(duì)應(yīng)的文件，內(nèi)存中維護(hù)為n個(gè)塊準(zhǔn)備的讀緩沖區(qū)和一個(gè)為最終合并索引準(zhǔn)備的寫緩沖區(qū)每次迭代中，利用優(yōu)先級(jí)隊(duì)列或者類似的數(shù)據(jù)結(jié)構(gòu)選擇最小的未處理詞項(xiàng)ID進(jìn)行處理。讀入該詞項(xiàng)的各個(gè)倒排記錄表并合并，合并結(jié)果寫回磁盤中②內(nèi)存式單遍掃描索引構(gòu)建方法SPIMI(single-passin-memoryindexing)SPIMI使用詞項(xiàng)而不是其ID，它將每個(gè)塊的詞典寫入磁盤，對(duì)于下一個(gè)塊則重新采用新的詞典只要硬盤空間足夠大，就能夠索引任何大小的文檔集性能分析優(yōu)點(diǎn)：由于不需要排序操作，因此處理的速度更快由于保留了倒排記錄表對(duì)詞項(xiàng)的歸屬關(guān)系，因此能夠節(jié)省內(nèi)存，詞項(xiàng)的ID也不需要保存這樣，每次單獨(dú)的SPIMI-Invert調(diào)用能夠夠處理的塊大小可以非常大，整個(gè)倒排索引的構(gòu)建過程也因此會(huì)非常高效。缺點(diǎn)每次當(dāng)空間放滿的時(shí)候，就會(huì)申請(qǐng)加倍的空間。這意味著一些空間被浪費(fèi)正好抵消了不用保存詞項(xiàng)ID所省下的空間?？傮w來說，SPIMI所需的內(nèi)存空間仍然比BSBI少③

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

AND

b

AND

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

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

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

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

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

簇剪枝方法之變形

b1

=b2=1時(shí)是原始簇剪枝方法增加b1

和b2

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

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

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

p=random();

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

y=pmodF；

//

映射到0和F-1之間

if(S[y]==0)

//確保m位置1

{S[y]=1；

j++；

}

}4)結(jié)束，返回Sblocksignatures塊的簽名Block1Block2WordsWordsignaturesfree001000110010text000010101001information000000011110retrieval101000100001101000111111001010111011freetextinformationretrieval文本串:假設(shè)一個(gè)塊包含兩個(gè)連續(xù)的詞塊的簽名是通過塊中所有詞的簽名按位進(jìn)行“或”操作得到簽名文件按順序存放塊簽名的文件簽名文件指針文件文檔N塊Fbits0010101110111010001111114.3.2簽名文件的使用和維護(hù)對(duì)單個(gè)詞的查詢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ù)對(duì)單個(gè)詞的查詢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ù)對(duì)單個(gè)詞的查詢q進(jìn)行檢索Step1：使用相同的散列算法生成q的簽名sqStep2：將sq與所有文本塊的簽名si進(jìn)行匹配Step3：對(duì)所有匹配上的文本塊執(zhí)行字符串匹配，確定其是否真正含有要查找的單詞簽名文件的設(shè)計(jì)簽名文件的性能指標(biāo)存儲(chǔ)開銷M誤檢率F一個(gè)文本塊據(jù)其簽名看包含某個(gè)關(guān)鍵詞，但事實(shí)上并不包含該關(guān)鍵詞的概率需要確定的參數(shù)塊的大小一般將一個(gè)文本看作是一塊Signature的長度經(jīng)驗(yàn)表明，取文本平均長度的30%~40%為宜每個(gè)詞的Signature中多少位置1簽名文件應(yīng)用：作為過濾器排除不包含查詢關(guān)鍵詞的文檔=過濾出的文本匹配的文本QuerySignature文件文檔集合Query

signature4.3.3簽名文件的性能分析優(yōu)點(diǎn)組織簡單，容易生成，維護(hù)費(fèi)用較低缺點(diǎn)和倒排文檔相比，搜索速度較慢檢索的時(shí)間復(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模板向右移動(dòng)算法描述將模式P=p1p2…pm

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

12345678文本

abdadefg模式

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

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

則可以直接移動(dòng)

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

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

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

的時(shí)間復(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);向右移動(dòng)

m=5

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

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

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

D1,移動(dòng)一個(gè)字符abcabdacababcabdacab僅基于D2,移動(dòng)5個(gè)字符S:babcbadcabcaabcaP:abcabdacab根據(jù)模式中是否還包含已經(jīng)匹配上的子模式”cab”來確定模板移動(dòng)的距離如何計(jì)算Δ2？ijD2Shift的實(shí)現(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