Windiff 原理初探(续1)

作者:半瓶墨水   链接:http://www.2maomao.com/blog/how-windiff-works-continued-1/

前两天虽然找到初步解决方案,因其效率奇差,后来提出一些思路,这里只说思路1:贪心算法。

原来的方案(方案1)里面,为了找到最优解,采用全盘动态规划算法,先规划,再回推,对于n行文件的比较,需要O(nxn)的时间复杂度和空间复杂度。更具体一些的话,两个10000行代码的文件比较,需要:10000×10000 x sizeof(int) ≈ 400M,时间是1亿次运算(加减,比较等等)

如果文件有十万行,那么内存数量相当客观,现有的个人计算机一般都达不到。

贪心算法的基本思路:从问题的某一个初始解出发逐步逼近给定的目标,以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时,算法停止。

首先还是简化问题:每个行根据内容映射到一个整型值,为了保证不出错(hash结果相同而内容不同),这里不用hash,后面会描述如何映射

这就将整个问题简化为整形数组的比较,姑且称之为Anew和Aold。定义如下:
左臂(leftHand,Anew里面新匹配位置距上一次被采用的匹配的距离),
右臂(rightHand,Aold里面新匹配位置距上一次被采用的匹配的距离)。

Anew纯粹就是整型值数组,而对于Aold,为了加快搜索匹配值的效率,先进行排序以方便二分查找。但是为了保证原来的序号不会丢失(显示结果时会用到),Aold里面每个元素是一对值(pair):first内容为真正的值,second内容为原来的序号。然后对Aold依据每个元素的first值进行排序。

程序处理流程简述:
while (还没到头)
{
   while (还可以继续找,还可以更贪心:)
   {
      找到下一个匹配的(依次对ANew的元素,用二分算法查找其在AOld中的位置)
      if (找的到)
         计算其贪心值,如果当前更贪则用这个匹配做当前最佳匹配
      else
         break;
   }
}

输出剩余的未匹配节点。

其中“还可以更贪心”是如何判定的呢?

首先要找一个目标,在这里我给定的目标是左右平衡情况下的最近匹配。比如一个匹配左臂1,右臂10,另一个匹配是左臂3,右臂3,这时候倾向于选择后一个匹配。

为了公式化和便于计算,我采用一个简单的具有这个逻辑的函数:leftHand*leftHand + rightHand*rightHand的值(贪心值)最小。

定义了这个目标以后,你会发现只要左臂过长,lefthand自身的平方超过上个候选匹配的贪心值,则可以停止往下计算了。

然后这个循环继续下去,直到找到所有的匹配,对每两个匹配之间,如果有内容,则表示有Add/Delete/Modify发生,根据左臂右臂是否为0可以明显区分。

举个例子
Anew Aold
1     1
2     1
3     3
2     2
4     4

首次匹配找到1<-->1,匹配立即停止,因为1*1 + 1*1 = 2,2*2 > 2,所以没有比较进行下去了

然后往下找到2<-->2,这时候左臂等于1,右臂等于3,(注意臂长是相对上一次被采用的匹配的),1*1 + 3*3 = 10,当前贪心值是10;然后往下找到3<-->3,左臂为2,右臂为2,2*2 + 2*2 = 8,这个匹配优于上一个匹配;然后继续往下找到2<-->2(左边第二个2),左臂3,右臂3,3*3本身的平方已经超过目前的贪心值8,没有必要再继续往下匹配,这一轮匹配查询结束。

这里可以看出采用平方和做贪心算式的好处,很快可以收敛,而且符合“左右平衡”以及“最近匹配”。
后面2和4的分析略去。

程序运行结果对比:
我用C++在WindowsXP下实现这个程序,AMD2500+/512内存,Release版,删除printf输出(这里只算分析时间)以后,对两个12万行的文本做diff跑了10秒不到。

我试了一下WinMerge,不算其界面操作时间(即只算到分析结束,他后来死翘翘了),应该在5秒之内

不过,好像Windiff更快,一秒都不到,结果我打开一看,丫好像全错了:(,各位可以试试看,将1, 2, 3, 4, 5, 6, 7, 8每个数字一行然后重复这些行直到10万行,另一个文件用1, 2, 2, 4, 6, 6, 5每个数字一行然后重复到10万行,反正我机器VS2005的Windiff分析结果飞快,结果是这两个文件没有一行相同 😮 ,汗一个

有没有更好的方法?上文里面提到的想法里面,想法2会优化结果,速度可能反而会慢一些,想法3应该是值得考虑的因素。

程序代码(估计有许多小bug):http://www.2maomao.com/blog/wp-content/uploads/mydiff.cpp.html
(注1:其中printf被我在前面算时间的时候注释掉,恢复既可:printf(“%d,%d,c,%d,%d,\n”, left1, left2, right1, right2);)
(注2:没有仔细区分Add/Delete/Change,全部认为是Change,这并不影响结果的正确与否)
(注3:彩色的html是采用VIM的命令”:runtime! syntax/2html.vim”进行导出。)

Update: 本算法的不足之处:对于两块代码交换的情况,只能找出不同,不能得出交换代码的结论,windiff做的好一点儿,但也不全能找到。

Tags:[tag]windiff, 算法[/tag]

9 条评论 发表在“Windiff 原理初探(续1)”上

  1. rain说道:

    谢谢了

  2. zjf说道:

    你用python编写一个可以吗?

  3. 半瓶墨水说道:

    @zjf 自己写吧

  4. hu_amao说道:

    有没有考虑文件大小为百万行级别?

  5. hu_amao说道:

    其实我想说的是一下子读入文件里的所有数据,这样对于超大文件来说肯定不可行。
    嗯 期待你修改后的代码 。。。 呵呵

  6. 半瓶墨水说道:

    是这样没错,但是这已经不是我想探讨的范畴了,你可以研究一下如何解决

  7. hu_amao说道:

    您好,因为最近也在研究字符串比较算法,对你提出的这个算法非常感兴趣,对于差异很小的两个字符串,“左右平衡”和“最近匹配”能够很大程度滴降低比较次数,但是对于求两个字符串的最长公共子串或者两个字符串的差异等类似问题,这样在局部做比较就认定两者匹配,可能会出现问题。
    举例:求两个字符串ABCA和BDABCA的最长公共子串。由这个算法求出的就是BA而不是ABCA。

  8. 半瓶墨水说道:

    @hu_amao,算法要根据实际情况进行调整,最长公共字串自有适合它的算法。

  9. louisa说道:

    windiff的处理单位是多大呢,你两串不同的数字以行为单位进行复制,可能在windiff看来就是每行都不同啊。如果把这些数字每个数字占一行,那windiff比对应该不是完全不同的。

留下回复