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

Question

使用Javascript，我想检查两个字符串之间有多少差异。

喜欢的东西：

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

• 任何字母添加到名称应该算作每个字母一个变化。
• 更改一个字母应视为每个字母的更改。交换两个
• 字母应该算作两个变化，因为你真的在改变每个
  leter。
• 但是，转移一个字母并插入另一个字符只应该算作一个改变。

例如：

更改“亚历克斯”为5个字母已添加

更改“亚历克斯”为“亚历山大”将是5个变为“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！

Working 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梅龙镇的功能：

Jame's post showing this function

Answer 1

我没有手头上一个Javascript实现本身，但你正在做一些事情为此已有完善的算法。具体而言，我相信您正在寻找两个字符串之间的“Levenshtein距离” - 即插入，替换和删除的数量（假设您将删除视为更改）。

The wikipedia page for Levenshtein distance拥有各种可以从中启动的伪代码实现，以及可能对您有帮助的引用。

Answer 2

Alternative implemenation:

/** 
* 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]; 
};