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

Question

我想比较两个字符串(a before 和 after)并准确检测它们之间的变化和变化。

对于任何变化，我想知道:

1. 变化的起始位置(含，从0开始)
2. 相对于上一段文字的变化结束位置(含，从0开始)
3. “改变”

假设字符串一次只会改变一个地方(例如，永远不会 "Bill"-> "K iln").

此外，我需要开始和结束位置来反射(reflect)变化的类型:

• 如果删除，起始位置和结束位置分别为被删除文本的起始位置和结束位置
• 如果替换，则开始和结束位置分别为“删除”文本的开始和结束位置(更改为“添加”文本)
• 如果插入，开始和结束位置应该相同；文本的入口
• 如果没有变化，让开始和结束位置保持为零，并有一个空的变化

例如:

"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));

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

---

我已经搜索并提出了一个 few other 类似的问题，但它们似乎没有帮助。

Answer 1

我已经阅读了您的代码，您匹配字符串的逻辑对我来说很有意义。它正确记录 ChangeStart、NewChangeEnd 和 OldChangeEnd，并且算法运行正常。您只想知道是否发生了插入、删除 或替换。以下是我的处理方式。

首先，您需要确保在获得第一个不匹配点后，即 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 的值更新为比 ma​​tched 值小 1。如果不匹配，您可以适本地存储这些值。

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

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);

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

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

1. 替换 - 如果 NewText != OldText 并且以上两个条件不满足，则是一个替代品。

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

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

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

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