信息检索 第05章 词典及容错式检索专业课课件

信息检索

第05章词典及容错式检索软件学院教研室陈鄞引言词汇表的存取是实现倒排文件查询的第一个步骤，需要非常高的存取效率词汇表的查找操作通常采用称为词典的数据结构本章将介绍支持词典快速查找的一些数据结构当查询中存在拼写错误时，IR系统通常提供自动校正技术IR系统通常提供通配符查询功能本章内容5.1词典搜索的数据结构5.2通配符查询5.3拼写校正5.1词典搜索的数据结构基于字符串排序的方法排序数组二叉树B树Trie树……散列方法不需要预先排序，检索速度相对较快，但很难处理前缀查找、区域查找等问题为了减少散列冲突，需要较大的空间存储散列表5.1.1排序数组排序数组是最简单的词典数据结构可以使用二分查找的方法，在O(log(n))这一较快的时间复杂性内，查找给定的关键词缺点维护代价高，插入和删除操作需要移动较多的元素5.1.2二叉树（binarytree）二叉树的平衡性是实现高效搜索的关键，为此，在增删词项时需要对树节点重新进行平衡化处理5.1.3B树（平衡树）B树是一种平衡的多叉树，一棵m阶的B树满足下列条件树中的每个结点至多有m个孩子除根结点和叶结点外，其他每个结点至少有ceil(m/2)个孩子（ceil(x)是一个取上限函数）若根结点不是叶结点，则至少有两个孩子有n个孩子的非终端结点恰好包含n-1个关键词所有叶结点都出现在同一层，叶结点不包含任何关键字信息102030158111518212632343543m=5因为叶结点不包含关键词，所以在实现的时候可以把叶节点看成在树里实际上并不存在的外部节点5.1.3B树（平衡树）在B树中，每个结点中的关键词从小到大排列，并且当该结点的孩子是非叶子结点时，该n个关键词正好是n+1个孩子包含的关键字的值域的划分B树中一个包含n个关键词、n+1个指针的结点的一般形式为(P0,

K1,P1,

K2,P2,…,Kn,Pn)其中，Ki为关键词，K1<K2<…<Kn，

Pi是指向包括Ki到Ki+1之间的关键词的子树的指针102030158111518212632343543m=5B树的查找例：查找20，21，22从根节点开始，在节点包含的关键词中查找给定的关键词。若找到则查找成功；否则，确定给定关键词可能在哪个子树，重复上面的操作，直到查找成功或者指针为空为止102030158111518212632343543m=5B树的插入首先在恰当的结点处添加关键词，如果该结点关键词不超过m-1个（例如插入22），则插入成功；否则（例如插入38），要把这个结点分裂为两个，并把中间的一个关键词取出插到结点的父亲结点里去102030158111518212632343543m=5B树的插入首先在恰当的叶节点处添加关键词，如果该节点关键词不超过m-1个（例如插入22），则插入成功；否则（例如插入38），要把这个节点分裂为两个，并把中间的一个关键词取出插到节点的父亲节点里去102030158111518212632343543m=5102030351581115182126323438

43B树的插入首先在恰当的叶结点处添加关键词，如果该结点关键词不超过m-1个（例如插入22），则插入成功；否则（例如插入38），要把这个结点分裂为两个，并把中间的一个关键词取出插到结点的父亲结点里去如果父结点已满，就需要再分裂，再进行向上插入如果需要分裂根，由于根没有父结点，这时就建立一个新的根结点102030158111518212632343543m=5B树的删除B树中的删除操作与插入操作类似，但要稍微复杂一些从一个节结中删除关键词时，需要保证删除后结点不会变得太小，因此可能需要重新安排一些结点5.1.4Trie树Trie树其名字来源于英文单词reTrievalTrie树包括两种类型的节点：元素节点和分支节点例由“information”、“retrieval”、“system”、“introduction”四个单词建立的Trie树“inference”“instance”informationintroductiontfnretrievalsystemirs当关键词的长度变化较大时，Trie树是一种特别有效的查找数据结构Trie树也称作前缀树，尤其适用于前缀式查询为提高空间利用率，Trie树可以被压缩成Patricia（PracticalAlgorithmToRetrievalInformationCodedinAlphanumeric）树。主要压缩一元结点，即只有一个子结点的结点informationintroductiontfnretrievalsystemirs13informationintroductiontfretrievalsystemirsTrie树Patricia树提纲5.1词典搜索的数据结构5.2通配符查询5.3拼写校正5.2通配符查询基于搜索树的方法轮排索引k-gram索引5.2.1基于搜索树的方法尾通配符查询如：mon*基于搜索树的词典结构可以方便地处理尾通配符查询如果通配符不出现在查询尾部该如何处理？首通配符查询如：*mon词典的反向B树原来B树中的每个从根到叶子路径所代表的词项全部反过来写如“lemon”在反向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)在字符集中引入一个新的符号$，用于标识词项结束例：hello→hello$对扩展词项的每一个旋转结果都构造一个指针来指向原始词项词项旋转后得到的集合称为轮排词汇表hello$ello$hllo$helo$hel··hello利用轮排索引处理通配符查询对于单通配符查询m*n，将查询进行旋转让*号出现在字符串末尾，即得到n$m*在轮排索引中查找该字符串（可以通过搜索树方式查找），实际上等价于查找m*n的旋转结果，从而查找到匹配通配符的原始词项man$an$mn$ma$man··manmoron$··oron$mron$moon$mormoronn$moro含有多个通配符的查询例fi*mo*er首先返回er$fi*对应的词项集合,然后检查该集合中的每个元素，过滤掉其中不含mo的词项fishmongerfilibuster轮排索引的缺点词典变得非常大，因为它保存了每个词项的所有旋转结果5.2.3

k-gram索引一个k-gram表示由k个字符组成的序列用一个特殊的字符$表示词项的开始或结束例：“castle”的全部3-gram包括$ca、cas、ast、stl、tle、le$在k-gram索引中，词典由词汇表中所有词项的所有k-gram构成，每个记录表由包含该k-gram的词项构成利用k-gram索引处理通配符查询例“re*ve”构造布尔查询“$reANDve$”返回relive、remove、retrieve等词使用k-gram索引时往往还需要进一步处理例：red*构造布尔查询“$reANDred”返回retired进行“后过滤”，即利用原始的查询red*对上述布尔查询产生的结果进行逐一过滤搜索引擎通常将通配符查询功能隐藏在一个大部分用户不能访问的界面（如“高级搜索”界面）如果把这些功能暴露在一般搜索界面上，用户会受鼓励而使用这些功能，即便在他们不是特别需要的时候（比如，通过*号只输入查询的前缀），这样会大大增加搜索引擎的负担提纲5.1词典搜索的数据结构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转换成s2所需的最少编辑操作数编辑操作插入（insertion）：将一个字符插入字符串删除（deletion）：从字符串中删除一个字符替换（substitution）：将字符串中的一个字符替换成另一个字符对调位置（transposition）：对调相邻两个字符的位置Levenshteindistance插入、删除、替换Dameraudistance插入、删除、替换、对调位置Wordswithineditdistance1of“acress”ErrorCandidateCorrectionCorrectLetterErrorLetterTypeacressactresst-deletionacresscress-ainsertionacresscaresscaactranspositionacressaccesscrsubstitutionacressacrossoesubstitutionacressacres-sinsertionacressacres-sinsertion80%oferrorsarewithineditdistance1Almostallerrorsarewithineditdistance2编辑距离的计算计算两个字符串x1x2…xm和y1y2…yn之间的编辑距离基于动态规划算法定义一个(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加权最小编辑距离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的权重将会比将s替换成a的权重大，因为在键盘上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