所以我有一个随机的 javascript 名称数组...
[@larry,@nicholas,@notch]等
它们都以@符号开头。我想按 Levenshtein 距离对它们进行排序,以便列表顶部的那些最接近搜索词。目前,我有一些 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
元素是它每次在数组中追加的元素,这形成了一个基于输入的搜索词的名称列表。
我也有编辑距离算法:
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];
}
关于javascript - 按 "Levenshtein Distance"对数组进行排序,在 Javascript 中性能最佳,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11919065/