Javascriptで2つの文字列の違いを検出する

Question

Javascriptでは、2つの文字列の間にいくつの違いがあるかを確認したいと思います。名前に追加された文字が文字ごとに1つの変更としてカウントすべきである

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

• ：よう

  何か。

• レターの変更は、レターごとの変更としてカウントされます。スワップ2つの
• の文字は実際にはそれぞれ
  という名前で変更されるため、2つの変更としてカウントされます。
• ただし、文字をシフトして別の文字を挿入すると、1つの変更としてカウントされます。例えば

：5つの文字は「アレックス」を変更する

を追加されているとして、「アレキサンダー」は5つの変更になるために「アレックス」を変更する

は「Allexでは」だけのように1つの変更になります"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); 
} 

しかし、私はとしてカウントしない文字のシフトを占めることができる方法変化する？

---

アップデート：ここで私はは私がまさに必要だった

レーベンシュタイン距離を作業それを得た方法です。ピーターに感謝！

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>

機能のためのジェームズウエストゲートへのクレジット：

Jame's post showing this function

Answer 1

私は自体手にJavascriptの実装を持っていません、あなたは何かしているよく確立されたアルゴリズムが存在する。具体的には、私はあなたが2つの文字列の間にある "Levenshtein distance"を探していると考えています。つまり、削除、変更、削除の回数です。

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