问题标签 [levenshtein-distance]

我同时使用 Daitch-Mokotoff soundexing 和 Damerau-Levenshtein 来确定应用程序中的用户条目和值是否“相同”。

Levenshtein 距离是否应该用作绝对值？如果我有一个 20 个字母的单词，那么 4 的距离还不错。如果单词有4个字母...

我现在正在做的是获取距离/长度以获得更好地反映单词已更改百分比的距离。

这是一种有效/经过验证的方法吗？还是单纯的愚蠢？

如果是这样，请解释如何。

回复：什么是距离——“两个字符串之间的距离定义为将一个字符串转换为另一个字符串所需的最少编辑次数。”

例如，xyz 到 XYZ 需要 3 次编辑，因此字符串 xYZ 更接近 XYZ 和 xyz。

如果模式是 [0-9]{3} 或例如 123，则 a23 将比 ab3 更接近模式。

如何找到正则表达式和不匹配字符串之间的最短距离？

以上是Damerau-Levenshtein距离算法。

下午好，

有谁知道 .NET 中的 Levenshtein DFA（确定性有限自动机）的“开箱即用”实现（或易于翻译）？我有一个非常大的字典，其中包含超过 160000 个不同的单词，并且我想给定一个初始单词w ，以有效的方式在 Levenshtein 距离最多 2 个w找到所有已知单词。

当然，有一个函数可以计算给定单词的一个编辑距离处的所有可能的编辑，并将其再次应用于这些编辑中的每一个，可以解决问题（并且以一种非常简单的方式）。问题是效率 --- 给定一个 7 个字母的单词，这已经需要 1 秒多的时间才能完成，我需要更高效的东西---如果可能的话，就像 Levenshtein DFA 一样，一个需要 O( | w| ) 步骤。

编辑：我知道我可以通过一点学习来构建自己的解决方法，但目前我无法阅读 Schulz 和 Mihov 的 60 页长的文章。

非常感谢你。

我目前正在为术语 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 并汇总它下面的所有终端节点（这将是很多）。但是，如果我们限制结果的数量，则会过于强调以查询开头的单词而不是编辑距离。因此，像导管插入这样的词比像外套这样的词更有可能被包括在内。

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

我正在玩Levenshteins Edit Distance algorithm，我想扩展它以计算换位 - 即相邻字母的交换 - 作为 1 个编辑。未修改的算法计算从另一个字符串到达​​某个字符串所需的插入、删除或替换。例如，从“KITTEN”到“SITTING”的编辑距离为 3。这是来自 Wikipedia 的解释：

1. kitten → sitten (用 's' 代替 'k')
2. sitten → sittin（用'i'代替'e'）
3. 坐→坐（在末尾插入“g”）。

按照同样的方法，“CHIAR”到“CHAIR”的编辑距离为2：

1. CHIAR → CHAR（删除“我”）
2. CHAR → CHAIR（插入“I”）

我想把这算作“1次编辑”，因为我只交换了两个相邻的字母。我该怎么做呢？

我一直在寻找一种先进的 levenshtein 距离算法，到目前为止我发现的最好的是 O(n*m) 其中 n 和 m 是两个字符串的长度。算法之所以处于这种规模，是因为空间，而不是时间，创建了一个由两个字符串组成的矩阵，例如：

是否有比 O(n*m) 更好的公开可用的 levenshtein 算法？我不反对查看高级计算机科学论文和研究，但一直找不到任何东西。我找到了一家公司，Exorbyte，据说它已经建立了一个超级先进和超级快速的 Levenshtein 算法，但这当然是一个商业机密。我正在构建一个我想使用 Levenshtein 距离计算的 iPhone 应用程序。有一个objective-c 实现可用，但是由于iPod 和iPhone 上的内存量有限，如果可能的话，我想找到一个更好的算法。

有没有一种通用的方法可以在相似度度量和距离度量之间进行转换？

考虑一个相似性度量，例如两个字符串共有的 2-gram 的数量。

如果我需要将其提供给期望差异度量的优化算法，例如 Levenshtein 距离，该怎么办？

这只是一个例子......我正在寻找一个通用的解决方案，如果存在的话。就像如何从 Levenshtein 距离到相似度的度量？

感谢您提供的任何指导。

将模式与一组字符串逐个进行比较，同时评估模式与每个字符串匹配的数量的最佳方法是什么？在我对正则表达式的有限经验中，使用正则表达式将字符串与模式匹配似乎是一个非常二元的操作......无论模式多么复杂，最终，它要么匹配要么不匹配。我正在寻找更强大的功能，而不仅仅是匹配。是否有与此相关的良好技术或算法？

这是一个例子：

假设我有一个模式foo bar，我想从以下字符串中找到最匹配它的字符串：

现在，这些都不匹配模式，但哪个不匹配最接近匹配？在这种情况下，foo bax将是最佳选择，因为它匹配 7 个字符中的 6 个。

抱歉，如果这是一个重复的问题，当我查看这个问题是否已经存在时，我真的不知道要搜索什么。

我已经实现了该算法，但现在我想找到与其他字符串具有最短编辑距离的字符串的编辑距离。

这是算法：

我想通过 q​​-gram 距离或简单的“袋子距离”或 Python 中的 Levenshtein 距离来聚集约 100,000 个短字符串。我打算填写一个距离矩阵（100,000 选择 2 个比较），然后使用pyCluster进行层次聚类。但我什至在起步之前就遇到了一些记忆问题。例如，距离矩阵对于 numpy 来说太大了。

这似乎是一件合理的事情吗？还是我注定要在这项任务中出现记忆问题？谢谢你的帮助。