信息檢索與web搜索課件 04學習資料

信息檢索與Web搜索

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

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

用于存儲詞項詞匯表的數(shù)據(jù)結構

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

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

mon*:找出所有包含以mon開頭的詞項的文檔首通配符查詢*mon:找出所有包含以mon結尾的詞項的文檔中間通配符查詢

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

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

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

k-gram索引K-gram索引：是一種特殊的倒排索引結構，其中詞典由詞匯表中所有詞項的所有K-gram構成，每個倒排記錄表則由包含該K-gram的所有詞項組成例子：

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

例，比如MOON16拼寫校正任務目標：對用戶輸入的錯誤查詢詞項進行糾正，通

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

糾錯時考慮周圍的單詞

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

s1

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

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

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

A=5,B=10

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

重合度=3/12

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

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

“fledformHeathrow”搜索

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

尋找發(fā)音相似的單詞，對查詢進行擴展，提高檢索效果比如，對查詢詞chebyshev，將其擴展到tchebyscheff算法步驟：將詞典中每個詞項轉換成一個4字符縮減形式(即進行Soundex編碼)，構建詞典的soundex索引對查詢詞項做同樣的處理基于soundex索引搜索音似詞30Soundex編碼算法保留詞項的首字母將后續(xù)所有的A、E、I、O、U、H、W及Y等字母轉換為0。按照如下方式將字母轉換成數(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)的兩個同一字符轉換為一個字符直至再沒有這種現(xiàn)象出現(xiàn)。在結果字符串中剔除0，并在結果字符串尾部補足0，然后返回前四個字符，該字符由1個字母加上3個數(shù)字組成。31例子:HERMAN的Soundex編碼保留HERMAN→0RM0N0RM0N→0650506505→655返回

H655注意:HERMANN

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

Findingapproximatematchesinlargelexicons.

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