逐日

V1

2022/08/01阅读:20主题:红绯

很有意思的经历,很有意思的项目--文件夹对比工具

一个有些意思的项目--文件夹对比工具(一)

前言

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

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

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

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

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

image-20220801211626345
image-20220801211626345

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

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

字符串转换

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

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

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

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

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

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

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

image-20220801214421370
image-20220801214421370

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

myers, minimal, patience, histogram

在git help diff的文档中,有简要介绍:

image-20220801212830510
image-20220801212830510

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

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

diff的另一种直观展示

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

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

image-20220801221137659
image-20220801221137659

这个图要这么看,左上角是零坐标,水平是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;

    image-20220801222140579
    image-20220801222140579
  • 从(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,变成空。

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

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

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

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

diff的图形表示之路线演示

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

image-20220801223706228
image-20220801223706228

现在(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%E7%94%9F%E6%88%90diff%E5%8E%9F%E7%90%86%EF%BC%9AMyers%E5%B7%AE%E5%88%86%E7%AE%97%E6%B3%95/

原始论文:

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

分类:

后端

标签:

后端

作者介绍

逐日
V1