按“Levenshtein Distance”对数组进行排序,在Javascript中具有最佳性能
Sort an array by the "Levenshtein Distance" with best performance in Javascript
所以我有一个随机的javascript名称数组...
[@larry,@nicholas,@notch]等
它们都以 @ 符号开头。我想按列文施泰因距离对它们进行排序,以便列表顶部的那些最接近搜索词。目前,我有一些javascript使用它jQuery的.grep()
,在按键时使用javascript .match()
方法围绕输入的搜索词:
(自首次发布以来编辑的代码)
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
是排序的数组。然后,.atResults
和.tagResults
元素是它每次在数组中附加到的元素,这根据输入的搜索词形成名称列表。
我也有Levenshtein距离算法:
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);
如何在当前代码中使用算法(或类似的算法)以对其进行排序而不会降低性能?
更新:
所以我现在使用James Westgate的Lev Dist函数。工作方式很快。所以性能解决了,现在的问题是将其与源代码一起使用......
modArr = limitArr.sort(function(a, b){
levDist(a, searchy)
levDist(b, searchy)
});
我现在的问题是对使用.sort()
方法的一般理解。感谢帮助,谢谢。
谢谢!
几年前我写了一个内联拼写检查器并实现了 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];
}
我得出了这个解决方案:
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
大多数速度是通过消除一些阵列使用而获得的。
更新: http://jsperf.com/levenshtein-distance/5
新修订版取消了所有其他基准。我特别追求Chromium/Firefox的性能,因为我没有IE8/9/10测试环境,但所做的优化通常应该适用于大多数浏览器。
列文施泰因距离
执行列文施泰因距离的矩阵可以一次又一次地重复使用。这是一个明显的优化目标(但要小心,这现在对字符串长度施加了限制(除非您要动态调整矩阵的大小))。
jsPerf 修订版 5 中未追求的唯一优化选项是记忆。根据您对Levenshtein Distance的使用,这可能会有很大帮助,但由于其实现特定性质而被省略。
// 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];
};
达梅劳-列文施泰因距离
jsperf.com/damerau-levenshtein-distance
Damerau-Levenshtein Distance是对Levenshtein Distance的一个小修改,包括换位。几乎没有什么需要优化的。
// 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;
排序算法
这个答案的第二部分是选择合适的排序函数。我将很快将优化的排序函数上传到 http://jsperf.com/sort。
如果您仍然需要它,我实现了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;
}
这是我对类似SO问题的回答最快的通用Levenshtein Javascript实现
更新
上述内容的改进版本现在在 github/npm 上,请参见https://github.com/gustf/js-levenshtein
这样做的明显方法是将每个字符串映射到一个(距离,字符串)对,然后对此列表进行排序,然后再次删除距离。通过这种方式,您可以确保莱文斯坦距离只需计算一次。也许也先合并重复项。
我肯定会建议使用更好的Levenshtein方法,就像@James Westgate的答案一样。
也就是说,DOM 操作通常是一笔巨大的开支。你当然可以提高你的jQuery使用率。
在上面的示例中,您的循环相当小,但是将为每个oneResult
生成的 html 连接到单个字符串并在循环结束时执行一个append
将更有效。
您的选择器很慢。 $('.oneResult')
将搜索 DOM 中的所有元素,并在较旧的 IE 浏览器中测试它们的className
。您可能需要考虑类似 atRes.find('.oneResult')
来限定搜索范围。
在添加click
处理程序的情况下,我们可能希望更好地避免在每个keyup
上设置处理程序。您可以通过在atRest
上为要设置keyup
处理程序的同一块中的所有结果设置单个处理程序来利用事件委派:
atRest.on('click', '.oneResult', function(){
window.location.href = 'http://hashtag.ly/' + $(this).html();
});
有关详细信息,请参阅 http://api.jquery.com/on/。
我刚刚写了一个新的修订版:http://jsperf.com/levenshtein-algorithms/16
function levenshtein(a, b) {
if (a === b) return 0;
var aLen = a.length;
var bLen = b.length;
if (0 === aLen) return bLen;
if (0 === bLen) return aLen;
var len = aLen + 1;
var v0 = new Array(len);
var v1 = new Array(len);
var i = 0;
var j = 0;
var c2, min, tmp;
while (i < len) v0[i] = i++;
while (j < bLen) {
c2 = b.charAt(j++);
v1[0] = j;
i = 0;
while (i < aLen) {
min = v0[i] - (a.charAt(i) === c2 ? 1 : 0);
if (v1[i] < min) min = v1[i];
if (v0[++i] < min) min = v0[i];
v1[i] = min + 1;
}
tmp = v0;
v0 = v1;
v1 = tmp;
}
return v0[aLen];
}
此修订版比其他修订版更快。甚至可以在IE上工作=)
- 它是否创建了许多不利于JavaScript性能的变量
- Javascript性能-在dom上迭代并添加侦听器
- 从自执行函数返回函数的Javascript性能命中率
- 循环的 JavaScript 性能问题
- Javascript性能:如何在数组中循环并检查每个值比indexOf、search和match更快
- 多年来浏览器的Javascript性能改进
- JavaScript性能预热
- 在JavaScript性能方面模拟结构处理的C数组
- 持续集成过程中的Javascript性能测试
- 奇怪的 JavaScript 性能取决于变量范围
- 基于 Chrome 的 JavaScript 性能滞后
- Javascript性能 - 如何提高小脚本的性能
- JavaScript 性能 - 除法还是乘法?/与*
- 避免单个变量是否会加快 JavaScript 性能
- 后台的Javascript性能测试
- 如何衡量JavaScript性能(除了页面加载时间)
- 使用新的javascript性能.在iframe上优化API
- JavaScript性能(arr[i]的类型==“未定义”||num<arr[i])
- 处理大型数组时的JavaScript性能
- Javascript性能-使用$.getScript()添加脚本