Possible Duplicate:

  How does the Google “Did you mean?” Algorithm work?

假设网站中已经有一个搜索系统。在某些搜索查询中，我们如何像Google那样实现"意思是：<spell_checked_word>"？

解决方案

回答

我建议我们查看SOUNDEX以在数据库中找到类似的单词。

我们还可以使用Google API拼写建议请求来访问Google自己的词典。

回答

Soundex非常适合进行语音匹配，但最适合与人的名字配合使用(Soundex最初是为普查数据开发的)

还要检查全文索引，其语法与Google逻辑不同，但是它非常快速并且可以处理类似的语言元素。

回答

Soundex和"波特阻止"(Soundex是琐碎的，不确定波特阻止)。

回答

在Wikipedia上查看有关Levenshtein距离的文章。确保我们仔细看一下可能的改进。

回答

实际上，Google所做的工作是非常平凡的，乍一看也违反直觉。他们没有像检查字典那样做任何事情，但是他们利用统计信息来识别返回比查询更多结果的"相似"查询，确切的算法当然是未知的。

这里有不同的子问题需要解决，作为所有自然语言处理统计数据的基础，必须有一本书：统计自然语言处理基础。

具体来说，为了解决单词/查询相似性的问题，使用"编辑距离"(一种字符串相似性的数学度量，效果非常好)使我获得了良好的结果。我曾经使用Levenshtein，但其他人可能值得研究。

根据我的经验，Soundex是胡扯。

实际上有效地存储和搜索大的拼写错误的词典，并且具有亚秒级的检索功能也是不平凡的，最好的选择是利用现有的全文索引和检索引擎(即不是数据库的那个)，Lucene当前是其中的一种最好的平台之一，巧合地移植到许多平台上。

回答

http://en.wikipedia.org/wiki/N-gram#Google_use_of_N-gram

回答

如果我们具有行业特定的翻译，则可能需要一个同义词库。例如，我在珠宝业工作过，在我们的描述中有缩写，例如kt karat，rd round，cwt克拉重量... Endeca(该职位的搜索引擎)有一个词库，该词库将翻译成常见的拼写错误，它确实需要手动干预。

回答

我认为这取决于网站的大小。在我们大约500名员工使用的本地Intranet上，我只查看返回零结果的搜索短语，然后将该搜索短语和新的建议搜索短语输入到SQL表中。

如果没有返回任何搜索结果，他们将在该表上进行调用，但是，这仅在站点相对较小的情况下才有效，并且我仅对最常见的搜索短语进行操作。

我们可能还想看看我对类似问题的回答：

• 喜欢使用MS SQL Server的"类似帖子"吗？

回答

我们可能想看看Peter Norvig的"如何编写拼写校正器"文章。

回答

我相信Google会记录所有查询并确定何时有人进行拼写更正。然后，当其他人提供相同的第一个查询时，可以建议进行此更正。这适用于任何语言，实际上是任何字符的任何字符串。

回答

Google的Dr Norvig概述了它的工作方式。他甚至给出了20行代码的Python实现：

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

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

在这个精彩的演讲中，诺维格博士还讨论了"意思"。当被问及"意思"是如何实现的时，诺维格博士是Google的研究负责人，他的回答是权威。

因此，它的拼写检查(大概是根据其他搜索甚至是实际的互联网短语等)来构建的动态字典。但这仍然是拼写检查。

大家快来看看SOUNDEX和其他猜测吧！

回答

有一种叫做aspell的东西可能会有所帮助：

http://blog.evanweaver.com/files/doc/fauna/raspell/classes/Aspell.html

有一个红宝石宝石，但我不知道如何从python与它交谈
http://blog.evanweaver.com/files/doc/fauna/raspell/files/README.html

Usage
  
  Aspell lets you check words and suggest corrections. For example:

  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

这是来自ruby实现的报价

输出：

回答

可能的纠正措施：
心
可能的更正：
将要

回答

以有效的方式为搜索引擎实施拼写校正并非易事(我们不能仅计算每个可能单词的编辑/保留距离)。 《信息检索简介》(在线提供全文)中介绍了一种基于k-gram索引的解决方案。

回答

我用Lucene的拼写检查器做到这一点。

有人问到如何为搜索引擎创建最先进的拼写建议系统，我感到非常惊讶。我在一家搜索引擎公司从事这一主题的工作已经一年多了，我可以指出有关该主题的公共领域信息。

如前一篇文章所述，Google(以及Microsoft和Yahoo!)不使用任何预定义的字典，也不使用成群的语言学家来思考可能的拼写错误的查询。由于问题的严重性，这将是不可能的，而且还因为人们不清楚人们是否可以正确识别查询的时间和是否拼错。

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

这个简单的算法非常适合许多类型的查询。如果我们想将其提高到一个新的水平，那么我建议我们阅读Microsoft Research关于该主题的论文。你可以在这里找到它

回答

本文有很好的介绍，但之后我们将需要熟悉诸如隐马尔可夫模型之类的概念。

我们可以使用ngram进行比较：http://en.wikipedia.org/wiki/N-gram

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]

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

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

段落数量不匹配