Unterschiede zwischen zwei Strings mit Javascript erkennen

Question

Mit Javascript möchte ich überprüfen, wie viele Unterschiede zwischen zwei Strings bestehen.

Etwas wie:

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

• Alle Briefe an den Namen angehängt sollte als eine Änderung pro Brief zählen.
• Das Ändern eines Buchstabens sollte als Änderung pro Buchstabe gezählt werden. Swaping zwei
• Buchstaben sollte als zwei Änderungen zählen, wie Sie wirklich jede
  leter ändern.
• Das Verschieben eines Buchstabens und das Einfügen eines anderen sollte jedoch nur als eine Änderung gezählt werden.

Zum Beispiel:

Ändern "Alex" zu "Alexander" 5 Änderungen würde als 5 Buchstaben

ändern "Alex" auf "Allex" nur eine Änderung würde hinzugefügt worden sein, wie du hast ein "l" hinzugefügt und den Rest verschoben, aber hast sie nicht geändert.

Ändern von "Alexander" zu "Allesander" wäre 2 Änderungen (Hinzufügen des "l" und Ändern von "x" zu einem "s").

Ich kann jeden Namen in ein Feld von Buchstaben aufgeteilt und vergleiche sie wie leicht genug, um in diesen jsFiddle mit der folgenden Funktion:

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

Aber wie kann ich mache das Verschieben von Buchstaben nicht als ein Zählen Veränderung?

---

Update: Hier ist, wie ich es

Levenshtein Entfernung Arbeit bekam, war genau das, was ich brauchte. Danke an 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>

Credit James Westgate für die Funktion:

Jame's post showing this function

Answer 1

I per se keine Javascript-Implementierung auf der Hand haben, aber du machst etwas für die es gut etablierte Algorithmen gibt. Insbesondere glaube ich, dass Sie nach der "Levenshtein-Distanz" zwischen zwei Strings suchen - d. H. Nach der Anzahl der Insertionen, Substitutionen und Deletionen (vorausgesetzt, Sie behandeln eine Deletion als Änderung).

The wikipedia page for Levenshtein distance hat verschiedene Pseudocode-Implementierungen, von denen Sie starten können, und Referenzen, die Ihnen auch helfen können.

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