前言#

为什么会写这个，因为遇到了有意思的事情，简而言之就是，面试某意向公司，没过；其中一位面试官非常nice，还仔细看了我博客，觉得是不是面试时没展现出来，因此第二天专程打电话过来，给了我一个额外机会，就是花几天时间做一个小项目，过几天提交给他。

这是背景，项目是关于做一个工具，可以指定两个目录进行对比，如果某个文件如a.txt在两个目录都存在，就对比其内容并呈现，呈现效果可以参考beyond compare或者git diff。

花了三天多时间编码，两天时间写文档，最终做了一个满足需求的简陋工具出来，幸不辱命吧；项目麻雀虽小，五脏俱全，也写了需求分析文档、概要设计、详细设计等，项目本身也非常有意思，所以给大家分享一下。
其中一个核心点就是文本差异对比算法，因此先来篇文章讲解一下，铺垫铺垫。

差异对比，很多人会想到beyond compare、git、svn等。这里以git来说吧，git作为版本管理工具，真的也太方便了，很多时候想推荐给非互联网行业的朋友们。

版本管理工具，最重要的一点就是不同版本的差异对比，看下图：

从图上来说，右边那一行比左边，就是多了几个字符”xxxww“；但是对于软件来说，怎么才知道，只是多了几个字符呢，毕竟，按理来说，插入了几个字符后，原来在右侧的字符被迫右移，其实在程序看来，是从插入的地方开始，两个字符串已经开始是不同的了。

但是软件并没有从插入的地方开始的右侧字符，全标记为差异，所以，软件是怎么识别出来的呢？

字符串转换#

其实以上的问题可以用下面的例子来简单阐述：

假设有一个原始字符串是：ABCABBA，现在我们想把它变成：CBABAC，是不是有很多种方式呢？

比如，最简单的方式，ABCABBA依次删掉：ABCABBA，现在，是不是变成一个空字符串了，删7个字符，一共操作7次；接下来，再在空字符串基础上，依次加上：CBABAC，加了6次。

最终，操作了13次，就把ABCABBA变成了CBABAC。

但是，这太暴力了，也不是很优雅，直观的感觉就是，太傻了，好像不需要这么多次吧？

所以，寻找一个算法，以保证：转换成功的同时，保证尽可能少的编辑次数。

这就是最短diff算法，diff就是把原始字符串变成目标字符串，要进行的各种增删操作；或者也可以和数学里的delta对比，我查了下，delta就有变动的意思。

"最短diff"这个算法有多种实现，在git diff的代码中，就有4种实现供我们选择，分别是：

myers, minimal, patience, histogram。

在git help diff的文档中，有简要介绍：

默认的是myers算法，什么时候用其他的呢，这边有篇文档：https://luppeng.wordpress.com/2020/10/10/when-to-use-each-of-the-git-diff-algorithms/，有需要的同学可以看看。

这篇就简单说下我对myers的理解，算法比较复杂，我也没怎么弄懂，大家也跟着有个概念就行了（狗头）

diff的另一种直观展示#

大佬们想了一个办法来表示diff。还是上面的例子，ABCABBA转换为CBABAC。

根据这两个字符串构造下面一张图，横轴是原始内容，纵轴是目标内容。

这个图要这么看，左上角是零坐标，水平是x轴，上下是y轴，x轴从（0，0）点到（1,0）点，为A字符；（1,0）到（2,0）是B字符，依次类推，横轴上的8个点，有7个空，依次为ABCABBA，即原始字符串的内容。y轴也是同理。

现在规定了，（0,0）处，你拥有原始字符串ABCABBA，当前指向第一个字符A。此时，向右表示删除对应的字符，向下表示新增对应字符，对角线则表示原内容保持不动（或者说先删再加，即不变）

现在举个例子：

• 从（0,0）移动到（1,0），需要删掉A，此时，ABCABBA从当前光标所在处，删掉A，变成了BCABBA，此时光标指向BCABBA的第一个字符B；

  

• 从（1,0）再向右移动一格到（2,0），此时要删去B，变成了CABBA

• 沿着x轴，继续移动到（3,0），删除C，变成ABBA；继续移动到（4,0），删除A，变成BBA；继续到（5,0），删除B，变成BA；继续到（6,0），删除B，变成A；继续到（7,0），删除A，变成空。

  

• 到目前为止，我们来到了7,0，字符串变成空的了；开始往下走，往下走的过程，是增加对应字符，比如，从(7,0)，走到（7,1），增加字符C，变成“C”；再走到（7,2），变成CB；再到（7,3），变成CBA；

• 最终走到(7,6)，变成了CBABAC.

大家可能发现了，只要沿着那个图一路走，从（0,0）到达右下角（7,6），原始字符串就能变成目标字符串。

当然，这条路是比较暴力的，先删除原始字符串（一路往右），再新增目标字符串（一路向下）。

diff的图形表示之路线演示#

我们来随便画个其他路线试试。

现在（0，0）处，我们为原始字符串ABCABBA，

• 接下来是向右一步-A，变成BCABBA。
• 向下，+C，变成CBCABBA
• 遇到对角线，对角线对应字符B，此时可以理解为删掉B，再加上B，相当于光标前移，依然是CB|CABBA，我们用|表示光标位置
• 向下，在当前光标处+A，变成CBA|CABBA；加B，变成CBAB|CABBA；再-C，变成CBAB|ABBA
• 又遇到对角线，对角线对应字符A，此时光标移动，变成CBABA| BBA
• 从(4,5)移动到（4,6），加C，变成CBABAC|BBA
• 从（4,6）移动到(7,6),依次删除BBA，即变成CBABAC

所以，我们再一次成功到达了右下角，此时字符串也变成了CBABAC。我们也可以算一下，移动了多少次

-A，+C，+A，+B，-C，+C，-B，-B，-A，合计是9次（走对角线的话，没有实际修改字符，不算在内）。

Myers 算法大概理解#

如果前面都理解了的话，我们大概知道，从图中的左上角，到达右下角的每一条路线，都是有效的diff。

而Myers的目标，应该就是从众多的路线中，选出一条距离最短（向右的次数 + 向下的次数之和；走对角线不算）的路线。

而这条最短的路线，就是最短diff算法的答案。

Myers的算法我还不是很理解，但是如果按照我们暴力的思路，就是每条路线的距离都计算一下（向右的次数 + 向下的次数之和；走对角线不算），然后取最短的路线即可。

网上有不少资料，有兴趣可以阅读：

https://chenshinan.github.io/2019/05/02/git生成diff原理：Myers差分算法/

原始论文：

https://neil.fraser.name/writing/diff/myers.pdf

博客分类导航贴：博客目录导航，让我们一起学起来吧（持续更新）

我是逐日, 鹅厂大头兵一枚，成都深圳反复横跳，鹅厂内推可以找我，可以关注我公号，想起来了就更新；或者右下角有个加号，咱们博客园见