拼写纠正_拼音手写混合输入法[通俗易懂]

拼写纠正

主要关注查询的拼写校正。例如，用户输入carot时，实际上可能想返回包含词项carrot的文档。Google的报告指出，当用户输入britian spears、britney’s spears、brandy spears或者prittany spears时，实际上搜索引擎都会当成是britney spears的错误拼写来处理。我们将会考虑解决该问题的两个步骤：第一步基于编程距离（edit distance），第二步基于k-gram重合度（k-gram overlap）。在介绍详细算法之前，我们首先简单介绍一下搜索引擎是如何实现拼写纠正并使其成为用户体验的一部分的。

拼写纠正的实现

对于大多数拼写纠正（spelling correction）算法而言，存在以下两个基本的原则。

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

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

1. 输入查询carot，系统往往会再返回包含carot的文档的同时，也返回包含carot多种可能拼写校正结果（如carrot和tarot）的文档。
2. 当carot不在词典时，采用第一种做法。
3. 当原始查询返回的文档结果数目录少于预定值（比如少于5篇文档）时，采用第一种做法。
4. 当原始查询返回的文档数少于预定值时，搜索界面会给用户提供一个拼写建议，建议中会包含拼写校正之后的结果。因此，这实际上相当于搜索引擎和用户进行交互：“你是在找carrot吗”？

拼写校正的方法

这里我们主要关注两种拼写校正的方法：一种是词项独立（isolated-term）的校正，另一种是上下文敏感（content-sensitive）的校正。在词项独立的校正方法中，不管查询中包含多少个查询词项，其每次只对单个查询项进行校正，也就是说在象征时词项是相互独立的。上面给出的carot例子就属于这一类做法。利用这种词项独立校正的方法，就很难检测到查询flew form Heathrow 中实际上包含一个错误的词项form（正确的形式应该是from），这是因为在校正时每个词项之间就是相互独立的。

首先我们介绍两种词项独立的校正方法：编辑距离方法及k-gram重合度方法。然后，我们基于上下文敏感校正方法。

拼写校正问题不知需要计算出编辑距离：给定字符串集合V（对应词项词汇表）和查询字符串q，我们要从V中寻找和q具有最小编辑距离的字符串。我们可以把这个问题看成是解码问题，其中编码词（对应V中的字符串）已经预先定义好。最直接的方法是，计算q到V中的每个字符串的编辑距离，然后选择其中编辑距离最小的字符串。很显然，这种穷举的搜索方法开销很大。因此实际中使用了多种启发式方法来提高查找的效率。 
最简单的启发式方法是将搜索限制在与查询词具有相同的首字母的字符串上，也就是说我们期望查询的拼写错误不会出现在第一个字符上。上述启发式方法的一个更复杂的做法是利用轮排索引的某种版本，忽略了刺猬的$符号。考虑查询字符串q的所有旋转结果集合，对集合中每个旋转r，通过遍历B树来访问轮排索引（即轮排索引的词汇表查找可以通过B树来实现），返回旋转结果中以r开头的词项。例如，如果q为mase，那么我们考虑其旋转r=sema，这是我们会返回诸如semantic和semaphore的词，而这些词和mase之间的编辑距离并不小。遗憾的是，采用这种做法我们会错过包括mare和mane在内的一些更可能相关的词。为解决这个问题，我们改变旋转的使用机制：对每个旋转结果，在遍历B树之前我们忽略其长度的e的后缀，这样做可以保证返回词项集合R中的每个词项和q之间都包含一段较长的公共子串。e的值取决于q的长度。当然我们也可以设置为常数。

拼写校正中的k-gram索引

为了进一步限制计算编辑距离后得到的词汇表大小，以下介绍如何通过使用k-gram索引来辅助返回与查询q具有较小编辑距离的词项。一旦返回这些词项之后，利用k-gram索引，就能从中找出与q具有最小编辑距离的词。 
实际上，我们利用k-gram索引来查找与查询具有很多公共k-gram的词项。只要对“具有很多公共k-gram”进行合理定义，我们认为上述查找实际上是对查询字符串q中k-gram的倒排记录表进行单遍扫面的过程。 
查询bord的2-gram索引的一个片段，其中包含3个2-gram组成的倒排记录表。假定我们想返回包含上面3个2-gram中的至少2个词项，对倒排记录表的单遍扫描（和第一章类似）会返回满足该条件的所有词项，本例当中词项包括aboard、boardroom及border。 

这种通过线性扫描并立即合并倒排记录表的做法十分简单，只需要待匹配词项包含查询q中某个固定数目的k-gram即可。但是这种做法有一个缺点，比如boardroom这种不可能是bord的正确拼写形式的词也会被返回。所以，我们需要计算词汇表中词项与查询q之间更精细的重叠计算方法。比如采用jaccard系数（jaccard coefficient）就可以对先前的线性扫描合并方法进行修正。这里，Jaccard系数的计算公式为|A∩B|/|A∪B|，其中A、B分别是查询q、词汇表词项中的k-gram集合、扫描过程中，一旦扫描到与当前的词项t，就快速计算出q和t的Jaccard系数，然后继续扫描下一个词项。如果Jaccard系数超过预定的阈值，则将t输出。否则，我们往往继续扫描。上述过程表明，在计算Jaccard系数时，我们需要知道q和t的k-gram集合。 
由于是对q中的所有k-gram扫描倒排记录表，因此q中的k-gram集合是已知的，于是问题就变成如何求解t中的所有k-gram。理论上我们可以穷举出t中所有k-gram。但是这种做法不仅慢而且在实际中也难以实现。在很多情况下，倒排记录本身很可能并不包含完整的t字符串而往往是t的某种编码形式。也就是说，往往并不知道t的k-gram集合。然而，一个重要的发现使得这种情况下q和tJaccard系数的计算成为可能。这个发现就是，在计算Jaccard系数的时候，我们只需要知道t的长度即可。对于查询q=bord扫描倒排记录表直到t=boardroom。这时我们知道有2个2-gram已经匹配上了。如果倒排记录表中已经预先记录了boardroom所包含的2-gram的数目（这里是8），那么所有计算Jaccard的系数的信息都已知，计算公式2/(8+3-2)。其中，分子为倒排记录的命中数（值为2，分别来自bo和rd），分母为bord及boardroom中的2-gram之和减去倒排记录表的命中数。 
需要指出的是，也可以把Jaccard系数替换成其他能够进行快速计算的衡量指标。那么如何拼写校正中使用这些度量方式呢?一种经验性的方法是，首先使用k-gram索引返回可能是q的潜在正确拼写形式的词项集合，然后计算该集合中的每个元素和q之间的编辑距离并选择具有较小距离的那些词项。

上下文敏感的拼写校正

独立的词项拼写校正方法在面对诸如flew form Heathrow 中的输出错误时无能为力，因此这3个单词独立看来拼写都没有错误。当输入这类查询时，搜索引擎可能会发现返回的文档非常少，随后也许提供正确的查询建议flew form Heathrow。 这种功能的一种简单的实现方法就是，及时每个单词拼写都是对的，仍然要对每个单词找到可能的拼写正确词，然后尝试对短语中的每个词进行替换。比如对于上面flew form Heathrow的例子，我们可能会返回如下短语fled from Heathrow 和 flew fore Heathrow。对每个替换后的短语，搜索引擎进行查找并确定最后的返回数目。 
对于单独的查询有多种可能的正确拼写形式，那么上述方法中穷举过程的开销会非常大，最后我们就会面对非常多的拼写组合。有一些启发式方法可以减少可能的拼写结果空间。上述例子中，我们对flew及from进行扩展时，我们只保留文档集合或者查询日志中的高频组合结果。比如，我们可能会保存flew from 而不是 fled fore 或 flea form，这是因为fled fore很可能比flew from 出现的次数少。接下来我们仅仅根据高频双词（如flew from）来获得Heathrow的可能的正确拼写。计算双词频率的时候可以使用文档集，也可以使用用户的查询日志。

基于发音的校正技术

最后一项用户容错检索技术与发音有关，即拼写错误的原因在于用户输入一个和目标词项发音相似的查询。该方法尤其适合用于人名的查找，其基本的思路是：对每个词项，进行一个语音的哈希操作，发音相似的词项都被映射为同一值。该思路最早源于国际警察部门的工作，它们自20世纪初开始就在全球范围内寻找与罪犯嫌疑人发音相似的人名，而不管这些人名在不同国家发音是否有所不同。上述思路主要用于专有名词的语音校正。 
这类通用语音哈希方法通常统称soundex算法（soundex algorithm）。其中，一个原始的soundex算法的构建方法如下。需要指出的是，该基本算法存在很多变形。

1. 将这些此项转为四字符的简化形式。基于这种简化形式建立原始词项的倒排索引，该索引被称为soundex索引。
2. 对查询词项进行同样的操作。
3. 当对查询进行soundex匹配时，就在soundex索引中检索。 
   上述算法不同变形之间的主要区别在于将词项转变为四字符简化形式的方法不同。一个普遍使用的转换方法会得到四字符的编码结果，其中第一个字符是字符而其他3个字符是0~9之间的数字。转换方法如下。
4. 保留词项的首字母。
5. 将后续所有的A、E、I、O、U、H、W及Y等字母转换为0。
6. 其他字母的转换规则如下： 
   将B、F、P和V转换为1； 
   将C、G、J、K、Q、S和Z准换为2； 
   将D和T转换为3； 
   将L转换为4； 
   将M和N转换为5； 
   将R转换为6；
7. 连续出现的两个同一字符转换为一个字符直至再没有这种现象的出现。
8. 在结果字符串中剔除0，并在结果字符串尾部补足0，然后返回前四个字符，该字符由1个字母加上3个数字组成。 
   利用上述转换方法，就可以将Herman转换为H655。给定一个查询（比如herman），就可以计算其soundex编码然后从soundex索引中返回具有相同编码的词项，最后再在普通倒排索引中得到最后结果。 
   上述算法依赖于如下观察结果：1.在名称转录时，元音是可以互换的；2. 发音相似的辅音字母归成同一类。就会导致相关的名称通常有相同的soundex编码结果。尽管上述规则在很多场合上都适用，特别是欧洲语言，但是上述规则仍然依赖文字系统。比如，汉语中人名可以用韦氏拼音（Wade-Giles）