第五章文本索引和搜索

1、信息組織、存儲(chǔ)與檢索信息組織、存儲(chǔ)與檢索第五章第五章 文本索引和檢索文本索引和檢索信息組織、存儲(chǔ)與檢索信息組織、存儲(chǔ)與檢索信息檢索系統(tǒng)工作流程信息檢索系統(tǒng)工作流程用戶界面用戶界面文本操作文本操作查詢操作查詢操作標(biāo)引標(biāo)引檢索檢索排序排序索引索引數(shù)據(jù)庫管理數(shù)據(jù)庫管理模塊模塊文本數(shù)據(jù)庫文本數(shù)據(jù)庫用戶需求用戶需求邏輯視圖邏輯視圖邏輯視圖邏輯視圖用用戶戶反反饋饋查詢查詢檢出文檔檢出文檔排序文檔排序文檔倒排文檔倒排文檔文本文本文本文本信息組織、存儲(chǔ)與檢索信息組織、存儲(chǔ)與檢索建立索引的目的建立索引的目的n對文檔或文檔集合建立索引，以加快檢索速度n倒排文檔（或倒排索引）是一種最常用的索引機(jī)制n倒排文檔的索引對

2、象是文檔或文檔集合中的詞語等。例如，有些書往往在最后提供的索引（單詞頁碼列表對），就可以看成是一種倒排索引信息組織、存儲(chǔ)與檢索信息組織、存儲(chǔ)與檢索在關(guān)系數(shù)據(jù)庫上建索引在關(guān)系數(shù)據(jù)庫上建索引n 這種想法也被應(yīng)用于數(shù)據(jù)庫技術(shù)中，即對數(shù)據(jù)庫中需要經(jīng)常進(jìn)行檢索的域建立索引結(jié)構(gòu)，進(jìn)行快速的查詢。n 索引結(jié)構(gòu): hashing, B+-treen 可以索引全部記錄，在全部記錄上進(jìn)行搜索n 精確地快速地查找地址姓名姓名索引查詢式:姓名 = “張三”張三南京理工大學(xué)泰州科技學(xué)院張三信息組織、存儲(chǔ)與檢索信息組織、存儲(chǔ)與檢索倒排文檔的組成倒排文檔的組成n倒排文檔一般由兩部分組成：詞匯表（vocabulary）和記錄

3、表（posting list）n詞匯表是文本或文本集合中所包含的所有不同單詞的集合。n對于詞匯表中的每一個(gè)單詞，其在文本中出現(xiàn)的位置或者其出現(xiàn)的文本編號構(gòu)成一個(gè)列表，所有這些列表的集合就稱為記錄表。信息組織、存儲(chǔ)與檢索信息組織、存儲(chǔ)與檢索對文檔進(jìn)行索引對文檔進(jìn)行索引n索引結(jié)構(gòu): hashing, B+-trees.n可以進(jìn)行部分匹配: %comput% n可以進(jìn)行短語搜索:查找包含“computer graphics”的文檔文檔索引D1D2D3computerD1, 23, 97, 104D3, 43graphicsD2, 5D3, 44“computer”在D1中出現(xiàn)的位置信息組織、存儲(chǔ)與檢

4、索信息組織、存儲(chǔ)與檢索一般的倒排索引一般的倒排索引n 索引文件可以用任何文件結(jié)構(gòu)來實(shí)現(xiàn)n 索引文件中的詞項(xiàng)是文檔集合中的詞表architecturecomputerdatabaseretrieval.D1, a1D1, a2D1, a3索引項(xiàng)索引項(xiàng)/詞表詞表索引索引/索引文件索引文件/索引數(shù)據(jù)庫索引數(shù)據(jù)庫Postings 列表列表Q = term1, term2, term3, .附加信息例如：詞位置，出現(xiàn)次數(shù)信息組織、存儲(chǔ)與檢索信息組織、存儲(chǔ)與檢索例子例子12345678910111213141516這是一本 關(guān)于 信息 檢索 的教材 。介紹 了檢索 的基本 技術(shù) 。技術(shù)教材檢索信息15,

5、8, 6, 12, 5, 詞匯表記錄表文本倒排文件信息組織、存儲(chǔ)與檢索信息組織、存儲(chǔ)與檢索以文本為記錄表以文本為記錄表 記錄表既可以存儲(chǔ)文本中單詞的編號位置，也可以指向單詞首字母的字符位置，還可以是其所在的文本編號，下圖是一個(gè)以文本為記錄表的情況信息組織、存儲(chǔ)與檢索信息組織、存儲(chǔ)與檢索倒排文檔的使用倒排文檔的使用n詞匯表檢索n將出現(xiàn)在查詢中的單詞分離出來，并在詞匯表中進(jìn)行檢索；n記錄表檢索n檢索出所有找到的單詞對應(yīng)的記錄表；n記錄表操作n對檢索出的記錄表進(jìn)行處理，實(shí)現(xiàn)短語查詢、相鄰查詢或布爾查詢等。信息組織、存儲(chǔ)與檢索信息組織、存儲(chǔ)與檢索倒排文檔的建立倒排文檔的建立 基于內(nèi)存基于內(nèi)存n基于內(nèi)存

6、的建立倒排文檔算法n輸入：文檔集合n輸出：基于文檔集合的倒排文檔n算法：n1.初始遍歷文檔集合，對于每一個(gè)單詞w，統(tǒng)計(jì)包含該單詞的文檔數(shù)fw；n2.在內(nèi)存中建立長度為 的數(shù)組，并且對每一個(gè)單詞w生成指向其記錄表塊首的指針pw；n3.第二次遍歷文檔集合，對每個(gè)文檔d中的每一個(gè)單詞w，在pw中追加文檔d的序號， pw后移。詞表wwf信息組織、存儲(chǔ)與檢索信息組織、存儲(chǔ)與檢索倒排文檔的建立倒排文檔的建立 基于排序基于排序單詞 文檔編號技術(shù)技術(shù)1教材1檢索1信息1計(jì)算機(jī)2檢索2排序技術(shù)技術(shù)1計(jì)算機(jī)2檢索1檢索2教材1信息1合并技術(shù)技術(shù)計(jì)算機(jī)檢索信息12121倒排文檔基于排序的建立倒排文檔方法信息組織、存

7、儲(chǔ)與檢索信息組織、存儲(chǔ)與檢索倒排文檔的建立倒排文檔的建立基于歸并基于歸并n 輸入：文檔集合n 輸出：基于文檔集合的倒排文檔n 算法：n1.初始生成一個(gè)基于內(nèi)存的臨時(shí)索引結(jié)構(gòu)，其中詞匯表和記錄表均使用動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)；n2.讀取一個(gè)文檔，并在其中出現(xiàn)的單詞的記錄表中加入文檔編號，直到占用的內(nèi)存大小超過一定的閾值為止；n3.將生成的包括詞匯表和其記錄表的臨時(shí)索引結(jié)構(gòu)轉(zhuǎn)存到磁盤，并清空內(nèi)存；n4.如果所有文檔處理完畢，則轉(zhuǎn)到5，否則轉(zhuǎn)到1；n5.歸并以上生成的字索引，生成單一索引。信息組織、存儲(chǔ)與檢索信息組織、存儲(chǔ)與檢索倒排文檔的更新倒排文檔的更新刪除刪除n 倒排文檔更新就是一個(gè)刪除操作，后面跟著一

8、個(gè)插入操作n 為了支持刪除操作，需要維護(hù)一個(gè)前向索引(forward index)來記錄文檔中包含的詞Doc IDword1, word2, .n找到將要被刪除的文檔IDn從前向索引中獲得該文檔中包含的詞n根據(jù)該文檔中的詞定位倒排索引中的posting項(xiàng)，并在這些posting項(xiàng)中將該文檔ID刪除信息組織、存儲(chǔ)與檢索信息組織、存儲(chǔ)與檢索倒排文檔的更新倒排文檔的更新插入插入n 一個(gè)文檔插入時(shí)最壞的情況:n 當(dāng)文檔包含n個(gè)詞，并且每個(gè)詞都不重復(fù)，插入時(shí)需要更新n個(gè)posting表n 對于posting表中的每個(gè)更新操作:n 如果postings表沒有排序，新的posting項(xiàng)可以被追加到表的末端，

9、更新操作很快，但是檢索無序的posting表很慢n 如果posting表示排序了的，那么插入一個(gè)新的posting項(xiàng)需要很大的開銷databaseD345, 25D348, 37D350, 8新文檔:D349 包含“database”D349, 10databaseD345, 25D348, 37D349, 10D350, 8信息組織、存儲(chǔ)與檢索信息組織、存儲(chǔ)與檢索通過排序進(jìn)行批插入通過排序進(jìn)行批插入n 收集所有將被插入索引中的新文檔n 從每個(gè)文檔中提取term，并準(zhǔn)備一個(gè)倒排文件:Doc idTermpaperreportnovelnovel 1111 reporthuman 22 huma

10、nnovelnovelpaperreportreport 211112 排序human2,1novel1,2paper1,1report1,12,1合并在此記錄頻率，詞的位置也可以記錄信息組織、存儲(chǔ)與檢索信息組織、存儲(chǔ)與檢索倒排索引上的布爾檢索倒排索引上的布爾檢索考慮查詢：同時(shí)包含Brutus和Caesar的文檔。詞匯表倒排記錄表BrutusCaesarCalpurnia12358132134248163264 128131612834248163264123581321BrutusBrutusCaesarCaesar28信息組織、存儲(chǔ)與檢索信息組織、存儲(chǔ)與檢索合并過程合并過程34128248

11、16326412358132112834248163264123581321BrutusBrutusCaesarCaesar28信息組織、存儲(chǔ)與檢索信息組織、存儲(chǔ)與檢索合并算法的偽代碼描述合并算法的偽代碼描述信息組織、存儲(chǔ)與檢索信息組織、存儲(chǔ)與檢索查詢優(yōu)化查詢優(yōu)化n查詢處理中是否存在處理的順序問題？n考慮n 個(gè)詞項(xiàng)的 AND n對每個(gè)詞項(xiàng)，取出其倒排記錄表，然后兩兩合并n查詢: Brutus AND Caesar AND Calpurnian查詢優(yōu)化：（Calpurnia AND Brutus） AND Caesarn按照表從小到大(即df從小到大)的順序進(jìn)行處理n每次從最小的開始合并信息組織

12、、存儲(chǔ)與檢索信息組織、存儲(chǔ)與檢索詞匯表的存取詞匯表的存取排序數(shù)組排序數(shù)組n排序數(shù)組中的每個(gè)元素由三個(gè)部分組成：n關(guān)鍵詞n記錄表大小n指向其記錄表的指針 .Term1記錄表的大小記錄表的地址Term2記錄表的大小記錄表的地址Term3記錄表的大小記錄表的地址信息組織、存儲(chǔ)與檢索信息組織、存儲(chǔ)與檢索詞匯表的存取詞匯表的存取樹結(jié)構(gòu)樹結(jié)構(gòu)n二叉樹n除根節(jié)點(diǎn)、葉子節(jié)點(diǎn)外的每個(gè)節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)。信息組織、存儲(chǔ)與檢索信息組織、存儲(chǔ)與檢索詞匯表的存取詞匯表的存取樹結(jié)構(gòu)樹結(jié)構(gòu)nB樹是一種平衡的多叉樹，一棵m階的B樹滿足下列條件：n1 )樹中每個(gè)節(jié)點(diǎn)至多有m個(gè)孩子；n2 )除根節(jié)點(diǎn)和葉子節(jié)點(diǎn)外，其他每個(gè)節(jié)點(diǎn)至少

13、有m/2個(gè)孩子；n3 )若根節(jié)點(diǎn)不是葉子節(jié)點(diǎn)，則至少有2個(gè)孩子；n4 )所有葉子節(jié)點(diǎn)都出現(xiàn)在同一層，葉子節(jié)點(diǎn)不包含任何關(guān)鍵詞信息；n5)有k個(gè)孩子的非終端節(jié)點(diǎn)恰好包含有k-1個(gè)關(guān)鍵詞；信息組織、存儲(chǔ)與檢索信息組織、存儲(chǔ)與檢索B樹實(shí)例樹實(shí)例10 20 301 5 811 15 1821 2632 34 35 43 53m=5信息組織、存儲(chǔ)與檢索信息組織、存儲(chǔ)與檢索詞匯表的存取詞匯表的存取哈希表哈希表(散列文件散列文件)n散列文件也稱直接存取文件，即根據(jù)文件中關(guān)鍵詞的特點(diǎn)，設(shè)計(jì)哈希函數(shù)（散列函數(shù)）和沖突處理方法，將記錄散列存儲(chǔ)到設(shè)備上。n記錄存儲(chǔ)的邏輯地址=HASH(記錄的關(guān)鍵詞值)n除留余數(shù)法n

14、HASH（KEY）=KEY mod P信息組織、存儲(chǔ)與檢索信息組織、存儲(chǔ)與檢索哈希表實(shí)例哈希表實(shí)例n某一文件有16個(gè)記錄，其關(guān)鍵字分別為：23，05，26，01，18，02，27，12，07，09，04，19，06，16，33，24。桶的容量m=3，桶數(shù)b=7。求哈希表的分布。KEY2305260118022712KEY%725514265KEY0709041906163324KEY%702456253信息組織、存儲(chǔ)與檢索信息組織、存儲(chǔ)與檢索哈希表實(shí)例哈希表實(shí)例07012302091418040526122706161933基桶溢出桶桶編號0123456信息組織、存儲(chǔ)與檢索信息組織、存儲(chǔ)與檢索

15、倒排索引的特點(diǎn)倒排索引的特點(diǎn)n快速索引 (長query需要更多時(shí)間)；n靈活性: 不同類型的信息都可以存儲(chǔ)在記錄表中；n如果存儲(chǔ)了足夠多的信息，則可以支持復(fù)雜的檢索操作；n存儲(chǔ)開銷較大；n更新、插入和刪除都需要很高的維護(hù)開銷，倒排索引相對靜態(tài)的環(huán)境(很少插入和更新)中使用比較好。信息組織、存儲(chǔ)與檢索信息組織、存儲(chǔ)與檢索后綴數(shù)組的定義后綴數(shù)組的定義n可以將文本看作是一個(gè)長的字符串，文本中的每個(gè)位置都被認(rèn)為是文本的一個(gè)后綴，即一個(gè)從當(dāng)前文本位置到文本末尾的字符串。n索引的位置可以是每個(gè)字符的位置、單詞的位置或者漢字的位置等。n后綴數(shù)組：后綴數(shù)組：就是對文本中的所有后綴按照詞典序存放每個(gè)后綴對應(yīng)的起

16、始位置的列表。信息組織、存儲(chǔ)與檢索信息組織、存儲(chǔ)與檢索原始文本，按字的順序位置索引文本中的部分后綴，按位置索引相同的部分后綴，按詞典順序索引后綴數(shù)組的構(gòu)造后綴數(shù)組的構(gòu)造 024681012141618202224262830323436384042444648這是一本關(guān)于信息檢索的教材。介紹了檢索的基本技術(shù)。021216223444這是是一信息檢索教材檢索技術(shù)441634222120技術(shù)檢索檢索教材是一信息這是信息組織、存儲(chǔ)與檢索信息組織、存儲(chǔ)與檢索后綴數(shù)組的使用后綴數(shù)組的使用 n在使用后綴數(shù)組進(jìn)行檢索的時(shí)候，將每個(gè)查詢同樣截取前n個(gè)字節(jié)，并于索引中進(jìn)行查找；n如果沒有找到，則表明不包含所需查

17、詢；n如果查找成功，則需要在相應(yīng)的文本位置上，進(jìn)行進(jìn)一步的字符串比較，以確定文本中是否包含查詢；信息組織、存儲(chǔ)與檢索信息組織、存儲(chǔ)與檢索后綴數(shù)組的分析后綴數(shù)組的分析 n對于需要大數(shù)據(jù)量的檢索問題，后綴數(shù)組并不適用 ；n因?yàn)闃?gòu)造出的后綴數(shù)組需要占用大量的空間，通常是原文本的1.7倍 ；n和倒排文檔相比，后綴數(shù)組里面儲(chǔ)存了較多的重復(fù)信息 ；信息組織、存儲(chǔ)與檢索信息組織、存儲(chǔ)與檢索文本檢索技術(shù)文本檢索技術(shù)布爾檢索布爾檢索ANDORNOT信息組織、存儲(chǔ)與檢索信息組織、存儲(chǔ)與檢索布爾檢索布爾檢索n布爾邏輯運(yùn)算符n邏輯與：”AND” 或”*”n邏輯或： ”O(jiān)R” 或”+”n邏輯非： ”NOT” 或”-”n

18、使用布爾運(yùn)算符注意事項(xiàng)n運(yùn)算執(zhí)行順序：NOTANDOR;先執(zhí)行括號內(nèi)的邏輯運(yùn)算；n使用規(guī)則：不同檢索工具規(guī)則不同信息組織、存儲(chǔ)與檢索信息組織、存儲(chǔ)與檢索文本檢索技術(shù)文本檢索技術(shù)截詞檢索截詞檢索n 利用詞干或不完整的詞形查找信息的檢索技術(shù)；n 按截?cái)嘧址臄?shù)量，分為有限截?cái)唷o限截?cái)?；n 按截?cái)嘧址奈恢?，分為n后截?cái)鄼z索（也稱前方一致檢索）n無限后截?cái)鄼z索：coagula*(coagulacoagulantcoagulasecoagulate)n有限后截?cái)鄼z索：mold?(moldmoldedmolder)n后截?cái)鄼z索的利用n單詞復(fù)數(shù)：apple?n年代：199？n作者：smith*n同根詞：attract*信息組織、存儲(chǔ)與檢索信息組織、存儲(chǔ)與檢索文本檢索技術(shù)文本檢索技術(shù)截詞檢索截詞檢索n前截?cái)鄼z索（也稱后方一致檢索）n無限前截?cái)鄼z索：*metern有限前截?cái)鄼z索：？metern前截?cái)嗪秃蠼財(cái)嘟Y(jié)合使用：*econom*n中截?cái)鄼z索（也稱中間一致檢索）nm?n,wom?nn截?cái)鄼z索的特點(diǎn)n減少檢索詞輸入量，提高召回率，降低準(zhǔn)確率信息組織、存儲(chǔ)與檢索信息組織、存儲(chǔ)與檢索文本檢索技術(shù)文本檢索技術(shù)限制檢索限制檢