问题标签 [levenshtein-distance]

我有带有数据的 excel 表，我想获得它们之间的 Levenshtein 距离。我已经尝试导出为文本，从脚本（php）中读取，运行 Levenshtein（计算 Levenshtein 距离），再次将其保存到 excel 中。

但我正在寻找一种在 VBA 中以编程方式计算 Levenshtein 距离的方法。我该怎么做呢？

晚安，

我一直在使用模糊字符串匹配一段时间，并且使用带有一些指针的 C，我可以编写一个非常快速的（满足我的需要）两个字符串之间的 Levenshtein 距离的实现。我尝试使用不安全代码和fixed关键字将代码移植到 C#，但性能要慢得多。所以我选择构建一个 C++ dll 并使用[DllImport]来自 C#，自动编组每个字符串。问题是，在分析之后，这一直是我的程序中最耗时的部分，占程序总运行时间的 50-57%。因为我认为我需要对来自大约 300 万条数据库记录的文本字段的大量子字符串做一些繁重的工作，所以我认为 Levenshtein 距离所花费的时间几乎是不可接受的。也就是说，我想知道您是否对下面的代码有任何建议，无论是算法还是编程相关，或者您是否知道任何更好的算法来计算这个距离？

请注意，BufferVar 和 BufferTab 是两个外部int *的（在这种情况下，int[]变量是从 C# 编组的），我不会在每个函数调用中实例化它们以加快整个过程。尽管如此，这段代码对于我的需要来说还是很慢的。谁能给我一些建议，或者，如果可能的话，提供一些更好的代码？

编辑：距离不能有界，我需要实际距离。

非常感谢，

我想知道是否有一个有效的数据结构来执行“检索所有列文距离小于 X 的字符串”。

我感兴趣的几件事：

• 算法说明。
• 现有数据库/编程语言中是否有现有实现？
• 我可以参考的论文/文章？

我正在尝试解决一个涉及比较大量单词集的问题，每个单词集都包含来自一组单词的大量有序单词（总计约 600+，非常高的维度！）以进行相似性，然后将它们聚类成不同的分组。解决方案需要尽可能不受监督。

数据看起来像

[苹果、香蕉、橙子...]
[苹果、香蕉、葡萄...]
[果冻、茴香、橙子...]
[草莓、香蕉、橙子...]
...等

每组单词的顺序很重要（[Apple, Banana, Orange] 与 [Apple, Orange, Banana] 不同

到目前为止，我一直使用的方法是使用 Levenshtein 距离（受距离阈值限制）作为在 Python 脚本中计算的度量，每个单词都是唯一标识符，从距离生成相似度矩阵，然后将该矩阵放入用于分组的 KNIME 中的 k-Mediods。

我的问题是：

• Levenshtein 是解决这个问题的最合适的距离度量吗？
• 均值/中心点原型聚类是进行分组的最佳方式吗？
• 我还没有花太多心思来验证集群中“k”的选择。评估聚类的 SSE 曲线是否是解决此问题的最佳方法？
• 我的方法有什么缺陷吗？
• 作为未来解决方案的扩展，在给定训练数据的情况下，是否有人碰巧对将概率分配给集群分配有任何想法？例如，集合 1 有 80% 的机会位于集群 1 中，等等。

我希望我的问题不会显得太愚蠢或答案很明显，我对数据挖掘还比较陌生。

谢谢！

我必须在源字符串和一组模式字符串之间执行模糊匹配。这种匹配由公式 1 - D(I,P) / max(length(I),length(P))
给出，其中

• 我是输入字符串
• P 是一个模式字符串
• D(I,P) 是 I 和 P 之间的 levenshtein 距离。

一旦我找到了最大化这个分数的 P，我想要 I 和 P 的公共部分之间的映射

例如：如果 I="sunday" 和 P="saturday"，则映射将类似于以下对的列表：
{{0, 0}, {1, 3}, {3, 5}, {4 , 6}, {5, 7}}
因为常见的字符有 's', 'u', 'd', 'a' 和 'y'

在这篇 wikipedia article 中，可以很容易地找到一种计算 levenshtein 距离的实现，但我并不完全清楚如何从它描述的过程中构建的矩阵中获取映射。任何人都可以启发我吗？

谢谢

我正在尝试使用我在网上找到的 levenshtein 算法来计算最接近搜索词的值。为了实现模糊词匹配。我当前的查询运行大约 45 秒。我希望我可以优化它。我已经为计算 levenshtein 值的字段添加了索引。我发现的 levenshtein 函数可能不是最优化的，我不相信它的实现。这是该功能：

这是我正在使用的查询：

我不是 DBA，所以请原谅我对任何最佳实践的无知——这就是我来这里学习的原因:)。我真的不想在业务层中卸载此处理，并希望将其保留在数据层中，但只有 16k 条记录需要 45 秒来处理它目前不可用。这只是记录的一小部分，一旦我处理完输入文件，它将构成整个数据存储。提前致谢。

我有一个带有 str1 str2 str3... 的文本文件，我想用 LD(str1,str2) LD(str2,str3) LD(str3,str4) 等输出另一个文本文件。这个怎么做？任何语言都可以。

好吧，伙计们正在使用 jQuery-UI AutoComplete 和来自 sql-sever 2008 db 的结果来处理搜索建议。使用 AdventureWorks DB Products 表进行测试。我想在此示例中搜索 2 个字段。产品编号和名称。

我之前问了两个与此相关的问题......这里和这里

到目前为止，我想出了这个......

我现在的问题是结果的排序......我得到了正确的结果，但它们只是按名称或产品编号排序，与输入字符串无关......

例如，我可以搜索以“BZ-”开头的产品编号，并且返回的顶部结果是以“A”开头的 ProductNums，尽管我确实在列表的其他地方获得了更多相关的结果..

根据与搜索字符串的相关性对结果进行排序的任何想法？

编辑：

关于在此处找到的 levenschtein 距离的 tql 实施（链接到上一个问题）...

我想知道确定发送到函数的 MAX 值的最佳方法是什么（在我上面的示例中为 6）

最好根据“似乎”对我的给定数据集有效的值来选择任意值吗？还是最好根据输入字符串的长度动态调整它...

我最初的想法是该值应该与 searchString 的长度成反比......所以随着搜索字符串的增长并变得更加具体......容差减少......想法？

对于我正在研究的问题，找到两个序列之间的距离以确定它们的相似性，序列顺序非常重要。但是，我拥有的序列的长度并不完全相同，因此我用空点填充任何有缺陷的字符串，以便两个序列的长度相同，以满足汉明距离要求。我这样做有什么大问题吗，因为我只关心换位的数量（而不是像 Levenshtein 那样的插入或删除）？

我发现汉明距离比 Levenshtein 快得多，作为更长长度序列的距离度量。什么时候应该使用 Levenshtein 距离（或 Levenshtein 距离的衍生物）而不是便宜得多的汉明距离？汉明距离可以被认为是两个序列之间可能的 Levenshtein 距离的上限，所以如果我比较两个序列的顺序偏差相似性度量，而不是匹配序列的绝对最小移动次数，则没有明显的我选择 Levenshtein 而不是 Hamming 作为指标的原因，有吗？

对于说荷兰语的人来说，两个字符“ij”被认为是一个很容易与“y”交换的字母。

对于我正在从事的项目，我希望有一个Damerau-Levenshtein 距离的变体，它将“ij”和“y”之间的距离计算为 1，而不是当前值 2。

我自己一直在尝试，但失败了。我的问题是我不知道如何处理两个文本长度不同的事实。有没有人有关于如何解决这个问题的建议/代码片段？

谢谢。