第五章 文本索引和搜索

1、第五章:文本索引和搜索任飛亮東北大學(xué)自然語(yǔ)言處理實(shí)驗(yàn)室2010 大綱n索引和搜索的概念n倒排文件索引n后綴數(shù)組索引n簽名文件索引n文本搜索技術(shù)大綱n索引和搜索的概念索引和搜索的概念n倒排文件索引n后綴數(shù)組索引n簽名文件索引n文本搜索技術(shù)應(yīng)用索引的例子n檢索的目的是為了在一大堆的信息中發(fā)現(xiàn)自己感興趣的信息;n但是,當(dāng)有了一大堆資料之后,并不能立即開(kāi)始搜索.n為什么?圖書(shū)館實(shí)例在檢索前必須建立索引在檢索前必須建立索引!索引的定義n所謂建立索引,是指將待搜索的信息進(jìn)行一定的分析分析,并將分析的結(jié)果按照一定的組織一定的組織方式存儲(chǔ)方式存儲(chǔ)起來(lái),通常是存儲(chǔ)在文件中.n存儲(chǔ)了分析結(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信息過(guò)濾、檢索結(jié)果后處理等n常用算法nBFnKMPnBM大綱n索引和搜索的概念n倒排文件索引倒排文件索引n后綴數(shù)組索引n簽名文件索引n文本搜索技術(shù)倒排索引主要內(nèi)容n倒排索引簡(jiǎn)介n倒排文件的使用n倒排文件的建立n倒排文件的維護(hù)n倒排文件的壓縮n倒排文件的性能分析n詞匯表的存取倒排索引主要內(nèi)容n倒排索

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

29、單詞的索引結(jié)構(gòu)n索引占用的空間大約為原始文檔集的3040%n在檢索時(shí)需要順序比較，適用于小規(guī)模的文本n在大多數(shù)應(yīng)用中，其性能不如倒排文件詞的Signatures詞“簽名”單詞這 是 一本 關(guān)于 信息 檢索 的 教材 。 介紹 了 檢索 的 基本 技術(shù) 。文本技術(shù)教材檢索信息001 000 110 010000 010 101 001000 000 011 110101 000 100 001n一個(gè)單詞的“簽名”是一個(gè)位向量位向量,由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);/初始化隨機(jī)種子c) j = 0;(3) while (j m。在文本T中找出模式P出現(xiàn)的位置。n三種常用的精確匹配算法 nBF算法nKMP算法nBM算法文本搜索技術(shù) n精確的字符串匹配問(wèn)題可以如下描述:n結(jié)定一個(gè)長(zhǎng)度為m的模式P(p1p2pm)，以及一個(gè)長(zhǎng)度為n的長(zhǎng)文本T(t1t2tn)，其中nm。在文本T中找出模式P出現(xiàn)的位置。n三種常用的精確匹配算法 nBF算法算法nKMP算法nBM算法BF算法算

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

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

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