Myers diff 2

Myers diff 2#

这是 diff 系列的第二篇文章。在上一篇 myers-diff 中，我们学习了如何将计算差分的过程转化为图搜索问题，以及如何搜索最短的编辑距离。在本文中，我们将学习如何扩展前一篇文章中的搜索过程，以获得完整的编辑序列。

记录搜索过程#

获得完整编辑序列的第一步是保存整个编辑过程。这一步相对简单：我们只需要保存当前搜索深度 d 和每个搜索轮开始时深度 d 的图节点。

fn shortest_edit(
  old~ : Array[Line],
  new~ : Array[Line]
) -> Array[(BPArray[Int], Int)] {
  let n = old.length()
  let m = new.length()
  let max = n + m
  let v = BPArray::make(2 * max + 1, 0)
  let trace = []
  fn push(v : BPArray[Int], d : Int) -> Unit {
    trace.push((v, d))
  }
  // v[1] = 0
  for d = 0; d < max + 1; d = d + 1 {
    push(v.copy(), d) 
    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 {
        x = x + 1
        y = y + 1
      }
      v[k] = x
      if x >= n && y >= m {
        return trace
      }
    }
  } else {
    abort("impossible")
  }
}

回溯编辑路径#

在记录了整个搜索过程之后，下一步是从端点返回以查找所使用的路径。但在我们这样做之前，让我们先定义 Edit 类型。

enum Edit {
  Insert(new~ : Line)
  Delete(old~ : Line)
  Equal(old~ : Line, new~ : Line) // old, new
} derive(Show)

接下来，让我们执行回溯。

fn backtrack(
  new~ : Array[Line],
  old~ : Array[Line],
  trace : Array[(BPArray[Int], Int)]
) -> Array[Edit] {
  let mut x = old.length()
  let mut y = new.length()
  let edits = Array::new(capacity=trace.length())

回溯的方法本质上与正向搜索相同，只是方向相反。

  • 使用 x 和 y 计算当前 k 值。

  • 访问历史记录并使用与前向搜索相同的判断标准来查找前一轮搜索中的 k 值。

  • 恢复上一轮搜索的坐标。

  • 尝试自由移动并记录相应的编辑动作。

  • 确定导致 k 值更改的编辑类型。

  • 继续迭代。

for i = trace.length() - 1; i >= 0; i = i - 1 {
  let (v, d) = trace[i]
  let k = x - y
  let prev_k = if k == -d || (k != d && v[k - 1] < v[k + 1]) {
    k + 1
  } else {
    k - 1
  }
  let prev_x = v[prev_k]
  let prev_y = prev_x - prev_k
  while x > prev_x && y > prev_y {
    x = x - 1
    y = y - 1
    edits.push(Equal(old=old[x], new=new[y]))
  }
  if d > 0 {
    if x == prev_x {
      edits.push(Insert(new=new[prev_y]))
    } else if y == prev_y {
      edits.push(Delete(old=old[prev_x]))
    }
    x = prev_x
    y = prev_y
  }
}

结合这两个函数，我们得到了一个完整的 diff 实现。

fn diff(old~ : Array[Line], new~ : Array[Line]) -> Array[Edit] {
  let trace = shortest_edit(old~, new~)
  backtrack(old~, new~, trace)
}

打印 diff#

要打印整齐的 diff，我们需要左对齐文本。另外，由于回溯过程中的顺序问题，我们需要从后往前打印。

let line_width = 4

fn pad_right(s : String, width : Int) -> String {
  String::make(width - s.length(), ' ') + s
}

fn pprint_edit(edit : Edit) -> String {
  match edit {
    Insert(_) as edit => {
      let tag = "+"
      let old_line = pad_right("", line_width)
      let new_line = pad_right(edit.new.number.to_string(), line_width)
      let text = edit.new.text
      "\{tag} \{old_line} \{new_line}    \{text}"
    }
    Delete(_) as edit => {
      let tag = "-"
      let old_line = pad_right(edit.old.number.to_string(), line_width)
      let new_line = pad_right("", line_width)
      let text = edit.old.text
      "\{tag} \{old_line} \{new_line}    \{text}"
    }
    Equal(_) as edit => {
      let tag = " "
      let old_line = pad_right(edit.old.number.to_string(), line_width)
      let new_line = pad_right(edit.new.number.to_string(), line_width)
      let text = edit.old.text
      "\{tag} \{old_line} \{new_line}    \{text}"
    }
  }
}

fn pprint_diff(diff : Array[Edit]) -> String {
  let buf = @buffer.new(size_hint = 100)
  for i = diff.length(); i > 0; i = i - 1 {
    buf.write_string(pprint_edit(diff[i - 1]))
    buf.write_char('\n')
  } else {
    buf.contents().to_unchecked_string()
  }
}

结果如下：

-    1         A
-    2         B
     3    1    C
+         2    B
     4    3    A
     5    4    B
-    6         B
     7    5    A
+         6    C

总结#

上面演示的 Myers 算法是完整的，但是由于频繁地复制数组，它有非常大的空间开销。因此，像 Git 这样的大多数软件使用 diff 算法的线性变体（在原始论文的附录中找到）。这种变体有时可能会产生比标准 Myers 算法质量更低的 diffs（对人类来说更难阅读），但仍然可以确保最短的编辑序列。

目录