问题标签 [fuzzy-search]

我有一个 ~300.000 行表；其中包括技术术语；使用 PHP 和 MySQL + FULLTEXT 索引进行查询。但是当我搜索输入错误的术语时；例如“超文本”；自然没有结果。

我需要“补偿”小的书写错误并从数据库中获取最近的记录。我怎样才能完成这样的功能？我知道 Levenshtein 距离、Soundex 和 Metaphone 算法，但目前还没有一个可靠的想法来实现它来查询数据库。

谢谢

我正在下载我的电子邮件主题行的长列表，目的是找到我多年前加入的电子邮件列表，并希望从我的 Gmail 帐户中清除它们（这变得非常缓慢。）

我特别考虑经常来自同一地址的通讯，并在主题中重复产品/服务/组的名称。

我知道我可以按来自特定电子邮件地址的常见项目进行搜索/排序（我打算这样做），但我想将这些数据与重复的主题行关联起来......

现在，许多主题行将无法匹配字符串，但“Google Friends : Our latest news”“Google Friends : What we are today”比随机主题行更相似，例如：“Virgin Airlines has今天大减价” “搭乘维珍航空的航班”

那么 - 我怎样才能开始自动提取可能更相似的字符串的趋势/示例。

我考虑过并放弃的方法（“因为必须有更好的方法”）：

• 提取所有可能的子字符串并按照它们出现的频率对其进行排序，并手动选择相关的子字符串
• 剥离第一个或两个单词，然后计算每个子字符串的出现次数
• 比较条目之间的 Levenshtein 距离
• 某种字符串相似度索引...

其中大多数因效率低下或可能需要大量人工干预而被拒绝。我想我需要某种模糊字符串匹配..？

最后，我可以想出一些笨拙的方法来做这件事，但我正在寻找更通用的东西，所以我已经添加到我的工具集中，而不是这个数据集的特殊外壳。

在此之后，我会将特定主题字符串的出现与“发件人”地址进行匹配 - 我不确定是否有一种构建数据结构的好方法，该数据结构表示两条消息是“同一电子邮件”的一部分的可能性有多大列表”或通过将我所有的电子邮件主题/地址过滤到可能的“相关”电子邮件池中，而不是 - 但这是在此之后要解决的问题。

任何指导将不胜感激。

在 TextMate 中有一个称为“转到文件”的功能，用于文件导航。它是一个框，您可以在其中键入项目中文件的名称，它将使用模糊匹配来生成您可以从中选择的候选文件列表。

其他编辑器也有这个功能，但他们都给它起了不同的名字：

Vim blurfinder
Emacs blur-find-in-project
TextMate 转到文件（模糊）
Eclipse OpenResource（不模糊）
Eclipse GotoFile（模糊）
Komodo 转到文件（不模糊）
Netbeans 转到文件（不模糊）

jEdit、Geany 或 Ultraedit 是否具有此功能？

我正在寻找诸如 Textmate 在 Command-T 上的模糊搜索、 Vim 中的FuzzyFinder或Emacs 中的Ido之类的东西。它存在吗？如果没有，你更喜欢怎么做？

通过模糊匹配，我并不是指 Levenshtein 距离或类似的字符串，而是它在 TextMate/Ido/Icicles 中的使用方式：给定字符串列表，找到包含搜索字符串中所有字符的字符串，但可能与其他字符串之间的字符，更喜欢最合适的。

我想使用 Lucene 的模糊搜索，我理解它是基于某种类似 Levenshtein 的算法。如果我使用一个相当高的阈值（即“new york~0.9”），它是否会首先计算编辑距离，然后查看它是否小于 0.9 对应的值，或者如果很明显它会切断算法文档与查询不匹配？我知道使用 levenshtein 算法可以做到这一点。

我需要通过检查每个条目的预定义字符串的模糊匹配来过滤文本文章流（我正在搜索拼写错误的产品名称，有时它们有不同的单词顺序和额外的非字母字符，如“：”或“，”）。

通过将这篇文章放入 sphinx 索引并对其执行搜索，我得到了很好的结果，但不幸的是，我每秒收到数百篇文章，并且在获取每篇文章后更新索引太慢（我知道它不是为此类任务设计的）。我需要一些库，它可以在大约 100kb 的小文本的内存索引中构建并对其执行模糊搜索，这样的东西存在吗？

如果我的索引包含三个布尔字段：a、b 和 c...
我想搜索：“a=True, b=False, c=True” 并且 SOLR 应该返回所有条目，它们的分数应该代表有多好整个查询匹配。

例如

那可能吗 ？

我正在为内部 CRM 做一些事情。该公司当前的前端允许大量重复。我试图阻止最终用户输入同一个人，因为他们搜索的是“Bill Johnson”而不是“William Johnson”。因此，用户将输入一些关于他们的新客户的信息，我们会找到相似的名称（包括模糊名称）并将它们与我们数据库中已有的内容进行匹配，并询问他们是否意味着这些东西......这样的数据库或技术存在吗？

我在哪里可以找到一些真实世界的错字统计？

我试图将人们的输入文本与内部对象相匹配，而人们往往会犯拼写错误。
有2种错误：

1. typos- “你好”而不是“你好”/“星期六”而不是“星期六”等。
2. Spelling- “Shikago”而不是“Chicago”

我将 Damerau-Levenshtein 距离用于拼写错误，使用Double Metaphone进行拼写（此处和此处的 Python 实现）。

我想专注于 Damerau-Levenshtein（或简单地说edit-distance）。教科书的实现总是使用“1”作为删除、插入替换和转置的权重。虽然这很简单并且允许使用很好的算法，但它与“现实”/“现实世界的概率”不匹配。

例子：

• 我确信“Hello”（“Hello”）的可能性大于“Helzlo”，但它们都在 1 个编辑距离之外。
• 在 QWERTY 键盘上，“Gello”比“Qello”更接近“Hello”。
• Unicode 音译：“München”和“Munchen”之间的“真实”距离是多少？

删除、插入、替换和转座的“真实世界”权重应该是多少？

即使是Norvig 非常酷的拼写校正器也使用非加权编辑距离。

顺便说一句-我确定权重需要是函数而不是简单的浮点数（根据上面的示例）...

我可以调整算法，但我在哪里可以“学习”这些权重？我无权访问Google 规模的数据...

我应该猜他们吗？

编辑 - 试图回答用户问题：

• 由于上述原因，我当前的非加权算法在遇到拼写错误时经常失败。“周四回归”：每个“真人”都可以轻松判断周四比周二更有可能，但他们都在 1 编辑距离之内！（是的，我会记录并衡量我的表现）。
• 我正在开发一个 NLP 旅行搜索引擎，所以我的字典包含 ~25K 目的地（预计增长到 100K）、时间表达式 ~200（预计 1K）、人物表达式 ~100（预计 300）、金钱表达式 ~100（预计 500 )、“粘合逻辑词”（“from”、“beautiful”、“apartment”）~2K（预计10K）等等……
• 对于上述每个词组，编辑距离的使用是不同的。我尝试“在明显时自动更正”，例如与字典中仅 1 个其他单词相距 1 个编辑距离。我还有许多其他手动调整的规则，例如 Double Metaphone 修复，它与长度 > 4 的字典单词的编辑距离不超过 2...随着我从现实世界的输入中学习，规则列表继续增长。
• “你的阈值内有多少对字典条目？”：嗯，这取决于“花式加权系统”和现实世界（未来）的输入，不是吗？无论如何，我进行了大量的单元测试，因此我对系统所做的每一次更改都只会让它变得更好（当然，基于过去的输入）。大多数低于 6 个字母的单词与一个单词的编辑距离在 1 个编辑距离之内，而该单词与另一个字典条目的编辑距离为 1 个编辑距离。
• 今天，当有 2 个字典条目与输入的距离相同时，我尝试应用各种统计数据来更好地猜测用户的意思（例如，法国巴黎比伊朗巴黎更可能出现在我的搜索中）。
• 选择错误单词的代价是向最终用户返回半随机（通常是荒谬的）结果，并可能失去客户。不理解的成本略低：将要求用户重新措辞。
• 复杂性的代价值得吗？是的，我敢肯定。您不会相信人们向系统抛出的拼写错误数量并期望它能够理解，而且我肯定可以使用Precision 和 Recall的提升。