你如何实现“你的意思”?

可能重复:
Google“你的意思是?”algorithm是如何工作的?

假设你的网站已经有一个search系统。 你怎么能像Google在某些search查询中那样实现“你的意思是: <spell_checked_word> ”?

其实Google所做的事情非常简单,而且起初也是违反直觉的。 他们不会像检查字典那样做任何事情,而是他们利用统计数据来识别返回比您的查询更多结果的“相似”查询,但确切的algorithm当然是未知的。

这里有不同的子问题需要解决,作为所有有关自然语言处理统计的基础,有一本必须具备的书: 统计自然语言处理的基础 。

具体来说,为了解决词/查询相似性问题,我使用了“ 编辑距离” ( Edit Distance) ,这是一个string相似度的math测量,效果出奇的好。 我曾经使用Levenshtein,但其他人可能值得研究。

Soundex – 以我的经验 – 是废话。

实际上,高效地存储和search拼写错误的单词的大型字典并进行次级检索也是非常重要的,最好的办法是利用现有的全文索引和检索引擎(即不是数据库的一个),其中Lucene目前是其中最好的和巧合的移植到许多平台。

Google的Norvig博士概述了它的工作原理。 他甚至给出了一个20行的Python实现:

http://googlesystem.blogspot.com/2007/04/simplified-version-of-googles-spell.html

http://www.norvig.com/spell-correct.html

Norvig博士还在这个优秀的演讲中讨论了“你的意思是什么”。 Norvig博士是Google 的研究负责人 – 当被问及“你的意思”是如何实施时,他的回答是有效的。

所以它的拼写检查,大概是从其他search甚至实际的互联网短语等这样的dynamic词典build立。 但是这仍然是拼写检查

SOUNDEX和其他猜测不看,人!

请查看维基百科有关Levenshtein距离的文章。 确保你仔细看看可能的改进。

我惊喜地发现有人问如何为search引擎创build最先进的拼写build议系统。 对于一家search引擎公司我一直在为这个问题工作一年多,而且我可以在这个问题上指出公有领域的信息。

正如前一篇文章中提到的,谷歌(以及微软和雅虎)并没有使用任何预定义的字典,也没有雇佣大量的语言学家来思考可能的拼写错误。 由于问题的严重性,这将是不可能的,也因为不清楚人们实际上是否能够正确识别查询是否拼写错误。

相反,有一个简单而有效的原则,也适用于所有的欧洲语言。 获取search日志中的所有唯一查询,计算所有查询对之间的编辑距离,假定参考查询是具有最高计数的查询。

这个简单的algorithm将适用于许多types的查询。 如果你想把它提升到一个新的水平,那么我build议你阅读微软研究所关于这个主题的论文。 你可以在这里find它

本文有一个很好的介绍,但之后,你将需要对诸如隐马尔可夫模型这样的概念有所了解。

我会build议看看SOUNDEX在你的数据库中find类似的单词。

您也可以使用Google API拼写build议请求访问Google自己的字典。

您可能想看看Peter Norvig的“ 如何编写拼写纠正器 ”文章。

我相信Google会logging所有查询,并确定何人进行拼写更正。 当其他人提供相同的第一个查询时,可以build议该修正。 这将适用于任何语言,实际上任何字符的任何string。

我想这取决于你的网站有多大呢。 在大约500名员工使用的本地Intranet上,我仅查看返回零结果的search短语,然后用新build议的search短语将该search短语input到SQL表中。

如果没有search结果被返回,他们就会打电话给我们,但是这只有在网站相对较小的情况下才有效,而且我只对最常见的search词组进行search。

你也可能想看看我的回答类似的问题:

  • “类似的post”像使用MS SQL Server的function?

如果你有行业特定的翻译,你可能会需要一个词库。 例如,我曾在珠宝行业工作过,在我们的描述中有一些缩写,例如kt – 克拉,rd – round,cwt – 克拉重量…… Endeca(那个工作的search引擎)有一个词库,拼写错误,但确实需要人工干预。

我用Lucene的拼写检查器来做。

Soundex适合语音匹配,但是最适合人们的姓名(最初是为人口普查数据开发的)

也检查全文索引,语法不同于谷歌的逻辑,但它很快,可以处理类似的语言元素。

Soundex和“波特词干”(soundex是微不足道的,不知道波特词干)。

有些东西叫aspell可能有帮助: http : //blog.evanweaver.com/files/doc/fauna/raspell/classes/Aspell.html

有一个ruby的gem,但我不知道如何从pythonhttp://blog.evanweaver.com/files/doc/fauna/raspell/files/README.html

这里有一个ruby实现的引用

用法

Aspell让你检查单词并build议更正。 例如:

  string = "my haert wil go on" string.gsub(/[\w\']+/) do |word| if !speller.check(word) # word is wrong puts "Possible correction for #{word}:" puts speller.suggest(word).first end end 

这输出:

哈特可能的更正:心脏可能的更正:威尔

以有效的方式为search引擎实施拼写纠正不是微不足道的(你不能只计算每个可能的单词的编辑/ levenshtein距离)。 信息检索简介 (在线提供全文) 介绍了基于k-gram索引的解决scheme。

你可以用ngram来比较: http : //en.wikipedia.org/wiki/N-gram

使用python ngram模块: http ://packages.python.org/ngram/index.html

 import ngram G2 = ngram.NGram([ "iis7 configure ftp 7.5", "ubunto configre 8.5", "mac configure ftp"]) print "String", "\t", "Similarity" for i in G2.search("iis7 configurftp 7.5", threshold=0.1): print i[1], "\t", i[0] 

你得到:

 >>> String Similarity 0.76 "iis7 configure ftp 7.5" 0.24 "mac configure ftp" 0.19 "ubunto configre 8.5" 

为什么不使用谷歌的你的意思是在你的code.For怎么看这里http://narenonit.blogspot.com/2012/08/trick-for-using-googles-did-you-mean.html