dsi*_*cha 7 string algorithm performance
给定一个长字符串L和一个较短的字符串S(约束是L.length必须> = S.length),我想找到长度等于.length的S任何子字符串之间的最小汉明距离.我们为此调用函数.例如,LSminHamming()
minHamming(ABCDEFGHIJ, CDEFGG) == 1.
minHamming(ABCDEFGHIJ, BCDGHI) == 3.
以明显的方式执行此操作(枚举L的每个子字符串)需要O(S.length*L.length)时间.在次线性时间有没有聪明的方法可以做到这一点？我L用几个不同的S字符串搜索相同的字符串,因此L可以接受一次复杂的预处理.
编辑:修改过的Boyer-Moore是个好主意,除了我的字母表只有4个字母(DNA).
j_r*_*ker 15
也许令人惊讶的是,这个确切的问题可以使用快速傅立叶变换(FFT)在O(| A | nlog n)时间内解决,其中n是较大序列的长度L并且|A|是字母表的大小.
以下是Donald Benson撰写的一篇免费的PDF文件,描述了它的工作原理:
总结:转换每个串S和L为几个指示器矢量(每个字符之一,在DNA的情况下SO 4),然后卷积对应向量,以确定每个可能的对准匹配计数.诀窍是在"时间"域,其通常需要O(N ^ 2)时间卷积,可以在"频率"域,其只需要O(n)的时间使用乘法来实现,加上所需的时间来转换在域之间再回来.使用FFT,每次转换只需要O(nlog n)时间,因此总时间复杂度为O(| A | nlog n).为了获得最大速度,使用有限域 FFT,其仅需要整数运算.
注意:对于任意的S和L这个算法显然是在简单的O(MN)算法作为一个巨大的性能取胜|S|和|L|变大,但OTOH如果S是一般短于log|L|(例如查询一个小序列的大型数据库时),那么显然这种方法没有提供加速.
更新21/7/2009:更新提及时间复杂度也线性地取决于字母表的大小,因为必须为字母表中的每个字符使用单独的一对指示符向量.