第五章-文本索引和搜索

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

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

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

AND

CaesarAND

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

AND

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