詞典及容錯(cuò)式檢索課件

IntroductiontoInformationRetrieval

現(xiàn)代信息檢索中國(guó)科學(xué)院大學(xué)2019年秋季課程《現(xiàn)代信息檢索》更新時(shí)間：ModernInformationRetrieval第3講詞典及容錯(cuò)式檢索Dictionaryandtolerantretrieval12019/8/6IntroductiontoInformationRe2提綱上一講回顧詞典通配查詢(xún)編輯距離拼寫(xiě)校正Soundex22提綱上一講回顧2提綱上一講回顧詞典通配查詢(xún)編輯距離拼寫(xiě)校正Soundex3提綱上一講回顧3

現(xiàn)代信息檢索上一講內(nèi)容文檔詞條/詞項(xiàng)基于跳表指針的合并短語(yǔ)查詢(xún)的處理(雙詞索引和位置索引)4現(xiàn)代信息檢索上一講內(nèi)容文檔4

現(xiàn)代信息檢索文檔索引的基本單位與文件不是一回事，嚴(yán)格地說(shuō)，一篇文檔可能包含多個(gè)文件，也可能一個(gè)文件包含多篇文檔依賴(lài)于具體應(yīng)用句子級(jí)檢索：一個(gè)句子為一篇文檔段落級(jí)檢索：一段文本為一篇文檔……5現(xiàn)代信息檢索文檔索引的基本單位56詞類(lèi)(type)/詞條(token)的區(qū)別詞條(Token)–詞或者詞項(xiàng)在文檔中出現(xiàn)的實(shí)例，出現(xiàn)多次算多個(gè)詞條詞類(lèi)(Type)–多個(gè)詞條構(gòu)成的等價(jià)類(lèi)(equivalenceclass)集合InJune,thedoglikestochasethecatinthebarn.12個(gè)詞條,9個(gè)詞類(lèi)詞類(lèi)經(jīng)過(guò)一些處理(去除停用詞、歸一化)之后，最后用于索引的稱(chēng)為為詞項(xiàng)66詞類(lèi)(type)/詞條(token)的區(qū)別詞條(Token77詞條化中考慮的問(wèn)題詞之間的邊界是什么？空格？撇號(hào)還是連接符？上述邊界不一定是真正的邊界(比如,中文)另外荷蘭語(yǔ)、德語(yǔ)、瑞典語(yǔ)復(fù)合詞中間沒(méi)有空格

(Lebensversicherungsgesellschaftsangestellter)777詞條化中考慮的問(wèn)題詞之間的邊界是什么？空格？撇號(hào)還是連接88詞項(xiàng)歸一化中的問(wèn)題詞項(xiàng)實(shí)際上是一系列詞條組成的等價(jià)類(lèi)如何定義等價(jià)類(lèi)？數(shù)字(3/20/91vs.20/3/91)大小寫(xiě)問(wèn)題詞干還原，Porter工具形態(tài)分析:屈折vs.派生其他語(yǔ)言中詞項(xiàng)歸一化的問(wèn)題比英語(yǔ)中形態(tài)更復(fù)雜芬蘭語(yǔ):單個(gè)動(dòng)詞可能有12,000個(gè)不同的形式differentforms重音符號(hào)、元音變音問(wèn)題（umlauts，由于一個(gè)音被另一個(gè)音詞化而導(dǎo)致的變化，尤其是元音的變化）888詞項(xiàng)歸一化中的問(wèn)題詞項(xiàng)實(shí)際上是一系列詞條組成的等價(jià)類(lèi)899跳表指針999跳表指針91010位置(信息)索引10在無(wú)位置信息索引中，每條倒排記錄只是一個(gè)docID在位置信息索引中，每條倒排記錄是一個(gè)docID加上一個(gè)位置信息表一個(gè)查詢(xún)的例子:

“to1be2or3not4to5be6”TO,993427:?1:?7,18,33,72,86,231?;2:?1,17,74,222,255?;

4:?8,16,190,429,433?;5:?363,367?;7:?13,23,191?;...?BE,178239:?1:?17,25?;

4:?17,191,291,430,434?;5:?14,19,101?;...?第4篇文檔能夠與查詢(xún)匹配！1010位置(信息)索引10在無(wú)位置信息索引中，每條倒排記錄1111位置信息索引基于位置信息索引，能夠處理短語(yǔ)查詢(xún)(phrasequery)，也能處理鄰近式查詢(xún)(proximityquery)111111位置信息索引基于位置信息索引，能夠處理短語(yǔ)查詢(xún)(ph1212本講內(nèi)容詞典的數(shù)據(jù)結(jié)構(gòu)：訪問(wèn)效率和支持查找的方式容錯(cuò)式檢索(Tolerantretrieval):如果查詢(xún)?cè)~項(xiàng)和文檔詞項(xiàng)不能精確匹配時(shí)如何處理？通配查詢(xún)：包含通配符*的查詢(xún)拼寫(xiě)校正：查詢(xún)中存在錯(cuò)誤時(shí)的處理121212本講內(nèi)容詞典的數(shù)據(jù)結(jié)構(gòu)：訪問(wèn)效率和支持查找的方式1213提綱上一講回顧詞典通配查詢(xún)編輯距離拼寫(xiě)校正Soundex1313提綱上一講回顧1314倒排索引對(duì)每個(gè)詞項(xiàng)t,保存所有包含t的

文檔列表14詞典(dictionary)倒排記錄表(postinglist)詞典(dictionary)倒排記錄表(postings)14倒排索引對(duì)每個(gè)詞項(xiàng)t,保存所有包含t的文檔列表14詞1515詞典詞典是指存儲(chǔ)詞項(xiàng)詞匯表的數(shù)據(jù)結(jié)構(gòu)詞項(xiàng)詞匯表(Termvocabulary):指的是具體數(shù)據(jù)詞典(Dictionary):指的是數(shù)據(jù)結(jié)構(gòu)151515詞典詞典是指存儲(chǔ)詞項(xiàng)詞匯表的數(shù)據(jù)結(jié)構(gòu)151616采用定長(zhǎng)數(shù)組的詞典結(jié)構(gòu)對(duì)每個(gè)詞項(xiàng)，需要存儲(chǔ):文檔頻率(DocumentFrequency,DF)指向倒排記錄表的指針...暫定每條詞項(xiàng)的上述信息均采用定長(zhǎng)的方式存儲(chǔ)假定所有詞項(xiàng)的信息采用數(shù)組存儲(chǔ)161616采用定長(zhǎng)數(shù)組的詞典結(jié)構(gòu)對(duì)每個(gè)詞項(xiàng)，需要存儲(chǔ):161717采用定長(zhǎng)數(shù)組的詞典結(jié)構(gòu)

空間消耗:20字節(jié)4字節(jié)4字節(jié)171717采用定長(zhǎng)數(shù)組的詞典結(jié)構(gòu)

現(xiàn)代信息檢索詞項(xiàng)定位(即查詞典)在詞典中查找給定關(guān)鍵字輸入“信息”，如何在詞典中快速找到這個(gè)詞？很多詞典應(yīng)用中的基本問(wèn)題。以下介紹支持快速查找的詞典數(shù)據(jù)結(jié)構(gòu)。18信息數(shù)據(jù)挖掘1819202122現(xiàn)代信息檢索詞項(xiàng)定位(即查詞典)在詞典中查找給定關(guān)鍵字119用于詞項(xiàng)定位的數(shù)據(jù)結(jié)構(gòu)主要有兩種數(shù)據(jù)結(jié)構(gòu):哈希表和樹(shù)有些IR系統(tǒng)用哈希表，有些系統(tǒng)用樹(shù)結(jié)構(gòu)采用哈希表或樹(shù)的準(zhǔn)則:詞項(xiàng)數(shù)目是否固定或者說(shuō)詞項(xiàng)數(shù)目是否持續(xù)增長(zhǎng)？詞項(xiàng)的相對(duì)訪問(wèn)頻率如何？詞項(xiàng)的數(shù)目有多少？1919用于詞項(xiàng)定位的數(shù)據(jù)結(jié)構(gòu)主要有兩種數(shù)據(jù)結(jié)構(gòu):哈希表和樹(shù)1

現(xiàn)代信息檢索哈希表20信息數(shù)據(jù)挖掘哈希函數(shù)，輸入詞項(xiàng)，輸出正整數(shù)(通常是地址)f(信息)=18,f(數(shù)據(jù))=19，f(挖掘)=191819202122現(xiàn)代信息檢索哈希表20信息數(shù)據(jù)挖掘哈希函數(shù)，輸入詞項(xiàng)，輸21哈希表(HashTable)每個(gè)詞項(xiàng)通過(guò)哈希函數(shù)映射成一個(gè)整數(shù)盡可能避免沖突查詢(xún)處理時(shí)：對(duì)查詢(xún)?cè)~項(xiàng)進(jìn)行哈希，如果有沖突，則解決沖突，最后在定長(zhǎng)數(shù)組中定位優(yōu)點(diǎn):在哈希表中的定位速度快于樹(shù)中的定位速度查詢(xún)時(shí)間是常數(shù)缺點(diǎn)：無(wú)法處理詞項(xiàng)的微小變形(resumevs.résumé)不支持前綴搜索(比如所有以automat開(kāi)頭的詞項(xiàng))如果詞匯表不斷增大，需要定期對(duì)所有詞項(xiàng)重新哈希2121哈希表(HashTable)每個(gè)詞項(xiàng)通過(guò)哈希函數(shù)映射成2222樹(shù)(Tree)樹(shù)可以支持前綴查找(相當(dāng)于對(duì)詞典再建一層索引)最簡(jiǎn)單的樹(shù)結(jié)構(gòu)：二叉樹(shù)搜索速度略低于哈希表方式：

O(logM),其中

M

是詞匯表大小，即所有詞項(xiàng)的數(shù)目O(logM)僅僅對(duì)平衡樹(shù)成立使二叉樹(shù)重新保持平衡開(kāi)銷(xiāo)很大B-樹(shù)能夠減輕上述問(wèn)題B-樹(shù)定義：每個(gè)內(nèi)部節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)目在[a,b]之間，其中a,b

為合適的正整數(shù),e.g.,[2,4].222222樹(shù)(Tree)樹(shù)可以支持前綴查找(相當(dāng)于對(duì)詞典再建一2323二叉樹(shù)232323二叉樹(shù)232424B-樹(shù)242424B-樹(shù)2425提綱上一講回顧詞典通配查詢(xún)編輯距離拼寫(xiě)校正Soundex2525提綱上一講回顧2526通配查詢(xún)通配查詢(xún)：包含通配符的查詢(xún)，例如：mon*:找出所有包含以mon開(kāi)頭的詞項(xiàng)的文檔

符合條件的詞項(xiàng)有：Monday,monster,monitor等*mon:找出所有包含以mon結(jié)尾的詞項(xiàng)的文檔符合條件的詞項(xiàng)有：summon,common,cinnamon等2626通配查詢(xún)通配查詢(xún)：包含通配符的查詢(xún)，例如：2627通配查詢(xún)的處理mon*:找出所有包含以mon開(kāi)頭的詞項(xiàng)的文檔如果采用B-樹(shù)詞典結(jié)構(gòu)，那么實(shí)現(xiàn)起來(lái)非常容易，只需要返回區(qū)間mon≤t<moo上的詞項(xiàng)t2727通配查詢(xún)的處理mon*:找出所有包含以mon開(kāi)頭的詞28通配查詢(xún)的處理*mon:找出所有包含以mon結(jié)尾的詞項(xiàng)的文檔將所有的詞項(xiàng)倒轉(zhuǎn)過(guò)來(lái)，然后基于它們建一棵附加的樹(shù)返回區(qū)間nom≤t<non上的詞項(xiàng)t比如有以下四個(gè)詞：absurd,Monday,monster,zoo全部倒轉(zhuǎn)過(guò)來(lái)：drusba,yadnom,retsnom,ooz然后基于倒轉(zhuǎn)過(guò)來(lái)的詞項(xiàng)再建一顆B樹(shù)也就說(shuō)，通過(guò)上述數(shù)據(jù)結(jié)構(gòu)，可能得到滿足通配查詢(xún)的一系列詞項(xiàng)，然后返回任一詞項(xiàng)的文檔2828通配查詢(xún)的處理*mon:找出所有包含以mon結(jié)尾的詞項(xiàng)2929詞項(xiàng)中間的*號(hào)處理例子:m*nchen在B-樹(shù)中分別查找滿足m*和*nchen的詞項(xiàng)集合，然后求交集這種做法開(kāi)銷(xiāo)很大另外一種方法:輪排(permuterm)索引基本思想：將每個(gè)通配查詢(xún)旋轉(zhuǎn)，使*出現(xiàn)在末尾將每個(gè)旋轉(zhuǎn)后的結(jié)果存放在詞典中，即B-樹(shù)中292929詞項(xiàng)中間的*號(hào)處理例子:m*nchen293030輪排索引對(duì)于詞項(xiàng)hello:將hello$,ello$h,llo$he,lo$hel,o$hell

和$hello加入到B-樹(shù)中，其中$是一個(gè)特殊符號(hào)(表示結(jié)尾)即在詞項(xiàng)前面再加一層索引該索引采用B-樹(shù)來(lái)組織該索引葉節(jié)點(diǎn)是詞項(xiàng)的各種變形303030輪排索引對(duì)于詞項(xiàng)hello:將hello$,e3131輪排結(jié)果→詞項(xiàng)的映射示意圖313131輪排結(jié)果→詞項(xiàng)的映射示意圖313232輪排索引對(duì)于hello，已經(jīng)存儲(chǔ)了

hello$,ello$h,llo$he,lo$hel,

o$hell和$hello查詢(xún)對(duì)于X,查詢(xún)X$對(duì)于X*,查詢(xún)$X*對(duì)于*X,查詢(xún)X$*對(duì)于*X*,查詢(xún)X*，比如*ello*，則只需要查到ello開(kāi)頭的串即可(上面是ello$h)，因?yàn)榇藭r(shí)ello右部一定包含一個(gè)$，$結(jié)不結(jié)尾的串均能滿足查詢(xún)*X*，對(duì)于X*Y,查詢(xún)Y$X*例子:假定通配查詢(xún)?yōu)閔el*o,那么相當(dāng)于要查詢(xún)o$hel*輪排索引稱(chēng)為輪排樹(shù)更恰當(dāng)?shù)禽喤潘饕姆Q(chēng)呼已經(jīng)使用非常普遍323232輪排索引對(duì)于hello，已經(jīng)存儲(chǔ)了hello$,

現(xiàn)代信息檢索輪排索引小結(jié)33……傳統(tǒng)倒排索引(詞項(xiàng)文檔)輪排索引(通配查詢(xún)?cè)~項(xiàng)，采用B樹(shù)來(lái)組織)現(xiàn)代信息檢索輪排索引小結(jié)33……傳統(tǒng)倒排索引(詞項(xiàng)文34使用輪排索引的查找過(guò)程將查詢(xún)進(jìn)行旋轉(zhuǎn)，將通配符旋轉(zhuǎn)到右部同以往一樣查找B-樹(shù)，得到匹配的所有詞項(xiàng)，將這些詞項(xiàng)對(duì)應(yīng)的倒排記錄表取出問(wèn)題：相對(duì)于通常的B-樹(shù)，輪排索引(輪排樹(shù))的空間要大4倍以上(經(jīng)驗(yàn)值)3434使用輪排索引的查找過(guò)程將查詢(xún)進(jìn)行旋轉(zhuǎn)，將通配符旋轉(zhuǎn)到右部3535k-gram索引比輪排索引空間開(kāi)銷(xiāo)要小枚舉一個(gè)詞項(xiàng)中所有連讀的k個(gè)字符構(gòu)成k-gram

。2-gram稱(chēng)為二元組(bigram)3-gram稱(chēng)為三元組(trigram)例子:Aprilisthecruelestmonth

2-gram:$aapprriill$$iiss$$tthhee$$ccrruueelleesstt$$mmoonnth$同前面一樣，$是一個(gè)特殊字符，表示單詞開(kāi)始或結(jié)束353535k-gram索引比輪排索引空間開(kāi)銷(xiāo)要小353636k-gram索引36構(gòu)建一個(gè)倒排索引，此時(shí)詞典部分是所有的k-gram，倒排記錄表部分是包含某個(gè)k-gram的所有詞項(xiàng)相當(dāng)于對(duì)詞項(xiàng)再構(gòu)建一個(gè)倒排索引(二級(jí)索引)3636k-gram索引36構(gòu)建一個(gè)倒排索引，此時(shí)詞典部分是3737k-gram(bigram,trigram,...)索引需要注意的是，這里有兩個(gè)倒排索引詞典-文檔的倒排索引基于詞項(xiàng)返回文檔而k-gram索引用于查找詞項(xiàng)，即基于查詢(xún)所包含的k-gram來(lái)查找所有的詞項(xiàng)373737k-gram(bigram,trigram,.3838利用2-gram索引處理通配符查詢(xún)例子：查詢(xún)mon*先執(zhí)行布爾查詢(xún):$mANDmoANDon該布爾查詢(xún)會(huì)返回所有以前綴mon開(kāi)始的詞項(xiàng)......當(dāng)然也可能返回許多偽正例(falsepositives)，比如MOON。同前面的雙詞索引處理短語(yǔ)查詢(xún)一樣，滿足布爾查詢(xún)只是滿足原始查詢(xún)的必要條件。因此，必須要做后續(xù)的過(guò)濾處理剩下的詞項(xiàng)將在詞項(xiàng)-文檔倒排索引中查找文檔k-gram索引vs.輪排索引k-gram索引的空間消耗小輪排索引不需要進(jìn)行后過(guò)濾383838利用2-gram索引處理通配符查詢(xún)例子：查詢(xún)mon*3939課堂練習(xí)Google對(duì)通配符查詢(xún)的支持極其有限比如：在Google中查詢(xún)

[gen*universit*]意圖：想查UniversityofGeneva,但是不知道如何拼寫(xiě)，特別是法語(yǔ)中的拼寫(xiě)按照Google自己的說(shuō)法,2010-04-29:“*操作符只能作為一個(gè)整體單詞使用，而不能作為單詞的一部分使用”但是這點(diǎn)并不完全對(duì)，嘗試一下[pythag*]和[m*nchen]問(wèn)題:為什么Google對(duì)通配查詢(xún)并不充分支持？393939課堂練習(xí)Google對(duì)通配符查詢(xún)的支持極其有限394040原因問(wèn)題1:一條通配符查詢(xún)往往相當(dāng)于執(zhí)行非常多的布爾查詢(xún)對(duì)于[gen*universit*]:genevauniversityORgenevauniversitéORgenèveuniversityORgenèveuniversitéORgeneraluniversitiesOR...開(kāi)銷(xiāo)非常大問(wèn)題2:用戶(hù)不愿意敲擊更多的鍵盤(pán)如果允許[pyth*theo*]代替[pythagoras’theorem]的話，用戶(hù)會(huì)傾向于使用前者這樣會(huì)大大加重搜索引擎的負(fù)擔(dān)GoogleSuggest是一種減輕用戶(hù)輸入負(fù)擔(dān)的好方法404040原因問(wèn)題1:一條通配符查詢(xún)往往相當(dāng)于執(zhí)行非常多的41提綱上一講回顧詞典通配查詢(xún)編輯距離拼寫(xiě)校正Soundex4141提綱上一講回顧41

現(xiàn)代信息檢索拼寫(xiě)錯(cuò)誤的查詢(xún)用戶(hù)想查information，但是錯(cuò)誤地輸入了informaton于是，我們?cè)噲D將informatoninformation需要使用拼寫(xiě)校正技術(shù)42現(xiàn)代信息檢索拼寫(xiě)錯(cuò)誤的查詢(xún)用戶(hù)想查information43拼寫(xiě)校正兩個(gè)主要用途糾正待索引文檔糾正用戶(hù)的查詢(xún)兩種拼寫(xiě)校正的方法詞獨(dú)立(Isolatedword)法只檢查每個(gè)單詞本身的拼寫(xiě)錯(cuò)誤如果某個(gè)單詞拼寫(xiě)錯(cuò)誤后變成另外一個(gè)單詞，則無(wú)法查出,e.g.,anasteroidthatfellformthesky上下文敏感(Context-sensitive)法糾錯(cuò)時(shí)要考慮周?chē)膯卧~能糾正上例中的錯(cuò)誤

form/from4343拼寫(xiě)校正兩個(gè)主要用途434444關(guān)于文檔校正本課當(dāng)中我們不關(guān)心文檔的拼寫(xiě)校正問(wèn)題(e.g.,MSWord)在IR領(lǐng)域,我們主要對(duì)OCR處理后的文檔進(jìn)行拼寫(xiě)校正處理.(OCR=opticalcharacterrecognition，光學(xué)字符識(shí)別)IR領(lǐng)域的一般做法是：不改變文檔444444關(guān)于文檔校正本課當(dāng)中我們不關(guān)心文檔的拼寫(xiě)校正問(wèn)題(4545查詢(xún)校正第一種方法:詞獨(dú)立(isolatedword)法假設(shè)1:對(duì)需要糾錯(cuò)的詞存在一系列“正確單詞形式”假設(shè)2:需要提供存在錯(cuò)誤拼寫(xiě)的單詞和正確單詞之間的距離計(jì)算方式簡(jiǎn)單的拼寫(xiě)校正算法:返回與錯(cuò)誤單詞具有最小距離的”正確”單詞例子:informaton→information可以將詞匯表中所有的單詞都作為候選的“正確”單詞454545查詢(xún)校正第一種方法:詞獨(dú)立(isolatedwo4646幾種可用的詞匯表采用標(biāo)準(zhǔn)詞典(韋伯詞典,牛津詞典等等)采用領(lǐng)域詞典(面向特定領(lǐng)域的IR系統(tǒng))采用文檔集上的詞項(xiàng)詞匯表(可以通過(guò)統(tǒng)計(jì)得到)，但是每個(gè)詞項(xiàng)均帶有權(quán)重464646幾種可用的詞匯表采用標(biāo)準(zhǔn)詞典(韋伯詞典,牛津詞典4747單詞間距離的計(jì)算以下將介紹幾種計(jì)算方法編輯距離(Editdistance或者Levenshteindistance)帶權(quán)重的編輯距離k-gram重疊率474747單詞間距離的計(jì)算以下將介紹幾種計(jì)算方法474848編輯距離兩個(gè)字符串s1和s2編輯距離是指從

s1

轉(zhuǎn)換成s2所需要的最少的基本操作數(shù)目Levenshtein距離:采用的基本操作是插入(insert)、刪除(delete)和替換(replace)Levenshtein距離dog-do:1Levenshtein距離

cat-cart:1Levenshtein距離

cat-cut:1Levenshtein距離

cat-act:2Damerau-Levenshtein距離：除了上述三種基本操作外，還包括兩個(gè)字符之間的交換（transposition）操作Damerau-Levenshtein距離cat-act:1484848編輯距離兩個(gè)字符串s1和s2編輯距離是指從s1轉(zhuǎn)

現(xiàn)代信息檢索VladimirIosifovich

Levenshtein俄羅斯科學(xué)家(1935-)研究信息論、糾錯(cuò)理論畢業(yè)于莫斯科國(guó)立大學(xué)1965年提出Levenshtein距離2006年獲得IEEERichardW.HammingMedal49現(xiàn)代信息檢索VladimirIosifovich

Le50Levenshtein距離:計(jì)算50fast中的f、s、t分別用c、t、s替換，即可得到cats，所以代價(jià)是3，即距離是3。50Levenshtein距離:計(jì)算50fast中的f、s5151Levenshtein距離:算法51(i-1,j-1)(i-1,j)(i,j-1)(i,j)5151Levenshtein距離:算法51(i-1,j-5252Levenshtein距離:算法52左鄰居(i-1,j-1)(i-1,j)(i,j-1)(i,j)5252Levenshtein距離:算法52左鄰居(i-15353Levenshtein距離:算法53上鄰居(i-1,j-1)(i-1,j)(i,j-1)(i,j)5353Levenshtein距離:算法53上鄰居(i-15454Levenshtein距離:算法54左上鄰居(i-1,j-1)(i-1,j)(i,j-1)(i,j)5454Levenshtein距離:算法54左上鄰居(i-5555Levenshtein距離:算法55左上鄰居(i-1,j-1)(i-1,j)(i,j-1)(i,j)5555Levenshtein距離:算法55左上鄰居(i-5656Levenshtein距離:例子56CopyReplacedeleteinsert5656Levenshtein距離:例子56Copyde5757Levenshtein矩陣中每個(gè)單元包含4個(gè)元素57從左上角鄰居到來(lái)的開(kāi)銷(xiāo)

(copy或replace)從上方鄰居到來(lái)的代價(jià)(delete)從左方鄰居到來(lái)的代價(jià)

(insert)上述三者之中最低的代價(jià)5757Levenshtein矩陣中每個(gè)單元包含4個(gè)元素575858Levenshtein距離:例子585858Levenshtein距離:例子585959動(dòng)態(tài)規(guī)劃算法(Cormenetal.)最優(yōu)子結(jié)構(gòu):最優(yōu)的問(wèn)題解決方案中包括子解決方案，及子問(wèn)題的最優(yōu)解決方案（兩點(diǎn)最短路徑問(wèn)題最典型的解法就是動(dòng)態(tài)規(guī)劃算法）重疊的子解決方案Overlappingsubsolutions:子解決方案中有重疊，如果采用暴力計(jì)算方法(窮舉法)，子解決方案將會(huì)被反復(fù)計(jì)算，從而使得計(jì)算開(kāi)銷(xiāo)很大.編輯距離計(jì)算中的子問(wèn)題:兩個(gè)前綴之間的編輯距離計(jì)算595959動(dòng)態(tài)規(guī)劃算法(Cormenetal.)最優(yōu)子結(jié)構(gòu)6060帶權(quán)重的編輯距離思路：對(duì)不同的字符進(jìn)行操作時(shí)權(quán)重不同希望能更敏銳地捕捉到鍵盤(pán)輸入的錯(cuò)誤,e.g.,m

更可能被輸成n

而不是

q因此，將

m

替換為

n

的編輯距離將低于替換為q的距離也就是輸入的操作代價(jià)矩陣是一個(gè)帶權(quán)重的矩陣對(duì)上述動(dòng)態(tài)規(guī)劃算法進(jìn)行修改便可以處理權(quán)重計(jì)算606060帶權(quán)重的編輯距離思路：對(duì)不同的字符進(jìn)行操作時(shí)權(quán)重不6161利用編輯距離進(jìn)行拼寫(xiě)校正給定查詢(xún)?cè)~，窮舉詞匯表中和該查詢(xún)的編輯距離(或帶權(quán)重的編輯聚類(lèi))低于某個(gè)預(yù)定值的所有單詞求上述結(jié)果和給定的某個(gè)“正確”詞表之間的交集將交集結(jié)果推薦給用戶(hù)代價(jià)很大，實(shí)際當(dāng)中往往通過(guò)啟發(fā)式策略提高查找效率(如：保證兩者之間具有較長(zhǎng)公共子串)616161利用編輯距離進(jìn)行拼寫(xiě)校正給定查詢(xún)?cè)~，窮舉詞匯表中和該6262課堂練習(xí)給出計(jì)算OSLO–SNOW之間Levenshtein距離的距離矩陣將cat轉(zhuǎn)換成catcat需要哪幾步Levenshtein編輯操作？626262課堂練習(xí)給出計(jì)算OSLO–SNOW之間Leve6363636363636464646464646565656565656666666666666767676767676868686868686969696969697070707070707171717171717272727272727373737373737474747474747575757575757676767676767777777777777878787878787979797979798080808080808181818181818282828282828383838383838484848484848585858585858686868686868787878787878888888888888989898989899090909090909191919191919292929292929393939393939494949494949595959595959696969696969797

如何從上述矩陣中找到編輯操作的路徑？979797 97989898989898999999999999100100100100100100101101101101101101102102102102102102103103103從cat到catcat103103103從cat到catcat104104104104104104105105105105105105106106106106106106107107107107107107108提綱上一講回顧詞典通配查詢(xún)編輯距離拼寫(xiě)校正Soundex108108提綱上一講回顧108109拼寫(xiě)校正剛才已經(jīng)介紹如何利用編輯距離進(jìn)行詞獨(dú)立方式下的拼寫(xiě)校正另一種方法：k-gram索引上下文敏感的拼寫(xiě)校正拼寫(xiě)校正中的一般問(wèn)題109109拼寫(xiě)校正剛才已經(jīng)介紹如何利用編輯距離進(jìn)行詞獨(dú)立方式下的110110基于k-gram索引的拼寫(xiě)校正列舉查詢(xún)?cè)~項(xiàng)中的所有k-gram例子：采用2-gram索引,錯(cuò)誤拼寫(xiě)的單詞為bordroom2-gram:bo,or,rd,dr,ro,oo,om利用

k-gram索引返回和能夠匹配很多查詢(xún)k-gram的正確單詞匹配程度(數(shù)目或者指標(biāo))上可以事先設(shè)定閾值E.g.,比如最多只有3個(gè)k-gram不同110110110基于k-gram索引的拼寫(xiě)校正列舉查詢(xún)?cè)~項(xiàng)中的所1111112-gram索引示意圖1111111112-gram索引示意圖111112112上下文敏感的拼寫(xiě)校正例子:anasteroidthatfellformthesky如何對(duì)form糾錯(cuò)？一種方法:基于命中數(shù)(hit-based)的拼寫(xiě)校正對(duì)于每個(gè)查詢(xún)?cè)~項(xiàng)返回

相近的“正確”詞項(xiàng)flewformmunich:flea->flew,from->form,munch->munich組合所有可能搜索

“fleaformmunich”搜索

“flewfrommunich”搜索

“flewformmunch”正確查詢(xún)

“flewfrommunich”會(huì)有最高的結(jié)果命中數(shù)(例如返回網(wǎng)頁(yè)數(shù))假定flew有7個(gè)可能的候選詞,form有20個(gè)，

munich有3個(gè)，那么需要窮舉出多少個(gè)查詢(xún)？112112112上下文敏感的拼寫(xiě)校正例子:anasteroi113113上下文敏感的拼寫(xiě)校正剛才提到的基于命中數(shù)的算法效率不高一種更高效的做法是：從查詢(xún)庫(kù)(比如歷史查詢(xún))中搜索而不是從文檔庫(kù)中搜索比較查詢(xún)被輸入的次數(shù)匹配查詢(xún)校正歷史113113113上下文敏感的拼寫(xiě)校正剛才提到的基于命中數(shù)的算法效114114拼寫(xiě)校正中的一般問(wèn)題用戶(hù)交互界面問(wèn)題全自動(dòng)vs.推薦式校正方法(Didyoumean…?)推薦式校正方法通常只給出一個(gè)建議如果有多個(gè)可能的正確拼寫(xiě)怎么辦？平衡:交互界面的簡(jiǎn)潔性vs.強(qiáng)大性開(kāi)銷(xiāo)問(wèn)題拼寫(xiě)校正的開(kāi)銷(xiāo)很大避免對(duì)所有查詢(xún)都運(yùn)行拼寫(xiě)校正模塊只對(duì)返回結(jié)果很少的查詢(xún)運(yùn)行拼寫(xiě)校正模塊猜測(cè):主流搜索引擎的拼寫(xiě)校正模塊非常高效，有能力對(duì)每個(gè)查詢(xún)進(jìn)行拼寫(xiě)校正114114114拼寫(xiě)校正中的一般問(wèn)題用戶(hù)交互界面問(wèn)題114115115課堂練習(xí):PeterNorvig拼寫(xiě)校正工具的理解115115115課堂練習(xí):PeterNorvig拼寫(xiě)校正工具116提綱上一講回顧詞典通配查詢(xún)編輯距離拼寫(xiě)校正Soundex116116提綱上一講回顧116117Soundex一種特殊的拼寫(xiě)錯(cuò)誤(發(fā)音相似的拼寫(xiě)錯(cuò)誤)比如:chebyshev/tchebyscheffSoundex是尋找發(fā)音相似的單詞的方法具體算法:將詞典中每個(gè)詞項(xiàng)轉(zhuǎn)換成一個(gè)4字符縮減形式對(duì)查詢(xún)?cè)~項(xiàng)做同樣的處理基于4-字符縮減形式進(jìn)行索引和搜索117117Soundex一種特殊的拼寫(xiě)錯(cuò)誤(發(fā)音相似的拼寫(xiě)錯(cuò)誤)118118Soundex算法保留詞項(xiàng)的首字母將后續(xù)所有的A、E、I、O、U、H、W及Y等字母轉(zhuǎn)換為0。按照如下方式將字母轉(zhuǎn)換成數(shù)字：B,F,P,V1C,G,J,K,Q,S,X,Z2D,T3L4M,N5R6將連續(xù)出現(xiàn)的兩個(gè)同一字符轉(zhuǎn)換為一個(gè)字符直至再?zèng)]有這種現(xiàn)象出現(xiàn)。在結(jié)果字符串中剔除0，并在結(jié)果字符串尾部補(bǔ)足0，然后返回前四個(gè)字符，該字符由1個(gè)字母加上3個(gè)數(shù)字組成。118118118Soundex算法保留詞項(xiàng)的首字母118119119例子:采用Soundex算法處理HERMAN保留HERMAN→0RM0N0RM0N→0650506505→0650506505→655返回H655注意:HERMANN

會(huì)產(chǎn)生同樣的編碼119119119例子:采用Soundex算法處理HERMAN保120120Soundex的應(yīng)用情況在IR中并不非常普遍適用于“高召回率”任務(wù)(e.g.,國(guó)際刑警組織Interpol在全球范圍內(nèi)追查罪犯)ZobelandDart(1996)提出了一個(gè)更好的發(fā)音匹配方法120120120Soundex的應(yīng)用情況在IR中并不非常普遍12121121課堂練習(xí)計(jì)算你的姓的拼音的Soundex編碼121121121課堂練習(xí)計(jì)算你的姓的拼音的Soundex編碼12122122本講小結(jié)詞典的數(shù)據(jù)結(jié)構(gòu)：訪問(wèn)效率和支持查找的方式哈希表vs.樹(shù)結(jié)構(gòu)容錯(cuò)式檢索(Tolerantretrieval):通配查詢(xún)：包含通配符*的查詢(xún)輪排索引vs.k-gram索引拼寫(xiě)校正：編輯距離vs.k-gram相似度詞獨(dú)立校正法vs.上下文敏感校正法Soundex算法122122122本講小結(jié)詞典的數(shù)據(jù)結(jié)構(gòu)：訪問(wèn)效率和支持查找的方式

現(xiàn)代信息檢索前一段小結(jié)目前的索引方式和查詢(xún)方式布爾查詢(xún)：普通倒排索引、+跳表短語(yǔ)查詢(xún)：雙詞索引、位置索引通配查詢(xún)：輪排索引、k-gram索引拼寫(xiě)錯(cuò)誤的查詢(xún)：k-gram索引發(fā)音錯(cuò)誤的查詢(xún)：Soundex索引包含各種格式索引的搜索引擎甚至可以處理如下查詢(xún)(SPELL(moriset)/3toron*to)ORSOUNDEX(chaikofski)現(xiàn)代信息檢索前一段小結(jié)目前的索引方式和查詢(xún)方式124參考資料《信息檢索導(dǎo)論》第3章、MG4.2高效拼寫(xiě)校正方法:

K.Kukich.Techniquesforautomaticallycorrectingwordsintext.ACMComputingSurveys24(4),Dec1992. J.ZobelandP.Dart.

Findingapproximatematchesinlargelexicons.

Software-practiceandexperience25(3),March1995.*** MikaelTillenius:EfficientGenerationandRankingofSpellingErrorCorrections.Master’sthesisatSweden’sRoyalInstituteofTechnology.***PeterNorvig:Howtowriteaspellingcorrector******Soundex演示Levenshtein距離的演示PeterNorvig的拼寫(xiě)校正工具124124參考資料《信息檢索導(dǎo)論》第3章、MG4.2124

現(xiàn)代信息檢索課后練習(xí)待補(bǔ)充125現(xiàn)代信息檢索課后練習(xí)待補(bǔ)充125IntroductiontoInformationRetrieval

現(xiàn)代信息檢索中國(guó)科學(xué)院大學(xué)2019年秋季課程《現(xiàn)代信息檢索》更新時(shí)間：ModernInformationRetrieval第3講詞典及容錯(cuò)式檢索Dictionaryandtolerantretrieval1262019/8/6IntroductiontoInformationRe127提綱上一講回顧詞典通配查詢(xún)編輯距離拼寫(xiě)校正Soundex1272提綱上一講回顧2提綱上一講回顧詞典通配查詢(xún)編輯距離拼寫(xiě)校正Soundex128提綱上一講回顧3

現(xiàn)代信息檢索上一講內(nèi)容文檔詞條/詞項(xiàng)基于跳表指針的合并短語(yǔ)查詢(xún)的處理(雙詞索引和位置索引)129現(xiàn)代信息檢索上一講內(nèi)容文檔4

現(xiàn)代信息檢索文檔索引的基本單位與文件不是一回事，嚴(yán)格地說(shuō)，一篇文檔可能包含多個(gè)文件，也可能一個(gè)文件包含多篇文檔依賴(lài)于具體應(yīng)用句子級(jí)檢索：一個(gè)句子為一篇文檔段落級(jí)檢索：一段文本為一篇文檔……130現(xiàn)代信息檢索文檔索引的基本單位5131詞類(lèi)(type)/詞條(token)的區(qū)別詞條(Token)–詞或者詞項(xiàng)在文檔中出現(xiàn)的實(shí)例，出現(xiàn)多次算多個(gè)詞條詞類(lèi)(Type)–多個(gè)詞條構(gòu)成的等價(jià)類(lèi)(equivalenceclass)集合InJune,thedoglikestochasethecatinthebarn.12個(gè)詞條,9個(gè)詞類(lèi)詞類(lèi)經(jīng)過(guò)一些處理(去除停用詞、歸一化)之后，最后用于索引的稱(chēng)為為詞項(xiàng)1316詞類(lèi)(type)/詞條(token)的區(qū)別詞條(Token132132詞條化中考慮的問(wèn)題詞之間的邊界是什么？空格？撇號(hào)還是連接符？上述邊界不一定是真正的邊界(比如,中文)另外荷蘭語(yǔ)、德語(yǔ)、瑞典語(yǔ)復(fù)合詞中間沒(méi)有空格

(Lebensversicherungsgesellschaftsangestellter)13277詞條化中考慮的問(wèn)題詞之間的邊界是什么？空格？撇號(hào)還是連接133133詞項(xiàng)歸一化中的問(wèn)題詞項(xiàng)實(shí)際上是一系列詞條組成的等價(jià)類(lèi)如何定義等價(jià)類(lèi)？數(shù)字(3/20/91vs.20/3/91)大小寫(xiě)問(wèn)題詞干還原，Porter工具形態(tài)分析:屈折vs.派生其他語(yǔ)言中詞項(xiàng)歸一化的問(wèn)題比英語(yǔ)中形態(tài)更復(fù)雜芬蘭語(yǔ):單個(gè)動(dòng)詞可能有12,000個(gè)不同的形式differentforms重音符號(hào)、元音變音問(wèn)題（umlauts，由于一個(gè)音被另一個(gè)音詞化而導(dǎo)致的變化，尤其是元音的變化）13388詞項(xiàng)歸一化中的問(wèn)題詞項(xiàng)實(shí)際上是一系列詞條組成的等價(jià)類(lèi)8134134跳表指針13499跳表指針9135135位置(信息)索引135在無(wú)位置信息索引中，每條倒排記錄只是一個(gè)docID在位置信息索引中，每條倒排記錄是一個(gè)docID加上一個(gè)位置信息表一個(gè)查詢(xún)的例子:

“to1be2or3not4to5be6”TO,993427:?1:?7,18,33,72,86,231?;2:?1,17,74,222,255?;

4:?8,16,190,429,433?;5:?363,367?;7:?13,23,191?;...?BE,178239:?1:?17,25?;

4:?17,191,291,430,434?;5:?14,19,101?;...?第4篇文檔能夠與查詢(xún)匹配！1010位置(信息)索引10在無(wú)位置信息索引中，每條倒排記錄136136位置信息索引基于位置信息索引，能夠處理短語(yǔ)查詢(xún)(phrasequery)，也能處理鄰近式查詢(xún)(proximityquery)1361111位置信息索引基于位置信息索引，能夠處理短語(yǔ)查詢(xún)(ph137137本講內(nèi)容詞典的數(shù)據(jù)結(jié)構(gòu)：訪問(wèn)效率和支持查找的方式容錯(cuò)式檢索(Tolerantretrieval):如果查詢(xún)?cè)~項(xiàng)和文檔詞項(xiàng)不能精確匹配時(shí)如何處理？通配查詢(xún)：包含通配符*的查詢(xún)拼寫(xiě)校正：查詢(xún)中存在錯(cuò)誤時(shí)的處理1371212本講內(nèi)容詞典的數(shù)據(jù)結(jié)構(gòu)：訪問(wèn)效率和支持查找的方式12138提綱上一講回顧詞典通配查詢(xún)編輯距離拼寫(xiě)校正Soundex13813提綱上一講回顧13139倒排索引對(duì)每個(gè)詞項(xiàng)t,保存所有包含t的

文檔列表139詞典(dictionary)倒排記錄表(postinglist)詞典(dictionary)倒排記錄表(postings)14倒排索引對(duì)每個(gè)詞項(xiàng)t,保存所有包含t的文檔列表14詞140140詞典詞典是指存儲(chǔ)詞項(xiàng)詞匯表的數(shù)據(jù)結(jié)構(gòu)詞項(xiàng)詞匯表(Termvocabulary):指的是具體數(shù)據(jù)詞典(Dictionary):指的是數(shù)據(jù)結(jié)構(gòu)1401515詞典詞典是指存儲(chǔ)詞項(xiàng)詞匯表的數(shù)據(jù)結(jié)構(gòu)15141141采用定長(zhǎng)數(shù)組的詞典結(jié)構(gòu)對(duì)每個(gè)詞項(xiàng)，需要存儲(chǔ):文檔頻率(DocumentFrequency,DF)指向倒排記錄表的指針...暫定每條詞項(xiàng)的上述信息均采用定長(zhǎng)的方式存儲(chǔ)假定所有詞項(xiàng)的信息采用數(shù)組存儲(chǔ)1411616采用定長(zhǎng)數(shù)組的詞典結(jié)構(gòu)對(duì)每個(gè)詞項(xiàng)，需要存儲(chǔ):16142142采用定長(zhǎng)數(shù)組的詞典結(jié)構(gòu)

空間消耗:20字節(jié)4字節(jié)4字節(jié)1421717采用定長(zhǎng)數(shù)組的詞典結(jié)構(gòu)

現(xiàn)代信息檢索詞項(xiàng)定位(即查詞典)在詞典中查找給定關(guān)鍵字輸入“信息”，如何在詞典中快速找到這個(gè)詞？很多詞典應(yīng)用中的基本問(wèn)題。以下介紹支持快速查找的詞典數(shù)據(jù)結(jié)構(gòu)。143信息數(shù)據(jù)挖掘1819202122現(xiàn)代信息檢索詞項(xiàng)定位(即查詞典)在詞典中查找給定關(guān)鍵字1144用于詞項(xiàng)定位的數(shù)據(jù)結(jié)構(gòu)主要有兩種數(shù)據(jù)結(jié)構(gòu):哈希表和樹(shù)有些IR系統(tǒng)用哈希表，有些系統(tǒng)用樹(shù)結(jié)構(gòu)采用哈希表或樹(shù)的準(zhǔn)則:詞項(xiàng)數(shù)目是否固定或者說(shuō)詞項(xiàng)數(shù)目是否持續(xù)增長(zhǎng)？詞項(xiàng)的相對(duì)訪問(wèn)頻率如何？詞項(xiàng)的數(shù)目有多少？14419用于詞項(xiàng)定位的數(shù)據(jù)結(jié)構(gòu)主要有兩種數(shù)據(jù)結(jié)構(gòu):哈希表和樹(shù)1

現(xiàn)代信息檢索哈希表145信息數(shù)據(jù)挖掘哈希函數(shù)，輸入詞項(xiàng)，輸出正整數(shù)(通常是地址)f(信息)=18,f(數(shù)據(jù))=19，f(挖掘)=191819202122現(xiàn)代信息檢索哈希表20信息數(shù)據(jù)挖掘哈希函數(shù)，輸入詞項(xiàng)，輸146哈希表(HashTable)每個(gè)詞項(xiàng)通過(guò)哈希函數(shù)映射成一個(gè)整數(shù)盡可能避免沖突查詢(xún)處理時(shí)：對(duì)查詢(xún)?cè)~項(xiàng)進(jìn)行哈希，如果有沖突，則解決沖突，最后在定長(zhǎng)數(shù)組中定位優(yōu)點(diǎn):在哈希表中的定位速度快于樹(shù)中的定位速度查詢(xún)時(shí)間是常數(shù)缺點(diǎn)：無(wú)法處理詞項(xiàng)的微小變形(resumevs.résumé)不支持前綴搜索(比如所有以automat開(kāi)頭的詞項(xiàng))如果詞匯表不斷增大，需要定期對(duì)所有詞項(xiàng)重新哈希14621哈希表(HashTable)每個(gè)詞項(xiàng)通過(guò)哈希函數(shù)映射成147147樹(shù)(Tree)樹(shù)可以支持前綴查找(相當(dāng)于對(duì)詞典再建一層索引)最簡(jiǎn)單的樹(shù)結(jié)構(gòu)：二叉樹(shù)搜索速度略低于哈希表方式：

O(logM),其中

M

是詞匯表大小，即所有詞項(xiàng)的數(shù)目O(logM)僅僅對(duì)平衡樹(shù)成立使二叉樹(shù)重新保持平衡開(kāi)銷(xiāo)很大B-樹(shù)能夠減輕上述問(wèn)題B-樹(shù)定義：每個(gè)內(nèi)部節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)目在[a,b]之間，其中a,b

為合適的正整數(shù),e.g.,[2,4].1472222樹(shù)(Tree)樹(shù)可以支持前綴查找(相當(dāng)于對(duì)詞典再建一148148二叉樹(shù)1482323二叉樹(shù)23149149B-樹(shù)1492424B-樹(shù)24150提綱上一講回顧詞典通配查詢(xún)編輯距離拼寫(xiě)校正Soundex15025提綱上一講回顧25151通配查詢(xún)通配查詢(xún)：包含通配符的查詢(xún)，例如：mon*:找出所有包含以mon開(kāi)頭的詞項(xiàng)的文檔

符合條件的詞項(xiàng)有：Monday,monster,monitor等*mon:找出所有包含以mon結(jié)尾的詞項(xiàng)的文檔符合條件的詞項(xiàng)有：summon,common,cinnamon等15126通配查詢(xún)通配查詢(xún)：包含通配符的查詢(xún)，例如：26152通配查詢(xún)的處理mon*:找出所有包含以mon開(kāi)頭的詞項(xiàng)的文檔如果采用B-樹(shù)詞典結(jié)構(gòu)，那么實(shí)現(xiàn)起來(lái)非常容易，只需要返回區(qū)間mon≤t<moo上的詞項(xiàng)t15227通配查詢(xún)的處理mon*:找出所有包含以mon開(kāi)頭的詞153通配查詢(xún)的處理*mon:找出所有包含以mon結(jié)尾的詞項(xiàng)的文檔將所有的詞項(xiàng)倒轉(zhuǎn)過(guò)來(lái)，然后基于它們建一棵附加的樹(shù)返回區(qū)間nom≤t<non上的詞項(xiàng)t比如有以下四個(gè)詞：absurd,Monday,monster,zoo全部倒轉(zhuǎn)過(guò)來(lái)：drusba,yadnom,retsnom,ooz然后基于倒轉(zhuǎn)過(guò)來(lái)的詞項(xiàng)再建一顆B樹(shù)也就說(shuō)，通過(guò)上述數(shù)據(jù)結(jié)構(gòu)，可能得到滿足通配查詢(xún)的一系列詞項(xiàng)，然后返回任一詞項(xiàng)的文檔15328通配查詢(xún)的處理*mon:找出所有包含以mon結(jié)尾的詞項(xiàng)154154詞項(xiàng)中間的*號(hào)處理例子:m*nchen在B-樹(shù)中分別查找滿足m*和*nchen的詞項(xiàng)集合，然后求交集這種做法開(kāi)銷(xiāo)很大另外一種方法:輪排(permuterm)索引基本思想：將每個(gè)通配查詢(xún)旋轉(zhuǎn)，使*出現(xiàn)在末尾將每個(gè)旋轉(zhuǎn)后的結(jié)果存放在詞典中，即B-樹(shù)中1542929詞項(xiàng)中間的*號(hào)處理例子:m*nchen29155155輪排索引對(duì)于詞項(xiàng)hello:將hello$,ello$h,llo$he,lo$hel,o$hell

和$hello加入到B-樹(shù)中，其中$是一個(gè)特殊符號(hào)(表示結(jié)尾)即在詞項(xiàng)前面再加一層索引該索引采用B-樹(shù)來(lái)組織該索引葉節(jié)點(diǎn)是詞項(xiàng)的各種變形1553030輪排索引對(duì)于詞項(xiàng)hello:將hello$,e156156輪排結(jié)果→詞項(xiàng)的映射示意圖1563131輪排結(jié)果→詞項(xiàng)的映射示意圖31157157輪排索引對(duì)于hello，已經(jīng)存儲(chǔ)了

hello$,ello$h,llo$he,lo$hel,

o$hell和$hello查詢(xún)對(duì)于X,查詢(xún)X$對(duì)于X*,查詢(xún)$X*對(duì)于*X,查詢(xún)X$*對(duì)于*X*,查詢(xún)X*，比如*ello*，則只需要查到ello開(kāi)頭的串即可(上面是ello$h)，因?yàn)榇藭r(shí)ello右部一定包含一個(gè)$，$結(jié)不結(jié)尾的串均能滿足查詢(xún)*X*，對(duì)于X*Y,查詢(xún)Y$X*例子:假定通配查詢(xún)?yōu)閔el*o,那么相當(dāng)于要查詢(xún)o$hel*輪排索引稱(chēng)為輪排樹(shù)更恰當(dāng)?shù)禽喤潘饕姆Q(chēng)呼已經(jīng)使用非常普遍1573232輪排索引對(duì)于hello，已經(jīng)存儲(chǔ)了hello$,

現(xiàn)代信息檢索輪排索引小結(jié)158……傳統(tǒng)倒排索引(詞項(xiàng)文檔)輪排索引(通配查詢(xún)?cè)~項(xiàng)，采用B樹(shù)來(lái)組織)現(xiàn)代信息檢索輪排索引小結(jié)33……傳統(tǒng)倒排索引(詞項(xiàng)文159使用輪排索引的查找過(guò)程將查詢(xún)進(jìn)行旋轉(zhuǎn)，將通配符旋轉(zhuǎn)到右部同以往一樣查找B-樹(shù)，得到匹配的所有詞項(xiàng)，將這些詞項(xiàng)對(duì)應(yīng)的倒排記錄表取出問(wèn)題：相對(duì)于通常的B-樹(shù)，輪排索引(輪排樹(shù))的空間要大4倍以上(經(jīng)驗(yàn)值)15934使用輪排索引的查找過(guò)程將查詢(xún)進(jìn)行旋轉(zhuǎn)，將通配符旋轉(zhuǎn)到右部160160k-gram索引比輪排索引空間開(kāi)銷(xiāo)要小枚舉一個(gè)詞項(xiàng)中所有連讀的k個(gè)字符構(gòu)成k-gram

。2-gram稱(chēng)為二元組(bigram)3-gram稱(chēng)為三元組(trigram)例子:Aprilisthecruelestmonth

2-gram:$aapprriill$$iiss$$tthhee$$ccrruueelleesstt$$mmoonnth$同前面一樣，$是一個(gè)特殊字符，表示單詞開(kāi)始或結(jié)束1603535k-gram索引比輪排索引空間開(kāi)銷(xiāo)要小35161161k-gram索引161構(gòu)建一個(gè)倒排索引，此時(shí)詞典部分是所有的k-gram，倒排記錄表部分是包含某個(gè)k-gram的所有詞項(xiàng)相當(dāng)于對(duì)詞項(xiàng)再構(gòu)建一個(gè)倒排索引(二級(jí)索引)3636k-gram索引36構(gòu)建一個(gè)倒排索引，此時(shí)詞典部分是162162k-gram(bigram,trigram,...)索引需要注意的是，這里有兩個(gè)倒排索引詞典-文檔的倒排索引基于詞項(xiàng)返回文檔而k-gram索引用于查找詞項(xiàng)，即基于查詢(xún)所包含的k-gram來(lái)查找所有的詞項(xiàng)1623737k-gram(bigram,trigram,.163163利用2-gram索引處理通配符查詢(xún)例子：查詢(xún)mon*先執(zhí)行布爾查詢(xún):$mANDmoANDon該布爾查詢(xún)會(huì)返回所有以前綴mon開(kāi)始的詞項(xiàng)......當(dāng)然也可能返回許多偽正例(falsepositives)，比如MOON。同前面的雙詞索引處理短語(yǔ)查詢(xún)一樣，滿足布爾查詢(xún)只是滿足原始查詢(xún)的必要條件。因此，必須要做后續(xù)的過(guò)濾處理剩下的詞項(xiàng)將在詞項(xiàng)-文檔倒排索引中查找文檔k-gram索引vs.輪排索引k-gram索引的空間消耗小輪排索引不需要進(jìn)行后過(guò)濾1633838利用2-gram索引處理通配符查詢(xún)例子：查詢(xún)mon*164164課堂練習(xí)Google對(duì)通配符查詢(xún)的支持極其有限比如：在Google中查詢(xún)

[gen*universit*]意圖：想查UniversityofGeneva,但是不知道如何拼寫(xiě)，特別是法語(yǔ)中的拼寫(xiě)按照Google自己的說(shuō)法,2010-04-29:“*操作符只能作為一個(gè)整體單詞使用，而不能作為單詞的一部分使用”但是這點(diǎn)并不完全對(duì)，嘗試一下[pythag*]和[m*nchen]問(wèn)題:為什么Google對(duì)通配查詢(xún)并不充分支持？1643939課堂練習(xí)Google對(duì)通配符查詢(xún)的支持極其有限39165165原因問(wèn)題1:一條通配符查詢(xún)往往相當(dāng)于執(zhí)行非常多的布爾查詢(xún)對(duì)于[gen*universit*]:genevauniversityORgenevauniversitéORgenèveuniversityORgenèveuniversitéORgeneraluniversitiesOR...開(kāi)銷(xiāo)非常大問(wèn)題2:用戶(hù)不愿意敲擊更多的鍵盤(pán)如果允許[pyth*theo*]代替[pythagoras’theorem]的話，用戶(hù)會(huì)傾向于使用前者這樣會(huì)大大加重搜索引擎的負(fù)擔(dān)GoogleSuggest是一種減輕用戶(hù)輸入負(fù)擔(dān)的好方法1654040原因問(wèn)題1:一條通配符查詢(xún)往往相當(dāng)于執(zhí)行非常多的166提綱上一講回顧詞典通配查詢(xún)編輯距離拼寫(xiě)校正Soundex16641提綱上一講回顧41

現(xiàn)代信息檢索拼寫(xiě)錯(cuò)誤的查詢(xún)用戶(hù)想查information，但是錯(cuò)誤地輸入了informaton于是，我們?cè)噲D將informatoninformation需要使用拼寫(xiě)校正技術(shù)167現(xiàn)代信息檢索拼寫(xiě)錯(cuò)誤的查詢(xún)用戶(hù)想查information168拼寫(xiě)校正兩個(gè)主要用途糾正待索引文檔糾正用戶(hù)的查詢(xún)兩種拼寫(xiě)校正的方法詞獨(dú)立(Isolatedword)法只檢查每個(gè)單詞本身的拼寫(xiě)錯(cuò)誤如果某個(gè)單詞拼寫(xiě)錯(cuò)誤后變成另外一個(gè)單詞，則無(wú)法查出,e.g.,anasteroidthatfellformthesky上下文敏感(Context-sensitive)法糾錯(cuò)時(shí)要考慮周?chē)膯卧~能糾正上例中的錯(cuò)誤

form/from16843拼寫(xiě)校正兩個(gè)主要用途43169169關(guān)于文檔校正本課當(dāng)中我們不關(guān)心文檔的拼寫(xiě)校正問(wèn)題(e.g.,MSWord)在IR領(lǐng)域,我們主要對(duì)OCR處理后的文檔進(jìn)行拼寫(xiě)校正處理.(OCR=opticalcharacterrecognition，光學(xué)字符識(shí)別)IR領(lǐng)域的一般做法是：不改變文檔1694444關(guān)于文檔校正本課當(dāng)中我們不關(guān)心文檔的拼寫(xiě)校正問(wèn)題(170170查詢(xún)校正第一種方法:詞獨(dú)立(isolatedword)法假設(shè)1:對(duì)需要糾錯(cuò)的詞存在一系列“正確單詞形式”假設(shè)2:需要提供存在錯(cuò)誤拼寫(xiě)的單詞和正確單詞之間的距離計(jì)算方式簡(jiǎn)單的拼寫(xiě)校正算法:返回與錯(cuò)誤單詞具有最小距離的”正確”單詞例子:informaton→information可以將詞匯表中所有的單詞都作為候選的“正確”單詞1704545查詢(xún)校正第一種方法:詞獨(dú)立(isolatedwo171171幾種可用的詞匯表采用標(biāo)準(zhǔn)詞典(韋伯詞典,牛津詞典等等)采用領(lǐng)域詞典(面向特定領(lǐng)域的IR系統(tǒng))采用文檔集上的詞項(xiàng)詞匯表(可以通過(guò)統(tǒng)計(jì)得到)，但是每個(gè)詞項(xiàng)均帶有權(quán)重1714646幾種可用的詞匯表采用標(biāo)準(zhǔn)詞典(韋伯詞典,牛津詞典172172單詞間距離的計(jì)算以下將介紹幾種計(jì)算方法編輯距離(Editdistance或者Levenshteindistance)帶權(quán)重的編輯距離k-gram重疊率1724747單詞間距離的計(jì)算以下將介紹幾種計(jì)算方法47173173編輯距離兩個(gè)字符串s1和s2編輯距離是指從

s1

轉(zhuǎn)換成s2所需要的最少的基本操作數(shù)目Levenshtein距離:采用的基本操作是插入(insert)、刪除(delete)和替換(replace)Levenshtein距離dog-do:1Levenshtein距離

cat-cart:1Levenshtein距離

cat-cut:1Levenshtein距離

cat-act:2Damerau-Levenshtein距離：除了上述三種基本操作外，還包括兩個(gè)字符之間的交換（transposition）操作Damerau-Levenshtein距離cat-act:11734848編輯距離兩個(gè)字符串s1和s2編輯距離是指從s1轉(zhuǎn)

現(xiàn)代信息檢索VladimirIosifovich

Levenshtein俄羅斯科學(xué)家(1935-)研究信息論、糾錯(cuò)理論畢業(yè)于莫斯科國(guó)立大學(xué)1965年提出Levenshtein距離2006年獲得IEEERichardW.HammingMedal174現(xiàn)代信息檢索VladimirIosifovich

Le175Levenshtein距離:計(jì)算175fast中的f、s、t分別用c、t、s替換，即可得到cats，所以代價(jià)是3，即距離是3。50Levenshtein距離:計(jì)算50fast中的f、s176176Levenshtein距離:算法176(i-1,j-1)(i-1,j)(i,j-1)(i,j)5151Levenshtein距離:算法51(i-1,j-177177Levenshtein距離:算法177左鄰居(i-1,j-1)(i-1,j)(i,j-1)(i,j)5252Levenshtein距離:算法52左鄰居(i-1178178Levenshtein距離:算法178上鄰居(i-1,j-1)(i-1,j)(i,j-1)(i,j)5353Levenshtein距離:算法53上鄰居(i-1179179Levenshtein距離:算法179左上鄰居(i-1,j-1)(i-1,j)(i,j-1)(i,j)5454Levenshtein距離:算法54左上鄰居(i-180180Levenshtein距離:算法180左上鄰居(i-1,j-1)(i-1,j)(i,j-1)(i,j)5555Levenshtein距離:算法55左上鄰居(i-181181Levenshtein距離:例子181CopyReplacedeleteinsert5656Levenshtein距離:例子56Copyde182182Levenshtein矩陣中每個(gè)單元包含4個(gè)元素182從左上角鄰居到來(lái)的開(kāi)銷(xiāo)

(copy或replace)從上方鄰居到來(lái)的代價(jià)(delete)從左方鄰居到來(lái)的代價(jià)

(insert)上述三者之中最低的代價(jià)5757Levenshtein矩陣中每個(gè)單元包含4個(gè)元素57183183Levenshtein距離:例子1835858Levenshtein距離:例子58184184動(dòng)態(tài)規(guī)劃算法(Cormenetal.)最優(yōu)子結(jié)構(gòu):最優(yōu)的問(wèn)題解決方案中包括子解決方案，及子問(wèn)題的最優(yōu)解決方案（兩點(diǎn)最短路徑問(wèn)題最典型的解法就是動(dòng)態(tài)規(guī)劃算法）重疊的子解決方案Overlappingsubsolutions:子解決方案中有重疊，如果采用暴力計(jì)算方法(窮舉法)，子解決方案將會(huì)被反復(fù)計(jì)算，從而使得計(jì)算開(kāi)銷(xiāo)很大.編輯距離計(jì)算中的子問(wèn)題:兩個(gè)前綴之間的編輯距離計(jì)算1845959動(dòng)態(tài)規(guī)劃算法(Cormenetal.)最優(yōu)子結(jié)構(gòu)185185帶權(quán)重的編輯距離思路：對(duì)不同的字符進(jìn)行操作時(shí)權(quán)重不同希望能更敏銳地捕捉到鍵盤(pán)輸入的錯(cuò)誤,e.g.,m

更可能被輸成n

而不是

q因此，將

m

替換為

n

的編輯距離將低于替換為q的距離也就是輸入的操作代價(jià)矩陣是一個(gè)帶權(quán)重的矩陣對(duì)上述動(dòng)態(tài)規(guī)劃算法進(jìn)行修改便可以處理權(quán)重計(jì)算1856060帶權(quán)重的編輯距離思路：對(duì)不同的字符進(jìn)行操作時(shí)權(quán)重不186186利用編輯距離進(jìn)行拼寫(xiě)校正給定查詢(xún)?cè)~，窮舉詞匯表中和該查詢(xún)的編輯距離(或帶權(quán)重的編輯聚類(lèi))低于某個(gè)預(yù)定值的所有單詞求上述結(jié)果和給定的某個(gè)“正確”詞表之間的交集將交集結(jié)果推薦給用戶(hù)代價(jià)很大，實(shí)際當(dāng)中往往通過(guò)啟發(fā)式策略提高查找效率(如：保證兩者之間具有較長(zhǎng)公共子串)1866161利用編輯距離進(jìn)行拼寫(xiě)校正給定查詢(xún)?cè)~，窮舉詞匯表中和該187187課堂練習(xí)給出計(jì)算OSLO–SNOW之間Levenshtein距離的距離矩陣將cat轉(zhuǎn)換成catcat需要哪幾步Levenshtein編輯操作？1876262課堂練習(xí)給出計(jì)算OSLO–SNOW之間Leve188188188636363189189189646464190190190656565191191191666666192192192676767193193193686868194194194696969195195195707070196196196717171197197197727272198198198737373199199199747474200200200757575201201201767676202202202777777203203203787878204204204797979205205205808080206206206818181207207207828282208208208838383209209209848484210210210858585211211211868686212212212878787213213213888888214214214898989215215215909090216216216919191217217217929292218218218939393219219219949494220220220959595221221221969696222222

如何從上述矩陣中找到編輯操作的路徑？2229797 97223223223989898224224224999999225225225100100100226226226101101101227227227102102102228228228從cat到catcat103103103從cat到catcat229229229104104104230230230105105105231231231106106106232232232107107107233提綱上一講回顧詞典通配查詢(xún)編輯距離拼寫(xiě)校正Soundex233108提綱上一講回顧108234拼寫(xiě)校正剛才已經(jīng)介紹如何利用編輯距離進(jìn)行詞獨(dú)立方式下的拼寫(xiě)校正另一種方法：k-gram索引上下文敏感的拼寫(xiě)校正拼寫(xiě)校正中的一般問(wèn)題234109拼寫(xiě)校正剛才已經(jīng)介紹如何利用編輯距離進(jìn)行詞獨(dú)立方式下的235235基于k-gram索引的拼寫(xiě)校正列舉查詢(xún)?cè)~項(xiàng)中的所有k-gram例子：采用2-gram索引,錯(cuò)誤拼寫(xiě)的單詞為bordroom2-gram:bo,or,rd,dr,ro,oo,om利用

k-gram索引返回和能夠匹配很多查詢(xún)k-gram的正確單詞匹配程度(數(shù)目或者指標(biāo))上可以事先設(shè)定閾值E.g.,比如最多只有3個(gè)k-gram不同235110110基于k-gram索引的拼寫(xiě)校正列舉