莱文斯坦距离子串

Question

有没有一种好方法可以使用 Levenstein 距离将一个特定字符串与第二个较长字符串中的任何区域进行匹配？

例子：

str1='aaaaa'
str2='bbbbbbaabaabbbb'

if str1 in str2 with a distance < 2:
    return True

因此，在上面的示例中，字符串 2 的一部分是aabaa，distance(str1,str2) < 2因此语句应该返回True。

我能想到的唯一方法是一次从 str2 中取出 5 个字符，与 str1 进行比较，然后在 str2 中重复此操作。不幸的是，这看起来效率很低，我需要以这种方式处理大量数据。

Answer 1

您可能会看一下支持模糊匹配的正则表达式模块：

>>> import regex
>>> regex.search("(aaaaa){s<2}", 'bbbbbbaabaabbbb')
<regex.Match object; span=(6, 11), match='aabaa', fuzzy_counts=(1, 0, 0)>

由于您正在寻找相同长度的字符串，因此您还可以在相同的两个字符串上执行汉明距离，这可能比 Levenstein 距离快得多：

str1='aaaaa'
str2='bbbbbbaabaabbbb'
for s in [str2[i:i+len(str1)] for i in range(0,len(str2)-len(str1)+1)]:
    if sum(a!=b for a,b in zip(str1,s))<2:
        print s    # prints 'aabaa'