如何找到与其他 2 个字符串相似的字符串（就 Levenshtein 距离而言）？

Question

假设我有 2 个非常相似的字符串。我想找到在 Levenshtein 距离方面接近 s1 和 s2 的其他字符串。

import Levenshtein
s1 = 'aaabbbccc'
s2 = 'abacbbbccde'
dist = Levenshtein.distance(s1, s2)
print(dist)
mid_str = get_avg_string(s1, s2)

什么可以有效实现功能：

def get_avg_string(s1, s2):
    return ''

我需要这个变量：

sum_lev = Levenshtein.distance(s1, mid_str) + Levenshtein.distance(s2, mid_str)
diff_lev = abs(Levenshtein.distance(s1, mid_str) - Levenshtein.distance(s2, mid_str)

最小（我认为sum_lev将等于dist和diff_lev <= 1）。

Answer 1

恐怕你所要求的是不可能的，因为问题是 NP-hard。我将尝试概述为什么会出现这种情况的一些关键概念，但我鼓励您查找Center Strings和Steiner Strings。

假设您有一组称为 S 的字符串。最佳 Steiner 字符串是一个字符串，它使 S 中每个字符串与其自身的距离之和最小（也称为共识错误）。这对应于您调用的第一个属性sum_lev。最佳 Steiner String 通常是不明确的，并且不是原始集合 S 的一部分（但不一定是）。

您面临的问题是没有有效的方法来计算最佳 Steiner 弦。即使您设法限制您的搜索空间，您仍然会有指数数量的候选人。因此，问题是 NP 难的。

可以证明 S 总是包含一个字符串，它是最优 Steiner 字符串的合理近似。因此，即使您只关注您的两个属性中的第一个，您拥有的最佳镜头也是简单地选择一个原始字符串。由于您显然只处理两个字符串，因此选择哪一个都无关紧要。

TL; 博士

总而言之，您正在处理一个无法有效解决而只能近似解决的 NP 难题。如果您只处理两个字符串，则您要查找的字符串可以用给定字符串之一来近似。很抱歉，这可能不是您希望的答案，但希望它仍然有些帮助。

Answer 2

假设

因此，首先让我们假设string1（我们称之为s1）是转换之前和string2（我们称之为s2）转换之后。这样我们就可以轻松分离添加和删除字符操作。

这个例子

让我们考虑一下您给出的例子。 Levenshtein.distance(s1='aaabbbccc', s2='abacbbbccde') 这意味着我们要问的问题是有多少操作将这些字符串分开（将一个字符串转变为另一个字符串需要多少成本）。

编辑矩阵

现在我们假设s1是起点，让我们看看算法给我们带来了什么。我们可以计算和
之间的距离，它会输出整数值 It 来自计算的 Levenshtein 矩阵的最后一个值，如下所示：s1s24

游走编辑矩阵

正如我们所看到的，有些地方的价值会上升，有些地方则保持不变。
如果我们从左上角遍历矩阵，我们应该这样读：

• 向下表示：向s1字符串添加一个字符
• 向右走意味着：从s1字符串中删除一个字符
• 向右对角线走的意思是：替换字符

我们的目标是到达右下角，结果值是与之相关的成本（或距离）。

矩阵的距离变化

让我们看看当我们改变最后一个值时矩阵将如何改变它的值s1 正如我们所看到的，之前cx的交集d更改为dx d，现在这个地方的成本没有增加，这导致这些字符串之间的距离更小。
我们看到的是， 的微小变化s1将导致 的距离变化1，并且如果我们将原始值s1与修改后的值进行比较：

就编辑距离而言，它看起来非常接近。

结论

可能有一种算法可以生成大量类似于s1和 的字符串s2。
它将遍历生成的矩阵并更改字符串中的单个字符以生成下一个解决方案。
我们应该考虑对原始矩阵进行多次更改。然后，对于每个新的解决方案，我们可能想要计算新的 Levenshtein 矩阵，并将其用作生成解决方案的下一个来源。
我们永远不应该考虑只降低这些值，这只会产生部分潜在的解决方案。

需要考虑的一件事很重要。就编辑距离而言，我们是否将字符进行比较并不重要，a重要b的a是c“这些是相同的字符吗？” 如果不是，我们不关心它的价值。