一尘不染

找到任何子串的最小汉明距离的最快方法?

algorithm

给定一个长字符串L和一个短字符串S(约束是L.length必须> =
S.length),我想找到与长度等于.length的S任何子字符串之间的最小汉明距离。让我们为此调用函数。例如,L``S``minHamming()

minHamming(ABCDEFGHIJ, CDEFGG) == 1

minHamming(ABCDEFGHIJ, BCDGHI) == 3

这样做很明显(枚举L的每个子串)需要O(S.length * L.length)时间。在亚线性时间内,有什么聪明的方法可以做到这一点吗?我L用几个不同的S字符串搜索相同的内容,因此L一次进行一些复杂的预处理是可以接受的。

编辑:修改过的Boyer-Moore是一个好主意,除了我的字母只有4个字母(DNA)。


阅读 290

收藏
2020-07-28

共1个答案

一尘不染

也许令人惊讶的是,使用快速傅立叶变换(FFT)可以仅 在O(| A | nlog n)时间内
解决这个确切的问题,其中n是较大序列的长度,L并且|A|是字母的大小。

这是唐纳德·本森(Donald Benson)免费提供的一份PDF文件,描述了其工作原理:

总结: 转换每个串SL为几个 指示器矢量 (每个字符之一,在DNA的情况下SO
4),然后进行卷积对应矢量,以确定每个可能的对准匹配计数。诀窍在于,通常可以使用O(n
^
2)时间的“时间”域中的卷积,而仅需O(n)时间加上转换所需的时间即可在“频率”域中使用乘法来实现域之间并再次返回。使用FFT,每次转换仅花费O(nlog
n)时间,因此总的时间复杂度为O(| A | nlog n)。为了达到最高速度,使用了 有限域 FFT,仅需整数运算即可。

注意: 对于任意算法SL此算法显然比直接O(mn)算法具有巨大的性能优势,|S|并且|L|变得很大,但是OTOH
S通常短于log|L|(例如,当查询具有较小序列的大DB时),那么显然这种方法没有提供加速。

2009年7月21日更新 :更新以提及时间复杂度还线性地取决于字母的大小,因为字母中的每个字符都必须使用一对单独的指示符向量。

2020-07-28