Myers diff#
你是否曾经使用过 Unix 系统中的 ‘diff’ 工具？简单来说，它是一种用于比较两个文本文件之间差异的工具。此外，Unix 系统中还有名为 ‘patch’ 的工具。
现在很少有人手动应用软件包的修补，但 ‘diff’ 在另一个领域中仍然非常有用：版本控制系统。你有看到特定提交后代码文件所做更改（并以不同的颜色突出显示）的函数是非常方便的。例如，最受欢迎的版本控制系统之一，git，就是一个很好的例子。
diff --git a/main/main.mbt b/main/main.mbt
index 99f4c4c..52b1388 100644
--- a/main/main.mbt
+++ b/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 的默认比较差异算法由 Eugene W. Myers 在他的论文一个 O(ND) 的差分算法及其变体中提出。这篇论文主要聚焦于证明该算法的正确性。接下来，我们将以一种不那么严谨的方式理解其基本架构，并使用 MoonBit 编写一个简单的实现。
“差异”的定义及其度量标准#
当我们讨论两个文本文件之间的“差异”时，我们实际上是在指能将文本 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
- A
+ C
+ B
+ A
+ B
+ A
+ C
但是这样的结果可能对程序员阅读程序来说并没有太大帮助。接下来的编辑序列会好很多，至少它更短。
- A
- B
C
+ B
A
B
- B
A
+ C
实际上，这是实现文本 a 转换为文本 b 所需的最简编辑序列，仅需要 5 个操作。如果我们只考虑编辑序列的长度，这一结果已经令人满意。但在探索多种编程语言时，我们发现除了编辑序列长度外，还有其他度量指标对用户体验同样重要。让我们来看看以下例子：
// good quality
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 }
+ }
// bad quality
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 算法可以满足所有这些需求。它是一种贪婪算法，每次都尽可能地跳过匹配行（避免在出现’{‘之前插入文本），同时也会尝试将删除操作置于插入操作之前，避免后者发生。
算法概述#
Myers 的论文中的基本思路是构建一个编辑操作的网格图，并在该网格上搜索最短路径。以之前的例子 ‘a = ABCABBA’ 和 ‘b = CBABAC’ 为例，我们创建一个 ‘(x, y)’ 坐标网格。
0 1 2 3 4 5 6 7
0 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-----o
A 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 算法的整个原理基于这种广度优先搜索。
实现#
我们已经概述了基本思想，现在是详细考虑设计的时候了。算法的输入是两个字符串，但是搜索需要在一个图上进行。而构造图然后再去搜索它是浪费内存和时间成本的。
Myers 算法的实现采用了一种聪明的方法，定义了一个新的坐标 k = x - y。
向右移动会使
k增加 1。向左移动会使
k减少 1沿对角线向左下方移动保持
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] 范围内（因为在一次移动中，它最多可以比前一轮增加或减少 1），并且点之间的 k 值的间隔为 2。Myers 算法的基本思想来自于这样一个思想：通过遍历 d 和 k 来进行搜索。当然，它还需要保存每一轮的 x 坐标，以便在下一轮搜索中使用。
让我们首先定义 Line 结构，它代表文本中的一行。
///|
struct Line {
number : Int // Line number
text : String // Does not include newline
} derive(Show)
///|
fn Line::new(number : Int, text : String) -> Line {
Line::{ number, text }
}
然后，定义一个辅助函数，根据换行符将字符串拆分为 Array[Line]。注意，行号从 1 开始。
fn lines(str : String) -> Array[Line] {
let lines = Array::new(capacity=50)
let mut line_number = 0
for line in str.split("\n") {
line_number = line_number + 1
lines.push(Line::new(line_number, line))
} else {
return lines
}
}
接下来，我们需要包装数组，以便它支持负索引，因为我们将使用 k 的值作为索引。
type BPArray[T] Array[T] // BiPolar Array
fn BPArray::make[T](capacity : Int, default : T) -> BPArray[T] {
let arr = Array::make(capacity, default)
BPArray(arr)
}
fn copy(self : BPArray[Int]) -> BPArray[Int] {
let BPArray(arr) = self
let newarr = Array::make(arr.length(), 0)
for i = 0; i < arr.length(); i = i + 1 {
newarr[i] = arr[i]
} else {
BPArray(newarr)
}
}
fn op_get[T](self : BPArray[T], idx : Int) -> T {
let BPArray(arr) = self
if idx < 0 {
arr[arr.length() + idx]
} else {
arr[idx]
}
}
fn op_set[T](self : BPArray[T], idx : Int, elem : T) -> Unit {
let BPArray(arr) = self
if idx < 0 {
arr[arr.length() + idx] = elem
} else {
arr[idx] = elem
}
}
现在我们可以开始编写搜索函数了。在搜索完整路径之前，让我们从第一个目标开始，即找到最短路径的长度（等于搜索深度）。以下是基本框架：
fn shortest_edit(old~ : Array[Line], new~ : Array[Line]) -> Int {
let n = old.length()
let m = new.length()
let max = n + m
let 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 { // When d equals 0, k must also equal 0
x = 0
y = x - k
while x < n && y < m && old[x].text == new[y].text {
// Skip all matching lines
x = x + 1
y = y + 1
}
v[k] = x
}
当 d > 0 时，需要前一轮存储的坐标信息。当我们知道一个点的 k 值和前一轮搜索中点的坐标时，就很容易推导出 v[k] 的值。因为每一步 k 只能增加或减少 1，所以搜索树中的 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 // add 1 to move horizontally
} 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 shortest_edit(old~ : Array[Line], new~ : Array[Line]) -> Int {
let n = old.length()
let m = new.length()
let max = n + m
let v = BPArray::make(2 * max + 1, 0)
// v[1] = 0
for d = 0; d < max + 1; d = d + 1 {
for k = -d; k < d + 1; k = k + 2 {
let mut x = 0
let 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 - k
while x < n && y < m && old[x].text == new[y].text {
// Skip all matching lines
x = x + 1
y = y + 1
}
v[k] = x
if x >= n && y >= m {
return d
}
}
} else {
abort("impossible")
}
}
由于数组的初始值为 0，我们可以省略 d == 0 的分支。
结语#
我们已经实现了 Myers 算法的一个不完整版本，它完成了正向路径搜索。在下一篇文章中，我们将实现回溯以恢复完整的编辑路径，并编写一个函数来输出彩色差值。
本文引用：
感谢作者 James Coglan。