我试图量化两个字符串之间的差异，作为变更监控系统的一部分。

我遇到的问题是字符串很大- 我经常可以处理 100K+ 个字符的字符串。

我目前正在使用 Levenshtein 距离，但计算大字符串的 levenshtein 距离非常低效。即使是最好的实现也只能管理O(min(mn)).

由于两个字符串的长度大致相同，因此距离计算过程可能需要很多秒。

我不需要高精度。千分之一的变化分辨率（例如 0.1%）对于我的应用程序来说已经足够了。

有哪些选项可以更有效地计算字符串距离？

我正在使用 ZSS 库计算 Tree-Edit-Distance b/w 两个代码。在任何代码中使用 while 循环时，它都会引发一个名为 Invalid syntax 的错误。它适用于 for 循环。我为此使用[链接] https://github.com/timtadh/zhang-shasha。

给定一个任意字符串s，我想要一种方法从一大组字符串 M （其中 |M| > 100 万）中快速检索所有字符串 S ⊆ M ，其中 S 的所有字符串具有最小编辑距离 < t （一些最小值阈值）来自s。

在最坏的情况下，如果 M 中没有符合此条件的字符串，则 S 可能为空，而在最好的情况下，S = { s }（完全匹配）。对于介于两者之间的任何情况，我完全预计 S 可能会很大。

一般来说，我希望最大编辑距离阈值是固定的（例如，2），并且需要在任意字符串s上多次执行此操作，因此需要一种有效的方法，因为天真地迭代和测试所有字符串将是太贵了。

虽然我使用编辑距离作为示例指标，但我也想使用其他指标，例如 Jaccard 索引。

任何人都可以对可以实现此目标的现有 Java 实现提出建议，或者指出我解决此问题的正确算法和数据结构吗？

更新#1

从那以后，我了解到度量树正是我所追求的那种结构，它利用距离度量来组织 M 中的字符串子集，基于它们与度量之间的距离。Vantage-Point、BK和其他类似的度量树数据结构和算法似乎都非常适合这类问题。现在，要在 Java 中找到易于使用的实现......

更新#2

使用这个bk-tree和这个Levenshtein 距离实现的组合，我能够成功地从一百万个字符串的集合 (M) 中检索任意字符串的子集，检索时间约为 10 毫秒。

有以下声明：

它输出如下表：

我想在 where/in 语句中使用这个临时集合：

我有两个问题：

1. 怎么办p.name in (tokenkeys.wordsplit)？
2. 如何将临时集合与 edit_distance_similarity 函数混合，并获得最大结果：

例子：

非常感谢。

对于我的数据分析问题，我通常需要规范名称，即名称 A 和 B，如果 A 和 B 共享大量公共子字符串，无论这些子字符串的顺序如何，我都会认为它们相同或非常相似。

例如，对于 "COLD" 和 c("FLOOD", "COLD/WIND CHILL")，我想选择 "COLD/WIND CHILL" 更类似于 "COLD" 而不是 "FLOOD"。

我目前的任务是在 R 中。所以我的具体问题如下：

1. R中是否已经定义了这样的指标？

2. 是否可以提供我自己的实现并以某种方式与 R 的 stringdist 包集成？

对于我的要求，我可以简单地使用正则表达式搜索，只要我能在 B 中找到 A 或在 A 中找到 B，我可以认为它们的距离为 0。

非常感谢！

编辑：

在以下情况下：

我希望从“COLD”到“COLD/WIND CHILL”的距离小于“COLD”到“FLOOD”。

在找到匹配的子字符串后，指标似乎必须忽略要删除的剩余部分。

编辑1：

我原来的问题已经解决了。以下是在 R中使用amatchof的相关问题的跟进：stringdist

在我看来，我无法重现与 . 相同的结果adist，甚至无法stringdist在与amatch.

下面是插图：

在上述上下文中，通过使用 的计算stringdist，amatch应该返回2，而不是1。

基于stringdist的文档，

“权重：
对于method='osa'或'dl'，删除、插入、替换和转置的惩罚，依此顺序。当method='lv'时，转置的惩罚被忽略。”

我相应地选择了权重以消除对删除的惩罚，同时最大化对其他操作的惩罚。令人鼓舞的是stringdist，使用权重设置显示了预期的行为。

我假设这amatch将用于进行计算，但与 ! 的行为相矛盾的行为stringdist似乎很奇怪！amatchstringdist

我希望开始amatch工作，这样我就不必使用adistor重新实现它stringdist。

再次感谢您的帮助。

我有一张这样的桌子：

等等

我想知道如何使用 Levenshtein 指标来比较我的“名称”列的不同行？

我已经知道我可以使用它来比较列：

但是行呢？

我有一个字符串列表，我想根据列文斯坦距离过滤掉过于相似的字符串。所以如果lev(list[0], list[10]) < 50; 然后del list[10]。有什么方法可以更有效地计算列表中每对字符串之间的距离吗？谢谢！！

上面相当愚蠢的代码计算时间太长了......

我试图让我的 Levenshtein 编辑距离算法工作，但由于某种原因，编辑的数量不正确。我看不出我的错误在哪里，我想知道是否有人看到我做错了什么。

输入

预期产出

我的输出

查找编辑距离

获取距离

更新链

我有两个排名 A 和 B 的列表，如下所示：

A：

乙：

我想使用相关方法比较这两个列表，以了解这些列表彼此之间的差异。目前我正在使用“Spearman”相关方法，但问题是每次运行它都会得到不同的结果。这是我的代码：

计算相关等级

任何人都可以帮助比较这两个列表吗？

我不明白如何根据这篇文章计算 levenshtein 矩阵中的值。我确实知道我们如何达到 3 的编辑距离。有人可以用外行的方式解释我们如何达到每个单元格中的每个值吗？