拼写纠错

对大多数拼写纠错来说，存在两个基本原则：

1. 对于一个拼写纠错的查询，在其中正确的拼写中，选择距离最近的一个。
2. 当两个正确拼写查询临近度相等时，选择更常见的那个。

有两大类拼写纠错的方法，一种是词项独立的校正，另一种是上下文敏感的校正。其中，在词项独立的校正中，不管查询中包含多少个查询词项，每次只对单个查询词项进行校正。利用这种词项独立的方式，很难检测到查询 flew form Heathrow中form这个错词。

方法1：编辑距离

给定两个字符串s1和s2， 两者的编辑距离定义为将s1转换为s2的最小编辑操作次数。编辑操作主要包括：

1. 将一个字符插入字符串、

2. 将一个字符从字符串中删除

3. 将一个字符替换为另一个字符

   基于这些操作的编辑距离也称为Levenshtein距离，例如：cat和dog的编辑距离是3。

​ 可以在O(|s1| * |s2|)的时间复杂度下计算两个字符串的编辑距离。|si| (i=1,2)表示字符串si的长度。主要解决思路是采用动态规划的思想：

s1和s2以字符数组的形式存放，整数矩阵M的行号和列号分别是两个字符串的长度，算法在运行过程中不断填充矩阵，矩阵的第i行和第j列保存的是s1的前i个字符构成的字符串和s2的前j个字符构成的字符串的编辑距离。其中求最小值的三个参数分别对应在s1中替换一个字符、在s1中插入一个字符和在s2中插入一个字符。

​ 两个字符串的编辑距离计算算法如下：

public int  minDistance(String word1,String word2){
    int m=word1.length();
    int n=word2.length();
    int [][]dp=new int [m+1][n+1];
    for(int i=0;i<=m;i++){
        dp[i][0]=i; //单纯的删除操作
    }
    for(int i=0;i<=n;i++){
        dp[0][i]=i; //单纯的插入操作
    }
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(word1.charAt(i)==word2.charAt(j)){
                dp[i+1][j+1]=dp[i][j];
            }else{
                dp[i+1][j+1]=Math.min(dp[i][j+1],Math.min(dp[i+1][j],dp[i][j]))+1;
            }
        }
    }
    return dp[m][n];
}

​ 拼写纠错的问题：

给定字符串集合V（对应词项词汇表）和查询词字符串，从V中寻找和q具有最小编辑距离的字符串。最直接的算法是计算q到V中的每个词项的编辑距离，然后选择其中编辑距离最小的字符串。很显然这种穷举的搜索开销很大，实际当中使用列多种启发式方法来提升查询效率。最简单的启发式方法是将搜索限制在与查询词有相同首字母的字符串上，也就是说我们期望查询的拼写错误不会出现在第一个字符上。

方法2：k-gram 索引

​ 为了进一步限制需要计算编辑距离的词汇表大小，利用k-gram索引来辅助返回与查询q具有较小编辑距离的词项，一旦返回这些词项后，就能从中找到与q具有最小编辑距离的词。

​ 查询bord的2-gram索引如下所示，其中包含3个2-gram组成的倒排记录，假定我们要返回包含上面3个2-gram的至少2个词项，对倒排记录表的单遍扫描会返回满足该条件的所有词项。

bo ----> aboard ----> about ----> boardroom ----> border
or ----> border ----> lord  ----> morbid    ----> sordid
rd ----> aboard ----> ardent ---> boardroom ----> border

​ 缺点：

比如boardroom这种不可能是bord的正确拼写也会返回。

针对上面的问题，需要计算查询词和词汇表更精细的重叠度计算方法。比如：Jaccard系数

Jaccard系数的计算公式为：

其中，A、B分别是查询q、词汇表词项中的k-gram集合。扫描过程中，一旦扫描到当前的词项t，就快速计算q和t的Jaccard系数，然后继续扫描下一个词项。如果Jaccard系数超过阈值，则将t输出，否则继续下一个扫描。

方法3: 上下文敏感的拼写校正

​ 独立的词项拼写校正方法在面对诸如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的可能的正确拼写。计算双词频率的时候可以使用文档集，也可以使用用户的查询日志。