457

我一直在为投资组合管理工具开发一个内部网站。有很多文本数据、公司名称等。一些搜索引擎能够非常快速地响应“您的意思是：xxxx”的查询，这给我留下了深刻的印象。

我需要能够智能地接受用户查询，并且不仅可以使用原始搜索结果进行响应，还可以使用“您的意思是吗？” 当有一个很可能的替代答案等时的响应

[我在ASP.NET中开发（VB - 不要反对我！）]

更新：好的，如果没有数百万“未付费用户”，我怎么能模仿呢？

  • 为每个“已知”或“正确”术语生成拼写错误并执行查找？
  • 其他一些更优雅的方法？
4

18 回答 18

384

这是直接来自源的解释（几乎）

搜索 101！

22:03 分

值得一看！

基本上，根据谷歌前首席技术官 Douglas Merrill 的说法，它是这样的：

1）你在谷歌写了一个（拼错的）词

2）你没有找到你想要的（不要点击任何结果）

3) 你意识到你拼错了这个词，所以你在搜索框中重写了这个词。

4）你找到你想要的（你点击第一个链接）

这种模式乘以数百万倍，显示了最常见的拼写错误和最“常见”的更正。

这样，谷歌几乎可以立即提供每种语言的拼写纠正。

这也意味着如果一夜之间每个人都开始拼写“晚上”，谷歌会建议这个词。

编辑

@ThomasRutter：道格拉斯将其描述为“统计机器学习”。

他们知道谁更正了查询，因为他们知道哪个查询来自哪个用户（使用 cookie）

如果用户执行查询，并且只有 10% 的用户点击了一个结果，而 90% 的用户返回并输入另一个查询（使用更正的单词），而这次 90% 的用户点击了一个结果，那么他们就知道他们找到了一个修正。

他们还可以知道这些是否是两个不同的“相关”查询，因为他们拥有所显示的所有链接的信息。

此外，他们现在将上下文包含在拼写检查中，因此他们甚至可以根据上下文建议不同的单词。

请参阅此google wave (@44m 06s) 演示，该演示显示了如何考虑上下文以自动更正拼写。

这里解释了自然语言处理是如何工作的。

最后，这是一个很棒的演示，展示了在混合中添加自动机器翻译(@1h 12m 47s) 可以做什么。

我已经在视频中添加了分钟和秒的锚点以直接跳到内容，如果它们不起作用，请尝试重新加载页面或手动滚动到标记处。

于 2008-11-20T23:58:45.657 回答
110

前段时间我发现了这篇文章：如何编写拼写校正器，由Peter Norvig（Google Inc. 研究总监）撰写。

这是一本关于“拼写更正”主题的有趣读物。这些示例是用 Python 编写的，但它清晰易懂，我认为该算法可以很容易地翻译成其他语言。

下面是对该算法的简短描述。该算法包括两个步骤，准备和单词检查。

第一步：准备——建立词库

最好是您可以使用实际的搜索词及其出现。如果您没有这样的大量文本，则可以改用。计算每个单词的出现次数（流行度）。

步骤 2. 单词检查 - 查找与所检查的单词相似的单词

类似意味着编辑距离较低（通常为 0-1 或 0-2）。编辑距离是将一个单词转换为另一个单词所需的最小插入/删除/更改/交换次数。

从上一步中选择最流行的单词并建议将其作为更正（如果不是单词本身）。

于 2008-11-20T23:41:37.517 回答
60

关于“你的意思是”算法的理论，你可以参考信息检索导论的第 3 章。它可以免费在线获得。第 3.3 节（第 52 页）准确回答了您的问题。并且要专门回答您的更新，您只需要一个单词字典就可以了（包括数百万用户）。

于 2008-11-21T00:55:31.750 回答
11

嗯......我认为谷歌使用他们庞大的数据语料库（互联网）来做一些严肃的 NLP（自然语言处理）。

例如，他们拥有来自整个互联网的大量数据，以至于他们可以计算出三个单词序列（称为三元组）出现的次数。因此，如果他们看到类似“pink frugr concert”这样的句子，他们可以看到它的点击率很少，然后在他们的语料库中找到最有可能的“pink * Concert”。

不过，他们显然只是对 Davide Gualano 所说的话做了一个变体，所以一定要阅读那个链接。谷歌当然会使用它所知道的所有网页作为语料库，因此它的算法特别有效。

于 2008-11-20T23:45:57.930 回答
8

我的猜测是，他们结合了Levenshtein 距离算法和他们收集的有关运行搜索的大量数据。他们可以从输入的搜索字符串中提取一组 Levenshtein 距离最短的搜索，然后选择结果最多的搜索。

于 2008-11-20T23:57:13.430 回答
7

通常，生产拼写校正器使用几种方法来提供拼写建议。有些是：

  • 决定一种方法来确定是否需要进行拼写更正。这些可能包括结果不足、结果不够具体或不够准确（根据某种衡量标准）等。然后：

  • 使用大量文本或字典，其中所有或大部分已知拼写正确。这些很容易在网上找到，比如LingPipe。然后，要确定最佳建议，您需要根据几个度量来寻找最接近匹配的单词。最直观的是相似字符。通过研究和实验表明，两个或三个字符序列匹配效果更好。（二元组和三元组）。为了进一步改善结果，请在单词开头或结尾的匹配项上权衡更高的分数。出于性能原因，将所有这些单词索引为 trigrams 或 bigrams，以便在执行查找时转换为 n-gram，并通过 hashtable 或 trie 进行查找。

  • 根据字符位置使用与潜在键盘错误相关的启发式方法。所以“hwllo”应该是“hello”，因为“w”接近“e”。

  • 使用语音键（Soundex、Metaphone）来索引单词并查找可能的更正。在实践中，这通常会返回比使用 n-gram 索引更差的结果，如上所述。

  • 在每种情况下，您都必须从列表中选择最佳校正。这可能是距离度量，例如 levenshtein、键盘度量等。

  • 对于多词短语，只有一个词可能拼写错误，在这种情况下，您可以使用剩余的词作为上下文来确定最佳匹配。

于 2009-04-16T18:07:37.297 回答
7

使用Levenshtein distance，然后创建一个度量树（或 Slim 树）来索引单词。然后运行 ​​1-Nearest Neighbor 查询，您就得到了结果。

于 2009-10-04T18:07:10.097 回答
4

谷歌显然建议具有最佳结果的查询，而不是那些拼写正确的查询。但是在这种情况下，可能拼写更正器会更可行，当然，您可以根据返回结果的好坏程度为每个查询存储一些值。

所以，

  1. 您需要一本字典（英文或基于您的数据）

  2. 使用您的字典生成一个单词格子并计算转换的概率。

  3. 添加解码器以使用您的格子计算最小误差距离。当然，在计算距离时应该注意插入和删除。有趣的是，QWERTY 键盘可以最大限度地提高距离，如果你敲击彼此靠近的键。（cae 会转动汽车，cay 会变成猫）

  4. 返回具有最小距离的单词。

  5. 然后您可以将其与您的查询数据库进行比较，并检查其他紧密匹配是否有更好的结果。

于 2008-11-21T01:17:17.153 回答
4

这是我找到的最佳答案，由 Google 的研究总监 Peter Norvig 实施和描述的拼写校正器。

如果你想了解更多关于这背后的理论，你可以阅读他的书章节。

该算法的思想基于统计机器学习。

于 2014-03-12T06:29:58.800 回答
3

作为一个猜测......它可以

  1. 搜索单词
  2. 如果找不到，请使用一些算法来尝试“猜测”这个词。

可能是来自人工智能的东西，比如 Hopfield 网络或反向传播网络，或者是其他东西“识别指纹”，恢复损坏的数据，或者 Davide 已经提到的拼写更正......

于 2008-11-20T23:45:25.513 回答
3

几年前我在这方面看到了一些东西，所以可能从那以后发生了变化，但显然他们是通过分析他们在短时间内提交非常相似查询的相同用户的日志来开始的，并根据用户的纠正方式使用机器学习他们自己。

于 2008-11-20T23:46:48.410 回答
2

简单的。他们有大量的数据。他们有每个可能的术语的统计数据，基于它被查询的频率，以及它的哪些变体通常会产生用户点击的结果......所以，当他们看到你为搜索词输入了一个频繁的拼写错误时，他们会继续并提出建议更常见的答案。

实际上，如果拼写错误实际上是最常见的搜索词，那么算法会将其视为正确的词。

于 2008-11-20T23:48:43.913 回答
2

关于您的问题如何在没有大量数据的情况下模仿行为 - 为什么不使用谷歌收集的大量数据？下载拼写错误单词的 google 搜索结果并在 HTML 中搜索“您的意思是：”。

我想现在这叫做混搭:-)

于 2008-11-21T00:57:36.257 回答
2

除了上面的答案，如果你想自己快速实现一些东西，这里有一个建议——

算法

您可以在GitHub上找到该算法的实现和详细文档。

  • 使用比较器创建优先级队列。
  • 创建一个 Ternay 搜索树并插入所有英文单词（来自Norvig 的帖子）及其频率。
  • 开始遍历 TST，对于 TST 中遇到的每个单词，从 input_word计算其 Levenshtein Distance( LD )
  • 如果 LD ≤ 3，则将其放入优先队列。
  • 最后从优先队列中提取 10 个单词并显示。
于 2017-06-08T04:53:15.867 回答
1

你的意思是说拼写检查？如果它是拼写检查器而不是整个短语，那么我有一个关于拼写检查的链接，该算法是在 python 中开发的。检查此链接

同时，我还在从事包括使用文本搜索数据库的项目。我想这会解决你的问题

于 2011-07-13T11:49:50.450 回答
1

这是一个老问题，我很惊讶没有人建议使用 Apache Solr 的 OP。

Apache Solr 是一个全文搜索引擎，除了许多其他功能外，它还提供拼写检查或查询建议。从文档中：

默认情况下，Lucene 拼写检查器首先根据字符串距离计算的分数对建议进行排序，然后根据索引中建议的频率（如果可用）对建议进行排序。

于 2012-03-06T20:29:54.907 回答
0

有一种特定的数据结构——三元搜索树——自然支持部分匹配和近邻匹配。

于 2009-09-07T11:24:45.377 回答
-1

最简单的方法是谷歌动态编程。

这是一种从信息检索中借来的算法，并在现代生物信息学中大量使用，以查看两个基因序列的相似程度。

最优解使用动态规划和递归。

这是一个非常解决的问题，有很多解决方案。只需搜索一下，直到找到一些开源代码。

于 2008-11-21T01:05:37.253 回答