编辑距离与diff工具的实现

06 Nov 2013

Diff工具是大家经常用的一个工具,特别是使用Git GUI程序之后,每次提交前都会瞄一眼代码 不过关于怎么实现的一直没有仔细想过,最近突然想自己实现一个试试,于是仔细思考了一下。

怎么知道2个文件的不同的,最一开始想到的就是以行为单位的编辑距离了,可是想到diff的合并格式(Unified_format)并没有修改这种显示方式,于是想去掉“修改”这个路径,只剩下删除和增加的修改。这样其实就是在求最小合并串。 于是动态转移方程就是

dp[i][j] 表示 A串的前i行,与B串前j行的最小合并串总行数。
if a[i] == b[j]:
    dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] +1)
else:
    dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] +1, dp[i-1][j-1] + 1)

为了显示,合并之后的文本结果,并不只是数字,我们需要记录每一步的 pre_i, pre_j 表示从什么状态过来。 最后需要从dp[end_i][end_j]状态根据 pre_i, pre_j 回到开始,再逆序一下,就得到了每一步的路径。

得到路径还不够,还需要知道每一步的修改是什么。其实很简单的:

import pydiff

a = '''a
a
b
c
d
e'''

b = '''b
b
b
c
d
d
e'''

def main():
    result =  pydiff.diff(a,b)
    for one in result:
        if one.status == -1:
            print '-',one.val
        elif one.status == 1:
            print '+',one.val
        else:
            print ' ',one.val

if __name__ == '__main__':
    main()

输出:

- a
- a
+ b
+ b
  b
  c
+ d
  d
  e

代码以及测试如下: https://github.com/dingyaguang117/PyDiff