搜索关键词纠错算法
1. 问题背景
现在各大搜索引擎都具备一个功能，那就是提供拼写纠错功能。用户将查询的关键词提交给搜索引擎之后，搜索引擎便开始分析用户的输入，检查用户的拼写是否有错误，如果有的话，给出正确的拼写建议。
千米搜索平台面向社会各个阶层的电商D、P、C用户，为了具有更好的交互性和可操作性，有必要为用户输入关键字提供纠错。千米搜索平台的搜索关键词纠错能力，可以人性化的指导用户尽可能地搜索到商品信息，提升客户的下单率。
我们看下天猫的商品搜索，
首先我们输入“appl”，看看天猫会怎么处理：
我们再输入“苹国”，看看结果会是什么：
2. 问题分析
从上面的例子可知，搜索平台的拼写纠错功能，要完成两部分的工作：
- 首先，对用户输入的查询进行处理，判断是否有拼写错误；
- 然后，对于有拼写错误的查询输入，给出正确词汇的提示；
3. 解决方案
3.1. 电商搜索引擎关键词拼写错误的定义
和通用搜索引擎（Google、Baidu）不同，电商搜索引擎并不关心拼写错误。举例来说，用户输入“appla”，我们不好判断这个关键词是否错误，用户想要的是不是“apple”，如果正好有个商品的品牌或者厂家包含“appla”词呢。对于百度或者天猫来说，会有很多人维护搜索引擎的词汇表或者分词字典，我们没有这样的条件，能否有一种简单的方法判断用户可能存在拼写错误，需要给出正确的提示呢？
目前千米搜索平台推荐业务采用的办法是如果关键词（特别是没有其它搜索条件的情况下）没有搜索到商品，可能需要对用户的关键词进行纠错。
3.2. 词典
在现实中，我们如果要检查一个单词是否拼写错误，我们就会查词典。搜索引擎要想纠正错误，也必须有一个词典。对于千米搜索平台来说，如何才能获取一个比较准确的词典呢？词典必须满足如下的要求：
首先词典必须是和用户的商品强相关的。
词典不能是类似搜狗词汇、新华词典等类似的通用词典。试想一下，一个食品网站给出的推荐词是“电脑”、“手机”，或者推荐的关键词没有任何商品，这样的关键词没有任何意义。词典必须能够自动生成
对现阶段的公司客户现状来说，任何需要人工参与的方案都是不可行的。
我们在搜索提示 中生成了一个用户的搜索提示词列表，这个提示词列表满足我们对词典的要求。
3.3. 正确词标准
有了词典，下一步是如何从词典中找到用户可能真正在搜索的关键词，即如何找到错误词和正确词的关系。 自然语言处理中，中文远远比英文复杂。英文无需分词，只要找到字母接近的词即可。我们分析如下的错误场景：
中文同音字错误。
大部分人输入中文时都是用拼音输入法。拼音输入法一般是用数字选择汉字，这是很容易就选择了错误同音字。比如输入“苹果”，却误选择了“平果”。字符输入错误、拼写相近的词
比如“apple”拼写成“appla”，“苹果6 plus手机”拼写成“苹果干6 plus手机”。为了在效率和效果之间均衡，我们将“拼写相近”定义为两个关键词的“编辑距离”不超过2。编辑距离（Edit Distance），又称Levenshtein距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。编辑操作指删除、交换、更改和插入操作。一般来说，编辑距离越小，两个串的相似度越大。比如“appla”和“apple”之间只需要替换掉最后一个字符a即可，因此其编辑距离为1。
因此我们寻找正确词的标准就是中文的同音字和编辑距离不超过2的关键词。
3.4. 算法步骤
- 分析关键词，区分中英文
- 对于中文字符串，获取拼音，然后在词典查找同音词
- 无论中文、英文、中英文，在词典中查找编辑距离小于等于2的关键词
- 步骤2和3得到的词即为正确词
3.5. 排序
如果得到多个正确词，但是通常显示给用户只有一个，按照下面规则对它们进行排序，越前面的规则权重越高。
- 同音词优先，同音词之间的顺序由同音词的搜索建议权重决定。搜索建议权重由搜索词的商品数目、搜索次数、添加方式决定。
- 拼写相近词的顺序由相似度决定，越相似的词排在越前面。
4. 效果展示
这是我在公司私有云Kstore APP时实现的关键词纠错：
输入“appla”：
推荐一下Google大神Peter Norvig用python写的只有21行代码的拼写检查器，基于贝叶斯定理，不过只能针对英文。本文算法也部分借鉴了这篇文章，这篇文章有各个语言版本的。
话说这位大神也是一个神人，List大神，后来转到python，有兴趣可以了解下。