编辑距离与diff工具的实现
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 回到开始，再逆序一下，就得到了每一步的路径。
得到路径还不够，还需要知道每一步的修改是什么。其实很简单的：
- 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行一致
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
Back