信息檢索

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

K1,P1,

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

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

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

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