主题：[推荐]《An Introduction to Information Retrieval》参考译文之四——字典和容错性检索（tolerant retrieval）

容错性检索允许信息检索系统能够有效的应对键入错误或者替代拼写问题。常见的符号就是*，它代表着任意数量的字符（包含没有）。如果用户无法确定正确的拼写方式，或者想搜索查询词语的某些变体形式，这些都需要使用容错性检索。

3．1 字典的数据结构
给定一个现成的查询和索引，信息检索系统的主要任务就是决定查询词语出现对应哪些词表中的词项，如果有，则通过指针获取到对应的标记列表。词表的组织方式有两种，分别是哈希表方式（hashing）和搜索树（search tree）方式。在这些数据结构中，通常将词表中的词称为键（key）。不论使用哪种方式，一定要解决下面几个问题：
1）键的数量为多少？
2）键的数量是静态的还是动态的？如果是动态的，这种改变是因为插入新的键还是因为删除了现有键？
3）不同键的相对访问频率为多少？
哈希表是一种常见的词表组织方式，广泛的应用于搜索引擎的设计中。每个键都被映射为一个很难重复的整数值。如果出现了重复，往往需要额外的数据结构来辅助解决。这里不建议使用能够消除重复的哈希算法，因为它们的实施复杂度和运算复杂度都较高。采用哈希算法，即便是具有轻微差别的变体词，也会被映射为完全不同的数据。所以，这种方式并不易于实现这种模糊检索。另外，即便是适应当前数据特点的哈希函数也不一定适用于经常被更新的数据，因此对经常更新的动态数据而言，使用哈希方式并不十分理想。
搜索树方式就能克服上述不足。首先，它可以运行查询诸如开头为某些特定字符的相关词语。最为著名的搜索树就是二叉树（binary tree），它的每个节点都只有两个子节点。搜索首先从根节点开始，包括根节点在内的每个节点都代表着一个二值判断，从而决定下一个需要处理的节点。

要想实现有效的检索，必须要保证整个二叉树基本平衡。任何一个节点的两个子节点所包含的下级子节点数量应当相同或者只相差一个。当添加了新的节点或者删除了原有的旧节点，都需要对整个树结构重新进行平衡处理。
为了减轻重新平衡操作的压力，一个可行的方法就是将每个节点的下级节点树限定在一个固定的范围内变化。所以，字典所使用的搜索树往往都是B树，这种树结构中每个节点的下级子节点都位于一个固定的范围内[a,b]，这里的a和b都是一个合适的正整数。

B树可以看成是将多个不同层次的二叉树折叠了起来。对于基于磁盘存储的字典而言，这样做效果很好，可以预读取相关数据。在这种情况下，a和b的值都受到磁盘块结构大小的影响。值得注意的是，和哈希表不一样，搜索树需要存储的键值具有一个预先设定的顺序，如按照A到Z的字母顺序等。一些亚洲字符，如中文可能具有多种排序方式，所以必须首先设定好一种顺序方式才能使用搜索树。

3．2 通配符查询（Wildcard queries）
通配符查询适用于下面几种情况：
1）用户无法确定正确的拼写方式（Sydney和Sidney，使用S*dney）
2）用户知道词语的多种变体，想找到任何一种变体词语的相关信息（color和colour）
3）用户无法确定搜索引擎是否截取了所要找的变体词语（judicial和judiciary，使用judicia*）
4）用户无法知道外来词语的正确的翻译写法（Peking和Beijing）
通配符检索分为很多种。常见的方式就是尾部通配符检索（trailing wildcard query），如mon*，此时通配符只使用一次并且应用于词语的尾部。搜索树的字典结构非常适合这种类型的检索需求：从键值为m的节点开始下移，依次找到o和n的相关节点，最终就能得到以mon开头的所有词语，然后在根据这些词语索引找到标记列表。
但是，对于通配符不位于尾部的词语，又该如何进行处理呢？
对于首部通配符检索（leading wildcard query），如*mon。这时可以使用翻转B树结构来处理，在它的结构中，从根结点到叶节点对应的路径正好就是正常B树中的叶节点到根节点的路径。
对于位于中间的通配符检索，有效的结合标准B树（regular B-tree）和翻转B树（reverse B-tree）完全可以实现检索要求。如对于se*mon而言，首先可以使用标准B树来搜索所有以se开头的词项，然后在到翻转B树中搜索所有以mon结尾的词项，将得到的两个命中词项结果计算并集。这个并集中的所有词语就是满足条件的全部搜索词项。
对于一般的通用型通配符查询而言，如位于中间的通配符等，完全可以使用更为特殊的索引来加快处理速度。

3．2．1 轮排索引（Permuterm index）
它是倒排索引的一种。首先，需要引入一种特殊的标记$，用以表示词语的结尾，如词语term应该表示为term$。其次，对于所要索引的词语设置轮排索引，将它的所有轮排变换形式都制作相应的索引项，如：

此主题相关图片如下：

通常将轮排索引中的所有轮排词语项构成的整体称为轮排词表（permuterm vocabulary）。
如何利用轮排索引来处理通配符查询呢？如m*n，对它的处理要点在于要将*轮排到词语的末尾，因此，最终形成的查询词语为n$m*。接下里，就需要对轮排索引中的所有词语进行匹配查询。
轮排索引最终可以使得我们获取满足匹配条件的所有词语，然后还要根据这些词语进一步查询相关文档。对于单独的*，可以匹配任意词语，但是对于fi*mo*er之类的通配符查询该怎么处理呢？首先，需要在轮排索引中查询满足er$fi*条件的所有词语，当然，获得的词语显然不会都包含mo，所以接下来就需要非常费时费力的逐项查询。
由于轮排索引需要存放每个词语的所有轮排对应项，所以它的规模会很大。
值得注意的是，轮排索引和B树有非常密切的联系。事实上，常见的组合就是轮排B树。

3．2．2 k-gram索引（k-gram index）
对于轮排索引而言，虽然简单，但是却会造成字典规模的过分增大。相比而言，k-gram索引就显得更为高效和灵活。所谓k-gram，是指一个由k个字符组成的序列，如castle包含的3-grams就有三个，分别为cas，ast和stl。如果使用特殊的符号$来标记词语的开头和结尾，则castle所有的3-grams就为$ca，cas，ast，stl，tle，le$。
在k-gram索引中，字典将会对任何词语的所有k-gram元素进行索引。每个k-gram索引项都指向所有包含这个k-gram的词语。
使用k-gram索引如何来处理通配符查询呢？考虑查询re*ve，首先可以将此查询理解为等价的布尔查询$re AND ve$，这可以在3-grams索引中找到所有的匹配词语。
然而有时也会存在问题。如查询red*，转换为等价的布尔查询后为：$re AND red，但是retired会被命中，虽然它并不符合原先的通配符定义。为了解决这个问题，必须要采用后置过滤步骤，即对布尔查询所得到的全部词语进一步和原先的通配符进行匹配比较，以确定是否满足要求。
可以注意到，通配符查询可以产生多个命中的查询词语，每一个词语都是需要在标准倒排索引上继续查询相关文档。很多搜索引擎还可以允许结合使用布尔检索和通配符检索，如re*d AND fe*ri，它所命中的文档需要同时含有匹配re*d的词语和匹配fe*ri的词语。
即便是没有布尔查询与通配符查询的结合，通配符查询的处理仍然是比较复杂的，它既需要查找一些额外的特殊索引，而且还要过滤相关词语，并最终以得到的命中词语再去查找标准倒排索引。一个搜索引擎当然要支持如此强大的功能，但是在通常情况下，这项功能都会隐藏在高级查询界面中，大多数的用户不会去使用它。相反，如果在主页上直接显示这项功能反而会激发用户进行一些本来并无必要的访问，如a*等，无疑会增加搜索引擎服务器的负担。

3．3 拼写矫正
用户可能键入错误的查询词语，导致查询的失败。Google在网站上公布了各种键入“britney spears”词语错误的情况。

对这种问题的解决可以采用两种做法，一是编辑距离法，另一个是k-gram重叠法。

3．3．1 拼写矫正的实现
任何拼写矫正算法都有两个基本原则：
1）对任何错误的拼写词语，总是要选择一个最接近（nearest）的正确词语来替换之。这就要求要有一种可以计算两个查询词语相近程度的方法。
2）如果有多个正确的词语可供选择，而且最接近的词语也多于一个，此时就需要选择一个最常见的词语作为替代词语。如grunt和grant都是与grnt最为接近的替换词语。判断哪个词语更常见，可以通过比较词语在所有文档集合中的出现频率来判断。在搜索引擎中更为常见的一种判断策略是检查词语在用户键入的所有查询词语中出现的频率，显然，这更符合Web用户使用的实际情况。

在得到拼写矫正的词语后，搜索引擎通常会继续下一步的处理，可以分为以下几种常见情况（以用户键入carot为例）：
1）检索所有含有carot的相关文档，同时还检索所有拼写正确的相关词语，如carrot和tarot。
2）和1）一样，但是只有在字典中没有查询词语carot时才进行同样的操作。
3）和1）一样，但是只有在原先的查询返回结果远远少于矫正后的查询结果时，或者说原先的查询结果少于5篇文档等。
4）一旦原先的查询返回结果远远少于矫正后的查询结果时，搜索引擎界面上通常就会显示一个拼写建议，它由相关的正确词语组成，如这里可以为显示“Did you mean carrot?”。

3．3．2 拼写矫正的方式
常见的拼写矫正方式可以分为两种，一种是词语独立式（isolated-term），一种是上下文相关式（context-sensitive）。前者一次只进行一个词语的独立矫正，即便是用户的一次查询可以键入多个查询词语。然而，由于用户键入的词语往往存在密切的语义联系，所以这种词语独立式的矫正方法会产生一些错误，如查询“flew form Heathrow”中的form明显是from的错误拼写，但是按照词语独立式方法检测，将很难给出正确的矫正词语。

3．3．2．1 词语独立式的矫正方法
它主要基于编辑距离法和k-gram重叠法。
1）编辑距离法
编辑距离也被称为Levenshtein距离。给定两个字符串s1和s2，它们的编辑距离就是将s1转换为s2所需的最少操作步骤次数。这些操作步骤包括插入、删除和替换。如cat和dog的编辑距离为3。事实上，在计算编辑距离时，可以对不同的操作指定不同的权值，如对字符s而言，如果替换成p则理应比替换成a要具有更大的权重，因为在键盘上s和a的距离要比s和p的距离更近。根据出现的可能性来设置不同的权重显然具有很大的实际意义。为了简化问题，下文所说的问题只考虑相同权重的情况。
计算s1和s2的编辑距离需要花费的时间为O（|s1|×|s2|），这里的|s|表示字符串s的长度。
该方法中的字符串s1和s2都是以数组的方式提供的。算法的主要内容在于以整数元素来填充一个矩阵，该矩阵的两个维度正好是两个字符串的长度，矩阵元素（i，j）表示s1前面i个字符和s2前面j个字符之间的编辑距离。

每个矩阵元素都分为四个小格子，右下角的格子中存在其他三个格子的最小值，其他三个格子的数值分别为m[i-1,j-1]+0或者m[i-1,j-1]+1（依赖于s1[i]是否等于s2[j]），m[i-1,j]+1和m[I,j-1]+1。
当然，拼写矫正问题远非仅仅一个编辑距离的计算问题。给定一个字符串集合S，查找与查询p之间编辑距离最小的相关字符串集合V。由于事先已经知道需要计算的相关编码（即编辑距离最小的相关字符串集合V），所以可以将计算编辑距离的问题看成是一个解码问题。
由于这种计算需要匹配所有可能的字符串，因此计算消耗相当惊人。所以在实践中，往往可以使用一些启发式算法来快速得到更有可能具有较小编辑距离的词语。最为简单的方法就是限定搜索的字典范围，只限于那些和查询词具有相同开头字母的词语，因为一般而言拼写错误不会发生在第一个字母上。更为复杂的方法是利用轮排索引，此时无需再次使用结束标记$。不过，这种方法也存在一些问题。考虑查询q，对于它的每个轮排词语，都可以从B树中找到所有以这个轮排词语开头的词语。如查询词语为mase，轮排词语为sema，这样可以找到诸如semantic或者semaphore一些编辑距离并不小的词语。同时，对于诸如mare和mane之类更为合适的词语，使用轮排索引并不能找到相关词语。为了解决这些问题，可以对此方法进行改进，如对每次产生的轮排查询都截取后面的若干字符后缀，这个后缀的长度应该根据查询词语的长度来设定，一般为2个字符，然后再进行相关词语的扩展检索。这样既可以保证找到一些利用简单轮排无法直接找到的正确词语，也可以保证这些找到的词语和原先的词语具有相同的一部分子串。
2）k-gram重叠法
为了进一步限定计算编辑距离的相关词语集合，可以使用k-gram索引来获取具有较小编辑距离的相关词语。一旦获取这些词语，即可从中找到具有最小编辑距离的词语。
事实上，使用k-gram索引可以有效的获取与查询词具有很多相同k-gram的词语。当然，究竟什么是“具有很多相同k-gram”值得探讨，但是相关的处理过程却很简单，那就是一次性的遍历所有的k-gram索引，以确定是否出现在查询词语中。

下图展示了2-gram索引（也被称为bigram索引），内容为与查询词bord有关的三个标记：

此主题相关图片如下：

假设需要检索包含上述三个bigram中至少2个的词语，一次性的遍历bigram索引即可找到所有相关词语，结果为“aboard，boardroom，border”。但是，这种利用标记并操作的直接方法来暴露出很多问题，如词语boardroom明显就不能看成bord的矫正写法。所以，需要探索一种可以更为精确测量k-gram索引标记词语和查询词语重叠度的方法。常见的方法就是Jaccard系数，它通常用于测度两个集合的重叠程度，定义为：|A∩B|/|A∪B|。随着处理的进行，一个个具有相同gram的词表词语都被取出和查询词语比对Jaccard系数，一旦超过一定阈值，就可以输出对应的词语。
不过，为了计算Jaccard系数，需要得到查询词语q和标记词语t的k-gram集合。由于需要拿查询词语q的所有k-gram去比较k-gram索引，所以很容易得到查询词语的所有k-gram。但是，如何得到标记词语t的k-gram集合呢？虽然可以实时分析得到，但是这种方法显然低效，所以一种简单有效的方法就是利用词语的长度。如在上述例子中，bord查询词语有两个匹配标记词语boardroom的k-gram，因此计算为：2/(8+3-2)。
也可以使用其他方法来计算词语的匹配程度。经验表明，首先使用k-gram索引来得到候选的词语，然后再计算这些词语与查询词语的编辑距离，选择编辑距离最小的词语作为最后的输出。

3．3．2．2 上下文相关式的矫正方法
词语独立式的矫正方法难以处理一些虽然单个词语没错但是整体表达出现错误的问题，如“flew form Heathrow”。由于这种拼写会产生较少的匹配结果，所以很多搜索引擎会及时的给出提示“flew from Heathrow”。这种效果需要比较复杂的处理过程，首先需要按照前文所述方法得到该查询中所有词语的其他相关正确词语，其次要对这些词语进行各种组合，如“fled form Heathrow”、“flew fore Heathrow”等，最后再对每一个候选项计算可能的命中结果数量，返回那个匹配数量最多的词语组合。
当然，如果具有较多的查询词语，而每个词语又有较多的匹配词语，这样的矫正做法未免过于代价昂贵，所需的计算数量是非常惊人的。可以借鉴一些启发式方法来缩小计算的所需数量，如可以通过查询最为常见的词语集合列表和相关用户查询日志信息。如发现flew from的共现频率明显高于其他的一些组合，因此就可以在接下来的比较中，直接拿这个词语组合来和剩下的词语进行匹配。当然，由于用户查询日志信息可能也有错误，但是从统计上看，这种错误词语组合的数量一定明显小于正确词语组合的数量。

3．4 语音矫正（Phonetic correction）
语音矫正也是一种容错性检索（tolerant retrieval），它主要适用于用户键入的查询词语表现为虽然文字错误但是语音正确的情况，这种方法非常有助于人名检索。它的主要思想就是对每个词语生成相应的语音哈希（phonetic hash），所以具有相似读音的词语会具有相似的语音哈希值。这个方法来源于20世纪早期国际警察组织的相关工作，他们主要通过这种方法来查找由于国别原因造成名称不同的可疑罪犯。它广泛的应用于专有名词的语音矫正中。
计算语音哈希的算法就是广被人知的soundex算法。目前这种算法有很多变体，都是基于一种基本原则：
1）将每个被索引的词语转换为4个字符的简化形式，被对这些简化词语制作相应的倒排索引，这个索引通常也被称为soundex索引。
2）将查询词语也做同样的简化分析处理。
3）当要求进行语音查询时，利用soundex索引来得到命中结果。
其中，简化词语的做法通常会产生4个字符的结果词语，它的首字符是字母，而后的三个字符为0到9之间的数字。具体计算方法如下：
1）保持原有词语的首字母。
2）将下列字母全部转换为0：A，E，I，O，U，H，W，Y。
3）将下列字母分别转换为对应的数字：
B, F, P, V to 1.
C, G, J, K, Q, S, X, Z to 2.
D,T to 3.
L to 4.
M, N to 5.
R to 6
4）不断的对连续出现的两个相同数字化简为一个数字，直至不出现连续的相同数字。
5）将结果中的所有0删除。如果整体长度不足，以0补充，如果长度超出，则截取前四个字符。最终得到的结果应该为一个字母带3个数字。
如词语“Hermann”的语音哈希为H655。
这个算法基于以下几个基本经验，这些做法可以使得相关的名称往往具有相同的语音哈希：1）在描述姓名时，元音可以互换；2）具有相似发音的辅音可以看成是等价的，如D和T。
虽然这种方法非常适用于诸如欧洲语系的各种语言，但是它在处理其他一些语系语言时可能不是非常有效。如中文姓名既可以按照威氏注音（Wade-Giles Spelling），也可以按照拼描述（Pinyin transcription）。而这两种方法的语音哈希并不一致，如威氏注音的hs和拼音种的x都映射为2