python - 如何找到与其他 2 个字符串相似的字符串(就 Levenshtein 距离而言)?
问题描述
假设我有 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
and diff_lev <= 1
)。
解决方案
恐怕你所要求的是不可能的,因为问题是 NP 难的。我将尝试概述为什么会出现这种情况的一些关键概念,但我鼓励您查看Center Strings和Steiner Strings。
假设您有一组称为 S 的字符串。最佳 Steiner 字符串是一个字符串,它使 S 中每个字符串与其自身的距离之和最小化(也称为一致性误差)。这对应于您调用的第一个属性sum_lev
。最佳 Steiner 字符串通常是模棱两可的,并且不是原始集合 S 的一部分(但不一定是)。
您面临的问题是没有有效的方法来计算最佳施泰纳字符串。即使您设法限制您的搜索空间,您仍然会有指数级的候选人。因此问题是 NP 难的。
可以证明,S 总是包含一个字符串,它是最优 Steiner 字符串的合理近似值。因此,即使您只关注两个属性中的第一个,最好的办法就是简单地选择一个原始字符串。由于您显然只处理两个字符串,因此选择哪一个并不重要。
TL;博士
总而言之,您正在处理一个 NP-hard 问题,该问题无法有效解决,只能近似。如果您只处理两个字符串,则您要查找的字符串可以由给定字符串之一来近似。很抱歉,这可能不是您希望的答案,但希望它仍然有些帮助。
推荐阅读
- apache-flink - zetcd 滚动重启导致 Flink 进程终止
- html - 刀片视图中未呈现自定义 CSS 文件
- direnv - Direnv 不允许我允许
- python - 使用另一个列表搜索列表,但在第一次匹配时停止
- javascript - 使用 Netlify lambda 函数从 GatsbyJS 站点发送电子邮件
- python - Flask 站点与 SQlite 一起工作,但在连接到 Postgres 时中断
- python - 如何在不跳过的情况下在新行上打印?
- javascript - 在Javascript中的每个新字母之前拆分字符串
- python - pyInstaller 找不到数据文件
- docker-compose - WSO2 APIM 3 docker 持久化 API 数据