正确地猜测用户的意图

原创
2015/06/03 19:13
阅读数 517

当我们在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




展开阅读全文
打赏
0
4 收藏
分享
加载中
"一架飞机会飞" [一架,飞机,会飞]
"一架机飞会飞" [一架, 机, 飞, 会飞] 我想判断会不会构成一句合理合理的话,应该怎么做呢?
2016/05/17 14:11
回复
举报
更多评论
打赏
1 评论
4 收藏
0
分享
返回顶部
顶部