信息檢索技術(shù)

信息檢索技術(shù)1第1頁，課件共52頁，創(chuàng)作于2023年2月內(nèi)容提要倒排文檔檢索加權(quán)檢索全文檢索2第2頁，課件共52頁，創(chuàng)作于2023年2月4.1倒排文檔檢索3第3頁，課件共52頁，創(chuàng)作于2023年2月信息檢索系統(tǒng)的體系結(jié)構(gòu)文本數(shù)據(jù)庫數(shù)據(jù)庫管理建索引索引提問處理搜索排序排序后的文檔用戶反饋文本處理用戶界面檢出的文檔用戶需求文本提問邏輯視圖倒排文檔4第4頁，課件共52頁，創(chuàng)作于2023年2月建立索引的目的對文檔或文檔集合建立索引，以加快檢索速度倒排文檔（或倒排索引）是一種最常用的索引機制倒排文檔的索引對象是文檔或文檔集合中的單詞等。5第5頁，課件共52頁，創(chuàng)作于2023年2月在關(guān)系數(shù)據(jù)庫上建索引這種想法也被應(yīng)用于數(shù)據(jù)庫技術(shù)中，即對數(shù)據(jù)庫中需要經(jīng)常進(jìn)行檢索的域建立索引結(jié)構(gòu)，進(jìn)行快速的查詢。索引結(jié)構(gòu):hashing,B+-tree可以索引全部記錄，在全部記錄上進(jìn)行搜索精確地快速地查找地址姓名姓名索引查詢式:姓名

=“張三”張三哈爾濱工業(yè)大學(xué)張三6第6頁，課件共52頁，創(chuàng)作于2023年2月對文檔進(jìn)行索引索引結(jié)構(gòu):hashing,B+-trees,tries.可以進(jìn)行部分匹配:’%comput%’可以進(jìn)行短語搜索:查找包含“computergraphics”的文檔文檔索引D1D2D3computerD1,23,97,104D3,43graphicsD2,5D3,44“computer”在D1中出現(xiàn)的位置7第7頁，課件共52頁，創(chuàng)作于2023年2月倒排文檔組成倒排文檔一般由兩部分組成：詞匯表（vocabulary）和記錄表（postinglist）詞匯表是文本或文本集合中所包含的所有不同單詞的集合。對于詞匯表中的每一個單詞，其在文本中出現(xiàn)的位置或者其出現(xiàn)的文本編號構(gòu)成一個列表，所有這些列表的集合就稱為記錄表8第8頁，課件共52頁，創(chuàng)作于2023年2月一般的倒排索引索引文件可以用任何文件結(jié)構(gòu)來實現(xiàn)索引文件中的詞項是文檔集合中的詞表architecturecomputerdatabaseretrieval...D1,a1D1,a2D1,a3索引項/詞表索引/索引文件/索引數(shù)據(jù)庫Postings列表Q=term1,term2,term3,...附加信息例如：詞位置，出現(xiàn)次數(shù)9第9頁，課件共52頁，創(chuàng)作于2023年2月例子12345678910111213141516這是一本關(guān)于信息檢索的教材。介紹了檢索的基本技術(shù)?！夹g(shù)教材檢索信息…15,…8,…6,12,…5,……詞匯表Postinglist文本倒排文件10第10頁，課件共52頁，創(chuàng)作于2023年2月以文本為記錄表

記錄表既可以存儲文本中單詞的編號位置，也可以指向單詞首字母的字符位置，還可以是其所在的文本編號，下圖是一個以文本為記錄表的情況11第11頁，課件共52頁，創(chuàng)作于2023年2月距離約束：需要位置信息為記錄表常常需要知道鄰接條件，例如：“database”

后面緊跟著“systems”例如：短語搜索

“databasesystems”“database”和“systems”之間不能間隔超過3個詞“database”和“architecture”在同一個句子里需求擴展:倒排索引中保存著關(guān)鍵詞在文檔中的位置，文檔的組成單元(標(biāo)題,小標(biāo)題,句子分割標(biāo)記等)檢索算法和位置信息相關(guān)聯(lián)，并需檢查文檔的組成單元12第12頁，課件共52頁，創(chuàng)作于2023年2月以位置信息為記錄表保存段落、句子和詞的位置：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個詞13第13頁，課件共52頁，創(chuàng)作于2023年2月以權(quán)重信息為記錄表可保存出現(xiàn)頻率，以便支持基于統(tǒng)計的檢索:databasefilesystems...D345,10D348,20D350,1D123,82D128,8D345,12在D345中“systems”比“database”重要1.2倍Postings中的第二個單元可以是該term的權(quán)重(例如,

可以被歸一化在0和1之間)，或者是該term的出現(xiàn)頻率14第14頁，課件共52頁，創(chuàng)作于2023年2月同義詞擴展詞匯表同義詞對于提高召回率很有意義同義詞可以通過指針指向同一個postingslist....databasedatabasessystemsD345,2,3,5D348,37,5,9D350,8,12,1D123,5,4,3D128,25,1,12D345,2,3,6dataset15第15頁，課件共52頁，創(chuàng)作于2023年2月建立索引的過程16第16頁，課件共52頁，創(chuàng)作于2023年2月建立索引的過程識別文檔中的詞刪除停用詞(stopwords)提取詞干(stemming)用索引項的標(biāo)號代替詞干(stems)

統(tǒng)計詞干的數(shù)量(tf)(可選)

對低頻詞項使用同義詞詞典(thesaurus)(可選)

對高頻詞項構(gòu)成短語計算所有單個詞項、短語和語義類的權(quán)重17第17頁，課件共52頁，創(chuàng)作于2023年2月

英文詞根還原(Stemming)進(jìn)行詞根還原：stop/stops/stopping/stoppedstop好處：減少詞典量；壞處：按詞形查不到，詞根還原還可能出現(xiàn)錯誤不進(jìn)行詞根還原：Stoppedsto+ppe+d好處：支持詞形查詢；壞處：增加詞典量18第18頁，課件共52頁，創(chuàng)作于2023年2月

停用詞消除停用詞(stopwords)是指那些出現(xiàn)頻率高但是無重要意義，通常不會作為查詢詞出現(xiàn)的詞，如“的”、“地”、“得”、“都”、“是”等等消除：通常是通過查表的方式去除，去除的好處----大大較少索引量，壞處----有些平時的停用詞在某些上下文可能有意義保留：索引空間很大19第19頁，課件共52頁，創(chuàng)作于2023年2月建立索引的過程

–

舉例輸入文本Theanalysisof25indexingalgorithmshasnotproducedconsistentretrievalperformance.Thebestindexingtechniqueforretrievingdocumentsisnotknown刪除stopwordsanalysisindexingalgorithmsproducedconsistentretrievalperformancebestindexingtechniqueretrievingdocumentsknownStemminganalysisindexalgorithmproducconsistentretrievperformbestindextechniqueretrievdocumentknown轉(zhuǎn)換為索引編號123345110223443235652302566345432135657551128計算tf11011231345214321566175511128123021234413565243211計算詞項的權(quán)值(依賴于使用的模型)20第20頁，課件共52頁，創(chuàng)作于2023年2月檢索過程給定query對query進(jìn)行stemming，算法與對文檔的處理相同用索引編號代替stems計算所有queryterms的權(quán)重形成query向量（對VSM模型而言）計算query向量和文檔向量之間的相似度返回排序后的文檔集合21第21頁，課件共52頁，創(chuàng)作于2023年2月倒排索引上的布爾檢索一個布爾檢索包含n個用布爾操作連接的詞項

，例如：“computerANDnewsANDNOTnewsgroup”可以用括號來調(diào)整邏輯運算次序每個term從倒排索引中返回一個postingslist如果term不在任何文檔中出現(xiàn)，則postingslist為空檢索結(jié)果根據(jù)邏輯關(guān)系相結(jié)合：AND:集合做交運算OR:集合做并運算NOT:集合做差運算ABAandB22第22頁，課件共52頁，創(chuàng)作于2023年2月倒排索引上的布爾檢索查詢:中國

AND

文化查找Dictionary，定位中國;讀取對應(yīng)的postings.查找Dictionary，定位文化;讀取對應(yīng)的postings.“Merge”

合并(AND)兩個postings:12834248163264123581321中國文化23第23頁，課件共52頁，創(chuàng)作于2023年2月34128248163264123581321合并Lists的合并算法34248163264123581321中國文化28Ifthelistlengthsarexandy,themergetakesO(x+y)operations.Crucial:postingssortedbydocID.24第24頁，課件共52頁，創(chuàng)作于2023年2月倒排索引上的布爾檢索標(biāo)準(zhǔn)的優(yōu)化技術(shù)應(yīng)用：從最短的postinglist開始做“與”操作，保證中間結(jié)果越小越好“網(wǎng)絡(luò)”

AND“病毒”

AND“蠕蟲”從哪個詞項開始做交運算呢？顯然是：“病毒”和“蠕蟲”25第25頁，課件共52頁，創(chuàng)作于2023年2月倒排索引的優(yōu)點快速索引

(長query需要更多時間)靈活性:不同類型的信息都可以存儲在postingslist中如果存儲了足夠多的信息，則可以支持復(fù)雜的檢索操作例如：如果記錄了詞在文檔中的準(zhǔn)確位置，就可以支持短語檢索，或模糊檢索26第26頁，課件共52頁，創(chuàng)作于2023年2月倒排索引的缺點很大的存儲開銷50%-150%-300%更新、插入和刪除都需要很高的維護(hù)開銷，倒排索引相對靜態(tài)的環(huán)境(很少插入和更新)中使用比較好處理開銷隨著布爾操作的增加而增長由于postings越來越多(例如引入同義詞)，導(dǎo)致索引檢索的代價越來越大，需要對位置進(jìn)行很多處理(例如短語匹配)27第27頁，課件共52頁，創(chuàng)作于2023年2月倒排文檔中研究的問題倒排文檔的壓縮倒排文檔的刪除倒排文檔的插入28第28頁，課件共52頁，創(chuàng)作于2023年2月

索引壓縮理論上，(全文)索引的大小和原始文件相當(dāng)，因為每個詞的每次出現(xiàn)都必須在postinglist中記錄。需不需要壓縮？要壓縮：索引大小通常和原始文本大小相當(dāng)，不壓縮可能會耗費大量存儲開銷不壓縮：硬盤很便宜，數(shù)據(jù)量不是特別大，而且不需要解壓縮的消耗29第29頁，課件共52頁，創(chuàng)作于2023年2月

倒排索引的更新情況一：出現(xiàn)了新的詞，則需要修改詞典結(jié)構(gòu)，在詞典中增加詞條。情況二：出現(xiàn)了新的文檔，則在相應(yīng)的詞條下增加postinglist。情況三：某些文檔不復(fù)存在，則在相應(yīng)的位置進(jìn)行標(biāo)記，等積累到一定時期進(jìn)行一次性操作。30第30頁，課件共52頁，創(chuàng)作于2023年2月

詞匯表的組織順序排序數(shù)組：采用字典序，查找采用二分法。空間消耗小，查找較快，但是插入刪除麻煩。二叉搜索樹、B樹、Trie樹等。Hash表：通過Hash函數(shù)直接把詞映射到地址，空間消耗和Hash函數(shù)設(shè)計有關(guān)。較快，插入刪除容易。31第31頁，課件共52頁，創(chuàng)作于2023年2月4.2加權(quán)檢索加權(quán)檢索根據(jù)每個詞在檢索要求中的重要程度不同，分別給予一定的數(shù)值（權(quán)值）加以區(qū)別，同時利用給出的檢索命中界限值（閾值，Threshold）限定檢索結(jié)果的輸出。加權(quán)檢索是布爾邏輯檢索的一種擴充，把量化思想引入定性檢索中。加權(quán)檢索分為標(biāo)引加權(quán)和檢索加權(quán)兩種類型。32第32頁，課件共52頁，創(chuàng)作于2023年2月4.2.1檢索詞賦權(quán)檢索對每一檢索詞給定一權(quán)值，代表其重要性。檢索時，對存在的檢索詞的記錄計算其權(quán)值總和。當(dāng)權(quán)值總和大于閾值時，則認(rèn)為命中。最簡單、最容易實現(xiàn)的加權(quán)檢索系統(tǒng)。33第33頁，課件共52頁，創(chuàng)作于2023年2月舉例一個企業(yè)管理者為了改進(jìn)企業(yè)管理模式，接受新的管理理念，提高企業(yè)的競爭力，希望獲取知識管理、競爭情報、企業(yè)文化方面的文獻(xiàn)資料，用加權(quán)法列出的提問式如下：

W=知識管理（4）競爭情報（2）企業(yè)文化（1）表中“√”表示相應(yīng)檢索詞與文獻(xiàn)中主題詞匹配，若設(shè)定閾值為4，由上表可知，組合1至4為命中文獻(xiàn)。34第34頁，課件共52頁，創(chuàng)作于2023年2月檢索詞賦權(quán)檢索的優(yōu)缺點檢索詞賦權(quán)檢索的優(yōu)點：明確了檢索詞在檢索中的重要程度；通過提高或降低閾值來擴大和縮小檢索輸出的范圍；檢索結(jié)果按符合檢索需求的重要程度順序排列。檢索詞賦權(quán)檢索的缺點：加權(quán)法提問式表達(dá)不如邏輯式直觀；權(quán)值的確定較為困難。35第35頁，課件共52頁，創(chuàng)作于2023年2月4.2.2加權(quán)標(biāo)引加權(quán)標(biāo)引是指在對文獻(xiàn)進(jìn)行標(biāo)引時，根據(jù)每個標(biāo)引詞在文獻(xiàn)中的重要程度不同，為它們附上不同的權(quán)值，檢索時通過對檢索詞的標(biāo)引權(quán)值相加來篩選命中記錄。36第36頁，課件共52頁，創(chuàng)作于2023年2月加權(quán)標(biāo)引在進(jìn)行加權(quán)標(biāo)引時，對反映文獻(xiàn)主要內(nèi)容的標(biāo)引詞給予高權(quán)值，反映文獻(xiàn)次要內(nèi)容的標(biāo)引詞給予較低的權(quán)值。詞頻加權(quán)檢索方法應(yīng)建立在對全文數(shù)據(jù)庫和文摘數(shù)據(jù)庫基礎(chǔ)之上，否則詞頻加權(quán)將失去意義。37第37頁，課件共52頁，創(chuàng)作于2023年2月簡單詞頻加權(quán)簡單詞頻加權(quán)檢索：指檢索時累計檢索詞在記錄中出現(xiàn)的次數(shù)來決定記錄的權(quán)值。最大缺點就是不論文章長短、詞頻高低都采用的是統(tǒng)一的詞頻標(biāo)準(zhǔn)。38第38頁，課件共52頁，創(chuàng)作于2023年2月相對詞頻加權(quán)檢索將每一個檢索詞在本文中頻率和在整個數(shù)據(jù)庫中的頻率綜合考慮，進(jìn)行加權(quán)檢索的方法。文內(nèi)頻率=指定詞在本文中的頻次/該文本詞匯總頻次文外頻率=指定詞在本文中的頻次/該詞在整個數(shù)據(jù)庫(所有文獻(xiàn))中總次數(shù)文內(nèi)頻率解決了短文章中詞頻過低的問題，文外頻率解決了新詞、專用詞的低頻問題。39第39頁，課件共52頁，創(chuàng)作于2023年2月4.2.3標(biāo)引加權(quán)的檢索過程檢索時給出檢索詞和檢索閾值，對滿足檢索閾值的檢索結(jié)果按其權(quán)值之和從大到小輸出來篩選命中記錄。在實際的人工標(biāo)引中尚未見有加權(quán)標(biāo)引的系統(tǒng)。在計算機自動標(biāo)引的系統(tǒng)中，可以方便而有效的采用加權(quán)標(biāo)引技術(shù)。40第40頁，課件共52頁，創(chuàng)作于2023年2月標(biāo)引加權(quán)檢索閾值的設(shè)定在檢索中，閾值有兩種設(shè)置方法：為每個檢索詞制定一個閾值，避免了次要內(nèi)容被檢出；給總的檢索結(jié)果指定一個閾值，保證了命中文獻(xiàn)的綜合相關(guān)度。41第41頁，課件共52頁，創(chuàng)作于2023年2月4.3全文檢索技術(shù)全文檢索，即檢索的數(shù)據(jù)源、檢索的對象、檢索匹配技術(shù)、檢索結(jié)果都是全文信息的檢索。全文檢索有兩種實現(xiàn)方式：對全文編索引；不對全文進(jìn)行任何加工處理，只是從前至后的逐字匹配。42第42頁，課件共52頁，創(chuàng)作于2023年2月4.3.1全文檢索的技術(shù)指標(biāo)（1）索引膨脹系數(shù)索引的膨脹系數(shù)是指針對全文所建的索引文件大小與全文文件大小之比。索引膨脹系數(shù)=索引文件的大小/全文數(shù)據(jù)庫的大小全文索引需要以最小的標(biāo)引單位作為索引主鍵字，英語一般為單詞，中文則為單漢字。（2）檢索速度43第43頁，課件共52頁，創(chuàng)作于2023年2月4.3.2全文檢索的實現(xiàn)全文檢索的實現(xiàn)通常用檢索詞對全文產(chǎn)生的詞（字）索引文檔的匹配。西文的全文檢索多數(shù)采用位置檢索技術(shù)，這樣可以提高全文檢索的查準(zhǔn)率。位置檢索分為四種級別：記錄級檢索、字段或段落級檢索或自然句級檢索、詞位置檢索。44第44頁，課件共52頁，創(chuàng)作于2023年2月詞位置級檢索（1）詞位置順序相鄰（W）檢索時要求（W）兩邊的詞在原文中不能有其他單詞，并且次序不能顛倒。例如：？selectinformation（W）retrieval可檢得含有固定詞組“informationretrieval”的文獻(xiàn)全文。45第45頁，課件共52頁，創(chuàng)作于2023年2月詞位置級檢索（2）位置順序隔詞（nW）表示由算符（nW）所連接的檢索詞之間最多只能含有n（n可以為0）個單詞，并且兩詞的順序不能顛倒。例如：：?selectcomputer（1W）communication

其檢索式表示含有下述詞組的文獻(xiàn)都可作為檢索命中結(jié)果：computercommunication；computerandcommunication；computerforcommunication。

46第46頁，課件共52頁，創(chuàng)作于2023年2月詞位置級檢索（3）詞位置相鄰（N）若文獻(xiàn)滿足由算符（N）構(gòu)成的檢索式，這些文獻(xiàn)中必須包含算符（N）兩側(cè)的詞，并且它們是緊連的，但兩詞的順序可以顛倒。例如：?selectcomputer（N）television其檢索結(jié)果是所有含有詞組“computertel