使用Javascript检测两个字符串之间的差异

Question

使用Javascript，我想检查两个字符串之间有多少不同之处。

类似这样的操作：

var oldName = "Alec";
var newName = "Alexander";
var differences = getDifference(oldName, newName) // differences = 6

• 将名字中添加的任何字母视为每个字母一次更改。
• 更改一个字母应该算作每个字母的一次更改。交换两个字母应该算作两次更改，因为您实际上更改了每个字母。
• 但是，移动一个字母并插入另一个字母应该只算作一次更改。

例如：

将 "Alex" 更改为 "Alexander" 应该算作 5 次更改，因为添加了 5 个字母。

将 "Alex" 更改为 "Allex" 只应该算作一次更改，因为你添加了一个 "l" 并移动了其余部分，但没有更改它们。

将 "Alexander" 更改为 "Allesander" 应该算作 2 次更改（添加 "l" 并将 "x" 更改为 "s"）。

我可以将每个名称拆分为字母数组，并像此 jsFiddle 中的函数那样轻松比较它们：

function compareNames(){
    var oldName = $('#old').val().split("");
    var newName = $('#new').val().split("");
    var changeCount = 0;
    var testLength = 0;
    if(oldName.length > newName.length){
        testLength=oldName.length;    
    }
    else testLength=newName.length;
    for(var i=0;i<testLength;i++){
        if(oldName[i]!=newName[i]) {
           changeCount++;           
        }
    }
    alert(changeCount);
}

但是如何解释字母的移动不算作一次更改呢？

---

更新：以下是我使它工作的方法

Levenshtein距离 正是我所需要的。感谢Peter！

工作中的jsFiddle

$(function () {
    $('#compare').click(function () {
        var oldName = $('.compare:eq(0)').val();
        var newName = $('.compare:eq(1)').val();
        var count = levDist(oldName, newName);
        $('#display').html('There are ' + count + ' differences present');
    });
});

function levDist(s, t) {
    var d = []; //2d matrix

    // Step 1
    var n = s.length;
    var m = t.length;

    if (n == 0) return m;
    if (m == 0) return n;

    //Create an array of arrays in javascript (a descending loop is quicker)
    for (var i = n; i >= 0; i--) d[i] = [];

    // Step 2
    for (var i = n; i >= 0; i--) d[i][0] = i;
    for (var j = m; j >= 0; j--) d[0][j] = j;

    // Step 3
    for (var i = 1; i <= n; i++) {
        var s_i = s.charAt(i - 1);

        // Step 4
        for (var j = 1; j <= m; j++) {

            //Check the jagged ld total so far
            if (i == j && d[i][j] > 4) return n;

            var t_j = t.charAt(j - 1);
            var cost = (s_i == t_j) ? 0 : 1; // Step 5

            //Calculate the minimum
            var mi = d[i - 1][j] + 1;
            var b = d[i][j - 1] + 1;
            var c = d[i - 1][j - 1] + cost;

            if (b < mi) mi = b;
            if (c < mi) mi = c;

            d[i][j] = mi; // Step 6

            //Damerau transposition
            if (i > 1 && j > 1 && s_i == t.charAt(j - 2) && s.charAt(i - 2) == t_j) {
                d[i][j] = Math.min(d[i][j], d[i - 2][j - 2] + cost);
            }
        }
    }
    // Step 7
    return d[n][m];
}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.0/jquery.min.js"></script>
<input type="button" id="compare" value="Compare" /><br><br>
<input type="text" id="old" class="compare" value="Alec" />
<input type="text" id="new" class="compare" value="Alexander" />
<br>
<br>
<span id="display"></span>

感谢James Westgate提供的函数：

Jame的帖子展示此功能

- Wesley Smith

---

如果你减去字母会发生什么？例如，从“Alex”减去“Ale”会怎样？ - elclanrs

是的，那也将是一种变化。 - Wesley Smith

这个问题真的需要更多的关注，这太酷了。@DelightedD0D，有两件事情：1. 你是从其他来源得到这个函数还是自己编写的？2. 我可以使用它吗？ - Chris Cirefice

@ChrisCirefice 不好意思，这有点超出我的能力范围。@JamesWestgate 按照我理解编写了该函数 https://dev59.com/Gmct5IYBdhLWcg3wqfL9#11958496 - Wesley Smith

请查看 https://code.google.com/p/google-diff-match-patch/。 - user663031

@torazaburo 这比我之前需要的要复杂一些，但是因为你让我知道了这个存在，所以点赞。肯定值得收藏。我可以看到自己在未来会使用它。谢谢！ - Wesley Smith

Answer 1

我手头没有一个JavaScript的实现 per se ，但您正在进行的工作已经存在了成熟的算法。具体来说，我相信您正在寻找两个字符串之间的"Levenshtein距离"--即插入、替换和删除的次数（假设您将删除视为一种更改）。

Levenshtein距离的维基百科页面有各种伪代码实现，您可以从中开始，并参考其他可能对您有帮助的参考资料。

- Peter

Answer 2

替代实现方法：

/**
 * Computes the Levenshtein edit distance between two strings.
 * @param {string} a
 * @param {string} b
 * @return {number} The edit distance between the two strings.
 */
goog.string.editDistance = function(a, b) {
  var v0 = [];
  var v1 = [];

  if (a == b) {
    return 0;
  }

  if (!a.length || !b.length) {
    return Math.max(a.length, b.length);
  }

  for (var i = 0; i < b.length + 1; i++) {
    v0[i] = i;
  }

  for (var i = 0; i < a.length; i++) {
    v1[0] = i + 1;

    for (var j = 0; j < b.length; j++) {
      var cost = Number(a[i] != b[j]);
      // Cost for the substring is the minimum of adding one character, removing
      // one character, or a swap.
      v1[j + 1] = Math.min(v1[j] + 1, v0[j + 1] + 1, v0[j] + cost);
    }

    for (var j = 0; j < v0.length; j++) {
      v0[j] = v1[j];
    }
  }

  return v1[b.length];
};

- ClojureMostly

---

goog是什么？ - Wesley Smith

这是来自谷歌的闭包库。你可以直接移除 goog.string。 - ClojureMostly