用Hamming距离搜索较大字符串中是否存在子串

Question

我有两个文件，file1和file2 文件1包含完整字符串“abcdef”的所有4-mer、5-mer和6-mer子字符串

file2有更长的字符串，比如

ddghtgabcdtttfwe公司

DDGHTGADTTFWE公司

hhttaddsbcdeggd公司

等等，我想看看文件2中的字符串是否与文件1中的字符串匹配，从而允许一些不匹配（最大汉明距离2）。例如 ddghtgabcdtttfwe和ddghtgabcdatttfwe分别是子串abcd和abcd，abcde的命中数。你能推荐一个用python做这件事的好方法吗

Answer 1

部分解决方案：

def hamming(s1,s2):
    return len([(c1,c2) for (c1,c2) in zip(s1,s2) if c1 != c2])

然后：

def almostIn(s1,s2):
    n = len(s1)
    for s in (s2[i:i+n] for i in range(1 + len(s2)-n)):
        if hamming(s1,s) <= 2: return True
    return False

如果s1出现在s2中且Hamming距离<；=2，则后面的函数将返回True。对相同的字符进行一定量的重新扫描，因此这可能不是最佳的，但对于您预期的应用程序来说可能已经足够了。你知道吗