|
Diff 算法
Diff 在Linux下非常有用, 最近在对定向蜘蛛的研究中, 发现网页的信息大部分在Diff部分, 所以考虑了Diff的原理.1. Unix DiffLinux Diff 的基本原理在文 [ Dynamic Programming | http://www.sbc.su.se/~pjk/molbioinfo2001/dynprog/dynamic.html ] 中介绍的很详细了.如果一个文件有n行, 则需要对一个n*n的矩阵进行计算以得到最佳匹配.2. 贪心算法在[ Windiff原理初探 | http://www.2maomao.com/blog/how-windiff-works-continued-1/ ]中看到一个贪心算法, 感觉在某种情况下还是比较适合的,但是有些情况还是存在一些问题.贪心算法的基本思路是: 从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。首先还是简化问题：每个行根据内容映射到一个整型值, 这就将整个问题简化为整形数组的比较，姑且称之为Anew和Aold。程序处理流程简述：while (还没到头){ while (还可以继续找，还可以更贪心） { 找到下一个匹配的（依次对ANew的元素，查找其在AOld中的位置） if (找的到) 计算其贪心值，如果当前更贪则用这个匹配做当前最佳匹配 else break; }}输出剩余的未匹配节点。其中“还可以更贪心”是如何判定的呢？首先定义左臂（leftHand，Anew里面新匹配位置距上一次被采用的匹配的距离），右臂（rightHand，Aold里面新匹配位置距上一次被采用的匹配的距离）。要找一个目标，在这里我给定的目标是左右平衡情况下的最近匹配。比如一个匹配左臂1，右臂10，另一个匹配是左臂3，右臂3，这时候倾向于选择后一个匹配。为了公式化和便于计算，我采用一个简单的具有这个逻辑的函数：leftHand*leftHand + rightHand*rightHand的值（贪心值）最小。定义了这个目标以后，你会发现只要左臂过长，lefthand自身的平方超过上个候选匹配的贪心值，则可以停止往下计算了。然后这个循环继续下去，直到找到所有的匹配，对每两个匹配之间，如果有内容，则表示有Add/Delete/Modify发生，根据左臂右臂是否为0可以明显区分。举个例子：Anew Aold1 12 13 32 24 4首次匹配找到11，匹配立即停止，因为1*1 + 1*1 = 2，2*2 > 2，所以没有比较进行下去了.然后往下找到22，这时候左臂等于1，右臂等于3，（注意臂长是相对上一次被采用的匹配的），1*1 + 3*3 = 10，当前贪心值是10；然后往下找到33，左臂为2，右臂为2，2*2 + 2*2 = 8，这个匹配优于上一个匹配；然后继续往下找到22（左边第二个2），左臂3，右臂3，3*3本身的平方已经超过目前的贪心值8，没有必要再继续往下匹配，这一轮匹配查询结束。这里可以看出采用平方和做贪心算式的好处，很快可以收敛，而且符合“左右平衡”以及“最近匹配”。后面2和4的分析略去。但是这个算法存在一个问题,它的算法只针对单行最优, 而无法实现多行的最优, 比如Anew Aolda ab ac b像上面的两个文件, Anew:1 匹配 Aold:1, 但是应该使 Anew:1 匹配 Aold:2, 这样子才可以使Anew中序列ab 与 Aold的序列ab匹配.3. 下一步工作 * 调整贪心值计算函数 * 贪心算法 + 部分动态规划
posted on 2006-10-08 19:23 泡泡牛 阅读(4116) 评论(1) 编辑 收藏 引用
|