家装设计网站怎么做,图片滤镜网站开发,聊城seo,wordpress页眉页脚你使用过 Unix 下的小工具 diff 吗#xff1f;
没有也没关系#xff0c;简而言之#xff0c;它是一个比对两个文本文件之间有什么不同之处的工具。它的作用不止于此#xff0c;Unix 下还有一个叫 patch 的小工具。
时至今日#xff0c;很少有人手动为某个软件包打补丁了…你使用过 Unix 下的小工具 diff 吗
没有也没关系简而言之它是一个比对两个文本文件之间有什么不同之处的工具。它的作用不止于此Unix 下还有一个叫 patch 的小工具。
时至今日很少有人手动为某个软件包打补丁了但 diff 在另一个地方仍然保留着它的作用版本管理系统。能够看见某一次提交之后的源码文件发生了哪些变化(并且用不同颜色标出来)是个很有用的功能。我们以当今最流行的版本管理系统 git 为例它可以
diff --git a/main/main.mbt b/main/main.mbt
index 99f4c4c..52b1388 100644
--- a/main/main.mbtb/main/main.mbt-3,7 3,7 fn main {let a lines(A\nB\nC\nA\nB\nB\nA)
- let b lines(C\nB\nA\nB\nA\nC)let b lines(C\nB\nA\nB\nA\nA)let r shortst_edit(a, b)println(r)}
但是究竟怎样计算出两个文本文件的差别呢
git 的默认 diff 算法是 Eugene W. Myers在他的论文An O(ND) Difference Algorithm and Its Variations 中所提出的这篇论文的 pdf 可以在网上找到但论文内容主要集中于证明该算法的正确性。
在下文中我们将以不那么严谨的方式了解该算法的基本框架并且使用 MoonBit 编写该算法的一个简单实现。
01 定义差别及其度量标准
当我们谈论两段文本的差别时我们说的其实是一系列的编辑动作通过执行这段动作我们可以把文本 a 转写成文本 b。
假设文本 a 的内容是
A
B
C
A
B
B
A
文本 b 的内容是
C
B
A
B
A
C
要把文本 a 转写成文本 b最简单的编辑序列是删除每一个 a 中的字符用减号表示然后插入每一个 b 中的字符用加号表示。
- A
- B
- C
- A
- B
- B
- ACBABAC
但这样的结果对阅读代码的程序员可能没有什么帮助而下面这个编辑序列就好很多至少它比较短。
- A
- BCBAB
- BAC
实际上它是最短的可以将文本 a 转写成文本 b 的编辑序列之一总共有5个动作。如果仅仅以编辑序列长度作为衡量标准这个结果足以让我们满意。但当我们审视现实中已经存在的各种编程语言我们会发现在此之外还有一些对用户体验同样重要的指标让我们看看下面这两个例子
// 质量好struct RHSet[T] {set : RHTable[T, Unit]}fn RHSet::new[T](capacity : Int) - RHSet[T] {let set : RHTable[T, Unit] RHTable::new(capacity){ set : set }}// 质量不好struct RHSet[T] {set : RHTable[T, Unit]}fn RHSet::new[T](capacity : Int) - RHSet[T] {let set : RHTable[T, Unit] RHTable::new(capacity){ set : set }}
当我们在文件末尾处插入了一个新的函数定义那计算出的编辑序列最好把更改都集中在后面。还有些类似的情况当同时存在删除和插入时最好不要计算出一个两种操作交织穿插的编辑序列下面是另一个例子。
Good: - one Bad: - one- two four- three - two four five five six six - three
myers 的 diff 算法能够满足我们在上面提到的这些需求它是一种贪心算法会尽可能地跳过相同的行避免了在{前面插入文本的情况同时它还会尽可能地把删除安排在插入前面这又避免了后面一种情况。
02 算法概述
Myers 论文的基本想法是构建一张编辑序列构成的网格图然后在这条图上搜索一条最短路径。我们沿用上面的例子 a ABCABBA 和 b CBABAC建立一个 (x, y) 坐标网格。 0 1 2 3 4 5 6 70 o-----o-----o-----o-----o-----o-----o-----o| | | \ | | | | || | | \ | | | | | C| | | \ | | | | |
1 o-----o-----o-----o-----o-----o-----o-----o| | \ | | | \ | \ | || | \ | | | \ | \ | | B| | \ | | | \ | \ | |
2 o-----o-----o-----o-----o-----o-----o-----o| \ | | | \ | | | \ || \ | | | \ | | | \ | A| \ | | | \ | | | \ |
3 o-----o-----o-----o-----o-----o-----o-----o| | \ | | | \ | \ | || | \ | | | \ | \ | | B| | \ | | | \ | \ | |
4 o-----o-----o-----o-----o-----o-----o-----o| \ | | | \ | | | \ || \ | | | \ | | | \ | A| \ | | | \ | | | \ |
5 o-----o-----o-----o-----o-----o-----o-----o| | | \ | | | | || | | \ | | | | | C| | | \ | | | | |
6 o-----o-----o-----o-----o-----o-----o-----oA B C A B B A
这张网格中左上方为起点(0, 0) 右下方为终点(7, 6)。沿着 x 轴向右前进一步为删除 a 中对应位置文本沿 y 轴向下前进一步为插入 b 中对应位置文本对角斜线标记的则是相同的文本这些斜线可以直接跳过它们不会触发任何编辑。
在编写实际执行搜索的代码之前让我们先手动执行两轮搜索
第一轮搜索起点为(0, 0)移动一步可以到达(0,1)和(1,0)。第二轮搜索起点为(0,1)和(1,0)从(0,1)出发下移可以到达(0,2) 但是那里有一条通向(1,3)的斜线所以最终落点为(1,3)。
整个myers算法的基础就是这样的广度优先搜索。
03 实现
虽然我们已经敲定了算法的基本思路但仍有一些关键的设计需要考虑。算法的输入是两个字符串但搜索需要在图上进行如果真的把图构造出来再去搜索这既非常浪费内存也很费时间。
myers 算法的实现使用了一个聪明的想法它定义了一个新的坐标 k x - y。
右移一步会让k加一左移一步会让k减一沿对角线向左下方移动k值不变
让我们再定义一个坐标 d 用于代表搜索的深度以 d 为横轴 k 为纵轴画出搜索过程的树状图 | 0 1 2 3 4 5
------------------------------------------|4 | 7,3| /3 | 5,2| /2 | 3,1 7,5| / \ / \1 | 1,0 5,4 7,6| / \ \0 | 0,0 2,2 5,5| \ \
-1 | 0,1 4,5 5,6| \ / \
-2 | 2,4 4,6| \
-3 | 3,6
可以看出来在每一轮搜索中k都严格地处于[-d, d]区间中(因为一次移动中最多也就能在上一轮的基础上加一或者减一), 且各点之间的k值间隔为2。myers算法的基本思路便源于此通过遍历d和k进行搜索。当然了它还需要保存每轮搜索的x坐标供下一轮搜索使用。
让我们首先定义Line结构体它表示文本中的一行。
struct Line {number : Int // 行号text : String // 不包含换行
} derive(Debug, Show)fn Line::new(number : Int, text : String) - Line {Line::{ number : number, text : text }
}
然后定义一个辅助函数它将一个字符串按照换行符分割成 Array[Line]。这里需要注意的是行号是从1开始的。
fn lines(str : String) - Array[Line] {let mut line_number 0let buf Buffer::make(50)let vec []for i 0; i str.length(); i i 1 {let ch str[i]buf.write_char(ch)if ch \n {let text buf.to_string()buf.reset()line_number line_number 1vec.push(Line::new(line_number, text))}} else {// 可能文本不以换行符为结尾let text buf.to_string()if text ! {line_number line_number 1vec.push(Line::new(line_number, text))}vec}
}
接下来我们需要包装一下数组使其支持负数索引原因是我们要用k的值做索引。
type BPArray[T] Array[T] // BiPolar Arrayfn BPArray::make[T](capacity : Int, default : T) - BPArray[T] {let arr Array::make(capacity, default)BPArray(arr)
}fn op_get[T](self : BPArray[T], idx : Int) - T {let BPArray(arr) selfif idx 0 {arr[arr.length() idx]} else {arr[idx]}
}fn op_set[T](self : BPArray[T], idx : Int, elem : T) - Unit {let BPArray(arr) selfif idx 0 {arr[arr.length() idx] elem} else {arr[idx] elem}
}
现在我们可以开始编写搜索函数了不过搜索出完整的路径是比较复杂的我们的第一个目标是搜索出最短路径的长度大小和搜索深度一样。我们先展示它的基本框架
fn shortst_edit(a : Array[Line], b : Array[Line]) - Int {let n a.length()let m b.length()let max n mlet v BPArray::make(2 * max 1, 0)for d 0; d max 1; d d 1 {for k -d; k d 1; k k 2 {......}}
}
通过最极端的情况(两段文本没有相同的行)可以推出最多需要搜索n m步最少需要搜索0步。故设变量max n m。数组v是以k为索引保存x值的历史记录因为k的范围是[-d, d]这个数组的大小被设为2 * max 1。
但即使到了这一步接下来该怎么做还是挺不好想所以我们暂且只考虑d 0; k 0的情况。此时一定在(0, 0)点。同时假如两段文本的开头相同那就允许直接跳过。我们将这一轮的最终坐标写入数组v。
if d 0 { // d等于0 k也一定等于0x 0y x - kwhile x n y m a[x].text b[y].text {// 跳过所有相同的行x x 1y y 1}v[k] x
}
在d 0时就需要用到上一轮存储的坐标信息了。当我们知道一个点的k值以及上一轮搜索中点的坐标时v[k]的值其实很好推算。因为搜索每深入一步k的值只能加一或者减一所以v[k]在搜索树中一定是从v[k - 1]或者v[k 1]延伸出来的。接下来的问题是以v[k - 1]为末端的和以v[k 1]为末端的这两条路径应该如何选择
有两种边界情况k -d和k d
k -d时只能选择v[k 1]k d时只能选择v[k - 1]
回顾一下我们之前提到的要求尽可能地把删除安排在插入前面这基本上意味着我们应该选择x值最大的前一个位置。
if k -d {x v[k 1]
} else if k d {x v[k - 1] 1 // 横向移动需要加一
} else if v[k - 1] v[k 1] {x v[k 1]
} else {x v[k - 1] 1
}
合并一下这四个分支我们得到这样的代码
if k -d || (k ! d v[k - 1] v[k 1]) {x v[k 1]
} else {x v[k - 1] 1
}
综合上面的所有步骤我们可以得到这样的代码
fn shortst_edit(a : Array[Line], b : Array[Line]) - Int {let n a.length()let m b.length()let max n mlet v BPArray::make(2 * max 1, 0)// v[1] 0for d 0; d max 1; d d 1 {for k -d; k d 1; k k 2 {let mut x 0let mut y 0// if d 0 {// x 0// }if k -d || (k ! d v[k - 1] v[k 1]) {x v[k 1]} else {x v[k - 1] 1}y x - kwhile x n y m a[x].text b[y].text {x x 1y y 1}v[k] xif x n y m {return d}}} else {abort(impossible)}
}
由于数组的初始值为0我们可以省略 d 0 这个分支。
04 尾声
我们实现了一个不完整的myers算法它完成了正向的路径搜索在下一篇文章中我们将实现回溯还原出完整的编辑路径并写一个可以输出彩色diff的打印函数。
本篇文章参考了The Myers diff algorithm: part 2
感谢这篇博客的作者James Coglan。
