正确地猜测用户的意图

当我们在Collins词典中输入“voilent”的时候，会有如下提示：

当我们在Google中搜索“voilent”的时候，也会有如下提示：

Collins和Google是如何做到的呢？它是怎么知道我们把i和o的位置弄反了呢？

当我们输入一个词，而这个词不存在于Google的倒排索引或者Collins的词典中时，我们就可以假设用户输入可能有误，接着我们通过算法找出一个和用户的输入最相似的词推荐给用户，这个找出和用户输入最相似的词的算法有很多种，最常用的有编辑距离算法（Edit Distance），因为这个算法是俄罗斯科学家Vladimir Levenshtein在1965年提出的，所以编辑距离（Edit Distance）又叫做Levenshtein距离。

编辑距离算法是指两个字串之间，由一个转成另一个所需的最少编辑操作次数，允许的编辑操作包括将一个字符替换成另一个字符，增加一个字符，删除一个字符。

例如将kitten转成sitting： 

sitten （k→s）将一个字符k替换成另一个字符s

sittin  （e→i） 将一个字符e替换成另一个字符i

sitting （→g） 增加一个字符g

所以编辑距离为3，word分词提供了编辑距离算法的Java代码实现，同时superword项目也演示了编辑距离算法对于单词记忆的辅助作用。

 

下面我们看看中文的情况，当我们在Google搜索“热挨”的时候，Google在倒排索引中找不到“热挨”这个词，于是它猜测我们真正想搜索的是“热爱”，那么Google是怎么猜测到我们的意图的呢？

工作原理和上面介绍的英文词比较相似，只是算法不一样，如果把编辑距离算法应用到这里，效果会很差，那么怎么办呢？

解决方法是利用汉语的同音词原理，先把“热挨”转换为拼音“reai”，然后找出所有拼音为“reai”的双字词，在按照词的出现频率取频率最大者“热爱”。

 

更多资料：

How to Write a Spelling Corrector​

Using the Web for Language Independent Spellchecking and Autocorrection

How Difficult is it to Develop a Perfect Spell-checker A Cross-linguistic Analysis through Complex Network Approach