如何找到不完美的子串？

Question

我有一串长度相同的子字符串，我想在一个大字符串中找到它们的位置。不过，比较棘手的是，我还需要找到那些与目标子字符串有一定数量不匹配的子字符串（不匹配的数量也是给定的）。我原本想用正则表达式来解决这个问题，但找不到方法。更新一下：我使用的是Python 2.7。

举个例子： 输入字符串是 s = 'ATGTCGATCGATGCTAGCTATAGATAAAA'，输入的子字符串是 s0 = 'ATG'，允许的不匹配数量是 n = 1。我想要的结果是返回一个可迭代的对象，比如一个列表，里面是位置：[0,7,19,23,6]，这些位置对应的是 'ATG'（出现两次）、'ATA'（出现两次）、'ATC'（出现一次），因为其他不匹配的3个字符组合在这个字符串中没有出现。

Answer 1

根据我对你问题的理解：

类型 1

def diff_count(s1, s2):
    count = 0
    for i in range(len(s1)):
        if s1[i] != s2[i]:
            count += 1
    return count

def diff_filter1(s1, s2, max_count):
    return diff_count(s1, s2) < max_count

类型 2（更高效）

def diff_filter2(s1, s2, max_count):
    count = 0
    i = 0
    while i < len(s1) and count < max_count:
        if s1[i] != s2[i]:
            count += 1
        i += 1
    return count < max_count

还有计算 Levenshtein 距离 的 Python 代码

def LevenshteinDistance(s, t):
    len_s = len(s)- 1
    len_t = len(t)- 1
    if(len_s == 0): return len_t
    if(len_t == 0): return len_s
    if(s[len_s-1] == t[len_t-1]): cost = 0
    else:                         cost = 1
    return min(LevenshteinDistance(s[0:len_s-1], t) + 1,
               LevenshteinDistance(s, t[0:len_t-1]) + 1,
               LevenshteinDistance(s[0:len_s-1], t[0:len_t-1]) + cost)

Answer 2

你有没有考虑过使用Levenshtein距离算法来帮助你呢？这个算法是用来判断两个字符串之间有多相似的。

下面是一个简单的实现方法：

1. 从0开始，到haystack_str的长度减去needle_str的长度为止，逐个检查
2. 把haystack_str中从位置i开始的部分，长度为needle_str的长度，称为potential_match
3. 计算potential_match和needle_str之间的Levenshtein距离
4. 如果距离是0，那就说明完全匹配
5. 如果距离小于某个设定的阈值，那就是不完全匹配，但也很接近
6. 否则，就继续检查下一个i

Answer 3

新的 regex 模块支持模糊匹配。举个例子，

(?:foo){s<=2} 

这个匹配“foo”，允许有2个字符的替换。

还要注意文档中的这段说明：

默认情况下，模糊匹配会寻找第一个符合条件的匹配项。使用 ENHANCEMATCH 标志会让它尝试改善找到的匹配结果（也就是减少错误的数量）。

而 BESTMATCH 标志则会让它寻找最佳匹配。

示例：

>>> regex.findall(r'(?:foo){s<=2}', 'xxfoo')
['xfo']
>>> regex.findall(r'(?:foo){s<=2}', 'xxfoo', regex.BESTMATCH)
['foo']