1

我尝试将 google diff-match-path 库用于行差异： https ://github.com/google/diff-match-patch/wiki/Line-or-Word-Diffs 。当两个输入的总和超过 65,536 (2^16) 行时，我得到错误的补丁。

这是一个错误（在我的代码或 diff-match-patch 中），还是我遇到了 javascript/nodejs 的已知限制？我可以做些什么来将 dmp 用于更大的文件？

使用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
4

1 回答 1

2

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

为了加快行差异，该算法不比较整个文本，而是用单个 unicode 字符替换每一行。所以替换中的每个字符都映射到哈希图中的一个唯一行。然而，unicode 字符的数量是有限的，当前的实现只是溢出。

这不会导致误报（相同的行仍将被视为相同），但对于自然差异，它可能会以每行 1/65K 的低概率错过一些行差异。

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

通过使用更大的符号目标空间，例如通过使用 2 或 3 个字符来表示唯一行，应该可以将正确的差异缩放到更大的输入。

于 2018-12-04T02:09:31.417 回答