半瓶墨水

前两天虽然找到初步解决方案，因其效率奇差，后来提出一些思路，这里只说思路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分析结果飞快，结果是这两个文件没有一行相同 :o ，汗一个

有没有更好的方法？上文里面提到的想法里面，想法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]

八月 16th, 2006 | 分类: 编程随笔, 原创精选 | 阅读(4920) | | (2 人投票, 平均5)  Loading ...