题
可能的重复:
Google“你的意思是什么?”算法工作?
假设您的网站中已有搜索系统。您如何实施“您的意思是:<spell_checked_word>
“就像谷歌在某些方面所做的那样 搜索查询?
解决方案
事实上,谷歌所做的事情非常重要,而且一开始也是违反直觉的。他们不会做类似检查字典之类的事情,而是利用统计数据来识别返回比您的查询更多结果的“相似”查询,确切的算法当然是未知的。
这里有不同的子问题需要解决,作为所有与自然语言处理统计相关的基础,有一本必备书: 统计自然语言处理基础.
具体来说,为了解决单词/查询相似性的问题,我使用以下方法取得了良好的结果 编辑距离, ,一种字符串相似度的数学度量,效果出奇的好。我曾经使用 Levenshtein,但其他的可能值得研究。
Soundex - 根据我的经验 - 很糟糕。
实际上,有效地存储和搜索大量拼写错误单词的字典并进行亚秒级检索也很重要,您最好的选择是利用现有的全文索引和检索引擎(即不是您的数据库的数据库),其中 卢塞恩 是目前最好的之一,并且巧合地移植到了许多平台。
其他提示
谷歌的诺维格博士概述了它的工作原理;他甚至给出了 20 行左右的 Python 实现:
http://googlesystem.blogspot.com/2007/04/simplified-version-of-googles-spell.html
http://www.norvig.com/spell- Correct.html
Norvig 博士还讨论了“你的意思是”吗? 这次精彩的演讲. 。诺维格博士是 研究主管 在 Google - 当被问到“你的意思是”是如何实现时,他的回答是 权威的.
因此,它的拼写检查可能是通过其他搜索甚至实际的互联网短语等构建的动态字典。但那还是 拼写检查.
SOUNDEX 和其他猜测不会被关注,朋友们!
查看 这 维基百科上有关编辑距离的文章。请务必仔细查看可能的改进。
我很惊喜地发现有人问如何为搜索引擎创建最先进的拼写建议系统。我已经在一家搜索引擎公司研究这个主题一年多了,我可以指出有关该主题的公共领域的信息。
正如之前的文章中提到的,谷歌(以及微软和雅虎!)不使用任何预定义的字典,也不雇用大量语言学家来思考查询可能的拼写错误。由于问题的规模,这是不可能的,而且还因为不清楚人们是否能够真正正确地识别查询何时以及是否拼写错误。
相反,有一个简单且相当有效的原则,也适用于所有欧洲语言。获取搜索日志中的所有唯一查询,计算所有查询对之间的编辑距离,假设参考查询是计数最高的查询。
这个简单的算法非常适合多种类型的查询。如果您想将其提升到一个新的水平,那么我建议您阅读微软研究院关于该主题的论文。你可以找到它 这里
这篇论文有一个很好的介绍,但之后您将需要了解隐马尔可夫模型等概念。
我建议看看 声音指数 在数据库中查找相似的单词。
您还可以使用以下命令访问谷歌自己的词典 Google API 拼写建议请求.
您可能想看看 Peter Norvig 的“如何编写拼写纠正器“ 文章。
我相信谷歌会记录所有查询并识别何时有人进行拼写更正。然后,当其他人提供相同的第一查询时,可以建议该更正。这适用于任何语言,实际上是任何字符的任何字符串。
我认为这取决于您的网站有多大。在我们大约 500 名员工使用的本地 Intranet 上,我只需查看返回零结果的搜索短语,然后将该搜索短语与新建议的搜索短语一起输入到 SQL 表中。
如果没有返回搜索结果,我会调用该表,但是,这只在站点相对较小的情况下才有效,并且我只针对最常见的搜索短语执行此操作。
您可能还想看看我对类似问题的回答:
如果您有行业特定的翻译,您可能需要同义词库。例如,我在珠宝行业工作,我们的描述中有缩写,例如 kt - 克拉、rd - 圆形、cwt - 克拉重量...Endeca(该工作的搜索引擎)有一个同义词库,可以翻译常见的拼写错误,但它确实需要手动干预。
Soundex 适合语音匹配,但最适合人名(它最初是为人口普查数据开发的)
另请查看全文索引,其语法与 Google 逻辑不同,但它非常快并且可以处理类似的语言元素。
Soundex 和“Porter 词干”(soundex 很简单,不确定 Porter 词干)。
有一种叫做 aspell 的东西可能会有所帮助:http://blog.evanweaver.com/files/doc/fauna/raspell/classes/Aspell.html
有一个 ruby gem,但我不知道如何从 python 与它对话http://blog.evanweaver.com/files/doc/fauna/raspell/files/README.html
这是 ruby 实现的引用
用法
Aspell 可让您检查单词并提出更正建议。例如:
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
这输出:
可能的 haert 修正:威尔的心脏可能纠正:将要
以有效的方式为搜索引擎实施拼写纠正并非易事(您不能只计算到每个可能单词的编辑/编辑距离)。基于k-gram索引的解决方案描述于 信息检索简介 (全文可在线获取)。
你可以使用 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"
为什么不使用谷歌的你的意思是在你的代码中。如何看这里http://narenonit.blogspot.com/2012/08/trick-for-using-googles-did-you-mean.html