Levenshtein //JavaScript Repository

Description

Amount of characters that must be removed, inserted or replaced on the string A to make it equal to string B.
Created: 2005.11.12

Code (Download)

//+ Carlos R. L. Rodrigues
//@ http://jsfromhell.com/string/levenshtein [rev. #1]

String.prototype.levenshtein = function(c){
    var s, l = (s = this.split("")).length, t = (c = c.split("")).length, i, j, m, n;
    if(!(l || t)) return Math.max(l, t);
    for(var a = [], i = l + 1; i; a[--i] = [i]);
    for(i = t + 1; a[0][--i] = i;);
    for(i = -1, m = s.length; ++i < m;)
        for(j = -1, n = c.length; ++j < n;)
            a[(i *= 1) + 1][(j *= 1) + 1] = Math.min(a[i][j + 1] + 1, a[i + 1][j] + 1, a[i][j] + (s[i] != c[j]));
    return a[l][t];
};

Example (Example)

<script type="text/javascript">
//<![CDATA[

var s = "Carlos", s2 = "Carlitos";
document.write(
    "\"", s,"\".levenshtein(\"", s2,"\") = ", s.levenshtein(s2), " modifica?es/inser?es/remo?es"
);

//]]>
</script>

Help

String.levenshtein(compare: String): String
Returns the amount of characters that must be removed, inserted or replaced on the string A to make it equal to string B.
compare
string that will be used to make the comparison

Rank (Votes: 3)

3.67