第五章-文本索引和搜索

第五章文本索引和檢索信息檢索系統(tǒng)工作流程用戶界面文本操作查詢操作標(biāo)引檢索排序索引數(shù)據(jù)庫管理模塊文本數(shù)據(jù)庫用戶需求邏輯視圖邏輯視圖用戶反饋查詢檢出文檔排序文檔倒排文檔文本文本建立索引的目的對文檔或文檔集合建立索引，以加快檢索速度倒排文檔（或倒排索引）是一種最常用的索引機制倒排文檔的索引對象是文檔或文檔集合中的詞語等。例如，有些書往往在最后提供的索引（單詞—頁碼列表對），就可以看成是一種倒排索引在關(guān)系數(shù)據(jù)庫上建索引這種想法也被應(yīng)用于數(shù)據(jù)庫技術(shù)中，即對數(shù)據(jù)庫中需要經(jīng)常進行檢索的域建立索引結(jié)構(gòu)，進行快速的查詢。索引結(jié)構(gòu):hashing,B+-tree可以索引全部記錄，在全部記錄上進行搜索精確地快速地查找地址姓名姓名索引查詢式:姓名

=“張三”張三南京理工大學(xué)泰州科技學(xué)院張三倒排文檔的組成倒排文檔一般由兩部分組成：詞匯表（vocabulary）和記錄表（postinglist）詞匯表是文本或文本集合中所包含的所有不同單詞的集合。對于詞匯表中的每一個單詞，其在文本中出現(xiàn)的位置或者其出現(xiàn)的文本編號構(gòu)成一個列表，所有這些列表的集合就稱為記錄表。對文檔進行索引索引結(jié)構(gòu):hashing,B+-trees.可以進行部分匹配:’%comput%’可以進行短語搜索:查找包含“computergraphics”的文檔文檔索引D1D2D3computerD1,23,97,104D3,43graphicsD2,5D3,44“computer”在D1中出現(xiàn)的位置一般的倒排索引索引文件可以用任何文件結(jié)構(gòu)來實現(xiàn)索引文件中的詞項是文檔集合中的詞表architecturecomputerdatabaseretrieval...D1,a1D1,a2D1,a3索引項/詞表索引/索引文件/索引數(shù)據(jù)庫Postings列表Q=term1,term2,term3,...附加信息例如：詞位置，出現(xiàn)次數(shù)例子12345678910111213141516這是一本關(guān)于信息檢索的教材。介紹了檢索的基本技術(shù)?！夹g(shù)教材檢索信息…15,…8,…6,12,…5,……詞匯表記錄表文本倒排文件以文本為記錄表記錄表既可以存儲文本中單詞的編號位置，也可以指向單詞首字母的字符位置，還可以是其所在的文本編號，下圖是一個以文本為記錄表的情況倒排文檔的使用詞匯表檢索將出現(xiàn)在查詢中的單詞分離出來，并在詞匯表中進行檢索；記錄表檢索檢索出所有找到的單詞對應(yīng)的記錄表；記錄表操作對檢索出的記錄表進行處理，實現(xiàn)短語查詢、相鄰查詢或布爾查詢等。倒排文檔的建立—基于內(nèi)存基于內(nèi)存的建立倒排文檔算法輸入：文檔集合輸出：基于文檔集合的倒排文檔算法：1.初始遍歷文檔集合，對于每一個單詞w，統(tǒng)計包含該單詞的文檔數(shù)fw；2.在內(nèi)存中建立長度為的數(shù)組，并且對每一個單詞w生成指向其記錄表塊首的指針pw；3.第二次遍歷文檔集合，對每個文檔d中的每一個單詞w，在pw中追加文檔d的序號，pw后移。倒排文檔的建立—基于排序單詞文檔編號技術(shù)1教材1檢索1信息1……計算機2檢索2……排序技術(shù)1計算機2檢索1檢索2教材1信息1……合并技術(shù)計算機檢索信息12121倒排文檔基于排序的建立倒排文檔方法倒排文檔的建立—基于歸并輸入：文檔集合輸出：基于文檔集合的倒排文檔算法：1.初始生成一個基于內(nèi)存的臨時索引結(jié)構(gòu)，其中詞匯表和記錄表均使用動態(tài)數(shù)據(jù)結(jié)構(gòu)存儲；2.讀取一個文檔，并在其中出現(xiàn)的單詞的記錄表中加入文檔編號，直到占用的內(nèi)存大小超過一定的閾值為止；3.將生成的包括詞匯表和其記錄表的臨時索引結(jié)構(gòu)轉(zhuǎn)存到磁盤，并清空內(nèi)存；4.如果所有文檔處理完畢，則轉(zhuǎn)到5，否則轉(zhuǎn)到1；5.歸并以上生成的字索引，生成單一索引。倒排文檔的更新—刪除倒排文檔更新就是一個刪除操作，后面跟著一個插入操作為了支持刪除操作，需要維護一個前向索引(forwardindex)來記錄文檔中包含的詞DocIDword1,word2,….找到將要被刪除的文檔ID從前向索引中獲得該文檔中包含的詞根據(jù)該文檔中的詞定位倒排索引中的posting項，并在這些posting項中將該文檔ID刪除倒排文檔的更新—插入一個文檔插入時最壞的情況:當(dāng)文檔包含n個詞，并且每個詞都不重復(fù)，插入時需要更新n個posting表對于posting表中的每個更新操作:如果postings表沒有排序，新的posting項可以被追加到表的末端，更新操作很快，但是檢索無序的posting表很慢如果posting表示排序了的，那么插入一個新的posting項需要很大的開銷databaseD345,25D348,37D350,8新文檔:D349

包含“database”D349,10databaseD345,25D348,37D349,10D350,8通過排序進行批插入收集所有將被插入索引中的新文檔從每個文檔中提取term，并準(zhǔn)備一個倒排文件:DocidTermpaperreportnovelnovel……1111…reporthuman……22…h(huán)umannovelnovelpaperreportreport……211112…排序human2,1novel1,2paper1,1report1,12,1合并在此記錄頻率，詞的位置也可以記錄倒排索引上的布爾檢索考慮查詢：同時包含Brutus和Caesar的文檔。詞匯表倒排記錄表BrutusCaesarCalpurnia12358132134248163264128131612834248163264123581321BrutusCaesar28合并過程3412824816326412358132112834248163264123581321BrutusCaesar28合并算法的偽代碼描述查詢優(yōu)化查詢處理中是否存在處理的順序問題？考慮n個詞項的AND對每個詞項，取出其倒排記錄表，然后兩兩合并查詢:Brutus

AND

CaesarAND

Calpurnia查詢優(yōu)化：（CalpurniaANDBrutus）

AND

Caesar按照表從小到大(即df從小到大)的順序進行處理每次從最小的開始合并詞匯表的存取—排序數(shù)組排序數(shù)組中的每個元素由三個部分組成：關(guān)鍵詞記錄表大小指向其記錄表的指針……..Term1記錄表的大小記錄表的地址Term2記錄表的大小記錄表的地址Term3記錄表的大小記錄表的地址詞匯表的存取—樹結(jié)構(gòu)二叉樹除根節(jié)點、葉子節(jié)點外的每個節(jié)點都有兩個子節(jié)點。詞匯表的存取—樹結(jié)構(gòu)B樹是一種平衡的多叉樹，一棵m階的B樹滿足下列條件：1)樹中每個節(jié)點至多有m個孩子；2)除根節(jié)點和葉子節(jié)點外，其他每個節(jié)點至少有m/2個孩子；3)若根節(jié)點不是葉子節(jié)點，則至少有2個孩子；4)所有葉子節(jié)點都出現(xiàn)在同一層，葉子節(jié)點不包含任何關(guān)鍵詞信息；5)有k個孩子的非終端節(jié)點恰好包含有k-1個關(guān)鍵詞；B樹實例10203015811151821263234354353m=5詞匯表的存取—哈希表(散列文件)散列文件也稱直接存取文件，即根據(jù)文件中關(guān)鍵詞的特點，設(shè)計哈希函數(shù)（散列函數(shù)）和沖突處理方法，將記錄散列存儲到設(shè)備上。記錄存儲的邏輯地址=HASH(記錄的關(guān)鍵詞值)除留余數(shù)法HASH（KEY）=KEYmodP哈希表實例某一文件有16個記錄，其關(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哈希表實例07^01^23020914^1804^0526122706^16^1933^基桶溢出桶桶編號0123456倒排索引的特點快速索引(長query需要更多時間)；靈活性:不同類型的信息都可以存儲在記錄表中；如果存儲了足夠多的信息，則可以支持復(fù)雜的檢索操作；存儲開銷較大；更新、插入和刪除都需要很高的維護開銷，倒排索引相對靜態(tài)的環(huán)境(很少插入和更新)中使用比較好。后綴數(shù)組的定義可以將文本看作是一個長的字符串，文本中的每個位置都被認(rèn)為是文本的一個后綴，即一個從當(dāng)前文本位置到文本末尾的字符串。索引的位置可以是每個字符的位置、單詞的位置或者漢字的位置等。后綴數(shù)組：就是對文本中的所有后綴按照詞典序存放每個后綴對應(yīng)的起始位置的列表。原始文本，按字的順序位置索引文本中的部分后綴，按位置索引相同的部分后綴，按詞典順序索引后綴數(shù)組的構(gòu)造024681012141618202224262830323436384042444648…這是一本關(guān)于信息檢索的教材。介紹了檢索的基本技術(shù)?！?21216223444…這是…是一…信息…檢索…教材…檢索…技術(shù)……441634222120…技術(shù)…檢索…檢索…教材…是一…信息…這是……后綴數(shù)組的使用在使用后綴數(shù)組進行檢索的時候，將每個查詢同樣截取前n個字節(jié)，并于索引中進行查找；如果沒有找到，則表明不包含所需查詢；如果查找成功，則需要在相應(yīng)的文本位置上，進行進一步的字符串比較，以確定文本中是否包含查詢；后綴數(shù)組的分析對于需要大數(shù)據(jù)量的檢索問題，后綴數(shù)組并不適用；因為構(gòu)造出的后綴數(shù)組需要占用大量的空間，通常是原文本的1.7倍；和倒排文檔相比，后綴數(shù)組里面儲存了較多的重復(fù)信息；文本檢索技術(shù)—布爾檢索ANDORNOT布爾檢索布爾邏輯運算符邏輯與：”AND”或”*”邏輯或：”O(jiān)R”或”+”邏輯非：”NOT”或”-”使用布爾運算符注意事項運算執(zhí)行順序：NOT>AND>OR;先執(zhí)行括號內(nèi)的邏輯運算；使用規(guī)則：不同檢索工具規(guī)則不同文本檢索技術(shù)—截詞檢索利用詞干或不完整的詞形查找信息的檢索技術(shù)；按截斷字符的數(shù)量，分為有限截斷、無限截斷；按截斷字符的位置，分為后截斷檢索（也稱前方一致檢索）無限后截斷檢索：coagula*(coagula\coagulant\coagulase\coagulate…)有限后截斷檢索：mold??(mold\molded\molder…)后截斷檢索的利用單詞復(fù)數(shù)：apple?年代：199？作者：smith*同根詞：attract*文本檢索技術(shù)—截詞檢索前截斷檢索（也稱后方一致檢索）無限前截斷檢索：*meter有限前截斷檢索：？？？？meter前截斷和后截斷結(jié)合使用：*econom*中截斷檢索（也稱中間一致檢索）m?n,wom?n截斷檢索的特點減少檢索詞輸入量，提高召回率，降低準(zhǔn)確率文本檢索技術(shù)—限制檢索通過給檢索詞附加一定的條件來縮小或約束檢索結(jié)果。限制字段檢索主題字段非主題字段限定位置檢索記錄級字段級