最小编辑距离及其C实现.docx

一、问题介绍：本题提出了一些关于将字符串x1.m转换成y1.n的操作。这些操作有复制、替代、删除、插入、互换和终止。这些操作所需的开销是不同的，但每个操作的开销都可以看是一个我们已经的常量，我们假设复制和替代这类操作的开销要比插入和删除这类操作的开销少。我们用x1.m来保存原字符串，数组下标用i表示，初始化为1；用y1.n来保存转换后的字符串，数组下标用j来表示，初始化为1；数组z用来存放中间结果，下标用j来表示，初始化为0。题目有两个待解决的问题：第一，给定两个序列x1.m和y1.n以及变换操作开销的集合。从x到y的编辑距离指的就是将x转换成y时的最小开销的操作序列。用动态规划的算法找出从x到y的编辑距离并输出最优操作序列。分析算法的时空复杂度。第二， 解释如何从给定的编辑操作集选择一个子集，从而把寻找总分最高的对齐结果的问题，转化为求序列编辑距离的问题的一个特例。二、算法分析：问题a解答：此题跟最长公共子序列的问题十分类似。因此，我仿照最长公共子序列问题的方法来求解这个问题。首先，定义了两个序列Xi=x1,2,.,m和Yj=y1,2,n，题目所求的就是将序列xi变为yj的编辑操作序列的最小开销。刻画最优解的结构：对于序列Xi(0im)和序列Yj(0jn)来说，定义ci,j为Xi转换成Yj的操作序列的最小开销。假定我们已经知道了最后一次执行的操作，此时分情况讨论问题的最优解结构。1. 最后一次操作为copy。此时，根据题目的定义可知xi=yj，我们待解决的问题就转化成了求将Xi-1转换为Yj-1的最小开销。将Xi-1转换为Yj-1的最优解一定包含在Xi转换为Yj的最优解内。用反证法证明：若存在从Xi-1到yj-1转换的更小的开销，那么用这个更小的开销来代替Xi-1转换为yj-1的最优解，这样就会得到一个更小的从Xi转换为Yj的开销，与已知的Xi转换为Yj的最优解矛盾，所以假设不成立。因此，当最后一次操作为copy时，可以定义ci,j=ci-1,j-1+cost(copy)。2. 最后一次操作为replace。此时，根据题目的定义可知xiyj。仿照上述分析，可以得到相同的最优子结构。此时ci,j=ci-1,j-1+cost(replace)。3. 最后一次操作为delete。根据题意，这时只是将xi从序列Xi中除去，对序列Yj没有任何影响，此时问题的最优子结构的形式为将Xi-1转换成Yj，于是可以得到ci,j=ci-1,j+cost(delete)。4. 最后一次操作为insert。根据题意，在进行插入操作时，序列Xi无任何变化，序列Yj添加一个字符，因此，这时候问题的最优子结构的形式为将Xi转换成为Yj-1，此时ci,j=ci,j-1+cost(insert)。5. 最后一次操作为twiddle。根据题意，互换操作是针对两个字符进行的，此时有yj=xi-1和yj-1=xi。在进行这个操作的时候，需要满足的条件是i,j2。在这种情况下，问题的最优子结构的形式为Xi-2转换为Yi-2，此时ci,j=ci-2,j-2+cost(twiddle)。6. 最后一次操作为kill。这种情况比较特殊，由于kill操作可以一次删除一个子串，对所有i=1.m-1, j=1.n，当X被检查到xi，Y被生成到yj的时候，用一个kill操作可以删除X中剩下的元素，用(n-i)个insert操作可以插入Y中尚未出现的全部元素。这样即可把X中的元素全部检查到，并且生成完整的Y。这种方式把X变成Y的总开销为cij+cost(kill)+(n-i) *cost(insert)。对所有cij求这个值，并且和上述忽略kill操作的前提下求出的编辑距离相比，取其中最小值，即求得编辑距离。考虑一些特殊的情况，当X和Y为空串时，c0,0=0。当Xi为一个非空序列Yj为空序列时，可以很明显的看出此时的操作全为delete，因此有ci,0=i*cost(delete)。当Xi为一个空序列Yj为非空序列时，可以很明显的看出此时的操作全为insert，因此有c0,j=j*cost(insert)算法的伪代码如下所示：Edit-Distance(x,y,m,n)for i0 to mdo ci,0=i*cost(delete)opi,0deletefor j0 to ndo c0,j=j*cost(insert)opj,0insertfor i1 to mdo for j1 to ndo ci,jif xi=yjthen ci,jci-1,j-1+cost(copy)opi,jcopyif xiyj and ci-1,j-1+cost(replace)ci,jthen ci,j= ci-1,j-1+cost(replace)opi,jreplaceif ci-1,j+cost(delete)ci,jthen ci,jci-1,j+cost(delete)opdeleteif ci,j-1+cost(insert)ci,jthen ci,jci,j-1+cost(insert)opinsertif i2 and j2 and xi-1=yj and xi=yj-1 and ci-2,j-2+cost(twiddle)ci,jthen ci,j= ci-2,j-2+cost(twiddle)optwiddlefor i0 to m-1do if ci,n+cost(kill)cm,nthen cm,nci,n+cost(kill)opm,nkillireturn c and op算法的时间复杂度分析：该算法是对一个(m+1)(n+1)的表格进行填写的过程，填写每一个格cij花费的开销，只是根据ci-1j, cij-1, ci-1j-1, ci-2j-1进行简单的加减运算，得到五个数字，选择其中最小的一个。所以该算法的时间复杂度为O(mn)。最后构造问题的最优解，编辑序列输出的算法伪代码如下所示：Out-Operation(op,i,j)if i=0 and j=0then returnif opi,j = copy or opi,j = replacethen ii-1jj-1else if opi,j=deletethen i=i-1j=jelse if opi,j = insertthen i=ij=j-1else if opi,j=twiddlethen i=i-2j=j-2elselet opi,j=killki=kj=jOut-Operation(op,i,j)print opi,jC+的源码如下（没有实现kill，个人认为没有使用价值）：cpp:collapse:showcolumns+ expand sourceview plaincopy102030405060708090100110120130140150问题b解答：在DNA对齐问题中，最高得分的对齐方法可以通过选择下面四个操作并相应赋给开销，来转换成一个编辑距