信息檢索 第05章 詞典及容錯式檢索專業(yè)課課件

信息檢索

第05章詞典及容錯式檢索軟件學(xué)院教研室陳鄞引言詞匯表的存取是實現(xiàn)倒排文件查詢的第一個步驟，需要非常高的存取效率詞匯表的查找操作通常采用稱為詞典的數(shù)據(jù)結(jié)構(gòu)本章將介紹支持詞典快速查找的一些數(shù)據(jù)結(jié)構(gòu)當(dāng)查詢中存在拼寫錯誤時，IR系統(tǒng)通常提供自動校正技術(shù)IR系統(tǒng)通常提供通配符查詢功能本章內(nèi)容5.1詞典搜索的數(shù)據(jù)結(jié)構(gòu)5.2通配符查詢5.3拼寫校正5.1詞典搜索的數(shù)據(jù)結(jié)構(gòu)基于字符串排序的方法排序數(shù)組二叉樹B樹Trie樹……散列方法不需要預(yù)先排序，檢索速度相對較快，但很難處理前綴查找、區(qū)域查找等問題為了減少散列沖突，需要較大的空間存儲散列表5.1.1排序數(shù)組排序數(shù)組是最簡單的詞典數(shù)據(jù)結(jié)構(gòu)可以使用二分查找的方法，在O(log(n))這一較快的時間復(fù)雜性內(nèi)，查找給定的關(guān)鍵詞缺點維護代價高，插入和刪除操作需要移動較多的元素5.1.2二叉樹（binarytree）二叉樹的平衡性是實現(xiàn)高效搜索的關(guān)鍵，為此，在增刪詞項時需要對樹節(jié)點重新進行平衡化處理5.1.3B樹（平衡樹）B樹是一種平衡的多叉樹，一棵m階的B樹滿足下列條件樹中的每個結(jié)點至多有m個孩子除根結(jié)點和葉結(jié)點外，其他每個結(jié)點至少有ceil(m/2)個孩子（ceil(x)是一個取上限函數(shù)）若根結(jié)點不是葉結(jié)點，則至少有兩個孩子有n個孩子的非終端結(jié)點恰好包含n-1個關(guān)鍵詞所有葉結(jié)點都出現(xiàn)在同一層，葉結(jié)點不包含任何關(guān)鍵字信息102030158111518212632343543m=5因為葉結(jié)點不包含關(guān)鍵詞，所以在實現(xiàn)的時候可以把葉節(jié)點看成在樹里實際上并不存在的外部節(jié)點5.1.3B樹（平衡樹）在B樹中，每個結(jié)點中的關(guān)鍵詞從小到大排列，并且當(dāng)該結(jié)點的孩子是非葉子結(jié)點時，該n個關(guān)鍵詞正好是n+1個孩子包含的關(guān)鍵字的值域的劃分B樹中一個包含n個關(guān)鍵詞、n+1個指針的結(jié)點的一般形式為(P0,

K1,P1,

K2,P2,…,Kn,Pn)其中，Ki為關(guān)鍵詞，K1<K2<…<Kn，

Pi是指向包括Ki到Ki+1之間的關(guān)鍵詞的子樹的指針102030158111518212632343543m=5B樹的查找例：查找20，21，22從根節(jié)點開始，在節(jié)點包含的關(guān)鍵詞中查找給定的關(guān)鍵詞。若找到則查找成功；否則，確定給定關(guān)鍵詞可能在哪個子樹，重復(fù)上面的操作，直到查找成功或者指針為空為止102030158111518212632343543m=5B樹的插入首先在恰當(dāng)?shù)慕Y(jié)點處添加關(guān)鍵詞，如果該結(jié)點關(guān)鍵詞不超過m-1個（例如插入22），則插入成功；否則（例如插入38），要把這個結(jié)點分裂為兩個，并把中間的一個關(guān)鍵詞取出插到結(jié)點的父親結(jié)點里去102030158111518212632343543m=5B樹的插入首先在恰當(dāng)?shù)娜~節(jié)點處添加關(guān)鍵詞，如果該節(jié)點關(guān)鍵詞不超過m-1個（例如插入22），則插入成功；否則（例如插入38），要把這個節(jié)點分裂為兩個，并把中間的一個關(guān)鍵詞取出插到節(jié)點的父親節(jié)點里去102030158111518212632343543m=5102030351581115182126323438

43B樹的插入首先在恰當(dāng)?shù)娜~結(jié)點處添加關(guān)鍵詞，如果該結(jié)點關(guān)鍵詞不超過m-1個（例如插入22），則插入成功；否則（例如插入38），要把這個結(jié)點分裂為兩個，并把中間的一個關(guān)鍵詞取出插到結(jié)點的父親結(jié)點里去如果父結(jié)點已滿，就需要再分裂，再進行向上插入如果需要分裂根，由于根沒有父結(jié)點，這時就建立一個新的根結(jié)點102030158111518212632343543m=5B樹的刪除B樹中的刪除操作與插入操作類似，但要稍微復(fù)雜一些從一個節(jié)結(jié)中刪除關(guān)鍵詞時，需要保證刪除后結(jié)點不會變得太小，因此可能需要重新安排一些結(jié)點5.1.4Trie樹Trie樹其名字來源于英文單詞reTrievalTrie樹包括兩種類型的節(jié)點：元素節(jié)點和分支節(jié)點例由“information”、“retrieval”、“system”、“introduction”四個單詞建立的Trie樹“inference”“instance”informationintroductiontfnretrievalsystemirs當(dāng)關(guān)鍵詞的長度變化較大時，Trie樹是一種特別有效的查找數(shù)據(jù)結(jié)構(gòu)Trie樹也稱作前綴樹，尤其適用于前綴式查詢?yōu)樘岣呖臻g利用率，Trie樹可以被壓縮成Patricia（PracticalAlgorithmToRetrievalInformationCodedinAlphanumeric）樹。主要壓縮一元結(jié)點，即只有一個子結(jié)點的結(jié)點informationintroductiontfnretrievalsystemirs13informationintroductiontfretrievalsystemirsTrie樹Patricia樹提綱5.1詞典搜索的數(shù)據(jù)結(jié)構(gòu)5.2通配符查詢5.3拼寫校正5.2通配符查詢基于搜索樹的方法輪排索引k-gram索引5.2.1基于搜索樹的方法尾通配符查詢?nèi)纾簃on*基于搜索樹的詞典結(jié)構(gòu)可以方便地處理尾通配符查詢?nèi)绻ㄅ浞怀霈F(xiàn)在查詢尾部該如何處理？首通配符查詢?nèi)纾?mon詞典的反向B樹原來B樹中的每個從根到葉子路徑所代表的詞項全部反過來寫如“l(fā)emon”在反向B樹中的路徑為：root-n-o-m-e-l對反向B樹遍歷后可以返回包含同一后綴的詞項一般的單通配符查詢例：se*mon同時使用B樹和反向B樹通過B樹來返回所有前綴為se且后綴非空的詞項子集W通過反向B樹來返回所有后綴為mon且前綴非空的詞項子集R對W和R求交集W∩R5.2.2輪排索引(permutermindex)在字符集中引入一個新的符號$，用于標(biāo)識詞項結(jié)束例：hello→hello$對擴展詞項的每一個旋轉(zhuǎn)結(jié)果都構(gòu)造一個指針來指向原始詞項詞項旋轉(zhuǎn)后得到的集合稱為輪排詞匯表hello$ello$hllo$helo$hel··hello利用輪排索引處理通配符查詢對于單通配符查詢m*n，將查詢進行旋轉(zhuǎn)讓*號出現(xiàn)在字符串末尾，即得到n$m*在輪排索引中查找該字符串（可以通過搜索樹方式查找），實際上等價于查找m*n的旋轉(zhuǎn)結(jié)果，從而查找到匹配通配符的原始詞項man$an$mn$ma$man··manmoron$··oron$mron$moon$mormoronn$moro含有多個通配符的查詢例fi*mo*er首先返回er$fi*對應(yīng)的詞項集合,然后檢查該集合中的每個元素，過濾掉其中不含mo的詞項fishmongerfilibuster輪排索引的缺點詞典變得非常大，因為它保存了每個詞項的所有旋轉(zhuǎn)結(jié)果5.2.3

k-gram索引一個k-gram表示由k個字符組成的序列用一個特殊的字符$表示詞項的開始或結(jié)束例：“castle”的全部3-gram包括$ca、cas、ast、stl、tle、le$在k-gram索引中，詞典由詞匯表中所有詞項的所有k-gram構(gòu)成，每個記錄表由包含該k-gram的詞項構(gòu)成利用k-gram索引處理通配符查詢例“re*ve”構(gòu)造布爾查詢“$reANDve$”返回relive、remove、retrieve等詞使用k-gram索引時往往還需要進一步處理例：red*構(gòu)造布爾查詢“$reANDred”返回retired進行“后過濾”，即利用原始的查詢red*對上述布爾查詢產(chǎn)生的結(jié)果進行逐一過濾搜索引擎通常將通配符查詢功能隱藏在一個大部分用戶不能訪問的界面（如“高級搜索”界面）如果把這些功能暴露在一般搜索界面上，用戶會受鼓勵而使用這些功能，即便在他們不是特別需要的時候（比如，通過*號只輸入查詢的前綴），這樣會大大增加搜索引擎的負(fù)擔(dān)提綱5.1詞典搜索的數(shù)據(jù)結(jié)構(gòu)5.2通配符查詢5.3拼寫校正5.3拼寫校正拼寫錯誤類型非詞錯誤（Non-wordErrors）hte→thereluctent→reluctant真詞錯誤（Real-wordErrors）字形相近three→there讀音相近piece→peacetoo→twohear→hereit’s→its非詞拼寫錯誤校正流程圖查錯（SpellingDetection）糾錯（SpellingCorrection）HCIissuesinspellingIfveryconfidentincorrectionAutocorrectLessconfidentGivethebestcorrectionLessconfidentGiveacorrectionlistUnconfidentJustflagasanerror30單詞拼寫相似性計算方法基于編輯距離的方法基于噪聲信道模型的方法基于語言模型的方法基于k-gram索引的方法5.3.1基于編輯距離的方法編輯距離（Editdistance）給定兩個字符串s1和s2，兩者的編輯距離定義為將s1轉(zhuǎn)換成s2所需的最少編輯操作數(shù)編輯操作插入（insertion）：將一個字符插入字符串刪除（deletion）：從字符串中刪除一個字符替換（substitution）：將字符串中的一個字符替換成另一個字符對調(diào)位置（transposition）：對調(diào)相鄰兩個字符的位置Levenshteindistance插入、刪除、替換Dameraudistance插入、刪除、替換、對調(diào)位置Wordswithineditdistance1of“acress”ErrorCandidateCorrectionCorrectLetterErrorLetterTypeacressactresst-deletionacresscress-ainsertionacresscaresscaactranspositionacressaccesscrsubstitutionacressacrossoesubstitutionacressacres-sinsertionacressacres-sinsertion80%oferrorsarewithineditdistance1Almostallerrorsarewithineditdistance2編輯距離的計算計算兩個字符串x1x2…xm和y1y2…yn之間的編輯距離基于動態(tài)規(guī)劃算法定義一個(m+1)×(n+1)的矩陣M，M[i,j]表示x1x2…xi和y1y2…yj的編輯距離例：求fast和cats之間的編輯距離012341234221132224333544423223311423253433433243233224322454435433422333312341234XYInitializationD(i,0)=iD(0,j)=jRecurrenceRelation: Foreachi=1…M Foreachj=1…N

D(i-1,j)+1 D(i,j)=minD(i,j-1)+1

D(i-1,j-1)+1;ifX(i)≠Y(j)

0;ifX(i)=Y(j)Termination:D(N,M)isdistanceinsertiondeletionsubstitutionXY加權(quán)最小編輯距離InitializationD(i,0)=iD(0,j)=jRecurrenceRelation: Foreachi=1…M Foreachj=1…N

D(i-1,j)+1 D(i,j)=minD(i,j-1)+1

D(i-1,j-1)+1;ifX(i)≠Y(j)

0;ifX(i)=Y(j)Termination:D(N,M)isdistancesomelettersaremorelikelytobemistypedthanothersinsertiondeletionsubstitution例如，將字符s替換成p的權(quán)重將會比將s替換成a的權(quán)重大，因為在鍵盤上a離s更近，因此花費的代價更小拼寫錯誤的混淆矩陣Initialization:D(0,0)=0D(i,0)=D(i-1,0)+del[x(i)];1<i≤ND(0,j)=D(0,j-1)+ins[y(j)];1<j≤MRecurrenceRelation:

D(i-1,j)+del[x(i)]D(i,j)=minD(i,j-1)+ins[y(j)]D(i-1,j-1)+sub[x(i),y(j)]Termination:D(N,M)isdistanceXY5.3.2基于噪聲信道模型的方法噪聲信道模型

（NoisyChannelModel）Foramisspelledwordx,findthecorrectwordw.LanguageModel，PriorProbabilityChannelModel，ErrorProbabilityWordswithin1of“acress”Error(x)CandidateCorrection(w)CorrectLetterErrorLetterTypeacressactresst-deletionacresscress-ainsertionacresscaresscaactranspositionacressaccesscrsubstitutionacressacrossoesubstitutionacressacres-sinsertionacressacres-sinsertionPriorProbabilityUnigramPriorprobabilityCountsfrom404,253,213wordsin

CorpusofContemporaryEnglish(COCA)wordFrequencyofwordP(word)actress9,321.0000230573cress220.0000005442caress686.0000016969access37,038.0000916207across120,844.0002989314acres12,874.0000318463ErrorProbabilityComputingerrorprobability:confusionmatrix del[x,y]:count(xytypedasx) ins[x,y]:count(xtypedasxy) sub[x,y]:count(xtypedasy) trans[x,y]:count(xytypedasyx)ErrorProbabilityComputingerrorprobability:confusionmatrix del[x,y]:count(xytypedasx) ins[x,y]:count(xtypedasxy) sub[x,y]:count(xtypedasy) trans[x,y]:count(xytypedasyx)ErrorProbabilityComputingerrorprobability:confusionmatrix del[x,y]:count(xytypedasx) ins[x,y]:count(xtypedasxy) sub[x,y]:count(xtypedasy) trans[x,y]:count(xytypedasyx)x=x1,x2,x3…xmw=w1,w2,w3,…,wnChannelmodelforacressCandidateCorrectionCorrectLetterErrorLetterx|wP(x|word)P(word)109*P(x|w)P(w)actresst-c|ct.000117.00002312.7cress-aa|#.00000144.000000544.00078caresscaacac|ca.00000164.00000170.0028accesscrr|c.000000209.0000916.019acrossoee|o.0000093.0002992.8acres-ses|e.0000321.00003181.0acres-sss|s.0000342.00003181.0NoisychannelprobabilityforacressCandidateCorrectionCorrectLetterErrorLetterx|wP(x|word)P(word)109*P(x|w)P(w)actresst-c|ct.000117.00002312.7cress-aa|#.00000144.000000544.00078caresscaacac|ca.00000164.00000170.0028accesscrr|c.000000209.0000916.019acrossoee|o.0000093.0002992.8acres-ses|e.0000321.00003181.0acres-sss|s.0000342.00003181.05.3.3基于語言模型的方法Usingabig