python - 如何找到与其他 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。我将尝试概述为什么会出现这种情况的一些关键概念，但我鼓励您查找中心弦和斯坦纳弦。
假设您有一组称为 S 的字符串。最佳 Steiner 字符串是一个字符串，它使 S 中每个字符串与其自身的距离之和最小(也称为共识错误)。这对应于您称为 sum_lev 的第一个属性.最佳 Steiner String 通常是不明确的，并且不是原始集合 S 的一部分(但不一定是)。
您面临的问题是没有有效的方法来计算最佳 Steiner 弦。即使您设法限制您的搜索空间，您仍然会有指数数量的候选人。因此，问题是 NP 难的。
可以证明 S 总是包含一个字符串，它是最优 Steiner 字符串的合理近似。因此，即使您只关注您的两个属性中的第一个，您拥有的最佳镜头也是简单地选择一个原始字符串。由于您显然只处理两个字符串，因此选择哪一个都无关紧要。
TL;博士
总而言之，您正在处理一个无法有效解决而只能近似解决的 NP 难题。如果您只处理两个字符串，则可以使用给定字符串之一来近似您要查找的字符串。很抱歉，这可能不是您希望的答案，但希望它仍然有些帮助。