一个有些意思的项目–文件夹对比工具（一）
前言
为什么会写这个，因为遇到了有意思的事情，简而言之就是，面试某意向公司，没过；其中一位面试官非常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算法，什么时候用其他的呢，这边有篇文档：//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的算法我还不是很理解，但是如果按照我们暴力的思路，就是每条路线的距离都计算一下（向右的次数 + 向下的次数之和；走对角线不算），然后取最短的路线即可。
网上有不少资料，有兴趣可以阅读：
//chenshinan.github.io/2019/05/02/git生成diff原理：Myers差分算法/
原始论文：
//neil.fraser.name/writing/diff/myers.pdf
