第五章文本索引和搜索

1、第五章:文本索引和搜索任飛亮東北大學自然語言處理實驗室2010 大綱n索引和搜索的概念n倒排文件索引n后綴數(shù)組索引n簽名文件索引n文本搜索技術大綱n索引和搜索的概念索引和搜索的概念n倒排文件索引n后綴數(shù)組索引n簽名文件索引n文本搜索技術應用索引的例子n檢索的目的是為了在一大堆的信息中發(fā)現(xiàn)自己感興趣的信息;n但是,當有了一大堆資料之后,并不能立即開始搜索.n為什么?圖書館實例在檢索前必須建立索引在檢索前必須建立索引!索引的定義n所謂建立索引,是指將待搜索的信息進行一定的分析分析,并將分析的結果按照一定的組織一定的組織方式存儲方式存儲起來,通常是存儲在文件中.n存儲了分析結果的文件的集合就是所謂的

2、索引索引.n準確定義:索引索引（Index）是一種數(shù)據(jù)結構數(shù)據(jù)結構，其將關鍵詞與包含該關鍵詞的文檔（或關鍵詞在文檔中的位置）建立了一種映射關系，以加快檢索的速度。文本搜索的概念n不使用任何索引技術，而快速的在給定文本或文本集合中查找是否出現(xiàn)某一關鍵詞，這種技術通常被稱為單模式匹配單模式匹配n應用領域n信息過濾、檢索結果后處理等n常用算法nBFnKMPnBM大綱n索引和搜索的概念n倒排文件索引倒排文件索引n后綴數(shù)組索引n簽名文件索引n文本搜索技術倒排索引主要內容n倒排索引簡介n倒排文件的使用n倒排文件的建立n倒排文件的維護n倒排文件的壓縮n倒排文件的性能分析n詞匯表的存取倒排索引主要內容n倒排索

3、引簡介倒排索引簡介n倒排文件的使用n倒排文件的建立n倒排文件的維護n倒排文件的壓縮n倒排文件的性能分析n詞匯表的存取倒排文件簡介 n倒排文件 (Inverted File)n也稱倒排索引，索引對象是文檔或文檔集合中的單詞單詞等，用來存儲這些單詞在一個文檔或者一組文檔中的存儲位置存儲位置，是對文檔或文檔集合的一種最常用的索引機制n倒如:有些書往往在最后提供的索引(單詞頁碼列表表)就可以看成是一種倒排索引.即通過一些關鍵詞,在全書中檢索出與之相關的部分;n這種思想也被應用于數(shù)據(jù)庫技術中,即對數(shù)據(jù)庫中需要經(jīng)常進行檢索的域建立索引結構,從而實現(xiàn)快速查詢.在關系數(shù)據(jù)庫上建索引n如上圖所示,對”姓名”字段

4、使用便于查找的數(shù)據(jù)結構(如排序數(shù)組、B樹或散列等)建立索引，當查詢某個名字時，就不需要從頭至尾遍歷整個字段，而可以快速找到該姓名，從而查找出與其對應的信息。地址姓名姓名索引查詢式:姓名 = “張三”張三哈爾濱工業(yè)大學張三倒排文件組成n詞匯表(vocabulary)+記錄表(posting list)n詞匯表n文檔或文檔集合中所包含的所有不同單詞不同單詞的集合n占用的空間V=cn，c是常數(shù)，n是文檔集合的大小，是一個0到1之間的常數(shù)，一般在0.4到0.6之間 n記錄表n對于詞匯表中的每一個單詞在文檔中出現(xiàn)的位置位置或者其出現(xiàn)的文文檔編號檔編號構成的列表n占用的空間P=cn，其中c是常數(shù)，隨著記錄

5、表中存儲的信息豐富程度而變化 n記錄表既可以存儲文本中單詞的編號位置，也可以指向單詞首字母的字符位置，還可以是其所在的文檔編號，即可以根據(jù)不同的應用需求，使用不同的尋址粒度(addressing granularity)對單文檔的倒排文件 對文檔集合的倒排文件倒排索引主要內容n倒排索引簡介n倒排文件的使用倒排文件的使用n倒排文件的建立n倒排文件的維護n倒排文件的壓縮n倒排文件的性能分析n詞匯表的存取倒排文件的使用 n三個步驟n詞匯表檢索n將出現(xiàn)在查詢（Query）中的單詞分離出來，并在詞匯表中進行檢索。n記錄表檢索n檢索出所有找到的單詞對應的記錄表。n記錄表操作n對檢索出的記錄表進行后處理，以

6、實現(xiàn)短語查詢、相鄰查詢或者布爾查詢。詞匯表檢索n規(guī)模相對較小的獨立文件，全部調入內存n常用數(shù)據(jù)結構n樹狀結構，如：B樹和Trie樹n前綴查詢和范圍查詢n散列n檢索速度快，但是不支持前綴查詢和范圍查詢等n需要根據(jù)實際需求情況，決定采用什么樣的數(shù)據(jù)結構。記錄表操作n如果查詢中僅包含一個單詞，則在詞匯表中找到該單詞，并取出其對應的記錄表即完成了檢索操作n如果查詢中包含多個單詞，則需將各個單詞檢索出的記錄表進行合并n同步遍歷記錄表，實現(xiàn)合并過程倒排索引主要內容n倒排索引簡介n倒排文件的使用n倒排文件的建立倒排文件的建立n倒排文件的維護n倒排文件的壓縮n倒排文件的性能分析n詞匯表的存取倒排文件的建立 n

7、建立倒排文件的最關鍵問題最關鍵問題是由于需要索引的文檔數(shù)量過大，有可能導致不能在內存中存儲整個倒排文件。n根據(jù)索引文檔的大小，介紹三種倒排文件的建立方法。n基于內存的方法 n基于排序的方法 n基于歸并的方法 倒排文件的建立 n建立倒排文件的最關鍵問題最關鍵問題是由于需要索引的文檔數(shù)量過大，有可能導致不能在內存中存儲整個倒排文件。n根據(jù)索引文檔的大小，介紹三種倒排文件的建立方法。n基于內存的方法基于內存的方法 n基于排序的方法 n基于歸并的方法 基于內存的方法輸入：輸入：文檔集合輸出：輸出：基于文檔集合的倒排文件算法：算法：(1) 初始遍歷文檔集合。對于每一個單詞w，統(tǒng)計包含該單詞的文檔數(shù)fw；

8、(2) 在內存中建立長度為w詞表fw的數(shù)組，并且對于每一個單詞w，生成指向其記錄表塊首的指針pw。(3) 第二次遍歷文檔集合，對每個文檔d中的每一個單詞w，在pw中追加文檔d的序號，pw后移?；趦却娴姆椒?n核心思想是經(jīng)過兩次遍歷n第一次遍歷首先獲得每個單詞出現(xiàn)的文檔的個數(shù)，從而獲得所需內存的大??；n第二次遍歷充分利用內存的隨機訪問功能，快速更新每個單詞的記錄表；n優(yōu)點：n只要內存比最終生成的倒排文件（包括詞匯表和記錄表）大一些，該算法是可行的；n可以很方便地擴展該方法，在記錄表中增加更多的信息，如單詞的位置等；倒排文件的建立 n建立倒排文件的最關鍵問題是由于需要索引的文檔數(shù)量過大，有可能導

9、致不能在內存中存儲整個倒排文件。n根據(jù)索引文檔的大小，介紹三種倒排文件的建立方法。n基于內存的方法 n基于排序的方法基于排序的方法 n基于歸并的方法 基于排序的方法 n基于內存方法的不足n從磁盤讀取和分析文檔的操作需要花費較多時間，如果反復調用，必將成為倒排文件建立的一個瓶頸n解決方法n方法一：存儲分析好的文本。n潛在的代價是將會帶來大量的磁盤開銷，有時甚至要花費比第二步更多的時間。n方法二：基于排序的方法；n該方法將用二元組構成數(shù)組或文件，從由原來的按照文檔編號排序，變?yōu)橛蓡卧~排序，然后產(chǎn)生最終的倒排文件。 基于排序的方法通過使用多路歸并算法，排序過程可以在硬盤上完成另外一個好處是不必在內存

10、中存儲整個詞表，從而大大增加了在單臺機器上索引的數(shù)據(jù)量倒排文件的建立 n建立倒排文件的最關鍵問題是由于需要索引的文檔數(shù)量過大，有可能導致不能在內存中存儲整個倒排文件。n根據(jù)索引文檔的大小，介紹三種倒排文件的建立方法。n基于內存的方法 n基于排序的方法 n基于歸并的方法基于歸并的方法 基于歸并的方法 n提出背景n隨著文檔集合的增加，將所有詞匯表置于內存中的花費也越來越大n必須一部分一部分地生成索引，其中每一部分索引都可使用上面的方法生成；n最后，將各個子索引進行歸并，形成最終的索引?；跉w并的方法輸入：輸入：文檔集合輸出：輸出：基于文檔集合的倒排文件算法：算法：(1) 初始生成一個基于內存的臨時

11、索引結構，其中詞匯表和記錄表均使用動態(tài)數(shù)據(jù)結構存儲，如動態(tài)數(shù)組，鏈表等。(2) 讀取一個文檔，并在其中出現(xiàn)的單詞的記錄表中，加入文檔編號。直到占用的內存大小超過一定的閾值。(3) 將生成的包括詞匯表和其記錄表的臨時索引結構轉存到磁盤，并清空內存。(4) 如果所有文檔處理完畢，則轉到(5)，否則轉到(1)。(5) 歸并以上生成的子索引，生成單一索引?；跉w并的方法 n優(yōu)點：n適用于各種大小的文檔集合，即使對于內存不大的機器也同樣有效和實用；n該方法僅需一次掃描和分析文檔，效率較高。倒排索引主要內容n倒排索引簡介n倒排文件的使用n倒排文件的建立n倒排文件的維護倒排文件的維護n倒排文件的壓縮n倒排文

12、件的性能分析n詞匯表的存取倒排文件的維護 n維護倒排文件通常需要三種維護操作n插入、刪除和更新文檔或文檔集合 n通常的更新操作需要較高的代價n例如，要在存儲了單詞位置信息的倒排文件中進行一篇文檔的更新，即使該文檔僅僅改動很小的部分，文檔中出現(xiàn)的大部分單詞的記錄表都需要做出改動。n原因：單詞的位置很可能發(fā)生變化，這就需要頻繁地讀取和修改記錄表，這種代價是相當高的。n因此，在維護倒排文件時，一般不進行更新操作，而是使用刪除+插入操作代替插入操作的維護 n在已有的倒排文件中插入一篇文檔相當于在該文檔包含的單詞所對應的記錄表后面插入此文檔的編號或者每個單詞的位置信息n對于一般的文當，這種插入需要調用獲

13、取記錄表并在其末尾添加該文檔或者單詞位置信息的操作多次，以目前的硬件水平，這種操作需要較長的時間。 n如果使用批量插入，效率將大大的提高 n類似歸并操作,首先為待插入的多個文檔建立臨時內存索引結構,然后一次性地將此索引結構插入到原索引中;n在生成批的時候新插入的文檔不能馬上被檢索，會造成索引內容滯后的問題，可以通過對臨時內存索引進行檢索解決n除使用批量插入方法外,還可以在新文檔中包含單詞被用戶檢索的時候進行該單詞詞表的更新,或者使用后臺進程在機器空閑的時候進行插入操作;n效率都不如批量插入效率高刪除操作 n文檔的刪除操作與插入操作類似,其瓶頸也是記錄表從磁盤讀取和寫回的過程;n也可使用批量刪除

14、的方法n為了保持刪除的及時性,需要維護一張刪除文件列表n在檢索時如果結果包含列表中的文件，則將其從結果中刪除n總之,在維護倒排文件的時候,無率是插入操作還是刪除操作,為了提高效率,必須想辦法減少讀寫磁盤的操作,即提高磁盤I/O的效率倒排索引主要內容n倒排索引簡介n倒排文件的使用n倒排文件的建立n倒排文件的維護n倒排文件的壓縮倒排文件的壓縮n倒排文件的性能分析n詞匯表的存取倒排文件的壓縮 n優(yōu)點n減少內存和磁盤的空間占用n提高磁盤的吞吐量，提高索引維護和查找的效率n壓縮分類n有損壓縮n去停用詞、詞干提取等技術n使用這些技術會損失一些原文中的信息；n無損壓縮 n在壓縮倒排文件的同時，其原始信息完全

15、被保留，不會缺損。n分詞匯表詞匯表的壓縮和記錄表記錄表的壓縮詞匯表的壓縮 n在檢索的時候，需要經(jīng)常查詢詞匯表，在理想情況下，應將詞匯表始終置于內存之中。n實際情況：n隨著文檔數(shù)的增多，詞匯表也將逐漸增大；n存在一些對內存使用有限制的應用n必須對詞匯表進行壓縮；n壓縮常用方法：n使用一個長字符串連續(xù)存儲詞匯表n見下頁圖詞匯表的壓縮 n使用長字符串連續(xù)存儲單詞表 n這樣的存儲方式緊湊，且不會出現(xiàn)溢出問題；n通過該種簡單的壓縮方式，可以很容易地將詞匯表壓縮為原來大小的50%左右 記錄表的壓縮 n文檔和單詞的位置使用16位或32位整數(shù)表示n16位太小，32位太大，浪費空間n解決方法：僅記錄相鄰文檔編號

16、或詞位置之間的差異n用比較少的字節(jié)表示編號的相對變化databaseD345, 25, 34, 98, 120 D348, 37, 71, 85database345, 25, 9, 64, 223, 37, 34, 14Word positions記錄表的壓縮 (2)n整數(shù)的定長表示不是特別的節(jié)省空間n對于常用詞相對變化不多，使用16位編碼，浪費空間n對于非常用詞，有可能僅存在于少數(shù)的文檔之中，16位表示會溢出n解決方案：變長整數(shù)表示n基本原理n使用較少位數(shù)表示較小，出現(xiàn)次數(shù)較多的整數(shù)n使用較多位數(shù)表示較大，出現(xiàn)次數(shù)較少的整數(shù)倒排表壓縮總結n優(yōu)點：n1、降代了索引在內存和磁盤中占用的空間，經(jīng)

17、過適當?shù)膲嚎s，索引的大小可以降為原始文檔的25%左右；n2、由于索引被壓縮，提高了磁盤的傳輸效率，使得查詢的速度加快；n3、由于磁盤傳輸效率的提高，使得索引的構造和維護的效率也得到提高；n4、另外一個隱含的好處是，這樣提高了倒排文件的緩存能力；進而提高了檢索的速度倒排表壓縮總結n負面影響：n1、在搜索時必須花時間對壓縮的數(shù)據(jù)進行解碼;n2、在維護時,特別是進行刪除操作時,由于某些文檔被刪除,不得不對剩余的文檔編號進行重新編碼;n總體上：利大于弊倒排索引主要內容n倒排索引簡介n倒排文件的使用n倒排文件的建立n倒排文件的維護n倒排文件的壓縮n倒排文件的性能分析倒排文件的性能分析n詞匯表的存取倒排文

18、件性能分析 n可以證明,使用倒排文件,檢索查詢的開銷與文檔集合大小成次線性關系次線性關系,其時間復雜性nO(na)，其中0 a 1，與查詢有關,一般在0.40.8之間n在實際應用中,倒排文件的時間和空間復雜性接近O(n0.85), n在使用壓縮技術之后，在時間復雜性損失不多的條件下，空間的復雜性會進一步降低到原來的25%左右n-其它索引方法很難實現(xiàn)倒排索引主要內容n倒排索引簡介n倒排文件的使用n倒排文件的建立n倒排文件的維護n倒排文件的壓縮n倒排文件的性能分析n詞匯表的存取詞匯表的存取詞匯表的存取 n詞匯表的存取是實現(xiàn)倒排文件查詢的第一個步驟,需要非常高的存取效率n高效的詞匯表存取方法也被應用

19、于信息檢索的其他步驟或者其他信息技術應用領域n要實現(xiàn)高效的詞匯表搜索,往往需要設計特殊的數(shù)據(jù)結構數(shù)據(jù)結構n排序數(shù)組 n樹狀結構nB樹，Trie樹 n散列都是基于字符串比較的方法,需要事先將待查找的字符串排序1、不需要預先排序、檢索速度快2、很難處理前綴查找(如查找以“沈陽“開始的詞)、區(qū)域查找(如查找所有“技術”到“檢索”之間的單詞)3、要減少散列沖突，需要相對較大的存儲空間排序數(shù)組n最簡單的詞匯表搜索方法n是由一系列元素組成的數(shù)組，其中的元素一般包括三個域：關鍵詞、記錄表的大小以及指向其記錄表的指針n數(shù)組中的元素根據(jù)關鍵詞排序n可以采用二分查找的方法，在O(log(n) 的時間復雜性內，查找

20、給定的關鍵詞n缺點n維護代價較高，無論插入還是刪除，都需要移動較多的元素 n可能造成內存不足 引入樹狀結構引入樹狀結構!B樹 nB樹的定義：B樹是一種平衡的多叉樹，一棵m階的B樹滿足下列條件： 樹中每個節(jié)點至多有m個孩子； 除根節(jié)點和葉子節(jié)點外，其它每個節(jié)點至少有m/2個孩子； 若根節(jié)點不是葉子節(jié)點，則至少有2個孩子； 所有葉子節(jié)點都出現(xiàn)在同一層，葉子節(jié)點不包含任何關鍵字信息； 有k個孩子的非終端節(jié)點恰好包含有k-1個關鍵詞。 在B樹中，每個節(jié)點中的關鍵詞從小到大排列，并且當該結點的孩子是非葉子節(jié)點時，該k-1個關鍵詞正好是k個孩子包含的關鍵字的值域的劃分。B樹示例 nB樹中的一個包含n個關鍵

21、詞、n+1個指針的節(jié)點的一般形式為(P0,K1,P1, K2,P2,Kn,Pn)n其中，Ki為關鍵詞，K1K2Kn,Pi是指向包括Ki到Ki+1之間的關鍵詞的子樹的指針B樹操作n查找n在每個節(jié)點進行沿著指針查找節(jié)點和在節(jié)點內的關鍵詞中查找交叉的過程n從根結點開始，在節(jié)點包含的關鍵詞中查找給定的關鍵詞，找到則查找成功，否則確定給定關鍵詞可能在哪個子樹，重復上面的操作，直到查找成功或者指針為空為止 如何查找20？如何查找21？如何查找22？B樹操作n插入n在恰當?shù)娜~子節(jié)點中添加關鍵詞，如果該節(jié)點中關鍵詞超過m-1個，要把這個節(jié)點分裂為兩個，并把中間的一個關鍵詞拿出來插到節(jié)點的父節(jié)點里去。如果父節(jié)點

22、也是滿的，就需要再分裂，再往上插，以此類推，直到根節(jié)點如何插入22？如何插入38？B樹操作n刪除n刪除操作與插入操作類似，但要稍微復雜些。從一個節(jié)點中刪除關鍵詞時，需要重新安排一些節(jié)點，防止因刪除操作而導致樹的結構違反B樹的性質B樹的擴展：B+、B*樹等Trie樹 n又稱作前綴樹，其名字來源于英文詞reTrieval(檢索)n當關鍵詞的長度變化較大時，Trie樹是一種特別有效的查找數(shù)據(jù)結構；n另外，Trie樹還適合用于查找單詞前綴，如果找所有以”comput”開頭的詞，如”computing”、”computer”等nTrie樹的每一層分支不是靠整個單詞的值來確定，而是由單詞中的一個字符來確定

23、n例如存儲：information、retrieval、system、introduction的Trie樹nTrie樹包括兩種類型的節(jié)點：元素節(jié)點和分支節(jié)點。n元素節(jié)點包含整個單詞，在圖中用表示，分支節(jié)點用表示。n如要查找單詞”information”，則順次查找字母”i”、”n”和”f”，進入元素節(jié)點”information”，它與查詢單詞”information”相同，故查找成功；n如要查找”inference”，也會進入元素節(jié)點”information”，但在比較兩個單詞的時候會發(fā)現(xiàn)它們不同，故查找失敗。Patricia樹nTrie樹在最壞的情況下搜索的時間代價為O(l),其中l(wèi)是Tri

24、e樹的層數(shù);nTrie樹的改進n壓縮一元節(jié)點(即只有一個子節(jié)點的節(jié)點)，提高空間利用率nPatricia(Practical Algorithm To Retrieve Information Coded in Alphanumeric)樹Patricia樹n除了不含有一元節(jié)點外，Patricia樹與Trie樹的不同之處還在于其分支節(jié)點內包含待比較的字節(jié)編號。n如要查詢單詞”information”,Patricia樹只需查找第一個字母”i”，然后查找第3個字母”r”,即可進入元素節(jié)點”information”.與Trie樹查找相比,減少了一次對字母n的判斷n一般情況下，Patricia樹的性

25、能要優(yōu)于Trie樹大綱n索引和搜索的概念n倒排文件索引n后綴數(shù)組索引后綴數(shù)組索引n簽名文件索引n文本搜索技術后綴數(shù)組n在倒排文檔中，文本被看作是由單詞組成的序列限制了倒排文件的應用n情況1：詞組查詢在使用倒排文件查詢時就比較困難，因為不但需要記錄每個單詞在文檔中的位置，還要在合并時判斷其是否相鄰并構成詞組；n情況2：在某些應用中，如基因數(shù)據(jù)庫，不存在詞的概念。n解決方案：使用后綴數(shù)組后綴數(shù)組n在后綴數(shù)組中，可以將文本看作是一個長的字符串，文本中的每個位置都被認為是文本的一個后綴，即一個從當前文本位置到文本末尾的字符串。n索引的位置可以是每個字符的位置、單詞的位置或者漢字的位置等。n后綴數(shù)組后綴

26、數(shù)組(suffix array)就是對文本中的所有后綴按照詞典序存放每個后綴對應的起始位置的一個列表原始文本，按字的順序位置索引文本中的部分后綴，按位置索引相同的部分后綴，按字典序索引后綴數(shù)組的構造 024681012141618202224262830323436384042444648這是一本關于信息檢索的教材。介紹了檢索的基本技術。021216223444這是是一信息檢索教材檢索技術441634222120技術檢索檢索教材是一信息這是首先截取每個后綴的前n個字節(jié)，作為類似倒排文件中的“詞匯表”(此處n=4)后綴數(shù)組的使用 n在使用后綴數(shù)組進行檢索的時候，將每個查詢同樣截取前n個字節(jié)，并于

27、索引中進行查找n如果沒有找到，則表明不包含所需查詢n如果查找成功，則需要在相應的文本位置上，進行進一步的字符串比較，以確定文本中是否包含查詢 n實例n查找“信息檢索”，首先截取4個字節(jié)“信息”，并于后綴數(shù)組中查找到了位置12，接著在原文中的12號位置，找到“信息檢索”字符串，則查找成功；n查找“信息過濾”，則原文中的12號位置不能找到“信息過濾”字符串，則查找失敗；n更一般的例子，如果輸入的查詢?yōu)椤皵?shù)據(jù)庫”，在索引結構中不能找到“數(shù)據(jù)”，則查找直接失敗返回；441634222120技術檢索檢索教材是一信息這是后綴數(shù)組的分析 n對于需要大數(shù)據(jù)量的檢索問題，后綴數(shù)組并不適用 n因為構造出的后綴數(shù)組

28、需要占用大量的空間，通常是原文本的1.7倍 n和倒排文檔相比，后綴數(shù)組里面儲存了較多的重復信息 n同時，由于每個后綴位置的編號不能存儲相對位置的變化，所以很難被壓縮，需要較多的存儲空間；n后綴數(shù)組的另外一個缺點是不容易對檢索結果進行排序，因為計算查詢單詞的詞頻比較耗時；n實際上實際上,后綴數(shù)組的大部分功能可以通過倒排文檔來實現(xiàn)后綴數(shù)組的大部分功能可以通過倒排文檔來實現(xiàn)!n例如可以倒排索引文本中的二字串或者三字串，從而提高召回率 大綱n索引和搜索的概念n倒排文件索引n后綴數(shù)組索引n簽名文件索引簽名文件索引n文本搜索技術簽名文件 n簽名文件簽名文件(signature file)是基于散列技術的面

29、向單詞的索引結構n索引占用的空間大約為原始文檔集的3040%n在檢索時需要順序比較，適用于小規(guī)模的文本n在大多數(shù)應用中，其性能不如倒排文件詞的Signatures詞“簽名”單詞這 是 一本 關于 信息 檢索 的 教材 。 介紹 了 檢索 的 基本 技術 。文本技術教材檢索信息001 000 110 010000 010 101 001000 000 011 110101 000 100 001n一個單詞的“簽名”是一個位向量位向量,由F位組成,其中有m位置1;n如下圖給出了一段文本，以及文本中部分單詞的“簽名”示例，其中F=12,m=4;詞Signature的生成算法輸入：詞W，參數(shù)F和m輸出

30、：詞W的F位“簽名”S算法：(1) 將W轉換為ASCII值，然后轉換為32位整數(shù)i例如：free = 66726565 (hex)(2) 初始化：a) S的F位全置0;b) srandom(i);/初始化隨機種子c) j = 0;(3) while (j m。在文本T中找出模式P出現(xiàn)的位置。n三種常用的精確匹配算法 nBF算法nKMP算法nBM算法文本搜索技術 n精確的字符串匹配問題可以如下描述:n結定一個長度為m的模式P(p1p2pm)，以及一個長度為n的長文本T(t1t2tn)，其中nm。在文本T中找出模式P出現(xiàn)的位置。n三種常用的精確匹配算法 nBF算法算法nKMP算法nBM算法BF算法

31、算法nBF算法是Brute-Force(蠻力)算法的簡稱n是一種簡單、直接、容易實現(xiàn)的字符串匹配算法n基本思想：n將模式P和文本T中的m個字符的子串tktk+1tk+m-1進行匹配，1k m) return 匹配位置j;else return “匹配不成功”;BF算法分析算法分析n在BF算法中，可以更改循環(huán)條件為jn-m+1,使得循環(huán)可以更早地終止；n因為存在O(n)個文本位置，在最壞的情況下，驗證每個位置需要花費的時間為O(m),所以BF算法的最長時間為O(mn)nBF算法的平均時間為O(n)，因為對于一個隨機文本，一般在進行O(l)次比較之后，就可以發(fā)現(xiàn)錯誤的匹配。nBF算法無需進行任何形

32、式的預處理，實現(xiàn)簡單，被大多數(shù)程序設計語言所采用n如C語言中的字符串查找函數(shù)strstr()使用的就是BF算法nBF算法的時間復雜性與其他算法比較還是比較高的，在對效率要求較高的系統(tǒng)中，應該避免大量使用文本搜索技術 n精確的字符串匹配問題可以如下描述:n結定一個長度為m的模式P(p1p2pm)，以及一個長度為n的長文本T(t1t2tn)，其中nm。在文本T中找出模式P出現(xiàn)的位置。n三種常用的精確匹配算法 nBF算法nKMP算法算法nBM算法KMP算法 nD.E.Knuth、J.H.Morris和V.R.Pratt同時發(fā)現(xiàn)的改進的模式匹配算法n該算法是第一個可以在O(n+m)的時間內完成串模式匹

33、配的算法，但平均來說，它的效率并不比BF算法快很多。n基本思想n每當匹配過程中出現(xiàn)字符串比較不等時，不像BF算法那樣僅將模式向右“滑動”一個位置，而是利用已經(jīng)得到的“部分匹配”結果將模式向右“滑動”盡可能遠的一段距離后，繼續(xù)進行比較。n可以避免對那些能夠推斷出不匹配的位置進行徒勞的操作KMP算法 nKMP算法原則n從匹配成功匹配成功的子模式子模式中找出“能夠相互匹配的最長的前綴最長的前綴和后綴后綴”n在使用KMP算法進行模式匹配時，需要根據(jù)模式事先構造一個shift跳轉表，用來決定在某個位置匹配失敗時應該移動多少個字符nShift表的構造方法n如果當前不匹配的位置為j,重復字串的長度為k,則跳過的字符個數(shù)為j-k-1KMP算法的shift表n模式P=“abcabcacab”的shift表如果當前不匹配的位置為j,重復字串的長度為k,則跳過的字符個數(shù)為j-k-1nKMP算法的shift表可以在O(m)的時間復雜度下，通過對關鍵詞的分析而獲得,m是模式的長度 nKMP算法花費O(m+n)的時間來解決模式匹配問題文本搜索技術 n精確的字符串匹配問題可以如下描述:n結定一個長度為m的模式P(p1p2pm)，以及一個長度為n的長文本T(t1t2tn)，其中nm。在文本T中找出模式P出現(xiàn)的位置。n三種常用的精確匹配算法 nBF算法nKMP算法nBM算法算法BM算法 nB