Levenshtein //Repositório JavaScript

Descrição

Quantidade de caracteres que devem ser removidos, inseridos or substituidos na string A para torná-la igual a string B.
Criado: 2005.11.12

Código (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];
};

Exemplo (Exemplo)

<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>

Ajuda

String.levenshtein(compare: String): String
Retorna a quantidade de inserções, remoções ou alterações necessárias para se obter a string passada como parâmetro.
compare
string que será usada para efetuar a comparação

Ranque (Votos: 3)

3.67