代码之家 › 专栏 › 技术社区 › tkruse

为什么差异匹配补丁断线差异超过65K线

google-diff-match-patch node.js javascript

1

tkruse · 技术社区 · 6 年前

我尝试使用google diff match路径库进行线条差异: https://github.com/google/diff-match-patch/wiki/Line-or-Word-Diffs .当两个输入的行总和超过65536(2^16)行时,我会得到错误的补丁。

这是一个bug(在我的代码或diff-match补丁中),还是我遇到了已知的javascript/nodejs限制?我能用d-m-p处理更大的文件吗?

使用 node version v6.3.1, diff-match-patch 1.0.4

这个脚本重现了这个问题

var diff_match_patch = require("diff-match-patch")

// function copied from google wiki 
// https://github.com/google/diff-match-patch/wiki/Line-or-Word-Diffs
function diff_lineMode(text1, text2) {
  var dmp = new diff_match_patch();
  var a = dmp.diff_linesToChars_(text1, text2);
  var lineText1 = a.chars1;
  var lineText2 = a.chars2;
  var lineArray = a.lineArray;
  var diffs = dmp.diff_main(lineText1, lineText2, false);
  dmp.diff_charsToLines_(diffs, lineArray);
  return diffs;
}

// reproduce problem by diffing string with many lines to "abcd"
for (let size = 65534; size < 65538; size += 1) {
  let text1 = "";
  for (let i = 0; i < size; i++) {
    text1 += i + "\n";
  }

  var patches = diff_lineMode(text1, "abcb")
  console.log("######## Size: " + size + ": patches " + patches.length)
  for (let i = 0; i < patches.length; i++) {
    // patch[0] is action, patch[1] is value
    var action = patches[i][0] < 0 ? "remove" : (patches[i][0] > 0 ? "add" : "keep")
    console.log("patch" + i + ": " + action + "\n" + patches[i][1].substring(0, 10))
  }
}

给出这些输出:

######## Size: 65534: patches 2
patch0: remove
0
1
2
3
4

patch1: add
abcb
######## Size: 65535: patches 2
patch0: remove
0
1
2
3
4

patch1: add

######## Size: 65536: patches 2
patch0: keep
0

patch1: remove
1
2
3
4
5

######## Size: 65537: patches 3
patch0: remove
0

patch1: keep
1

patch2: remove
2
3
4
5
6

1 回复 | 直到 6 年前

1

2

tkruse 6 年前

这是ES5和将行映射到16位unicode字符的算法的限制。在ES6上,它可以扩展到2^21位,覆盖更长的文件。

为了加快行扩散,该算法不比较整个文本,而是用单个unicode字符替换每一行。因此,替换中的每个字符都映射到hashmap中唯一的一行。然而,unicode字符的数量是有限的,当前的实现只是溢出。

这不会导致误报(相同的线路仍然被认为是相同的),但它可能会在自然差异的低概率(每线1/65K)下漏掉一些线路差异。

而且它可以防止补丁被可靠地映射回原始文本行,因为不同的行被映射到同一个字符,所以逆过程将所有这些字符映射到第一个映射行。

通过使用更大的符号目标空间,例如通过使用2或3个字符来表示唯一的线,应该可以将正确的扩散扩展到更大的输入。