在“Levenshtein距离”中用Javascript中的最佳性能对数组进行sorting
所以我有一个随机的JavaScript数组名称…
[@ larry，@ nicholas，@ notch]等
他们都以@符号开头。 我想用Levenshtein距离对它们进行sorting，以便列表顶部的那些距离search项最近。 目前，我有一些JavaScript使用jQuery的.grep()使用JavaScript .match()方法围绕input的search词在按键：
（自首次发布后编辑的代码）
limitArr = $.grep(imTheCallback, function(n){ return n.match(searchy.toLowerCase()) }); modArr = limitArr.sort(levenshtein(searchy.toLowerCase(), 50)) if (modArr[0].substr(0, 1) == '@') { if (atRes.childred('div').length < 6) { modArr.forEach(function(i){ atRes.append('<div class="oneResult">' + i + '</div>'); }); } } else if (modArr[0].substr(0, 1) == '#') { if (tagRes.children('div').length < 6) { modArr.forEach(function(i){ tagRes.append('<div class="oneResult">' + i + '</div>'); }); } } $('.oneResult:first-child').addClass('active'); $('.oneResult').click(function(){ window.location.href = 'http://hashtag.ly/' + $(this).html(); });
它还有一些if语句，用于检测数组是否包含井号（＃）或提及（@）。 忽略这一点。 imTheCallback是名称的数组，或者是modArr或提到，然后modArr是数组sorting。 然后， .atResults和.tagResults元素是它每次添加到数组中的元素，这将根据input的search词形成一个名称列表。
我也有Levenshtein距离algorithm：
var levenshtein = function(min, split) { // Levenshtein Algorithm Revisited - WebReflection try { split = !("0")[0] } catch(i) { split = true }; return function(a, b) { if (a == b) return 0; if (!a.length || !b.length) return b.length || a.length; if (split) { a = a.split(""); b = b.split("") }; var len1 = a.length + 1, len2 = b.length + 1, I = 0, i = 0, d = [[0]], c, j, J; while (++i < len2) d[0][i] = i; i = 0; while (++i < len1) { J = j = 0; c = a[I]; d[i] = [i]; while(++j < len2) { d[i][j] = min(d[I][j] + 1, d[i][J] + 1, d[I][J] + (c != b[J])); ++J; }; ++I; }; return d[len1 - 1][len2 - 1]; } }(Math.min, false);
我如何使用algorithm（或类似的）到我当前的代码sorting它没有不良的performance？
更新：
所以我现在使用James Westgate的Lev Distfunction。 工作方式快速。 所以性能解决了，现在的问题是使用它的源…
modArr = limitArr.sort(function(a, b){ levDist(a, searchy) levDist(b, searchy) });
我现在的问题是使用.sort()方法的一般理解。 帮助表示赞赏，谢谢。
谢谢！
我几年前写了一个内联拼写检查器，并实现了一个Levenshteinalgorithm – 因为它是内联的，对于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]; }
我来到这个解决scheme：
var levenshtein = (function() { var row2 = []; return function(s1, s2) { if (s1 === s2) { return 0; } else { var s1_len = s1.length, s2_len = s2.length; if (s1_len && s2_len) { var i1 = 0, i2 = 0, a, b, c, c2, row = row2; while (i1 < s1_len) row[i1] = ++i1; while (i2 < s2_len) { c2 = s2.charCodeAt(i2); a = i2; ++i2; b = i2; for (i1 = 0; i1 < s1_len; ++i1) { c = a + (s1.charCodeAt(i1) === c2 ? 0 : 1); a = row[i1]; b = b < a ? (b < c ? b + 1 : c) : (a < c ? a + 1 : c); row[i1] = b; } } return b; } else { return s1_len + s2_len; } } }; })();
另见http://jsperf.com/levenshtein-distance/12
大多数速度是通过消除一些arrays用法获得的。
更新： http : //jsperf.com/levenshtein-distance/5
新修订版歼灭所有其他基准。 由于我没有IE8 / 9/10testing环境，所以我特别追逐Chromium / Firefox的性能，但所做的优化应该适用于大多数浏览器。
Levenshtein距离
执行Levenshtein距离的matrix可以重复使用。 这是优化的一个明显的目标（但要小心，现在对string长度施加了一个限制（除非是dynamic调整matrix大小））。
jsPerf Revision 5中没有追求的唯一select就是记忆。 根据您对Levenshtein距离的使用情况，这可能会有很大的帮助，但由于其具体的实现性而被忽略。
// Cache the matrix. Note this implementation is limited to // strings of 64 char or less. This could be altered to update // dynamically, or a larger value could be used. var matrix = []; for (var i = 0; i < 64; i++) { matrix[i] = [i]; matrix[i].length = 64; } for (var i = 0; i < 64; i++) { matrix[0][i] = i; } // Functional implementation of Levenshtein Distance. String.levenshteinDistance = function(__this, that, limit) { var thisLength = __this.length, thatLength = that.length; if (Math.abs(thisLength - thatLength) > (limit || 32)) return limit || 32; if (thisLength === 0) return thatLength; if (thatLength === 0) return thisLength; // Calculate matrix. var this_i, that_j, cost, min, t; for (i = 1; i <= thisLength; ++i) { this_i = __this[i-1]; for (j = 1; j <= thatLength; ++j) { // Check the jagged ld total so far if (i === j && matrix[i][j] > 4) return thisLength; that_j = that[j-1]; cost = (this_i === that_j) ? 0 : 1; // Chars already match, no ++op to count. // Calculate the minimum (much faster than Math.min(...)). min = matrix[i - 1][j ] + 1; // Deletion. if ((t = matrix[i ][j - 1] + 1 ) < min) min = t; // Insertion. if ((t = matrix[i - 1][j - 1] + cost) < min) min = t; // Substitution. matrix[i][j] = min; // Update matrix. } } return matrix[thisLength][thatLength]; };
Damerau-Levenshtein距离
jsperf.com/damerau-levenshtein-distance
Damerau-Levenshtein距离是对Levenshtein距离的小修改，包括换位。 有很less的优化。
// Damerau transposition. if (i > 1 && j > 1 && this_i === that[j-2] && this[i-2] === that_j && (t = matrix[i-2][j-2]+cost) < matrix[i][j]) matrix[i][j] = t;
sortingalgorithm
这个答案的第二部分是select一个合适的sortingfunction。 我将很快将优化的sorting函数上传到http://jsperf.com/sort 。
我肯定会build议使用更好的Levenshtein方法，比如@James Westgate的答案。
也就是说，DOM操作往往是一个很大的开销。 你当然可以改善你的jQuery的使用。
在上面的例子中，你的循环是相当小的，但是把每个oneResult生成的html连接成一个单一的string，并且在循环结尾做一个append将会更有效率。
你的select器很慢。 $('.oneResult')将searchDOM中的所有元素，并在较旧的IE浏览器中testing它们的className 。 你可能想要考虑像atRes.find('.oneResult')来search的范围。
在添加click处理程序的情况下，我们可能希望更好地避免在每个keyup上设置处理程序。 您可以通过在atRest上设置一个处理程序来利用事件委托来处理您在设置keyup处理程序的同一个块中的所有结果：
atRest.on('click', '.oneResult', function(){ window.location.href = 'http://hashtag.ly/' + $(this).html(); });
有关更多信息，请参阅http://api.jquery.com/on/ 。
这样做的明显方法是将每个string映射到（距离，string）对，然后对这个列表进行sorting，然后再次丢弃距离。 这样你才能保证levenstein距离只需要计算一次。 也许首先合并重复。
如果你仍然需要这个，我实现了levenshtein距离计算的一个非常高性能的实现。
function levenshtein(s, t) { if (s === t) { return 0; } var n = s.length, m = t.length; if (n === 0 || m === 0) { return n + m; } var x = 0, y, a, b, c, d, g, h, k; var p = new Array(n); for (y = 0; y < n;) { p[y] = ++y; } for (; (x + 3) < m; x += 4) { var e1 = t.charCodeAt(x); var e2 = t.charCodeAt(x + 1); var e3 = t.charCodeAt(x + 2); var e4 = t.charCodeAt(x + 3); c = x; b = x + 1; d = x + 2; g = x + 3; h = x + 4; for (y = 0; y < n; y++) { k = s.charCodeAt(y); a = p[y]; if (a < c || b < c) { c = (a > b ? b + 1 : a + 1); } else { if (e1 !== k) { c++; } } if (c < b || d < b) { b = (c > d ? d + 1 : c + 1); } else { if (e2 !== k) { b++; } } if (b < d || g < d) { d = (b > g ? g + 1 : b + 1); } else { if (e3 !== k) { d++; } } if (d < g || h < g) { g = (d > h ? h + 1 : d + 1); } else { if (e4 !== k) { g++; } } p[y] = h = g; g = d; d = b; b = c; c = a; } } for (; x < m;) { var e = t.charCodeAt(x); c = x; d = ++x; for (y = 0; y < n; y++) { a = p[y]; if (a < c || d < c) { d = (a > d ? d + 1 : a + 1); } else { if (e !== s.charCodeAt(y)) { d = c + 1; } else { d = c; } } p[y] = d; c = a; } h = d; } return h; }
这是我的答案类似的问题最快的通用Levenshtein Javascript实现
更新
上面的改进版本现在在github / npm上，见https://github.com/gustf/js-levenshtein
我刚刚写了一个新的修订： http : //jsperf.com/levenshtein-algorithms/16
这个修订比其他的更快。 即使在IE浏览器=）
