问题标签 [fuzzy-search]

我正在寻找一种适用于西欧语言的模糊搜索实现。

哪种算法效果最好，我在哪里可以找到 C# 中的实现？

更新

Soundex 适用于瑞典语：

• http://escuelle.blogspot.com/2008/03/swedish-soundex.html

NYSSIS 实施：

• http://www.gamedev.net/community/forums/topic.asp?topic_id=497137
• http://dropby.com/PhonKey.cs

莱文斯坦：

• http://www.merriampark.com/ldcsharp.htm

令人印象深刻的 Java 库：

• http://www.dcs.shef.ac.uk/~sam/stringmetrics.html

但是我仍然不知道哪个更适合西欧语言

Textmate 的“转到文件”模糊搜索真的很棒。

Wincent 的用于 vim 的 Command-T 插件做了类似的事情，它也很震撼。

有人可以解释这些是如何工作的吗？他们使用的方法有通用术语吗？

编辑：关于这些工具的作用，我稍微详细一点

这些工具可让您在键入时缩小选项列表（在本例中为文件路径）。

例如，如果我有以下文件：

要将列表缩小到/app/models/people.rb我可以键入以下任何内容：

它非常灵活，当我使用的应用程序没有它时，我发现我自己错过了这个“列表缩小”。我想了解更多关于它的信息，以便在我觉得有需要时可以实现自己的插件。希望我能更好地解释它，但这就是我在这里的原因:)

要查看它的实际效果，请查看 wincent 的command-t 演示

我需要使用包含大约 800 万行的索引来制作FuzzyQuery 。这种查询非常慢，每次匹配大约需要 20 秒。事实是，在进行模糊搜索之前，我可以使用另一个字段将结果缩小到大约 5000 个命中。为此，我应该能够先通过“较窄”字段进行搜索，然后在这些结果中使用模糊搜索。

根据lucene FAQ，我唯一要做的就是BooleanQuery，其中应该需要“更窄”（在 lucene 3 中为BooleanClause.Occur.MUST ）。

现在我尝试了两种不同的方法：

a)使用查询解析器，输入如下： narrower:+narrowing_text fuzzy:fuzzy_text~0.9

b)使用TermQuery和FuzzyQuery构造BooleanQuery

也没有工作，我得到的时间与不使用较窄的时间大致相同。

此外，只是为了检查是否窄的工作时间应该更好，我只重新索引了与窄匹配的 5000 个项目，搜索速度非常快。

如果有人想知道，我使用的是 pylucene 3.0.2。

我目前正在为术语 Web 服务实现模糊搜索，并且正在寻找有关如何改进当前实现的建议。分享的代码太多，但我认为一个解释可能足以引发深思熟虑的建议。我意识到要阅读的内容很多，但我会很感激任何帮助。

首先，术语基本上只是一些名称（或术语）。对于每个单词，我们按空格将其拆分为标记，然后遍历每个字符以将其添加到 trie 中。在终端节点上（例如当到达草莓中的字符 y 时），我们将主术语列表的索引存储在列表中。所以一个终端节点可以有多个索引（因为草莓的终端节点将匹配“草莓”和“草莓过敏”）。

至于实际搜索，搜索查询也被空格分解为标记。为每个令牌运行搜索算法。搜索标记的第一个字符必须是匹配的（因此 traw 永远不会匹配草莓）。之后，我们遍历每个连续节点的子节点。如果有匹配字符的子元素，我们继续使用搜索标记的下一个字符进行搜索。如果孩子与给定字符不匹配，我们使用搜索标记的当前字符查看孩子（因此不推进它）。这是模糊部分，所以 'stwb' 将匹配 'strawberry'。

当我们到达搜索标记的末尾时，我们将在该节点搜索剩余的 trie 结构以获取所有潜在匹配项（因为主术语列表的索引仅在终端节点上）。我们称之为汇总。我们通过在 BitSet 上设置它们的值来存储索引。然后，我们简单地和 BitSets 从结果中搜索每个 token 的结果。然后，我们从 anded BitSet 中获取前 1000 或 5000 个索引，并找到它们对应的实际术语。我们使用 Levenshtein 对每个术语进行评分，然后按分数排序以获得最终结果。

这工作得很好，而且速度很快。树中有超过 39 万个节点和超过 110 万个实际术语名称。但是，就目前情况而言，存在一些问题。

例如，搜索“car cat”将返回导管化，当我们不希望它返回时（由于搜索查询是两个单词，结果应该至少是两个）。这很容易检查，但它不处理像导管插入术这样的情况，因为它是两个词。理想情况下，我们希望它与心导管术等相匹配。

基于纠正这个问题的需要，我们提出了一些改变。一方面，我们在混合深度/广度搜索中遍历 trie。本质上，只要字符匹配，我们就会先深入。那些不匹配的子节点被添加到优先级队列中。优先级队列按编辑距离排序，可以在搜索trie时计算（因为如果有字符匹配，距离保持不变，如果没有，它增加1）。通过这样做，我们得到了每个单词的编辑距离。我们不再使用 BitSet。相反，它是索引到 Terminfo 对象的映射。该对象存储查询短语和术语短语的索引和分数。因此，如果搜索是“car cat”并且匹配的词是“Catheterization procedure” 术语短语索引将是 1，查询短语索引也是如此。对于“心导管术”，术语短语索引将是 1,2，查询短语索引也是如此。如您所见，之后查看术语短语索引和查询短语索引的计数非常简单，如果它们至少不等于搜索字数，则可以丢弃它们。

之后，我们将词的编辑距离相加，从词中剔除匹配词组索引的词，统计剩余的字母，得到真正的编辑距离。例如，如果您匹配术语“对草莓过敏”并且您的搜索查询是“稻草”，那么草莓的得分为 7，那么您将使用术语短语索引从术语中丢弃草莓，然后计算“过敏”（减去空格）得到 16 分。

这让我们得到了我们期望的准确结果。但是，它太慢了。以前我们可以在一个单词搜索上获得 25-40 毫秒，现在它可能长达半秒。它主要来自于实例化 TermInfo 对象、使用 .add() 操作、.put() 操作以及我们必须返回大量匹配项的事实。我们可以将每次搜索限制为仅返回 1000 个匹配项，但不能保证“car”的前 1000 个结果与“cat”的前 1000 个匹配项中的任何一个匹配（请记住，有超过 110 万个术语）。

即使对于单个查询词，例如 cat，我们仍然需要大量匹配。这是因为如果我们搜索“cat”，搜索将匹配 car 并汇总它下面的所有终端节点（这将是很多）。但是，如果我们限制结果的数量，则会过于强调以查询开头的单词而不是编辑距离。因此，像导管插入这样的词比像外套这样的词更有可能被包括在内。

那么，基本上，对于我们如何处理第二个实现解决的问题，但又没有它引入的速度减慢多少，我们有什么想法吗？如果可以使事情更清楚，我可以包含一些选定的代码，但我不想发布一堵巨大的代码墙。

我自己已经尝试了相当长的一段时间，并在网上到处寻找 - 但无法找到任何通过 Lucene.NET 2.9.2 搜索模糊短语的示例。（ C＃ ）

有什么东西能够详细建议如何做到这一点和/或提供一些示例代码 - 我会非常感谢任何帮助，因为我完全被困住了？

我正在寻找的是返回一些对行数的估计，而不是实际计数，这可能是一个昂贵的调用。类似于您在 google 搜索中看到的内容（... of about 1.000 rows）。

有一些开箱即用的解决方案吗？如果没有，一般的方法是什么？

我正在查询 Sql Server 2008 数据库。

编辑：为了澄清，结果计数与某些用户查询有关。例如，用户搜索“John”，结果应该是“大约有 1.280.000 行匹配 John”

我需要实现某种这样的：

这是用 C# 编写的函数存根：

但我不知道如何在 IsFuzzyMatch 方法中实现逻辑。有任何想法吗？也许为此目的有现成的解决方案？

对于学校项目，目标是将查询字符串与 Song 对象内的歌词字符串进行模糊匹配。整个数据结构是一个由唯一单词与歌词中包含该单词的歌曲集配对的 TreeMap。

我有包含查询字符串的初步匹配歌曲集。这里的转折是我必须根据匹配部分中的字符数为每首结果歌曲分配一个排名，包括空格。例如，搜索“她爱你”会在匹配项中返回以下内容：

“......她爱你......”披头士乐队，排名 = 13
“......她只是爱你......”邦妮雷特，排名 = 18
“......她爱我，你......”猫王普雷斯利，排名=23

我用来对结果进行排序的是：

由于结果集中的所有歌曲都以任何特定顺序包含查询词，因此它们不会全部包含在结果打印输出中。使用此算法，如果查询不匹配任何特定长度，我如何设置触发器以从集合中删除歌曲？

编辑-Lucene 是解决这个问题的方法吗？这是项目中的一个灰色地带，明天我将在课堂上提出。他允许我们为这个项目选择任何数据结构，但我不知道使用另一个实现进行字符串匹配是否会通过集合。

编辑 2 @belisarius-我看不到编辑距离如何应用在这里。Levenshtein 距离最常见的应用需要一个长度为 n 的字符串 a 和长度为 m 的字符串 b，而距离是 a==b 所需的编辑次数。对于这个项目，只需要匹配中字符的排名，起点和终点是未知的。通过对上面发布的代码进行一些更改，我可以准确地找到起点和终点。如果歌词以任何方式不适合搜索，我需要一种从集合中删除不匹配项的方法。

我遇到了匹配 OCR 识别文本中的字符串并找到它的位置的问题，考虑到可以任意容忍错误、缺失或额外的字符。结果应该是最佳匹配位置，可能（不一定）具有匹配子字符串的长度。

例如：

我试图调整 Levenstein 算法，但它不适用于子字符串并且不返回位置。

Delphi 中的算法将是首选，但任何实现或伪逻辑都可以。

我正在浏览所有现有的问题帖子，但无法获得非常相关的内容。

我有数百万条记录的人名、姓氏、地址 1、地址 2、国家代码、出生日期 - 我想每天检查我的客户名单和上述文件（我的客户名单也每天更新，并且文件也会每天更新）。

对于名字和姓氏，我想要模糊匹配（可能是 lucene 模糊查询/levenshtein 距离 90% 匹配），对于其余字段国家和出生日期，我想要完全匹配。

我是 Lucene 的新手，但是通过查看帖子的数量，看起来是可能的。

我的问题是：

• 我应该如何索引我的输入文件？我需要在 FN、LN、国家、DOB 的组合上建立索引并使用索引进行搜索
• 我如何在这里使用 Lucene 的模糊查询？

还有其他方法可以实现吗？