第五章文本索引和搜索

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

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

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

4、使用便于查找的數(shù)據(jù)結(jié)構(gòu)(如排序數(shù)組、B樹或散列等)建立索引，當(dāng)查詢某個名字時，就不需要從頭至尾遍歷整個字段，而可以快速找到該姓名，從而查找出與其對應(yīng)的信息。地址姓名姓名索引查詢式:姓名 = “張三”張三哈爾濱工業(yè)大學(xué)張三倒排文件組成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)的文文檔編號檔編號構(gòu)成的列表n占用的空間P=cn，其中c是常數(shù)，隨著記錄

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

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

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

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

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

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

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

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

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

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

15、被保留，不會缺損。n分詞匯表詞匯表的壓縮和記錄表記錄表的壓縮詞匯表的壓縮 n在檢索的時候，需要經(jīng)常查詢詞匯表，在理想情況下，應(yīng)將詞匯表始終置于內(nèi)存之中。n實際情況：n隨著文檔數(shù)的增多，詞匯表也將逐漸增大；n存在一些對內(nèi)存使用有限制的應(yīng)用n必須對詞匯表進(jì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ù)倒排表壓縮總結(jié)n優(yōu)點：n1、降代了索引在內(nèi)存和磁盤中占用的空間，經(jīng)

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

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

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

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

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

22、也是滿的，就需要再分裂，再往上插，以此類推，直到根節(jié)點如何插入22？如何插入38？B樹操作n刪除n刪除操作與插入操作類似，但要稍微復(fù)雜些。從一個節(jié)點中刪除關(guān)鍵詞時，需要重新安排一些節(jié)點，防止因刪除操作而導(dǎo)致樹的結(jié)構(gòu)違反B樹的性質(zhì)B樹的擴(kuò)展：B+、B*樹等Trie樹 n又稱作前綴樹，其名字來源于英文詞reTrieval(檢索)n當(dāng)關(guān)鍵詞的長度變化較大時，Trie樹是一種特別有效的查找數(shù)據(jù)結(jié)構(gòu)；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”，進(jìn)入元素節(jié)點”information”，它與查詢單詞”information”相同，故查找成功；n如要查找”inference”，也會進(jìn)入元素節(jié)點”information”，但在比較兩個單詞的時候會發(fā)現(xiàn)它們不同，故查找失敗。Patricia樹nTrie樹在最壞的情況下搜索的時間代價為O(l),其中l(wèi)是Tri

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

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

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

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

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

29、向單詞的索引結(jié)構(gòu)n索引占用的空間大約為原始文檔集的3040%n在檢索時需要順序比較，適用于小規(guī)模的文本n在大多數(shù)應(yīng)用中，其性能不如倒排文件詞的Signatures詞“簽名”單詞這 是 一本 關(guān)于 信息 檢索 的 教材 。 介紹 了 檢索 的 基本 技術(shù) 。文本技術(shù)教材檢索信息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轉(zhuǎn)換為ASCII值，然后轉(zhuǎn)換為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算法文本搜索技術(shù) n精確的字符串匹配問題可以如下描述:n結(jié)定一個長度為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進(jìn)行匹配，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)，因為對于一個隨機文本，一般在進(jìn)行O(l)次比較之后，就可以發(fā)現(xiàn)錯誤的匹配。nBF算法無需進(jìn)行任何形

32、式的預(yù)處理，實現(xiàn)簡單，被大多數(shù)程序設(shè)計語言所采用n如C語言中的字符串查找函數(shù)strstr()使用的就是BF算法nBF算法的時間復(fù)雜性與其他算法比較還是比較高的，在對效率要求較高的系統(tǒng)中，應(yīng)該避免大量使用文本搜索技術(shù) n精確的字符串匹配問題可以如下描述:n結(jié)定一個長度為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)的改進(jìn)的模式匹配算法n該算法是第一個可以在O(n+m)的時間內(nèi)完成串模式匹

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