Levenstein距离子串

Question

有没有一个很好的方法可以使用levenstein距离将一个特定的字符串匹配到另一个较长字符串内的任何区域？在

示例：

str1='aaaaa'
str2='bbbbbbaabaabbbb'

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

因此在上面的示例中，字符串2的部分是aabaa和{}，因此该语句应该返回True。在

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

Answer 1

诀窍是生成所有长度适当的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 2

您可以看看支持模糊匹配的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距离快得多：

^{pr2}$

Answer 3

诀窍通常是使用插入（表示较短）或删除（表示较长）成本。你也可以考虑改用达默劳·列文什坦。 https://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance