python - 编辑距 ionic 串

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

你可以看看 regex module支持模糊匹配:

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

因为你正在寻找的是等长的字符串，你也可以做一个 Hamming distance这可能比相同两个字符串上的 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'