编辑距离与diff工具的实现

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

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

python

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 回到开始，再逆序一下，就得到了每一步的路径。

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

1.如果 dp[i][j].pre_i == i-1 就表示 A 串 i 行删除了
2.如果 dp[i][j].pre_j == j-1 就表示 B 串新增加 j 行
3.如果 dp[i][j].pre_i == i-1 and dp[i][j].pre_j == j-1 就表示 A 串 i 行与 B 串 j 行一致

python

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()

输出：

python

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

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

编辑距离与diff工具的实现

输出： ​

输出：