从两个字符串中抓取编辑

Question

我将对我的问题进行一些深入探讨,你可以跳到TL;如果你不想阅读所有这些,DR

我想做什么

我需要存储一个可以由用户编辑的"文件" (文本文档).如果我有原始文件(可能很大)

Lorem ipsum dolor坐着

并且用户要进行更改:

Foo ipsum amet_坐下

基本上,我有原始字符串和用户编辑的字符串.我想找到差异,"编辑".防止存储非常大的字符串重复.我想存储原始和"编辑".然后将编辑应用于原始.有点像重复数据删除.问题是我不知道不同的编辑方式是什么,我还需要能够将这些编辑应用于字符串.

尝试

因为文本可能很大,我想知道在不存储两个单独版本的情况下,将文本编辑存储到文本的最"有效"方式是什么.我的第一个猜测是:

var str = 'Original String of text...'.split(' ') || [],
    mod = 'Modified String of text...'.split(' ') || [], i, edits = [];

for (i = 0; i < str.length; i += 1) {
    edits.push(str[i]===mod[i] ? undefined : mod[i]);
}

console.log(edits); // ["Modified", null, null, null] (desired output)

然后回复:

for (i = 0; i < str.length; i += 1) {
    str[i] = edits[i] || str[i];
}
str.join(' '); // "Modified String of text..."

基本上,我试图将空格分成数组.比较阵列并存储差异.然后应用差异以生成修改后的版本

问题

但是如果要改变空间的数量,就会出现问题:

str:Original String of text... mod:OriginalString of text...

输出: OriginalString of text... text...

我想要的输出: OriginalString of text...

---

即使我转str.length用mod.length和edits.length这样的:

// Get edits
var str = 'Original String of text...'.split(' ') || [],
    mod = 'Modified String of text...'.split(' ') || [], i, edits = [];

for (i = 0; i < mod.length; i += 1) {
    edits.push(str[i]===mod[i] ? undefined : mod[i]);
}

// Apply edits
var final = [];
for (i = 0; i < edits.length; i += 1) {
    final[i] = edits[i] || str[i];
}
final = final.join(' ');

edits将是:["ModifiedString", "of", "text..."]结果使整个'存储编辑的东西无用.更糟糕的是,如果要添加/删除一个单词.如果str成为Original String of lots of text....输出仍然是相同的.

---

我可以看出他们在做这件事的方式上有很多缺陷,但我想不出任何其他方式.

片段:

document.getElementById('go').onclick = function() {
  var str = document.getElementById('a').value.split(' ') || [],
    mod = document.getElementById('b').value.split(' ') || [],
    i, edits = [];

  for (i = 0; i < mod.length; i += 1) {
    edits.push(str[i] === mod[i] ? undefined : mod[i]);
  }

  // Apply edits
  var final = [];
  for (i = 0; i < edits.length; i += 1) {
    final[i] = edits[i] || str[i];
  }
  final = final.join(' ');
  alert(final);
};

document.getElementById('go2').onclick = function() {
  var str = document.getElementById('a').value.split(' ') || [],
    mod = document.getElementById('b').value.split(' ') || [],
    i, edits = [];

  for (i = 0; i < str.length; i += 1) {
    edits.push(str[i] === mod[i] ? undefined : mod[i]);
  }

  for (i = 0; i < str.length; i += 1) {
    str[i] = edits[i] || str[i];
  }
  alert(str.join(' ')); // "Modified String of text..."
};

Base String:
<input id="a">
<br/>Modified String:
<input id="b" />
<br/>
<button id="go">Second method</button>
<button id="go2">First Method</button>

TL; DR:

你如何找到两个字符串之间的变化？

---

我正在处理大块文本,每个文本大约是一兆字节的百万字节.这是在浏览器上运行的

Answer 1

仅使用 JavaScript 运行适当的 diff 可能会很慢，但这取决于性能要求和 diff 的质量，当然还取决于必须运行的频率。

一种非常有效的方法是在用户实际编辑文档时跟踪编辑，并仅在完成后立即存储这些更改。为此，您可以使用 ACE 编辑器或任何其他支持更改跟踪的编辑器。

http://ace.c9.io/

ACE 在编辑文档时跟踪更改。ACE 编辑器以易于理解的格式跟踪命令，例如：

{"action":"insertText","range":{"start":{"row":0,"column":0},
    "end":{"row":0,"column":1}},"text":"d"}

您可以挂钩 ACE 编辑器的更改并监听更改事件：

var changeList = []; // list of changes
// editor is here the ACE editor instance for example
var editor = ace.edit(document.getElementById("editorDivId"));
editor.setValue("original text contents");
editor.on("change", function(e) {
    // e.data has the change
    var cmd = e.data;
    var range = cmd.range;
    if(cmd.action=="insertText") {
        changeList.push([
            1, 
            range.start.row,
            range.start.column,
            range.end.row,
            range.end.column,
            cmd.text
        ])
    }
    if(cmd.action=="removeText") {
        changeList.push([
                2, 
                range.start.row,
                range.start.column,
                range.end.row,
                range.end.column,
                cmd.text
            ])
    }
    if(cmd.action=="insertLines") {
        changeList.push([
                3, 
                range.start.row,
                range.start.column,
                range.end.row,
                range.end.column,
                cmd.lines
            ])
    }
    if(cmd.action=="removeLines") {
        changeList.push([
                4, 
                range.start.row,
                range.start.column,
                range.end.row,
                range.end.column,
                cmd.lines,
                cmd.nl
            ])
    }
});

要了解它的工作原理，只需创建一些捕获更改的测试运行即可。基本上只有那些命令：

1. 插入文本
2. 删除文本
3. 插入行
4. 删除行

从文本中删除换行符可能有点棘手。

当您获得此更改列表后，您就可以重播对文本文件的更改了。您甚至可以将类似或重叠的更改合并为单个更改 - 例如，插入后续字符可以合并为单个更改。

当你测试这个时，会出现一些问题，将字符串组合回文本并不简单，但相当可行，并且不应超过 100 行左右的代码。

好处是，完成后，您还可以轻松使用撤消和重做命令，因此您可以重播整个编辑过程。