Myers diff 3

本文是 diff 系列 的第三篇。在 上一部分 中，我们探讨了完整的 Myers 算法及其局限性。在这篇文章中，我们将学习如何实现 Myers 算法的一种变体，该算法具有线性空间复杂度。

分而治之

Git 使用的 Myers 的 diff 算法的线性变体采用了一个称为 Snake（有时称为 Middle Snake）的概念来分解整个搜索过程。编辑图中的 Snake 表示在一次向左或向下移动后的 0 到 N 步的对角线移动。线性 Myers 算法在最优编辑路径上找到中间的 Snake，并用它将整个编辑图分成两部分。随后的步骤将相同的技术应用于结果子图，最终生成完整的编辑路径。

    0   1   2   3   4   5   6   7   8   9  10  11  12  13  14
 0  o---o---o---o---o---o---o
    |   |   |   |   |   |   |
 1  o---o---o---o---o---o---o
    |   | \ |   |   |   |   |
 2  o---o---o---o---o---o---o
    |   |   |   |   |   |   |
 3  o---o---o---o---o---o---o
    |   |   |   |   | \ |   |
 4  o---o---o---o---o---o---o
    |   |   |   |   |   |   |
 5  o---o---o---o---o---o---o
                              \
 6                              @
                                  \
 7                                  @---o---o---o---o---o---o
                                        |   |   |   |   |   |
 8                                      o---o---o---o---o---o
                                        | \ |   |   |   |   |
 9                                      o---o---o---o---o---o
                                        |   |   |   |   |   |
10                                      o---o---o---o---o---o
                                        |   |   |   |   |   |
11                                      o---o---o---o---o---o
                                        |   |   | \ |   |   |
12                                      o---o---o---o---o---o
                                        |   |   |   |   |   |
13                                      o---o---o---o---o---o
                                        |   |   |   |   | \ |
14                                      o---o---o---o---o---o

简要回顾一下：最佳编辑路径是到端点的距离最短的路径（对角线距离为零），并且可以有多个这样的路径。

细心的读者可能已经注意到一个鸡生蛋还是蛋生鸡的问题：为了找到 Snake，你需要一个最优的编辑路径，但是为了获得最优的编辑路径，你似乎需要先运行原始的 Myers 算法。

事实上，线性 Myers 算法背后的思想有些不寻常：它从左上角和右下角替换原始 Myers 算法，但不存储历史。相反，它只是检查两边的搜索是否重叠。当它们这样做时，重叠的部分作为 Middle Snake 返回。

这种方法似乎很简单，但仍有一些细节需要解决。

当从右下搜索时，对角线坐标不能再被称为 k。我们需要定义一个新的对角线坐标 c = k - delta 。这个坐标是 k 的镜像，非常适合反向搜索。

        x                       k
                                  0     1     2     3
        0     1     2     3         \     \     \     \
  y  0  o-----o-----o-----o           o-----o-----o-----o
        |     |     |     |      -1   |     |     |     | \
        |     |     |     |         \ |     |     |     |   2
     1  o-----o-----o-----o           o-----o-----o-----o
        |     | \   |     |      -2   |     | \   |     | \
        |     |   \ |     |         \ |     |   \ |     |   1
     2  o-----o-----o-----o           o-----o-----o-----o
                                        \     \     \     \
                                        -3    -2    -1      0
                                                              c

我们如何确定搜索是否重叠？只需检查正向搜索中对角线上的位置的 x 值是否大于反向搜索中的 x 值。但是，由于同一对角线的 k 和 c 坐标不同，因此转换可能有点棘手。

代码实现

我们将首先定义 Snake 和 Box 类型，代表 middle snake 和子编辑图（因为它们是方形的，所以我们称之为 Box）。

struct Box {
  left : Int
  right : Int
  top : Int
  bottom : Int
} derive(Show)

struct Snake {
  start : (Int, Int)
  end : (Int, Int)
} derive(Show)

fn width(self : Box) -> Int {
  self.right - self.left
}

fn height(self : Box) -> Int {
  self.bottom - self.top
}

fn size(self : Box) -> Int {
  self.width() + self.height()
}

fn delta(self : Box) -> Int {
  self.width() - self.height()
}

为了避免太早陷入细节，让我们假设我们已经有一个函数：midpoint : (Box, Array[Line], Array[Line]) -> Snake? 去找 middle snake。然后，我们可以构建函数 find_path 来搜索完整的路径。

fn find_path(
  box : Box,
  old~ : Array[Line],
  new~ : Array[Line]
) -> Iter[(Int, Int)]? {
  guard midpoint(box, old~, new~) is Some(snake) else { None }
  let start = snake.start
  let end = snake.end
  let headbox = Box::{
    left: box.left,
    top: box.top,
    right: start.0,
    bottom: start.1,
  }
  let tailbox = Box::{
    left: end.0,
    top: end.1,
    right: box.right,
    bottom: box.bottom,
  }
  let head = find_path(headbox, old~, new~).or(Iter::singleton(start))
  let tail = find_path(tailbox, old~, new~).or(Iter::singleton(end))
  Some(head.concat(tail))
}

find_path 的实现很简单，但 midpoint 有点复杂：

• 对于大小为 0 的 Box，返回 None。

• 计算搜索边界。因为向前和向后搜索各占一半的距离，所以除以 2。但是，如果 Box 的大小是奇数，则在正向搜索边界上再添加一个。

• 将向前和向后搜索的结果存储在两个数组中。

• 在向前和向后搜索之间交替，如果没有找到结果则返回 None。

fn midpoint(self : Box, old~ : Array[Line], new~ : Array[Line]) -> Snake? {
  if self.size() == 0 {
    return None
  }
  let max = {
    let half = self.size() / 2
    if is_odd(self.size()) {
      half + 1
    } else {
      half
    }
  }
  let vf = BPArray::make(2 * max + 1, 0)
  vf[1] = self.left
  let vb = BPArray::make(2 * max + 1, 0)
  vb[1] = self.bottom
  for d = 0; d < max + 1; d = d + 1 {
    match self.forward(forward = vf, backward = vb, d, old~, new~) {
      None =>
        match self.backward(forward = vf, backward = vb, d, old~, new~) {
          None => continue
          res => return res
        }
      res => return res
    }
  } else {
    None
  }
}

与最初的 Myers 算法相比，向前和向后搜索有一些修改，需要做出解释：

• 因为我们需要返回 snake，所以搜索过程必须计算前一个坐标（px 代表前一个 x）。

• 搜索现在在 Box（不是全局编辑图）中工作，因此从 x 计算 y 需要转换（反之亦然）。

• 反向搜索最小化 y 是一种启发式策略，但最小化 x 也是可行的。

fn forward(
  self : Box,
  forward~ : BPArray[Int],
  backward~ : BPArray[Int],
  depth : Int,
  old~ : Array[Line],
  new~ : Array[Line]
) -> Snake? {
  for k = depth; k >= -depth; k = k - 2 {
    let c = k - self.delta()
    let mut x = 0
    let mut px = 0
    if k == -depth || (k != depth && forward[k - 1] < forward[k + 1]) {
      x = forward[k + 1]
      px = x
    } else {
      px = forward[k - 1]
      x = px + 1
    }
    let mut y = self.top + (x - self.left) - k
    let py = if depth == 0 || x != px { y } else { y - 1 }
    while x < self.right && y < self.bottom && old[x].text == new[y].text {
      x = x + 1
      y = y + 1
    }
    forward[k] = x
    if is_odd(self.delta()) &&
      (c >= -(depth - 1) && c <= depth - 1) &&
      y >= backward[c] {
      return Some(Snake::{ start: (px, py), end: (x, y) })
    }
  }
  return None
}


fn backward(
  self : Box,
  forward~ : BPArray[Int],
  backward~ : BPArray[Int],
  depth : Int,
  old~ : Array[Line],
  new~ : Array[Line]
) -> Snake? {
  for c = depth; c >= -depth; c = c - 2 {
    let k = c + self.delta()
    let mut y = 0
    let mut py = 0
    if c == -depth || (c != depth && backward[c - 1] > backward[c + 1]) {
      y = backward[c + 1]
      py = y
    } else {
      py = backward[c - 1]
      y = py - 1
    }
    let mut x = self.left + (y - self.top) + k
    let px = if depth == 0 || y != py { x } else { x + 1 }
    while x > self.left && y > self.top && old[x - 1].text == new[y - 1].text {
      x = x - 1
      y = y - 1
    }
    backward[c] = y
    if is_even(self.delta()) && (k >= -depth && k <= depth) && x <= forward[k] {
      return Some(Snake::{ start: (x, y), end: (px, py) })
    }
  }
  return None
}

总结

除了默认的 diff 算法之外，Git 还提供了另一种 diff 算法，称为 patience diff。它在方法上与 Myers diff 有很大不同，有时会产生更可读的 diff 结果。