在Javascript中查找字符串之间的差异

Question

我想比较两个字符串(前后),并准确检测它们之间的位置和变化.

对于任何改变,我想知道:

1. 变更的起始位置(包括从0开始)
2. 结束相对于前一文本的更改(包括从0开始)的位置
3. 改变"

假设字符串一次只在一个地方改变(例如,从不" B il l " - >" K il n ").

另外,我需要开始和结束位置来反映变化的类型:

• 如果删除,则开始和结束位置应分别是已删除文本的开始和结束位置
• 如果替换,开始和结束位置应分别是"已删除"文本的开始和结束位置(更改将是"添加"文本)
• 如果插入,开始和结束位置应该相同; 文本的切入点
• 如果没有变化,则让开始和结束位置保持为零,空位变化

例如:

"0123456789" -> "03456789"  
Start: 1, End: 2, Change: "" (deletion)

"03456789" -> "0123456789"  
Start: 1, End: 1, Change: "12" (insertion)

"Hello World!" -> "Hello Aliens!"  
Start: 6, End: 10, Change: "Aliens" (replacement)

"Hi" -> "Hi"  
Start: 0, End: 0, Change: "" (no change)

我能够在某种程度上检测到已更改文本的位置,但它并不适用于所有情况,因为为了准确地执行此操作,我需要知道所做的更改.

var OldText = "My edited string!";
var NewText = "My first string!";

var ChangeStart = 0;
var NewChangeEnd = 0;
var OldChangeEnd = 0;
console.log("Comparing start:");
for (var i = 0; i < NewText.length; i++) {
    console.log(i + ": " + NewText[i] + " -> " + OldText[i]);
    if (NewText[i] != OldText[i]) {
        ChangeStart = i;
        break;
    }
}
console.log("Comparing end:");
// "Addition"?
if (NewText.length > OldText.length) {
    for (var i = 1; i < NewText.length; i++) {
        console.log(i + "(N: " + (NewText.length - i) + " O: " + (OldText.length - i) + ": " + NewText.substring(NewText.length - i, NewText.length - i + 1) + " -> " + OldText.substring(OldText.length - i, OldText.length - i + 1));
        if (NewText.substring(NewText.length - i, NewText.length - i + 1) != OldText.substring(OldText.length - i, OldText.length - i + 1)) {
            NewChangeEnd = NewText.length - i;
            OldChangeEnd = OldText.length - i;
            break;
        }
    }
// "Deletion"?
} else if (NewText.length < OldText.length) {
    for (var i = 1; i < OldText.length; i++) {
        console.log(i + "(N: " + (NewText.length - i) + " O: " + (OldText.length - i) + ": " + NewText.substring(NewText.length - i, NewText.length - i + 1) + " -> " + OldText.substring(OldText.length - i, OldText.length - i + 1));
        if (NewText.substring(NewText.length - i, NewText.length - i + 1) != OldText.substring(OldText.length - i, OldText.length - i + 1)) {
            NewChangeEnd = NewText.length - i;
            OldChangeEnd = OldText.length - i;
            break;
        }
    }
// Same length...
} else {
    // Do something
}
console.log("Change start: " + ChangeStart);
console.log("NChange end : " + NewChangeEnd);
console.log("OChange end : " + OldChangeEnd);
console.log("Change: " + OldText.substring(ChangeStart, OldChangeEnd + 1));

如何判断插入,删除或替换是否发生？

---

我搜索并提出了一些 其他类似的问题,但它们似乎没有帮助.

Answer 1

我已经浏览了您的代码，您匹配字符串的逻辑对我来说很有意义。它正确地记录了,ChangeStart并且算法运行正常。您只想知道是否发生了插入、删除或替换。以下是我的做法。NewChangeEndOldChangeEnd

首先，您需要确保在获得第一个不匹配点之后，ChangeStart即当您从末尾遍历字符串时，索引不应该交叉ChangeStart。

我给你举个例子。考虑以下字符串：

 var NewText = "Hello Worllolds!";
 var OldText = "Hello Worlds!";

 ChangeStart -> 10 //Makes sense
 OldChangeEnd -> 8
 NewChangeEnd -> 11

 console.log("Change: " + NewText.substring(ChangeStart, NewChangeEnd + 1)); 
 //Ouputs "lo"

这种情况下的问题是，当它从后面开始匹配时，流程是这样的：

 Comparing end: 
  1(N: 12 O: 12: ! -> !) 
  2(N: 11 O: 11: s -> s) 
  3(N: 10 O: 10: d -> d)  -> You need to stop here!

 //Although there is not a mismatch, but we have reached ChangeStart and 
 //we have already established that characters from 0 -> ChangeStart-1 match
 //That is why it outputs "lo" instead of "lol"

假设我刚才所说的是有道理的，您只需要for像这样修改循环：

 if (NewText.length > OldText.length) {
 for (var i = 1; i < NewText.length && ((OldText.length-i)>=ChangeStart); i++) {
  ...

    NewChangeEnd = NewText.length - i -1;
    OldChangeEnd = OldText.length - i -1;
  if(//Mismatch condition reached){
         //break..That code is fine.
    }
 }

此条件 ->(OldText.length-i)>=ChangeStart处理我提到的异常，因此for如果达到此条件，循环将自动终止。然而，正如我所提到的，在遇到不匹配之前可能会达到此条件，就像我刚才演示的那样。因此，您需要将NewChangeEnd和的值更新OldChangeEnd为比匹配值小 1。如果出现不匹配的情况，您可以适当地存储这些值。

我们可以将这两个条件包装在我们知道绝对不else -if正确的情况下，即它是替换或删除，而不是 an 。同样也意味着根据您的示例，它可能是替换或插入，这是有道理的。所以可能是这样的：NewText.length > OldText.lengthNewText.length > OldText.lengthelse

else {
for (var i = 1; i < OldText.length && ((OldText.length-i)>=ChangeStart); i++) { 

    ...
    NewChangeEnd = NewText.length - i -1;
    OldChangeEnd = OldText.length - i -1;
  if(//Mismatch condition reached){
         //break..That code is fine.
    }
 }

如果您已经了解到目前为止的细微变化，那么识别具体情况就非常简单：

1. 删除- 条件 -> ChangeStart > NewChangeEnd。从 中删除了字符串ChangeStart -> OldChangeEnd。

删除的文字 ->OldText.substring(ChangeStart, OldChangeEnd + 1);

2. 插入- 条件 -> ChangeStart > OldChangeEnd。已在 处插入字符串ChangeStart。

插入的文本->NewText.substring(ChangeStart, NewChangeEnd + 1);

3. 更换- 如果不满足NewText != OldText上述两个条件，则为更换。

旧字符串中的文本已被替换 -> OldText.substring(ChangeStart, OldChangeEnd + 1);

替换文本 ->NewText.substring(ChangeStart, NewChangeEnd + 1);

OldText被替换的开始和结束位置->ChangeStart -> OldChangeEnd

我创建了一个jsfiddle，其中包含我在您的代码中提到的更改。您可能想检查一下。希望它能让您朝着正确的方向开始。