查找与目标字符串距离最小的"N Gram"子字符串

Question

我在寻找一个算法，最好是用Python写的，能够帮助我找到现有字符串中与目标字符串最接近的子字符串，这些子字符串的长度是N个字符。

假设目标字符串是4个字符长，比如：

targetString -> '1111'

假设这是我手头有的字符串（我会从中生成子字符串以进行“最佳对齐”匹配）：

nonEmptySubStrings -> ['110101']

上面字符串中长度为4的子字符串有：

nGramsSubStrings -> ['0101', '1010', '1101']

我想写一个“魔法函数”，它能够选择与目标字符串最接近的字符串：

someMagicFunction -> ['1101']

还有一些其他的例子：

nonEmptySubStrings -> ['101011']
nGramsSubStrings -> ['0101', '1010', '1011']

someMagicFunction -> ['1011']

nonEmptySubStrings -> ['10101']
nGramsSubStrings -> ['0101', '1010']

someMagicFunction -> ['0101', '1010']

这个“魔法函数”是一个众所周知的子字符串问题吗？

我真的想找到最少的修改次数，使得非空子字符串中能够包含目标字符串作为子字符串。

Answer 1

在之前关于基因匹配的讨论中，我写了一个pyparsing的例子，实现了一个叫做CloseMatch的类。一般来说，pyparsing的表达式会返回一个包含匹配字符串和任何命名结果的结构，但CloseMatch返回的是一个包含匹配字符串和一个不匹配位置列表的二元组。下面是CloseMatch的使用方法：

searchseq = CloseMatch("TTAAATCTAGAAGAT", 3)
for g in genedata: 
    print "%s (%d)" % (g.id, g.genelen) 
    print "-"*24 
    for t,startLoc,endLoc in searchseq.scanString(g.gene): 
        matched, mismatches = t[0] 
        print "MATCH:", searchseq.sequence 
        print "FOUND:", matched 
        if mismatches: 
            print "      ", ''.join(' ' if i not in mismatches else '*'  
                            for i,c in enumerate(searchseq.sequence)) 
        else: 
            print "<exact match>" 
        print "at location", startLoc 

这里是一个部分匹配的示例输出：

organism=Toxoplasma_gondii_RH (258)
------------------------
MATCH: TTAAATCTAGAAGAT
FOUND: TTAAATTTAGGAGCT
             *   *  * 
at location 195

需要注意的是，这个类不会找到重叠的匹配。虽然也可以做到这一点，但需要用稍微不同的方法来实现scanString（我会在下一个pyparsing版本中包含这个功能）。

Answer 2

我觉得你需要了解一下编辑距离。彼得·诺维格的拼写纠正器就是一个用Python实现的例子。这里有一个莱文斯坦距离的实现。

另外，你可以看看这个问题。

补充一下：在生物信息学中，这种情况非常常见。比如FASTA和BLAST。生物信息学中有很多种这种算法。你可以查看序列比对来了解各种方法。

Answer 3

根据提问者的评论，这里是他们想要的结果

import functools

def edit_distance(str1, str2): 
    #implement it here

f = functools.operator(edit_distance, target_string)
return min(f(s) for s in slices(string_))   # use slices from below

这个方法会返回任何子字符串与目标字符串之间的最小编辑距离。它不会告诉你具体是哪个字符串或者它的索引。不过，这个方法可以很容易地修改来实现这些功能。

---

一种简单的方法，虽然可能是最好的方法，就是

import functools

def diff(str1, str2):
    # However you test the distance gets defined here. e.g. Hamming distance, 
    # Levenshtein distance, etc.


def slices(string_, L):
    for i in xrange(len(string_) - L + 1)):
        yield string_[i:i+L]

best_match = min(slices(string_), key=functools.partial(diff, target_string))

不过，这个方法不会返回子字符串出现的索引。当然，你在提问时并没有说明你需要这个信息；)

如果你想要更好的结果，那就得看你是怎么计算距离的，基本上就是要避免检查一些子字符串，因为你可以推测出要想得到比现在更好的匹配，至少需要改变x个字符。到那时，你不如直接跳过x个字符，直接改变x个字符。