第五章文本索引和搜索_第1頁
第五章文本索引和搜索_第2頁
第五章文本索引和搜索_第3頁
第五章文本索引和搜索_第4頁
第五章文本索引和搜索_第5頁
已閱讀5頁,還剩83頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

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

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論