Git如何知晓文件差异

  求两版本之间的差异是一个动态规划问题

  git 能发现任何的改动,但它是怎么发现的呢?难道它监控了我们对文件的读写操作? git 才没这么鸡冻……它是通过比较新旧版本,掐指一算算出来的O(∩_∩)O。

  首先假设我们只能通过以下3个操作将旧版本演化为新版本:

copy —— 复制旧版本当前行到新版本

insert —— 在新版本中添加一行

delete —— 跳过旧版本当前行

  那么,如下旧版本(左)到新版本(右):

1 22 333   1 333  

可通过

方案一:copy、delete、copy

方案二:delete、delete、delete、insert、insert

演化而来。

  旧版本可通过这3个操作演化成任意一个新版本,即使新版本已经面目全非:

  假设旧版本有n行,新版本有m行。不管它们每行的内容是什么,总是可以通过 n次delete 和 m次insert 演化出新版本。

  但是,由于 1个copy 能顶替 1个insert+1个delete,所以方案一比方案二少两个步骤。而且我们实际进行的操作就是步骤最少的方案一(呵呵,人类是最聪明的O(∩_∩)O)。

--------------------------------------------------------------------------------

  现在我们有目标了:怎么得到一个步骤最少的演化方案?为了更清晰地描述演化过程,我们定义两个下标: i(旧版本行号)、j(新版本行号)。演化过程中会改变这两个下标:

copy : ++i,++j

insert : ++j

delete : ++i

  定义 minPrice[i][j] 为从位置 (i,j) 演化到(n,m) 的最少步骤数(i,j从0开始);那么,minPrice[0][0] 就是从旧版本演化到新版本的最少步骤数。

  求 minPrice 的递归式很容易得出:

Git如何知晓文件差异

--------------------------------------------------------------------------------

  如果照这个递归式写一个递归算法,那么递归算法会有很多重叠子问题,例如:

  minPrice[0][0]、minPrice[0][1]、minPrice[1][0] 都需要计算 minPrice[1][1]。

  因此适合采用动态规划逆向求解。下面我用 Java 实现了动态规划版的 Diff:

E:\temp>java Diff src.txt dest.txt
  1    1  1
  2      - 22
  3    2  333

E:\temp>

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/20156.html