spell check， 搜索引擎中的错词纠正

从一个问题开始，搜索引擎用户输入，可能会存在拼写出错，如何给出修改的建议？

可以从一个编辑距离说起；这个编辑距离大家是不是很熟悉，刷过leetcode都知道这样的题；
给定一个 字符串 s=abcd, t=dbcd,
可以对s中的 字符串 进行，增加 一个字母，删除一个字母，替换一个字母；使得 s = t;
最小的操作数，就叫做这两个字符串的编辑距离；

编辑距离的求解，是很标准的动态规划解法； dp[i][j] 可以根据i，j两个字母的关系，进行操作来获取；
递推公式：
dp[i][j] = dp[i-1][j-1]; if s[i]=s[j];
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1],dp[i-1][j-1])

那么，对于用户的一个输入，我们想到的第一个方案就是，计算用户输入，与我们的 词表中每个正确词的编辑距离；
让后按照，编辑距离倒序排序；从编辑距离为1-2 的词中，做进一步筛选；

这种做法面临的问题，通常对于一个应用，词表是非常的大的，比如搜索引擎；求编辑距离的复杂度是
Len(S) * o(N),N 为词表的长度，那么这个对于C端的应用的计算成本还是太大；

再次回到问题，通常我们只需要编辑距离为1，2的备选词，我们的方法其实计算了大量的其他编辑距离的case；
所以我们的关注点，反过来； 通过 s，生成 编辑距离为1-2的词，然后与词库去匹配；

对于给定一个 S，如何生成 编辑距离为1 的 target 串，也是有比较成熟的算法；
对S 进行break 切分， 切分点有 len(S)个；
L+R, 那么就可以 L+(a)+R; L+R(delete); L+R(replace); 这样就可以了；
再利用生成的 编辑距离为1的所有字串，在做一次。就是编辑距离为2 的字串；

对于 apple这样的单词，这样生产出来的字串大概也是在 2-3万之类；

有了这个列表之后，我们可以 去和词表mapping； 比如词表是一个大的hashMap；
那么我们就可以 以 o(N)的方式获得一个 编辑距离为1-2的备选词表； 如果我们只是做 编辑距离为1 的话，这个N 可能更小；
速度就会大大的加快；

加入这个时候我们获得一个 推荐词的列表：C； 那么我们到底如何排序？ 比如取出来前 3个概率最大的？
我们的目标函数：

P(C|S),对于输入S，找出最大的 P(C|S);
对于条件概率； P(C|S) = P(SC)|P(S) = P(S|C)P(C)|P(S) = P(S|C)P(C);

P(C)的概率，对于一个搜索引擎而言，我们可以计算为推荐词出现的概率，可以从历史搜索库中获得；
对于P(S|C), 比如 C=apple; S 为 appl; 也就是说，apple 被用户输入为 appl的概率； 这个也是需要我们从搜索log 里面去看；
比如之前用户输入了appl，然后点击我们推荐给他的 apple；这就是一个record；

有了这些数据，我们的P(C|S)就可以排序出来；然后给到用户一个比较满意的推荐；