erkennen Unterschiede zwischen zwei strings mit Javascript
Mit Javascript, ich möchte, um zu überprüfen, wie viele Unterschiede es zwischen den zwei Zeichenfolgen.
Etwas wie:
var oldName = "Alec";
var newName = "Alexander";
var differences = getDifference(oldName, newName) //differences = 6
- Irgendwelche Buchstaben Hinzugefügt, um den Namen zählen als eine änderung pro Brief.
- Verändert ein Brief sollte zählen als eine änderung pro Brief. Austauschen zwei
- Buchstaben zählen als zwei Veränderungen als Ihr wirklich ändern jede
leter. - Jedoch die Verlagerung einen Brief und einfügen von einem anderen sollte nur als eine änderung gezählt.
Beispiel:
Ändern "Alex" zu "Alexander" wäre 5 änderungen als 5 Buchstaben Hinzugefügt wurden
Ändern "Alex" zu "Allex" wäre nur eine änderung, wie Sie Hinzugefügt ein "l" und verschoben den rest über, aber nicht ändern Sie
Ändern "Alexander" zu "Allesander"würde 2 änderungen (durch hinzufügen der "l" und ändern Sie "x" ein "s").
Kann ich split jeden Namen in ein array von Buchstaben und vergleichen Sie Sie leicht genug, wie in diesem jsFiddle mit den unten 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 das Konto für die Verschiebung der Buchstaben nicht zählen, da eine änderung?
Update: Hier ist, wie ich es geschafft habe
Die Levenshtein-Distanz war genau das, was ich brauchte. Vielen Dank an Peter!
JS:
$(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];
}
HTML:
<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>
Kredit zu James Westgate für die Funktion:
Jame ' s post zeigt diese Funktion
- Was passiert, wenn Sie subtrahieren Buchstaben? Also "Alex" zu "Ale" zum Beispiel?
- Ja, dass wäre eine änderung zu
- Dieser Frage wirklich braucht mehr Aufmerksamkeit, das ist so cool. @DelightedD0D, zwei Dinge: 1. hast du diese Funktion aus einer anderen Quelle oder hast du den code selbst? 2. Habe ich die Erlaubnis es zu benutzen?
- Nee, N outta my league,@JamesWestgate schrieb die Funktion so wie ich es verstehe stackoverflow.com/a/11958496/1376624
- Check out code.google.com/p/google-diff-match-patch.
- Das ist ein bisschen komplexer als das, was ich brauchte, zurück, wenn dies gefragt wurde, aber +1 für die ließ mich wissen, dass da draußen war. Lohnt sich ein Lesezeichen für sicher. Ich sah mich schon mit, dass in die Zukunft. Danke!
Du musst angemeldet sein, um einen Kommentar abzugeben.
Habe ich nicht eine Javascript-Implementierung auf der hand per se, aber Sie tun etwas für die etablierten algorithmen existieren. Speziell, ich glaube, Sie suchen die "Levenshtein-Distanz" zwischen zwei strings -- also die Anzahl der Einfügungen, Ersetzungen und Löschungen (vorausgesetzt, Sie behandeln eine Löschung als änderung).
Die wikipedia-Seite für die Levenshtein-Distanz hat verschiedene pseudo-code-Implementierungen, von denen Sie starten konnte, und Verweise, die möglicherweise auch helfen Ihnen.
Alternative implementations:
goog
?goog.string