信息檢索與web搜索課件 04學(xué)習(xí)資料

信息檢索與Web搜索

第4講詞典及容錯(cuò)式檢索Dictionaryandtolerantretrieval授課人：高曙明

*改編自“現(xiàn)代信息檢索”網(wǎng)上公開課件（/~wangbin）2詞典數(shù)據(jù)結(jié)構(gòu)

用于存儲(chǔ)詞項(xiàng)詞匯表的數(shù)據(jù)結(jié)構(gòu)

采用定長(zhǎng)數(shù)組的詞典結(jié)構(gòu)空間消耗:20字節(jié)4字節(jié)4字節(jié)快速詞項(xiàng)定位給定查詢?cè)~項(xiàng)“信息”，如何在詞典中快速找到這個(gè)詞項(xiàng)？需要支持快速查找的詞典數(shù)據(jù)結(jié)構(gòu)哈希表方式搜索樹方式選擇何種方式需要考慮以下因素：詞項(xiàng)數(shù)目是否固定或者說詞項(xiàng)數(shù)目是否持續(xù)增長(zhǎng)？詞項(xiàng)的相對(duì)訪問頻率如何？詞項(xiàng)的數(shù)目有多少？34基于哈希表的詞典索引方法：將每個(gè)詞項(xiàng)通過哈希函數(shù)映射成一個(gè)整數(shù)查詢處理：對(duì)查詢?cè)~項(xiàng)進(jìn)行哈希，如果有沖突，則解決沖突，最后在定長(zhǎng)數(shù)組中定位優(yōu)點(diǎn):在哈希表中的定位速度快于樹中的定位速度查詢時(shí)間是常數(shù)

缺點(diǎn)：不支持前綴搜索(比如所有以automat開頭的詞項(xiàng))如果詞匯表不斷增大，需要定期對(duì)所有詞項(xiàng)重新哈希5基于搜索樹的詞典索引方法：采用搜索樹作為詞典的索引，一般采用平衡二叉樹優(yōu)點(diǎn)：可以支持前綴查找缺點(diǎn)：搜索速度略低于哈希表方式：O(logM),其中M是詞匯數(shù)使二叉樹重新保持平衡開銷很大改進(jìn)：采用B-樹減輕上述問題B-樹定義：每個(gè)內(nèi)部節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)目在[a,b]之間，其中a,b為合適的正整數(shù),e.g.,[2,4].6二叉搜索樹示例平衡性，字符集有預(yù)定的排序方式7B-樹示例子節(jié)點(diǎn)數(shù)目在[2,4]區(qū)間8通配查詢通配查詢：指詞項(xiàng)中帶有通配符“*”的查詢分類：尾通配符查詢

mon*:找出所有包含以mon開頭的詞項(xiàng)的文檔首通配符查詢*mon:找出所有包含以mon結(jié)尾的詞項(xiàng)的文檔中間通配符查詢

m*nchen：找出所有包含以m開頭并以nchen結(jié)尾的詞項(xiàng)的文檔作用:滿足用戶的以下需求用戶需要進(jìn)行拼寫不確定的查詢用戶需要查找某個(gè)查詢?cè)~項(xiàng)的所有變形9通配查詢的處理處理方法:mon*：采用B-樹詞典結(jié)構(gòu)，搜索區(qū)間mon≤t<moo上的所有詞項(xiàng)t，返回相關(guān)文檔*mon：將所有的詞項(xiàng)倒轉(zhuǎn)過來，然后基于它們建一棵反向的B樹；返回區(qū)間nom≤t<non上的詞項(xiàng)tm*nchen：在B-樹和反向B樹中分別查找滿足m*和*nchen的項(xiàng)集合，然后求交集10輪排索引(Permutermindex)輪排詞匯集：將一常規(guī)詞項(xiàng)旋轉(zhuǎn)后得到的集合舉例：對(duì)于詞項(xiàng)hello，（hello$,ello$h,llo$he,lo$hel,和o$hell）是其輪排詞匯集，其中

$是一個(gè)特殊符號(hào)，用于標(biāo)識(shí)詞項(xiàng)結(jié)束，每個(gè)擴(kuò)展詞都指向原始詞項(xiàng)輪排索引：將輪排詞匯集加入搜索樹形成的詞典索引目的：有效地支持一般性通配符查詢11輪排索引(Permutermindex)輪排索引與倒排索引的關(guān)聯(lián)示意圖相對(duì)于通常的B-樹，輪排樹的空間要大4倍以上12

基于輪排索引的通配符查詢方法：首先將每個(gè)通配查詢?cè)~項(xiàng)進(jìn)行旋轉(zhuǎn)，使*出現(xiàn)在末尾，然后在輪排索引的B-樹中搜索，最后將搜索結(jié)果映射到常規(guī)詞項(xiàng)舉例：對(duì)于*X,查詢X$*對(duì)于*X*,查詢X*對(duì)于X*Y,查詢Y$X*對(duì)于hel*o，查詢o$hel*對(duì)于fi*mo*er，先查er$fi*，再除去不包含mo的詞項(xiàng)13k-gram索引K-gram:由K個(gè)字符組成的序列（即長(zhǎng)度為K的字符序列）2-gram:由2個(gè)字符組成的序列，又稱為二元組(bigram)詞項(xiàng)的K-grams:是一個(gè)由詞項(xiàng)所包含的所有的k-gram組成的集合例子:April的bigrams:$aapprriill$$是一個(gè)特殊字符，標(biāo)識(shí)詞項(xiàng)的開始或結(jié)束14

k-gram索引K-gram索引：是一種特殊的倒排索引結(jié)構(gòu)，其中詞典由詞匯表中所有詞項(xiàng)的所有K-gram構(gòu)成，每個(gè)倒排記錄表則由包含該K-gram的所有詞項(xiàng)組成例子：

3-gram(trigram)索引本質(zhì)：對(duì)詞項(xiàng)構(gòu)建一個(gè)倒排索引(二級(jí)索引)優(yōu)點(diǎn)：比輪排索引空間開銷要小15基于K-gram索引的通配符查詢主要步驟：對(duì)給定的帶*的詞項(xiàng)，生成其所有的K-gram基于K-gram索引，找出包含上述所有K-gram的詞項(xiàng)集通過與給定詞項(xiàng)進(jìn)行字符串匹配，對(duì)詞項(xiàng)集進(jìn)行過濾用余下的詞項(xiàng)在詞項(xiàng)-文檔倒排索引中查找文檔例子：查詢mon*執(zhí)行布爾查詢:$mANDmoANDon所有以前綴mon開始的詞項(xiàng)被返回，當(dāng)然也包含許多偽正

例，比如MOON16拼寫校正任務(wù)目標(biāo)：對(duì)用戶輸入的錯(cuò)誤查詢?cè)~項(xiàng)進(jìn)行糾正，通

過糾正用戶的查詢，提高檢索效果兩種方法詞獨(dú)立糾錯(cuò)(Isolatedword)法只檢查每個(gè)單詞本身的拼寫錯(cuò)誤如果某個(gè)單詞拼寫錯(cuò)誤后變成另外一個(gè)單詞，則無法查出,e.g.,anasteroidthatfellformthesky上下文敏感(Context-sensitive)法

糾錯(cuò)時(shí)考慮周圍的單詞

能糾正上例中的錯(cuò)誤form/from17詞獨(dú)立糾錯(cuò)法基本思想：對(duì)于一個(gè)需要糾錯(cuò)的查詢?cè)~，在其可能的正確拼寫中，選擇距離最近中的最常見的一個(gè)可能正確拼寫的來源：文檔集上的詞項(xiàng)詞匯表計(jì)算兩個(gè)詞的鄰近度（相似度）最常見的選擇：詞頻（文檔集中或用戶查詢記錄中）核心問題：詞之間的鄰近度計(jì)算兩種方法：基于編輯距離的鄰近度計(jì)算基于k-gram重合度的鄰近度計(jì)算18基于編輯距離的鄰近度計(jì)算編輯距離(Editdistance或者Levenshteindistance)：兩個(gè)字符串s1和s2之間的編輯距離是指從

s1

轉(zhuǎn)換成s2所需要的最少的基本操作數(shù)目基本操作：插入(insert)、刪除(delete)、替換(replace)例子：cat-cart:1；cat-cut:1；cat-act:2計(jì)算方法：采用動(dòng)態(tài)規(guī)劃算法進(jìn)行計(jì)算19Levenshtein距離:實(shí)例fast中的f、s、t分別用c、t、s替換，即可得到cats，所以代價(jià)是3，即距離是320Levenshtein距離：算法21Levenshtein距離:算法(i-1,j-1)(i-1,j)(i,j-1)(i,j)左鄰居22Levenshtein矩陣單元的組成從左上角鄰居到來的開銷

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

(insert)上述三者之中最低的代價(jià)23Levenshtein距離:例子24帶權(quán)重的編輯距離特點(diǎn)：對(duì)不同字符進(jìn)行的操作賦予不同的權(quán)重必要性分析：將字符m替換成n與將字符m替換成q應(yīng)該有區(qū)別，前者的權(quán)重應(yīng)該更小目的：通過考慮出錯(cuò)操作發(fā)生概率的因素，提高距離計(jì)算準(zhǔn)確性25利用編輯距離進(jìn)行拼寫校正給定查詢?cè)~，窮舉詞匯表中和該查詢的編輯距離(或帶權(quán)重的編輯聚類)低于某個(gè)預(yù)定值的所有詞項(xiàng)將結(jié)果推薦給用戶代價(jià)很大，實(shí)際當(dāng)中往往通過啟發(fā)式策略提高效率限制在與查詢?cè)~具有相同首字母的詞項(xiàng)保證兩者之間具有較長(zhǎng)公共子串26基于k-gram重合度的鄰近度計(jì)算k-gram重合度：指∣A∩B∣/∣A∪B∣，其中A、B分別是兩個(gè)詞的k-gram集合例子：bord與boardroom之間的2-gram重合度

A=5,B=10

A∩B=3,A∪B=10+5-3=12

重合度=3/12

27基于K-gram索引的拼寫校正查詢?cè)~bord的2-gram索引片段主要步驟確定查詢?cè)~項(xiàng)的k-gram集合，A利用k-gram索引返回A相關(guān)倒排記錄表中的詞項(xiàng)對(duì)去重后的詞，計(jì)算其與查詢?cè)~的k-gram重合度根據(jù)給定閾值，確定匹配上的正確詞項(xiàng)返回28上下文敏感的拼寫校正對(duì)于flewformHeathrow，如何糾錯(cuò)form？一種方法:基于命中數(shù)(hit-based)的拼寫校正對(duì)于每個(gè)查詢?cè)~項(xiàng)返回

相近的“正確”詞項(xiàng)組合所有可能，分別進(jìn)行查詢，取具有最高命中數(shù)者搜索

“fledformHeathrow”搜索

“flewforeHeathrow”搜索“flewfromHeathrow”會(huì)有最高的結(jié)果命中數(shù)問題:假定flew有7個(gè)可能的候選詞,form有20個(gè)，Heathrow有3個(gè)，那么需要窮舉出多少個(gè)查詢？更高效的方法：基于查詢庫確定合理的組合29基于發(fā)音的校正（Soundex）目標(biāo):

尋找發(fā)音相似的單詞，對(duì)查詢進(jìn)行擴(kuò)展，提高檢索效果比如，對(duì)查詢?cè)~chebyshev，將其擴(kuò)展到tchebyscheff算法步驟：將詞典中每個(gè)詞項(xiàng)轉(zhuǎn)換成一個(gè)4字符縮減形式(即進(jìn)行Soundex編碼)，構(gòu)建詞典的soundex索引對(duì)查詢?cè)~項(xiàng)做同樣的處理基于soundex索引搜索音似詞30Soundex編碼算法保留詞項(xiàng)的首字母將后續(xù)所有的A、E、I、O、U、H、W及Y等字母轉(zhuǎn)換為0。按照如下方式將字母轉(zhuǎn)換成數(shù)字：B,F,P,V

1C,G,J,K,Q,S,X,Z

2D,T

3;L

4;M,N

5;R

6將連續(xù)出現(xiàn)的兩個(gè)同一字符轉(zhuǎn)換為一個(gè)字符直至再?zèng)]有這種現(xiàn)象出現(xiàn)。在結(jié)果字符串中剔除0，并在結(jié)果字符串尾部補(bǔ)足0，然后返回前四個(gè)字符，該字符由1個(gè)字母加上3個(gè)數(shù)字組成。31例子:HERMAN的Soundex編碼保留HERMAN→0RM0N0RM0N→0650506505→655返回

H655注意:HERMANN

會(huì)產(chǎn)生同樣的編碼32Soundex的應(yīng)用情況在IR中并不非常普遍適用于“高召回率”任務(wù)(e.g.,國(guó)際刑警組織Interpol在全球范圍內(nèi)追查罪犯)ZobelandDart(1996)提出了一個(gè)更好的發(fā)音匹配方法33參考資料《信息檢索導(dǎo)論》第3章、MG4.2高效拼寫校正方法:K.Kukich.Techniquesforautomaticallycorrectingwordsintext.ACMComputingSurveys24(4),Dec1992.J.ZobelandP.Dart.

Findingapproximatematchesinlargelexicons.

Software-practiceandexperience25(3),March1995./zobel95finding.htmlMikaelTillenius:EfficientGenerationandRa