18

我有以下要求： -

我有很多（比如 100 万个）值（名称）。用户将键入搜索字符串。

我不希望用户正确拼写名称。

所以，我想做一种谷歌“你的意思是”。这将列出我的数据存储中的所有可能值。这里有一个类似但不相同的问题。这没有回答我的问题。

我的问题： - 1）我认为将这些数据存储在 RDBMS 中是不可取的。因为那样我就不会对 SQL 查询进行过滤。而且我必须进行全表扫描。那么，在这种情况下应该如何存储数据呢？

2）第二个问题与此相同。但是，只是为了我的问题的完整性：我如何搜索大型数据集？假设数据集中有一个名字 Franky。如果用户键入为 Phranky，我如何匹配 Franky？我必须遍历所有名称吗？

我遇到了Levenshtein Distance，这将是找到可能的字符串的好方法。但同样，我的问题是我是否必须对数据存储中的所有 100 万个值进行操作？

3）我知道，谷歌通过观察用户行为来做到这一点。但我想在不观察用户行为的情况下做到这一点，即使用我还不知道的距离算法。因为前一种方法需要大量搜索才能开始！

4）正如柯克布罗德赫斯特在下面的回答中指出的那样，有两种可能的情况：-

  • 用户输入错误的单词（编辑距离算法）
  • 不认识单词的用户猜测（语音匹配算法）

我对这两个都很感兴趣。它们实际上是两个不同的东西。例如，Sean 和 Shawn 听起来一样，但编辑距离为 3 - 太高而不能被视为错字。

4

8 回答 8

7

Soundex 算法可以帮助您解决这个问题。

http://en.wikipedia.org/wiki/Soundex

您可以为每个名称预先生成 soundex 值并将其存储在数据库中，然后对其进行索引以避免必须扫描表。

于 2009-08-16T17:10:13.743 回答
6

Bitap 算法旨在找到文本正文中的近似匹配。也许你可以用它来计算可能的匹配。（它基于Levenshtein Distance）

（更新：在阅读了Ben S的 答案之后（可能使用现有的解决方案aspell）是要走的路）

正如其他人所说，谷歌通过观察用户自己纠正来进行自动纠正。如果我搜索“ someting”（原文如此），然后立即搜索“ something”，很可能第一个查询不正确。检测这一点的可能启发式方法是：

  • 如果用户在短时间内完成了两次搜索，并且
  • 第一个查询没有产生任何结果（或者用户没有点击任何东西）
  • 第二个查询确实产生了有用的结果
  • 这两个查询相似（Levenshtein 距离很小）

那么第二个查询可能是对第一个查询的改进，您可以将其存储并呈现给其他用户。

请注意，您可能需要大量查询来收集足够的数据才能使这些建议有用。

于 2009-08-16T17:40:40.787 回答
4

我会考虑为此使用预先存在的解决方案。

带有自定义名称字典的Aspell可能非常适合此操作。生成字典文件将预先计算快速给出建议所需的所有信息。

于 2009-08-16T17:23:05.150 回答
3

这是一个老问题，DWIM（Do What I Mean），由 Warren Teitelman 在 Xerox Alto 上著名地实现。如果您的问题是基于发音，这里有一份调查报告可能会有所帮助：

J. Zobel 和 P. Dart，“语音字符串匹配：信息检索的教训”，Proc。第 19 届国际米兰。ACM SIGIR 会议 信息检索研究与开发 (SIGIR'96)，1996 年 8 月，第 166-172 页。

从事信息检索工作的朋友告诉我，Knuth 所描述的 Soundex 现在被认为已经过时了。

于 2009-08-16T17:21:31.847 回答
3

只需使用Solr或类似的搜索服务器，您就不必成为该主题的专家。使用拼写建议列表，对每个建议的结果进行搜索，如果结果多于当前搜索查询，则将其添加为“您的意思是”结果。（这可以防止虚假拼写建议实际上不会返回更多相关命中。）这样，您不需要收集大量数据来进行初始“您的意思是”产品，尽管 Solr 具有您可以使用的机制可以手动调整某些查询的结果。

通常，您不会将 RDBMS 用于此类搜索，而是依赖用于此目的的只读、稍微陈旧的数据库。（Solr 为底层 Lucene 引擎和数据库添加了友好的编程接口和配置。）在我工作的公司的网站上，夜间服务从 RDBMS 中选择更改的记录，并将它们作为文档推送到 Solr。不费吹灰之力，我们就有了一个系统，搜索框可以非常高效地搜索产品、客户评论、网站页面和博客条目，并在搜索结果中提供拼写建议，以及像您在 NewEgg 看到的分面浏览， Netflix 或 Home Depot，对服务器（尤其是 RDBMS）几乎没有额外的压力。（我相信 Zappo 的 [新网站] 和 Netflix 都在内部使用 Solr，但不要

在您的场景中，您将使用名称列表填充 Solr 索引，并在配置文件中选择适当的匹配算法。

于 2009-08-16T18:26:49.457 回答
2

就像您引用的问题的答案之一一样，Peter Norvig 的出色解决方案将适用于此，并配有 Python 代码。谷歌可能会通过多种方式查询建议，但他们需要的是大量数据。当然，他们可以使用大量查询日志对用户行为进行建模，但他们也可以仅使用文本数据通过查看哪个更正更常见来找到最可能正确的单词拼写。这个词someting没有出现在字典中，即使它是一种常见的拼写错误，正确的拼写也更为常见。当您找到相似的单词时，您需要最接近拼写错误且在给定上下文中最可能出现的单词。

Norvig 的解决方案是从 Project Gutenberg 中获取几本书的语料库，并计算出现的单词。他根据这些词创建了一个字典，您还可以在其中估计一个词的概率 ( COUNT(word) / COUNT(all words))。如果将这一切存储为直接哈希，访问速度很快，但存储可能会成为问题，因此您也可以使用后缀 Trys之类的东西。访问时间仍然相同（如果您基于哈希实现它），但存储需求可以少得多。

接下来，他为拼写错误的单词生成简单的编辑（通过删除、添加或替换字母），然后使用语料库中的字典限制可能性列表。这是基于编辑距离（例如 Levenshtein 距离）的概念，具有简单的启发式方法，即大多数拼写错误发生在编辑距离为 2 或更小的情况下。您可以根据您的需求和计算能力来扩大这一范围。

一旦他有了可能的单词，他就会从语料库中找到最可能的单词，这就是你的建议。您可以添加许多东西来改进模型。例如，您还可以通过考虑拼写错误中字母的键盘距离来调整概率。当然，这假设用户使用的是英文 QWERTY 键盘。例如，转置 an和 a比转置 an和ea更有可能。qel

于 2009-08-24T02:54:36.867 回答
1

您有两个可能需要解决的问题（如果您愿意，也可以不解决）

  1. 用户输入错误的单词（编辑距离算法）
  2. 不认识单词的用户猜测（语音匹配算法）

你对这两个感兴趣，还是只对其中一个感兴趣？它们实际上是两个不同的东西。例如，Sean 和 Shawn 听起来一样，但编辑距离为 3 - 太高而不能被视为错字。

您应该预先索引字数，以确保您只建议相关答案（类似于 ealdent 的建议）。例如，如果我输入了，sith我可能会被问到我的意思是不是smith，但是如果我输入smith了，那么建议是没有意义的sith。确定一个算法来衡量一个单词的相对可能性，并且只建议更有可能的单词。

我在松散匹配方面的经验强化了一个简单但重要的学习——根据需要执行尽可能多的索引/筛选层，不要害怕包含超过 2 或 3 个。剔除任何不以正确字母开头的内容，因为例如，然后剔除不以正确字母结尾的所有内容，依此类推。您真的只想对尽可能小的数据集执行编辑距离计算，因为这是一项非常密集的操作。

因此，如果您有一个 O(n)、一个 O(nlogn) 和一个 O(n^2) 算法 - 按顺序执行所有这三个算法，以确保您只将“好前景”用于繁重的算法.

于 2009-09-01T02:33:51.670 回答
1

对于推荐 Soundex 的人来说，它已经过时了。Metaphone（更简单）或 Double Metaphone（复杂）要好得多。如果它真的是名称数据，它应该可以正常工作，如果名称是欧洲式的，或者至少是语音的。

至于搜索，如果你想自己动手，而不是使用 Aspell 或其他一些智能数据结构......在幼稚的情况下，预先计算可能的匹配是 O(n^2)，但我们知道为了要完全匹配，它们必须有一个“音素”重叠，甚至可能有两个。这个预索引步骤（误报率低）可以大大降低复杂性（在实际情况下，类似于 O(30^2 * k^2)，其中 k << n）。

于 2009-09-01T01:57:03.300 回答