<2006年10月>
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

统计

  • 随笔 - 44
  • 文章 - 0
  • 评论 - 86
  • 引用 - 0

常用链接

留言簿(6)

随笔分类(31)

随笔档案(44)

Mining

最新随笔

搜索

  •  

最新评论

阅读排行榜

评论排行榜

Diff 算法
Diff 在Linux下非常有用, 最近在对定向蜘蛛的研究中, 发现网页的信息大部分在Diff部分, 所以考虑了Diff的原理.

1. Unix Diff

Linux 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 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的分析略去。

但是这个算法存在一个问题,它的算法只针对单行最优, 而无法实现多行的最优, 比如
Anew Aold
a    a
b    a
c    b

像上面的两个文件, Anew:1 匹配 Aold:1, 但是应该使 Anew:1 匹配 Aold:2, 这样子才可以使Anew中序列ab 与 Aold的序列ab匹配.


3. 下一步工作

 * 调整贪心值计算函数
 * 贪心算法 + 部分动态规划


posted on 2006-10-08 19:23 泡泡牛 阅读(4242) 评论(1)  编辑 收藏 引用

评论

# re: Diff 算法[未登录] 2008-11-14 12:31 Tony

你的那个贪心算法,不如那个动态规划法好用啊
  回复  更多评论    

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理