Windiff 原理初探

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

编代码的大都用过diff工具。UNIX下面有Unix Diff Utils,Windows下面有Windiff和WinMerge(内部使用UNIX Diff Utils引擎)

Diff到底是如何工作的?这个问题从来没有细想过,一直以为比较简单。从昨晚到今天探索好久现在有了初步的答案。顺便说一下,这些探究不是基于源码的,而是从动态规划等算法上面研究,如果各位有兴趣看源代码(Unix Diff Util有源代码),看完之后请过来讨论一下:)

先将问题抽象并简化
首先,不考虑空行,因为空行在代码解析的时候一般都是被滤掉,而且如果考虑空行,会有许多不同的处理方式,这里只讨论算法,因此规避空行问题。
其次,Windiff是基于行的比较,把每行作为一个比较单位。我们可以用一个整型值来代替一行,每一个文件可以看作一个这样的整型数组。
再次,将问题再度简化为比较两个字符串,找出里面的公共子串以及相异子串。

然后呢?

哦,天哪,看看这里就全部都搞定了:http://www.sbc.su.se/~pjk/molbioinfo2001/dynprog/dynamic.html

Update:
经实验证明,在文件非常长的时候此算法非常之慢,一开始我以为是string操作太多,用了个hash巧妙转成int比较,还是不行,速度慢。
分析了一下,比如10k个文件,这样就会有个10k x 10k的int数组,内存一次性耗掉有400M之多,计算量庞大无比到了难以承受的地步。
我监测了一下windiff,人家在100k大小的两个文件比较只用了一秒多,内存最多时不超过50M。
一定有更好的解法。

Update2:
路上和朋友讨论一下,有以下几种思路:
1、贪心算法
2、贪心算法 + 部分动态规划
3、被比较对象每行的重复率很低,这个信息可能会有用。

Update3:
后来找到的算法:
Windiff 原理初探(续1)

Tags:[tag]coding, global-alignment, 动态规划, Windiff, 原理[/tag]

5 条评论 发表在“Windiff 原理初探”上

  1. rain说道:

    我想问一下,哪里可以找到Unix Diff Utils的源码,看完你提供的动态规划算法,但是内存的问题解决了吗?

  2. 兔毛猫说道:

    参见Windiff 原理初探(续1):http://www.2maomao.com/blog/how-windiff-works-continued-1/

    Unix Diff Utils这里有下载,解包后里面就有源码:http://ftp.gnu.org/pub/gnu/diffutils/

  3. 兔毛猫说道:

    @阿里
    多谢啦 😀

  4. 小杨说道:

    windiff 哪里下载, 我需要。

留下回复