几年前，我编写了一个内联拼写检查器，并实现了一个Levenshtein算法-因为它是内联的，对于IE8，我做了很多性能优化。
var levDist = function(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];}
