信息檢索

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

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

Tokenizing）詞條歸一化(TokenNormalization)去除停用詞某些情況下，一些常見詞在文檔和用戶需求進行匹配時價值并不大，需要徹底從詞匯表中去除。這些詞稱為停用詞（stopword）預處理對倒排索引的影響例：Reuters-RCV1語料規模：1GB文本數據內容：1996年8月20日到1997年8月19日一年間的路透社新聞180對Reuters-RCV1進行預處理前后詞項、無位置信息倒排記錄及詞條的數目4.1.3倒排文檔的建立DocidTermpaperreportnovelnovel……1111…reporthuman……22…humannovelnovelpaperreportreport……211112…排序歸并human2,1novel1,2paper1,1report1,12,11112在此記錄文檔頻率在此記錄詞項頻率基于排序的索引構建方法對于小規模文檔集來說，上述過程均可在內存中完成在大規模文檔條件下需要引入二級存儲介質時的索引方法基于塊排序的索引方法分布式索引構建方法為使索引構建過程效率更高，將詞項用其ID來代替，每個詞項的ID是唯一的序列編號①基于塊排序的索引方法BSBI(blockedsort-basedindexing)第1步，將文檔集分割成幾個大小相等的部分；第2步，將每個部分的詞項ID—文檔ID對排序；第3步，將中間產生的臨時排序結果存放到磁盤中；第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)合并時，同時打開所有塊對應的文件，內存中維護為n個塊準備的讀緩沖區和一個為最終合并索引準備的寫緩沖區每次迭代中，利用優先級隊列或者類似的數據結構選擇最小的未處理詞項ID進行處理。讀入該詞項的各個倒排記錄表并合并，合并結果寫回磁盤中②內存式單遍掃描索引構建方法SPIMI(single-passin-memoryindexing)SPIMI使用詞項而不是其ID，它將每個塊的詞典寫入磁盤，對于下一個塊則重新采用新的詞典只要硬盤空間足夠大，就能夠索引任何大小的文檔集性能分析優點：由于不需要排序操作，因此處理的速度更快由于保留了倒排記錄表對詞項的歸屬關系，因此能夠節省內存，詞項的ID也不需要保存這樣，每次單獨的SPIMI-Invert調用能夠夠處理的塊大小可以非常大，整個倒排索引的構建過程也因此會非常高效。缺點每次當空間放滿的時候，就會申請加倍的空間。這意味著一些空間被浪費正好抵消了不用保存詞項ID所省下的空間。總體來說，SPIMI所需的內存空間仍然比BSBI少③

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

AND

b

AND

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

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

wij得分最高的r個文檔構成tj

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

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

簇剪枝方法之變形

b1

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

和b2

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

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

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

p=random();

//生成一個隨機整數

y=pmodF；

//

映射到0和F-1之間

if(S[y]==0)

//確保m位置1

{S[y]=1；

j++；

}

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

=sq

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

001010111011block2

101000111111blocksignature如果sq與si

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

000

110

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

signature4.3.3簽名文件的性能分析優點組織簡單，容易生成，維護費用較低缺點和倒排文檔相比，搜索速度較慢檢索的時間復雜性與原始文檔集成線性關系去除Falsedrops需要昂貴的開銷很難支持排序操作很難使用其它查詢函數，例如同義詞、通配符、分離條件、鄰近操作提綱4.1倒排索引4.2后綴數組4.3簽名文件4.4全文掃描4.4全文掃描全文掃描不使用任何索引技術而快速在給定文本或文本集合中查找某一關鍵詞的技術。這種技術通常被稱為單模式匹配某些應用中，建立索引的方法并不適用簽名文件的候選塊確認過程文本過濾搜索引擎的結果后處理全文掃描技術也具有很廣闊的應用場合模式匹配問題的定義輸入模式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; }此循環可以更早地終止:j

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

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

12345678文本

abdadefg模式

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

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

則可以直接移動

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

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

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

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

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

m=5

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

在p中出現;移動P使之相互對齊，D1=2如果有多個E，應該和哪個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與其在文本中相對應的字符tm進行比較如果比較的結果是不匹配第一種情況，tm根本沒有在模式中的任何一個位置出現，那么就可以放心大膽地將模式向后移動m個字符如果tm是模式中的第r個字符（指最后一次出現的位置），那么就可以將模式向后移動m-r個字符如果比較的結果是匹配對模式中右數第2個字符pm-1與其在文本中相對應的字符tm-1進行比較。此過程往復循環。BM算法--D2Shift僅基于

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

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