第五章文本索引和搜索

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

18、使用布爾運算符注意事項n運算執(zhí)行順序：NOTANDOR;先執(zhí)行括號內的邏輯運算；n使用規(guī)則：不同檢索工具規(guī)則不同信息組織、存儲與檢索信息組織、存儲與檢索文本檢索技術文本檢索技術截詞檢索截詞檢索n 利用詞干或不完整的詞形查找信息的檢索技術；n 按截斷字符的數(shù)量，分為有限截斷、無限截斷；n 按截斷字符的位置，分為n后截斷檢索（也稱前方一致檢索）n無限后截斷檢索：coagula*(coagulacoagulantcoagulasecoagulate)n有限后截斷檢索：mold?(moldmoldedmolder)n后截斷檢索的利用n單詞復數(shù)：apple?n年代：199？n作者：smith*n同根詞：attract*信息組織、存儲與檢索信息組織、存儲與檢索文本檢索技術文本檢索技術截詞檢索截詞檢索n前截斷檢索（也稱后方一致檢索）n無限前截斷檢索：*metern有限前截斷檢索：？metern前截斷和后截斷結合使用：*econom*n中截斷檢索（也稱中間一致檢索）nm?n,wom?nn截斷檢索的特點n減少檢索詞輸入量，提高召回率，降低準確率信息組織、存儲與檢索信息組織、存儲與檢索文本檢索技術文本檢索技術限制檢索限制檢