Почему Diff-match-patch ломаная линефф за пределами линий 65K - PullRequest
Новая
       50

Почему Diff-match-patch ломаная линефф за пределами линий 65K

0 голосов
/ 03 декабря 2018

Я пытаюсь использовать библиотеку 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

1 Ответ

0 голосов
/ 04 декабря 2018

Это ограничение от ES5 и алгоритма, отображающего строки в 16-битные символы Unicode.На ES6 его можно расширить до 2 ^ 21 бит, охватывая более длинные файлы.

Для ускорения различий строк алгоритм не сравнивает весь текст, а заменяет каждую строку одним символом Unicode.Таким образом, каждый символ в замене отображается на одну уникальную строку в хэш-карте.Число символов Юникода, однако, ограничено, и текущая реализация просто переполняется.

Это не приведет к ложным срабатываниям (одни и те же строки будут считаться одинаковыми), но может пропустить некоторые различия строк при низкой вероятности1 / 65K на строку для естественных различий.

И это предотвращает надежное сопоставление патчей с исходными текстовыми строками, поскольку разные строки отображаются на один и тот же символ, поэтому обратный процесс сопоставляет все такие символы спервая отображенная строка.

Должна быть возможность масштабирования правильного дифференцирования до гораздо больших входов с использованием большего целевого пространства символов, например с помощью 2 или 3 символов для представления уникальных линий.

...