信息檢索技術(shù)

1、信息檢索技術(shù)1第1頁(yè)，共52頁(yè)，2022年，5月20日，0點(diǎn)54分，星期一內(nèi)容提要倒排文檔檢索加權(quán)檢索全文檢索2第2頁(yè)，共52頁(yè)，2022年，5月20日，0點(diǎn)54分，星期一4.1 倒排文檔檢索3第3頁(yè)，共52頁(yè)，2022年，5月20日，0點(diǎn)54分，星期一信息檢索系統(tǒng)的體系結(jié)構(gòu)文本數(shù)據(jù)庫(kù)數(shù)據(jù)庫(kù)管理建索引索引提問(wèn)處理搜索排序排序后的文檔用戶反饋文本處理用戶界面檢出的文檔用戶需求文本提問(wèn)邏輯視圖倒排文檔4第4頁(yè)，共52頁(yè)，2022年，5月20日，0點(diǎn)54分，星期一建立索引的目的對(duì)文檔或文檔集合建立索引，以加快檢索速度倒排文檔（或倒排索引）是一種最常用的索引機(jī)制倒排文檔的索引對(duì)象是文檔或文檔集合中的單

2、詞等。5第5頁(yè)，共52頁(yè)，2022年，5月20日，0點(diǎn)54分，星期一在關(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)行搜索精確地快速地查找地址姓名姓名索引查詢式:姓名 = “張三”張三哈爾濱工業(yè)大學(xué)張三6第6頁(yè)，共52頁(yè)，2022年，5月20日，0點(diǎn)54分，星期一對(duì)文檔進(jìn)行索引索引結(jié)構(gòu): hashing, B+-trees, tries.可以進(jìn)行部分匹配: %comput% 可以進(jìn)行短語(yǔ)搜索:查找包含“computer graphics”的文檔文檔索引D

3、1D2D3computerD1, 23, 97, 104D3, 43graphicsD2, 5D3, 44“computer”在D1中出現(xiàn)的位置7第7頁(yè)，共52頁(yè)，2022年，5月20日，0點(diǎn)54分，星期一倒排文檔組成倒排文檔一般由兩部分組成：詞匯表（vocabulary）和記錄表（posting list）詞匯表是文本或文本集合中所包含的所有不同單詞的集合。對(duì)于詞匯表中的每一個(gè)單詞，其在文本中出現(xiàn)的位置或者其出現(xiàn)的文本編號(hào)構(gòu)成一個(gè)列表，所有這些列表的集合就稱為記錄表8第8頁(yè)，共52頁(yè)，2022年，5月20日，0點(diǎn)54分，星期一一般的倒排索引索引文件可以用任何文件結(jié)構(gòu)來(lái)實(shí)現(xiàn)索引文件中的詞項(xiàng)是文

4、檔集合中的詞表architecturecomputerdatabaseretrieval.D1, a1D1, a2D1, a3索引項(xiàng)/詞表索引/索引文件/索引數(shù)據(jù)庫(kù)Postings 列表Q = term1, term2, term3, .附加信息例如：詞位置，出現(xiàn)次數(shù)9第9頁(yè)，共52頁(yè)，2022年，5月20日，0點(diǎn)54分，星期一例子12345678910111213141516這是一本關(guān)于信息檢索的教材。介紹了檢索的基本技術(shù)。技術(shù)教材檢索信息15, 8, 6, 12, 5, 詞匯表Posting list文本倒排文件10第10頁(yè)，共52頁(yè)，2022年，5月20日，0點(diǎn)54分，星期一以文本為記錄

5、表 記錄表既可以存儲(chǔ)文本中單詞的編號(hào)位置，也可以指向單詞首字母的字符位置，還可以是其所在的文本編號(hào)，下圖是一個(gè)以文本為記錄表的情況11第11頁(yè)，共52頁(yè)，2022年，5月20日，0點(diǎn)54分，星期一距離約束：需要位置信息為記錄表常常需要知道鄰接條件，例如：“database” 后面緊跟著“systems”例如：短語(yǔ)搜索 “database systems”“database”和“systems”之間不能間隔超過(guò)3個(gè)詞“database”和“architecture”在同一個(gè)句子里需求擴(kuò)展:倒排索引中保存著關(guān)鍵詞在文檔中的位置，文檔的組成單元(標(biāo)題, 小標(biāo)題, 句子分割標(biāo)記等)檢索算法和位置信息相

6、關(guān)聯(lián)，并需檢查文檔的組成單元12第12頁(yè)，共52頁(yè)，2022年，5月20日，0點(diǎn)54分，星期一以位置信息為記錄表保存段落、句子和詞的位置：databasefilesystems.D345, 25D348, 37D350, 8D123, 5D128, 25D345, 25保存倒排表中的位置信息:保存句子位置:文檔D350第8句databasefilesystems.D345, 2,3,5D348, 37,5,9D350, 8,12,1D123, 5,4,3D128, 25,1,12D345, 2,3,6文檔D350第8段，第12句第1個(gè)詞13第13頁(yè)，共52頁(yè)，2022年，5月20日，0點(diǎn)54分

7、，星期一以權(quán)重信息為記錄表可保存出現(xiàn)頻率，以便支持基于統(tǒng)計(jì)的檢索:databasefilesystems.D345, 10D348, 20D350, 1D123, 82D128, 8D345, 12在D345中“systems” 比“database”重要1.2倍Postings中的第二個(gè)單元可以是該term的權(quán)重 (例如, 可以被歸一化在0和1之間) ，或者是該term的出現(xiàn)頻率14第14頁(yè)，共52頁(yè)，2022年，5月20日，0點(diǎn)54分，星期一同義詞擴(kuò)展詞匯表同義詞對(duì)于提高召回率很有意義同義詞可以通過(guò)指針指向同一個(gè)postings list.databasedatabasessystemsD

8、345, 2,3,5D348, 37,5,9D350, 8,12,1D123, 5,4,3D128, 25,1,12D345, 2,3,6dataset15第15頁(yè)，共52頁(yè)，2022年，5月20日，0點(diǎn)54分，星期一建立索引的過(guò)程16第16頁(yè)，共52頁(yè)，2022年，5月20日，0點(diǎn)54分，星期一建立索引的過(guò)程識(shí)別文檔中的詞刪除停用詞(stop words)提取詞干(stemming)用索引項(xiàng)的標(biāo)號(hào)代替詞干(stems) 統(tǒng)計(jì)詞干的數(shù)量(tf)(可選) 對(duì)低頻詞項(xiàng)使用同義詞詞典(thesaurus)(可選) 對(duì)高頻詞項(xiàng)構(gòu)成短語(yǔ)計(jì)算所有單個(gè)詞項(xiàng)、短語(yǔ)和語(yǔ)義類的權(quán)重17第17頁(yè)，共52頁(yè)，2022

9、年，5月20日，0點(diǎn)54分，星期一英文詞根還原(Stemming)進(jìn)行詞根還原：stop/stops/stopping/stoppedstop好處：減少詞典量；壞處：按詞形查不到，詞根還原還可能出現(xiàn)錯(cuò)誤不進(jìn)行詞根還原：Stoppedsto+ppe+d好處：支持詞形查詢；壞處：增加詞典量18第18頁(yè)，共52頁(yè)，2022年，5月20日，0點(diǎn)54分，星期一停用詞消除停用詞(stop words)是指那些出現(xiàn)頻率高但是無(wú)重要意義，通常不會(huì)作為查詢?cè)~出現(xiàn)的詞，如“的”、“地”、“得”、“都”、“是”等等消除：通常是通過(guò)查表的方式去除，去除的好處-大大較少索引量，壞處-有些平時(shí)的停用詞在某些上下文可能有意

10、義保留：索引空間很大19第19頁(yè)，共52頁(yè)，2022年，5月20日，0點(diǎn)54分，星期一建立索引的過(guò)程 舉例輸入文本The analysis of 25 indexing algorithms has not produced consistent retrieval performance. The best indexing technique for retrieving documents is not known刪除stopwordsanalysis indexing algorithms produced consistent retrieval performance best i

11、ndexing technique retrieving documents knownStemminganalysis index algorithm produc consistent retriev perform best index technique retriev document known轉(zhuǎn)換為索引編號(hào)123 345 110 2234 432 3565 2302 566 345 4321 3565 755 1128計(jì)算tf110 1 123 1 345 2 1 432 1 566 1 755 1 1128 1 2302 1 2344 1 3565 2 4321 1計(jì)算詞項(xiàng)的權(quán)

12、值 (依賴于使用的模型)20第20頁(yè)，共52頁(yè)，2022年，5月20日，0點(diǎn)54分，星期一檢索過(guò)程給定query對(duì)query進(jìn)行stemming，算法與對(duì)文檔的處理相同用索引編號(hào)代替stems計(jì)算所有query terms的權(quán)重形成query向量（對(duì)VSM模型而言）計(jì)算query向量和文檔向量之間的相似度返回排序后的文檔集合21第21頁(yè)，共52頁(yè)，2022年，5月20日，0點(diǎn)54分，星期一倒排索引上的布爾檢索一個(gè)布爾檢索包含n個(gè)用布爾操作連接的詞項(xiàng) ，例如：“computer AND news AND NOT newsgroup”可以用括號(hào)來(lái)調(diào)整邏輯運(yùn)算次序每個(gè)term從倒排索引中返回一個(gè)po

13、stings list如果term不在任何文檔中出現(xiàn)，則postings list為空檢索結(jié)果根據(jù)邏輯關(guān)系相結(jié)合：AND: 集合做交運(yùn)算OR: 集合做并運(yùn)算NOT: 集合做差運(yùn)算ABA and B22第22頁(yè)，共52頁(yè)，2022年，5月20日，0點(diǎn)54分，星期一倒排索引上的布爾檢索查詢:中國(guó) AND 文化查找Dictionary，定位中國(guó);讀取對(duì)應(yīng)的postings.查找Dictionary，定位文化;讀取對(duì)應(yīng)的postings.“Merge” 合并(AND)兩個(gè)postings:12834248163264123581321中國(guó)文化23第23頁(yè)，共52頁(yè)，2022年，5月20日，0點(diǎn)54分，

14、星期一34128248163264123581321合并Lists的合并算法34248163264123581321中國(guó)文化28If the list lengths are x and y, the merge takes O(x+y)operations.Crucial: postings sorted by docID.24第24頁(yè)，共52頁(yè)，2022年，5月20日，0點(diǎn)54分，星期一倒排索引上的布爾檢索標(biāo)準(zhǔn)的優(yōu)化技術(shù)應(yīng)用：從最短的posting list開(kāi)始做“與”操作，保證中間結(jié)果越小越好“網(wǎng)絡(luò)” AND “病毒” AND “蠕蟲(chóng)”從哪個(gè)詞項(xiàng)開(kāi)始做交運(yùn)算呢？顯然是：“病毒”和“蠕蟲(chóng)”

15、25第25頁(yè)，共52頁(yè)，2022年，5月20日，0點(diǎn)54分，星期一倒排索引的優(yōu)點(diǎn)快速索引 (長(zhǎng)query需要更多時(shí)間)靈活性: 不同類型的信息都可以存儲(chǔ)在postings list中如果存儲(chǔ)了足夠多的信息，則可以支持復(fù)雜的檢索操作例如：如果記錄了詞在文檔中的準(zhǔn)確位置，就可以支持短語(yǔ)檢索，或模糊檢索26第26頁(yè)，共52頁(yè)，2022年，5月20日，0點(diǎn)54分，星期一倒排索引的缺點(diǎn)很大的存儲(chǔ)開(kāi)銷50% - 150% - 300%更新、插入和刪除都需要很高的維護(hù)開(kāi)銷，倒排索引相對(duì)靜態(tài)的環(huán)境(很少插入和更新)中使用比較好處理開(kāi)銷隨著布爾操作的增加而增長(zhǎng)由于postings越來(lái)越多(例如引入同義詞)，導(dǎo)致

16、索引檢索的代價(jià)越來(lái)越大，需要對(duì)位置進(jìn)行很多處理(例如短語(yǔ)匹配)27第27頁(yè)，共52頁(yè)，2022年，5月20日，0點(diǎn)54分，星期一倒排文檔中研究的問(wèn)題倒排文檔的壓縮倒排文檔的刪除倒排文檔的插入28第28頁(yè)，共52頁(yè)，2022年，5月20日，0點(diǎn)54分，星期一索引壓縮理論上，(全文)索引的大小和原始文件相當(dāng)，因?yàn)槊總€(gè)詞的每次出現(xiàn)都必須在posting list中記錄。需不需要壓縮？要壓縮：索引大小通常和原始文本大小相當(dāng)，不壓縮可能會(huì)耗費(fèi)大量存儲(chǔ)開(kāi)銷不壓縮：硬盤(pán)很便宜，數(shù)據(jù)量不是特別大，而且不需要解壓縮的消耗29第29頁(yè)，共52頁(yè)，2022年，5月20日，0點(diǎn)54分，星期一倒排索引的更新情況一：出現(xiàn)

17、了新的詞，則需要修改詞典結(jié)構(gòu)，在詞典中增加詞條。情況二：出現(xiàn)了新的文檔，則在相應(yīng)的詞條下增加posting list。情況三：某些文檔不復(fù)存在，則在相應(yīng)的位置進(jìn)行標(biāo)記，等積累到一定時(shí)期進(jìn)行一次性操作。30第30頁(yè)，共52頁(yè)，2022年，5月20日，0點(diǎn)54分，星期一詞匯表的組織順序排序數(shù)組：采用字典序，查找采用二分法?？臻g消耗小，查找較快，但是插入刪除麻煩。二叉搜索樹(shù)、B樹(shù)、Trie樹(shù)等。Hash表：通過(guò)Hash函數(shù)直接把詞映射到地址，空間消耗和Hash函數(shù)設(shè)計(jì)有關(guān)。較快，插入刪除容易。31第31頁(yè)，共52頁(yè)，2022年，5月20日，0點(diǎn)54分，星期一4.2 加權(quán)檢索加權(quán)檢索根據(jù)每個(gè)詞在檢索要

18、求中的重要程度不同，分別給予一定的數(shù)值（權(quán)值）加以區(qū)別，同時(shí)利用給出的檢索命中界限值（閾值，Threshold）限定檢索結(jié)果的輸出。加權(quán)檢索是布爾邏輯檢索的一種擴(kuò)充，把量化思想引入定性檢索中。加權(quán)檢索分為標(biāo)引加權(quán)和檢索加權(quán)兩種類型。32第32頁(yè)，共52頁(yè)，2022年，5月20日，0點(diǎn)54分，星期一4.2.1 檢索詞賦權(quán)檢索對(duì)每一檢索詞給定一權(quán)值，代表其重要性。檢索時(shí)，對(duì)存在的檢索詞的記錄計(jì)算其權(quán)值總和。當(dāng)權(quán)值總和大于閾值時(shí)，則認(rèn)為命中。 最簡(jiǎn)單、最容易實(shí)現(xiàn)的加權(quán)檢索系統(tǒng)。33第33頁(yè)，共52頁(yè)，2022年，5月20日，0點(diǎn)54分，星期一舉例一個(gè)企業(yè)管理者為了改進(jìn)企業(yè)管理模式，接受新的管理理念，

19、提高企業(yè)的競(jìng)爭(zhēng)力，希望獲取知識(shí)管理、競(jìng)爭(zhēng)情報(bào)、企業(yè)文化方面的文獻(xiàn)資料，用加權(quán)法列出的提問(wèn)式如下： W = 知識(shí)管理（4）競(jìng)爭(zhēng)情報(bào)（2）企業(yè)文化（1）表中“”表示相應(yīng)檢索詞與文獻(xiàn)中主題詞匹配，若設(shè)定閾值為4，由上表可知，組合1至4為命中文獻(xiàn)。34第34頁(yè)，共52頁(yè)，2022年，5月20日，0點(diǎn)54分，星期一檢索詞賦權(quán)檢索的優(yōu)缺點(diǎn)檢索詞賦權(quán)檢索的優(yōu)點(diǎn)：明確了檢索詞在檢索中的重要程度；通過(guò)提高或降低閾值來(lái)擴(kuò)大和縮小檢索輸出的范圍；檢索結(jié)果按符合檢索需求的重要程度順序排列。檢索詞賦權(quán)檢索的缺點(diǎn)：加權(quán)法提問(wèn)式表達(dá)不如邏輯式直觀；權(quán)值的確定較為困難。35第35頁(yè)，共52頁(yè)，2022年，5月20日，0點(diǎn)54

20、分，星期一4.2.2 加權(quán)標(biāo)引加權(quán)標(biāo)引是指在對(duì)文獻(xiàn)進(jìn)行標(biāo)引時(shí)，根據(jù)每個(gè)標(biāo)引詞在文獻(xiàn)中的重要程度不同，為它們附上不同的權(quán)值，檢索時(shí)通過(guò)對(duì)檢索詞的標(biāo)引權(quán)值相加來(lái)篩選命中記錄。36第36頁(yè)，共52頁(yè)，2022年，5月20日，0點(diǎn)54分，星期一加權(quán)標(biāo)引在進(jìn)行加權(quán)標(biāo)引時(shí)，對(duì)反映文獻(xiàn)主要內(nèi)容的標(biāo)引詞給予高權(quán)值，反映文獻(xiàn)次要內(nèi)容的標(biāo)引詞給予較低的權(quán)值。詞頻加權(quán)檢索方法應(yīng)建立在對(duì)全文數(shù)據(jù)庫(kù)和文摘數(shù)據(jù)庫(kù)基礎(chǔ)之上，否則詞頻加權(quán)將失去意義。37第37頁(yè)，共52頁(yè)，2022年，5月20日，0點(diǎn)54分，星期一簡(jiǎn)單詞頻加權(quán)簡(jiǎn)單詞頻加權(quán)檢索：指檢索時(shí)累計(jì)檢索詞在記錄中出現(xiàn)的次數(shù)來(lái)決定記錄的權(quán)值。最大缺點(diǎn)就是不論文章長(zhǎng)短、詞

21、頻高低都采用的是統(tǒng)一的詞頻標(biāo)準(zhǔn)。38第38頁(yè)，共52頁(yè)，2022年，5月20日，0點(diǎn)54分，星期一相對(duì)詞頻加權(quán)檢索將每一個(gè)檢索詞在本文中頻率和在整個(gè)數(shù)據(jù)庫(kù)中的頻率綜合考慮，進(jìn)行加權(quán)檢索的方法。文內(nèi)頻率=指定詞在本文中的頻次/該文本詞匯總頻次文外頻率=指定詞在本文中的頻次/該詞在整個(gè)數(shù)據(jù)庫(kù)(所有文獻(xiàn))中總次數(shù)文內(nèi)頻率解決了短文章中詞頻過(guò)低的問(wèn)題，文外頻率解決了新詞、專用詞的低頻問(wèn)題。 39第39頁(yè)，共52頁(yè)，2022年，5月20日，0點(diǎn)54分，星期一4.2.3 標(biāo)引加權(quán)的檢索過(guò)程檢索時(shí)給出檢索詞和檢索閾值，對(duì)滿足檢索閾值的檢索結(jié)果按其權(quán)值之和從大到小輸出來(lái)篩選命中記錄。 在實(shí)際的人工標(biāo)引中尚未見(jiàn)

22、有加權(quán)標(biāo)引的系統(tǒng)。在計(jì)算機(jī)自動(dòng)標(biāo)引的系統(tǒng)中，可以方便而有效的采用加權(quán)標(biāo)引技術(shù)。40第40頁(yè)，共52頁(yè)，2022年，5月20日，0點(diǎn)54分，星期一標(biāo)引加權(quán)檢索閾值的設(shè)定在檢索中，閾值有兩種設(shè)置方法：為每個(gè)檢索詞制定一個(gè)閾值，避免了次要內(nèi)容被檢出；給總的檢索結(jié)果指定一個(gè)閾值，保證了命中文獻(xiàn)的綜合相關(guān)度。41第41頁(yè)，共52頁(yè)，2022年，5月20日，0點(diǎn)54分，星期一4.3 全文檢索技術(shù)全文檢索，即檢索的數(shù)據(jù)源、檢索的對(duì)象、檢索匹配技術(shù)、檢索結(jié)果都是全文信息的檢索。全文檢索有兩種實(shí)現(xiàn)方式：對(duì)全文編索引；不對(duì)全文進(jìn)行任何加工處理，只是從前至后的逐字匹配。42第42頁(yè)，共52頁(yè)，2022年，5月20日

23、，0點(diǎn)54分，星期一4.3.1 全文檢索的技術(shù)指標(biāo)（1）索引膨脹系數(shù)索引的膨脹系數(shù)是指針對(duì)全文所建的索引文件大小與全文文件大小之比。索引膨脹系數(shù) =索引文件的大小/全文數(shù)據(jù)庫(kù)的大小全文索引需要以最小的標(biāo)引單位作為索引主鍵字，英語(yǔ)一般為單詞，中文則為單漢字。（2）檢索速度 43第43頁(yè)，共52頁(yè)，2022年，5月20日，0點(diǎn)54分，星期一4.3.2 全文檢索的實(shí)現(xiàn)全文檢索的實(shí)現(xiàn)通常用檢索詞對(duì)全文產(chǎn)生的詞（字）索引文檔的匹配。西文的全文檢索多數(shù)采用位置檢索技術(shù)，這樣可以提高全文檢索的查準(zhǔn)率。位置檢索分為四種級(jí)別：記錄級(jí)檢索、字段或段落級(jí)檢索或自然句級(jí)檢索、詞位置檢索。 44第44頁(yè)，共52頁(yè)，20

24、22年，5月20日，0點(diǎn)54分，星期一詞位置級(jí)檢索（1）詞位置順序相鄰（W）檢索時(shí)要求（W）兩邊的詞在原文中不能有其他單詞，并且次序不能顛倒。例如：？select information （W） retrieval可檢得含有固定詞組“information retrieval”的文獻(xiàn)全文。 45第45頁(yè)，共52頁(yè)，2022年，5月20日，0點(diǎn)54分，星期一詞位置級(jí)檢索（2）位置順序隔詞（nW） 表示由算符（nW）所連接的檢索詞之間最多只能含有n（n可以為0）個(gè)單詞，并且兩詞的順序不能顛倒。 例如：? select computer （1W） communication 其檢索式表示含有下述詞組的文獻(xiàn)都可作為檢索命中結(jié)果：computer communication；computer and communication；computer for communication。 46第46頁(yè)，共52頁(yè)，2022年，5月20日，0點(diǎn)54分，星期一詞位置級(jí)檢索（3）詞位置相鄰（N） 若文獻(xiàn)滿足由算符（N）構(gòu)成的檢索式，這些文獻(xiàn)中必須包含算符（N）兩側(cè)的詞，并且它們是緊連的，但兩詞的順序可以顛倒。 例如 ：? select computer （N） television其檢索結(jié)果是所有含有詞組“computer television”或“televisi