您可以使用带有亚线性间隙成本的 两两比对来实现这一点,对于长度分别为 n 和 m 的两个字符串,时间复杂度为 O(nm)。
首先声明:没有一种方法可以找到一个可证明的最小补丁(以使用的位或字节计)。那是因为如果有这样的方法,那么可以使用计算它的函数 shortest_patch(x,y)
来通过使用shortest_patch('',s)
调用它来找到任何给定字符串s
的可证明最小压缩,而科尔莫夫复杂性告诉我们,给定字符串的最短可能压缩在形式上是不可计算的。但是,如果编辑倾向于在空间中聚集,就像在这里看起来一样,那么肯定可以找到比使用传统的Levenshtein距离算法产生的更小的补丁。
编辑脚本
在计算机科学中,补丁通常称为“编辑脚本”。找到将一个字符串x
转换为另一个字符串y
的最小(以插入和删除次数计算)编辑脚本相当于在最优两两比对中找到每一对相等字符的值为0,每一对不相等字符的值为-inf,并且每个位置上,在一个字符与-
间隙字符对齐的情况下,值为-1。比对很容易可视化:
st--ing st-i-ng
stro-ng str-ong
这是两个字符串 sting
和 strong
的最优对齐方式,根据该模型,每个对齐的成本为-3。如果将不相等字符对的值设为-1而不是-inf,则可以得到一个成本等于Levenshtein距离的对齐(插入数量加上删除数量再加上替换数量):
st-ing sti-ng
strong strong
这是新模型下的两个最佳对齐方式,每个对齐方式的成本为-2。
为了看到它们如何与编辑脚本相对应,我们可以将顶部字符串视为“原始”字符串,将底部字符串视为“目标”字符串。包含不相等字符对的列对应于替换,顶行包含-
的列对应于字符插入,底行包含-
的列对应于字符删除。您可以通过使用“指令”(C)复制,(D)删除,(I)插入和(S)替换来从对齐中创建编辑脚本。每个指令后面跟着一个数字,表示要从对齐中消耗的列数,在I和S的情况下,还有要插入或替换的相应数量的字符。例如,前面2个对齐的编辑脚本为
C2, I1"r", S1"o", C2 and C2, S1"r", I1"o", C2
增加成串
现在,如果我们有像 mississippi
和 tip
这样的字符串,我们发现这两个对齐方式:
mississippi
------tip--
mississippi
t---i----p-
两者得分相同,都是-9:它们都需要相同数量的插入、删除和替换。但我们更喜欢上面那个,因为它的编辑脚本可以更简洁地描述:
D6,S1“t”,C2,D2
。第二个的编辑脚本将是
S1“t”,D3,C1,D4,C1,D1
。
为了让对齐算法也“偏爱”第一个对齐,我们可以调整间隙成本,使“开始间隙块”的成本高于“继续现有间隙块”。如果我们使包含间隙的列成本为-2而不是-1,当前一列不包含间隙时,则我们实际上正在惩罚连续间隙块的数量(因为每个连续间隙块显然必须有一个第一个位置)。在这种模型下,上面的第一个对齐现在成本为-11,因为它包含两个连续的间隙块。第二个对齐现在成本为-12,因为它包含三个连续的间隙块。换句话说,算法现在更喜欢第一个对齐。
这种模型,在其中每个包含间隙的对齐位置的成本为g,而任何连续的间隙列中的第一个位置的成本为g + s,称为仿射间隙成本模型,并且Gotoh在1982年提出了一个O(nm)算法:
http://www.genome.ist.i.kyoto-u.ac.jp/~aln_user/archive/JMB82.pdf。增加间隙开放成本s将导致对齐片段聚集在一起。您可以尝试使用各种成本参数,直到获得看起来合适且足够小的对齐(对应于补丁)。