使用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]; 
};