如何寻找与两个字符串相似的字符串（以Levenshtein距离为准）？

Question

假设我有两个非常相似的字符串。 我想找到另一个字符串，它在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).

- ZFTurbo

---

s1[:len(s1) // 2] + s2[len(s2) // 2:]是否能够近似满足该属性，还是您需要一个可证明的最小值？ - Joe

我认为在一般情况下，它可能会远离期望的结果。但我不确定。 - ZFTurbo

Answer 1

很抱歉，您所要求的内容并不可能实现，因为这是一个NP难问题。我将尝试概述一些关键概念，解释为什么会出现这种情况，但我建议您查找“中心字符串”和“斯坦纳字符串”。

假设您有一个称为S的字符串集。最优斯坦纳字符串是一串字符串，它使S中每个字符串到自身的距离之和最小化（也称为“一致性误差”）。这对应于您称之为sum_lev的第一个属性。最佳斯坦纳字符串通常是模棱两可的，而且不属于原始集合S（但可以是）。

您面临的问题是没有有效的方式来计算最优斯坦纳字符串。即使您设法限制搜索空间，候选人数仍然呈指数级增长。因此，该问题是NP难的。

可以证明，S始终包含一个合理近似于最优斯坦纳字符串的字符串。因此，即使您只关注您的两个属性中的第一个属性，您最好的选择就是简单选择其中一个原始字符串。由于您显然只涉及两个字符串，因此选择哪个字符串应该无关紧要。

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

- Matze

Answer 2

假设

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

实例

让我们考虑您提供的示例：Levenshtein.distance(s1='aaabbbccc', s2='abacbbbccde')。

这意味着我们正在问这些字符串之间有多少个操作（将一个字符串变异成另一个字符串需要多少成本）。

Levenshtein矩阵

现在我们假设s1是起点，让我们看看算法给我们什么。
我们可以计算s1和s2之间的距离，它返回整数值4。
它来自于计算出的Levenshtein矩阵的最后一个值，如下图所示：

遍历Levennshtein矩阵

正如我们所看到的，有些位置值会上升，有些位置值会保持不变。
如果我们从左上角开始遍历矩阵，我们应该按以下方式阅读它：

• 向下表示：将字符添加到s1字符串中
• 向右表示：从s1字符串中删除字符
• 向右下方对角线表示：替换字符

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

矩阵中距离的变化

让我们看看当我们更改s1中的最后一个值时，矩阵如何改变。
正如我们所看到的，cxd的前一个交点已经改变为dxd，现在这个地方的成本不再上升了，这就导致这些字符串之间的距离变小了。
我们看到的是，s1中的小改变将导致距离变化为1，并且如果我们将原始的s1与修改后的字符串进行比较：

从Levenshtein距离的角度来看，它们非常相近。

结论

可能存在一种算法可以生成很多与s1和s2相似的字符串。
它会遍历生成的矩阵并更改一个字符串中的单个字符来生成下一个解决方案。
我们应该考虑对原始矩阵进行多次更改。然后对于每个新解决方案，我们可能希望计算新的Levenshtein矩阵，并将其用作下一个源以生成解决方案。
而且我们不应该只考虑降低这些值，因为那只会生成部分潜在的解决方案。

有一件事情很重要需要考虑。在Levenshtein距离的术语中，比较字符a与b还是a与c并不重要，重要的是“这些是相同的字符吗？”如果不是，我们就不关心它的值。

- Iluvatar

Answer 3

对@Matze的回答进行一些扩展 - 当你需要解决NP难问题时，你可以使用遗传算法来找到某些解决方案，这些方案可能比在有限时间内仅仅选取其中一个字符串要好（不能保证它是最好的或甚至比原始字符串中的某个更好）

- konserw

Answer 4

这不是一个解决方案，而是一个起点；一种立即的改进是在函数eq_len_strings上，将字符串等同于右边;此外，您可以从s1中取子字符串到s2来创建您的第一个中间字符串（因为这有助于减少Levenshtein距离），然后只需使用您字母表中的任何字符填充_作为search_mid_string所做的那样。

另一个改进是避免（与我所做的相反）填充所有空白（_），也许将空字符串添加到您的字母表中或考虑两个字符串之间的长度差异。

import Levenshtein

def eq_len_strings(s1, s2):
    if len(s1) < len(s2):
        s1 = s1.ljust(len(s1)+len(s2)-len(s1), '_')
    elif len(s1) > len(s2):
        s2 = s2.ljust(len(s2)+len(s1)-len(s2), '_')
    return s1, s2

def keep_eq_chars(s1, s2):
    s = ''
    for char1, char2 in zip(s1, s2):
        if char1 == '_' or char2 == '_' or char1 != char2:
            s += '_'
        else:
            s += char1
    return s

def search_mid_string(s1, s2):
    alph = set(list(s1+s2))
    s1e, s2e = eq_len_strings(s1, s2)
    # start string
    s_mid = list(keep_eq_chars(s1e, s2e))
    
    alternate = 0
    for i in range(len(s_mid)):
        char1 = s1[i] if i < len(s1)-1 else '_'
        char2 = s2[i] if i < len(s2)-1 else '_'
        if s_mid[i] == '_':
            if alternate == 0 and char1 != '_':
                s_mid[i] = char1
                alternate = 1
            elif alternate == 1 and char2 != '_':
                s_mid[i] = char2
                alternate = 0
            else:
                s_mid[i] = ''
    s1_to_s2_dist = Levenshtein.distance(s1, s2)
    s1_to_mid_dist = Levenshtein.distance(s1, ''.join(s_mid))
    s2_to_mid_dist = Levenshtein.distance(s2, ''.join(s_mid))
    ans = {
        's1_to_s2_dist': s1_to_s2_dist,
        's1_to_mid_dist': s1_to_mid_dist,
        's2_to_mid_dist': s2_to_mid_dist,
        's_mid': ''.join(s_mid)
    }
    return ans

根据给定的字符串:

s1 = 'aaabbbccc'
s2 = 'abacbbbccde'

search_mid_string(s1, s2)

// Output
>{'s1_to_s2_dist': 4,
> 's1_to_mid_dist': 2,
> 's2_to_mid_dist': 3,
> 's_mid': 'aaacbbcccd'}

- Memristor

Answer 5

这不是一个解决方案，而是一种寻找接近两个字符串的字符串的基本思路：

import Levenshtein

s1 = 'aaabbbccc'
s2 = 'abacbbbccde'

dist = Levenshtein.distance(s1, s2)
print(dist)

def get_avg_string(s1, s2):
    s2, s1 = sorted([s1, s2], key=len)
    s3 = ''.join(a if i & 1 else b for i, (a, b) in enumerate(zip(s1, s2)))
    return s3

mid_str = get_avg_string(s1, s2)

print(Levenshtein.distance(s1, mid_str))
print(Levenshtein.distance(s2, mid_str))

输出：

4
2
3

---

解释函数功能。

def get_avg_string(s1, s2):
    s2, s1 = sorted([s1, s2], key=len)
    s3 = ''.join(a if i & 1 else b for i, (a, b) in enumerate(zip(s1, s2)))
    return s3

循环

for i, (a, b) in enumerate(zip(s1, s2))

这段代码将使用zip()方法并结合enumerate()方法，同时迭代字符串s1和s2及其索引。

条件为

a if i & 1 else b

如果索引是奇数（如果& 1返回1而不是0），则从s1和a中获取部分，否则从s2和b中获取部分。

我使用了

s2, s1 = sorted([s1, s2], key=len)

使下面的行从最长字符串中获取第一个字符。

- Ann Zen

Answer 6

这里是返回s1和s2之间所有字符串列表的代码。因此，您可以选择其中间的一个。

def get_all_avg_strings(s1, s2):
    import Levenshtein
    dist = Levenshtein.distance(s1, s2)
    s1_new = s1
    intermediate_strings = [s1_new]
    for i in range(dist):
        e = Levenshtein.editops(s1_new, s2)
        s1_new = Levenshtein.apply_edit(e[:1], s1_new, s2)
        intermediate_strings.append(s1_new)
    check = Levenshtein.distance(s2, s1_new)
    if check != 0:
        print('Some error here!')
        exit()
    return intermediate_strings[1:-1]

然后您可以创建所请求的函数，如下：

def get_avg_string(s1, s2):
    avg = get_all_avg_strings(s1, s2)
    if len(avg) > 0:
        s = avg[len(avg) // 2]
    else:
        s = s1
    return s

- ZFTurbo