Retirado do meu GIST: https://gist.github.com/1936620 (é uma porta de JAVA)
var levenshtein = function(str1, str2) {
str1 = str1.split("");
str2 = str2.split("");
var distance = [],
l = str1.length,
m = str2.length,
i, j;
for( i = 0; i <= l; i++ ) {
distance[i] = [i];
}
for( j = 0; j <= m; j++ ) {
distance[0][j] = j;
}
for( i = 1; i <= l; i++ ) {
for( j = 1; j <= m; j++ ) {
distance[i][j] = Math.min( distance[i-1][j]+1, distance[i][j-1]+1, distance[i-1][j-1]+
((str1[i-1]==str2[j-1])?0:1) );
}
}
return distance[l][m];
};