[拼写校正]　

　　对于大多数拼写校正 (spelling correction)算法而言,存在以下两个基本的原则。

　　(1) 对于一个拼写错误的查询,在其可能的正确拼写中,选择距离“最近” 的一个。这就要求在查询之间有距离或者邻近度的概念。

　　(2) 当两个正确拼写查询邻近度相等(或相近)时,选择更常见的那个。例如,grunt 和 grant都是查询 grnt 的可能的正确拼写。算法将会从它们之中选择更常见的那个作为最后的拼写结果。最简单的情况下, "更常见”可以通过统计各词项在文档集中出现的次数来获得。因此,如果grunt 在文档集中比 grant 出现得更多,则选择 grunt 作为校正结果。在很多搜索引擎中使用了另一种“ 更常见” 的概念,其基本思路是,使用所有其他用户输入的查询中出现最频繁的拼写形式作为最后的选择。也就是说,如果用户输入 grunt 作为查询的次数相比 grant 更多的话,那么用户输入 grnt 更有可能是想要查询 grunt。

　　拼写校正算法基于这些邻近度计算, 其功能主要通过以下几种方式来返回给用户。

　　(1) 输入查询 carot,系统往往在返回包含 carot 的文档的同时,也返回包含 carot 多种可能拼写校正结果(如 carrot 和 tarot)的文档。

　　(2) 当 carot 不在词典中时,采用第 1 种做法。

　　(3) 当原始查询返回的文档结果数目少于预定值(比如少于 5 篇文档) 采用第 1 种做法。

　　(4) 当原始查询返回的文档数目少于预定值时,搜索界面中会给用户提供一个拼写建议(spelling suggestion),建议中会包含拼写校正之后的结果。因此,这实际上相当于搜索引擎和用户进行交互: 你是在找 carrot 吗” ?

　　两种拼写校正的方法:一种是词项独立(isolated-term)的校正,另一种是上下文敏感(context-sensitive)的校正。在词项独立的校正方法中,不管查询中包含多少个查询词项,其每次只考虑一个词项的校正,也就说在校正时词项之间是相互独立的。上面给出的 carot 的例子就属于这一类做法。利用这种词项独立校正的方法,很难检测到查询 flew formHeathrow 中实际上包含一个错误的词项 form(正确的形式应该是 from),这是因为在校正时每个词项之间是相互独立的。

　　有两种词项独立的校正方法:编辑距离方法及 k-gram 重合度方法。

[编辑距离]

　　给定两个字符串s1 及s2,两者的编辑距离(edit distance)定义为将s1 转换成s2 的最小编辑操作(edit operation)数。通常,这些编辑操作包括:

　　　　(i) 将一个字符插入字符串;

　　　　(ii) 从字符串中删除一个字符;

　　　　(iii) 将字符串中的一个字符替换成另外一个字符。

　　 对于这些操作,编辑距离有时也称为Levenshtein 1 距离(Levenshtein distance)。例如,cat和dog的编辑距离是 3。实际上,编辑距离的概念可以进一步推广,比如允许不同的编辑操作具有不同的权重。例如,将字符s替换成字符p的权重会比将s换成a的权重大(这是因为在键盘上a离s更近,因此花费的代价更小) 采用这样的权重定义方法。(即根据字符之间替换的可能性计算权重)在实践中非常有效。然而,下面我们只考虑所有的编辑操作具有等权重的情况。

        可以在 O(|s1| × |s2|)的时间复杂度下计算两个字符串 s1 和 s2 的(带权)编辑距离,其中,|si| (i=1,2)表示字符串 si 的长度。其主要解决思路是采用动态规划算法,其中 s1 和 s2 以字符数组的方式进行存放。整数矩阵 m 的行数和列数分别是两个字符串的长度,算法在运行中不断填写矩阵元素。算法运行结束后,矩阵第 i 行第 j 列的元素保存的是s1 的前 i 个字符构成的字符串和 s2 前 j 个字符构成的字符串的编辑距离。

[拼写校正中的 k-gram 索引]

　　我们利用 k-gram 索引来查找与查询具有很多公共 k-gram 的词项。只要对“ 具有很多公共 k-gram” 进行合理定义,我们认为上述查找实际上是对查询字符串 q 中 k-gram 的倒排记录表进行单遍扫描的过程。图 3-7 给出的是查询 bord 的 2-gram 索引的一个片段,其中包含 3 个 2-gram 组成的倒排记录表。假定我们想返回包含上面 3 个 2-gram 中的至少 2 个词项,对倒排记录表的单遍扫描(和第 1章类似)会返回满足该条件的所有词项,本例当中,这些词项包括 aboard、boardroom 及 border。

　　这种通过线性扫描并立即合并倒排记录表的做法十分简单,只需要待匹配词项包含查询 q中某个固定数目的 k-gram 即可。但是这种做法有一个缺点,比如 boardroom 这种不可能是 bord的正确拼写形式的词也会被返回。所以,我们需要计算词汇表中词项与查询 q 之间更精细的重合度计算方法。比如采用雅可比系数(Jaccard coefficient)就可以对先前的线性扫描合并方法进行修正。这里,雅可比系数的计算公式为|A∩B|/|A∪B|,其中 A、B 分别是查询 q、词汇表词项中的 k-gram 集合。扫描过程中,一旦扫描到当前的词项 t,就快速计算出 q 和 t 的雅可比系数,然后继续扫描下一个词项。如果雅可比系数超过预定的阈值,则将 t 输出。

　　上述过程表明,在计算雅可比系数时,我们需要知道 q 和 t 的 k-gram 集合。由于是对q中的所有k-gram扫描倒排记录表,因此q中的k-gram集合是已知的,于是问题就变成如何求解t中的所有k-gram。理论上,我们可以穷举出t中所有的k-gram。但是这种做法不仅慢而且在实际中也难以实现。在很多情况下,倒排记录本身很可能并不包含完整的t字符串而往往是t的某种编码形式。也就是说,往往并不知道t的k-gram集合。然而,一个重要的发现使得这种情况下q和t雅可比系数的计算成为可能。这个发现就是,在计算雅可比系数的时候,我们只需要知道t的长度即可。为了说明这一点,我们重新回到图 3-7 中的例子,对于查询q = board扫描倒排记录表直到t = boardroom 2 。这时我们知道有 2 个 2-gram已经匹配上了。如果倒排记录表中已经预先记录了boardroom所包含的 2-gram的数目(这里是 8),那么所有计算雅可比系数的信息都已知,计算公式为:2/(8+3-2)。其中,分子为倒排记录的命中数(值为 2,分别来自bo和rd),分母为bord及boardroom中的 2-gram之和减去倒排记录表的命中数。

　　需要指出的是,也可以把雅可比系数替换成其他能够进行快速计算的衡量指标。一个经验性的方法是,首先使用 k-gram 索引返回可能是q 的潜在正确拼写形式的词项集合,然后计算该集合中的每个元素和 q 之间的编辑距离并选择具有较小距离的那些词项。

[基于发音的校正技术] 

　　最后一项用户容错检索技术与发音校正有关,即拼写错误的原因在于用户输入了一个和目标词项发音相似的查询。该方法尤其适用于人名的查找,其基本的思路是:对每个词项,进行一个语音哈希操作,发音相似的词项都被映射为同一值。该思路最早源于国际警察部门的工作,它们自 20 世纪初开始就在全球范围内寻找与犯罪嫌疑人发音相似的人名,而不管这些人名在不同国家的发音是否有所不同。上述思路主要用于专有名词的语音校正。

　　这一类通过语音哈希的方法通常统称为 soundex 算法(soundex algorithm)。其中,一个原始的 soundex 算法的构建方法如下。需要指出的是,该基本算法存在很多变形。

　　　　(1) 将所有的词项转变为四字符的简化形式。基于这些简化形式建立原始词项的倒排索引,该索引被称为 soundex 索引。

　　　　(2) 对查询词项进行同样的操作。

　　　　(3) 当对查询进行 soundex 匹配时,就在 soundex 索引中搜索。

　　上述算法不同变形之间的主要区别在于将词项转变为四字符简化形式的方法不同。一个普遍使用的算法, 其中第 1 个字符是字母而其他 3 个字符是 0~9 之遍使用的转换方法会得到四字符的编码结果, 间的数字。转换方法如下。

　　　　(1) 保留词项的首字母。

　　　　(2) 将后续所有的 A、E、I、O、U、H、W 及 Y 等字母转换为 0。

　　　　(3) 其他字母的转换规则如下:　　　　　　将 B、F、P 和 V 转换为 1;　　　　　　将 C、G、J、K、Q、S、X 和 Z 转换为 2;　　　　　　将 D 和 T 转换为 3;　　　　　　将 L 转换为 4;　　　　　　将 M 和 N 转换为 5;　　　　　　将 R 转换为 6。　　　　(4) 将连续出现的两个同一字符转换为一个字符直至再没有这种现象出现。　　　　(5) 在结果字符串中剔除 0,并在结果字符串尾部补足 0,然后返回前四个字符,该字符由1 个字母加上 3 个数字组成。

　　利用上述转换方法,就可以将 Herman 转换为 H655。给定一个查询(比如 herman),可以计算其 soundex 编码然后从 soundex 索引中返回具有相同编码的词项,最后再在普通倒排索引中得到最后结果。