编辑距离子串

Question

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

示例：

str1='aaaaa'
str2='bbbbbbaabaabbbb'

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

所以在上面的例子中字符串 2 的部分是 aabaa 和 distance(str1,str2) < 2 所以语句应该 return True.

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

Answer 1

技巧通常是使用插入（较短）或删除（较长）成本。您可能还想考虑改用 Damerau-Levenshtein。 https://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance

Answer 2

诀窍是生成 b 的所有适当长度的子串，然后比较每一个。

def lev_dist(a,b):
    length_cost = abs(len(a) - len(b))
    diff_cost = sum(1 for (aa, bb) in zip(a,b) if aa != bb)
    return diff_cost + length_cost

def all_substr_of_length(n, s):
    if n > len(s):
        return [s]
    else:
        return [s[i:i+n] for i in range(0, len(s)-n+1)]

def lev_substr(a, b):
    """Gives minimum lev distance of all substrings of b and
    the single string a.
    """

    return min(lev_dist(a, bb) for bb in all_substr_of_length(len(a), b))

if lev_substr(str1, str2) < 2:
    # it works!

Answer 3

你可以看看支持模糊匹配的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'

编辑距离子串

Levenstein distance substring

python

levenshtein-distance