rileva le differenze tra due stringhe con Javascript

Question

Con Javascript, voglio verificare quante differenze ci sono tra due stringhe.

Qualcosa di simile:

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

• Tutte le lettere aggiunte al nome dovrebbe contare come un cambio a lettera.
• La modifica di una lettera deve essere considerata come una modifica per lettera. Lo scambio di due
• lettere deve essere considerato come due modifiche, in base alla modifica effettiva di ciascun contatore
  .
• Tuttavia, lo spostamento di una lettera e l'inserimento di un'altra deve essere considerato come una sola modifica.

Ad esempio:

Modifica "Alex" a "Alexander" Sarebbe 5 modifiche sono state aggiunte 5 lettere

Modifica "Alex" a "Allex" sarebbe solo un cambiamento come hai aggiunto una "l" e hai spostato il resto ma non li hai modificati

Cambiare "Alexander" in "Allesander" corrisponderebbe a 2 modifiche (aggiungendo "l" e cambiando "x" a "s").

posso dividere ogni nome in un array di lettere e di confrontarli abbastanza facile come in questo jsFiddle con la funzione di seguito:

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

Ma come posso spiegare lo spostamento di lettere senza contare come modificare?

---

Aggiornamento: Ecco come ho ottenuto che funziona

Levenshtein distanza era esattamente quello che mi serviva. Grazie a 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>

credito a James Westgate per la funzione:

Jame's post showing this function

Answer 1

Non ho un'implementazione JavaScript a portata di mano per sé, ma stai facendo qualcosa per cui esistono algoritmi consolidati. Nello specifico, credo che tu stia cercando la "distanza di Levenshtein" tra due stringhe - cioè il numero di inserzioni, sostituzioni e cancellazioni (supponendo che tu stia trattando una cancellazione come una modifica).

The wikipedia page for Levenshtein distance ha varie implementazioni di pseudo-codice da cui è possibile iniziare e riferimenti che possono anche aiutare.

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