我修改了 jQuery 自动完成实现以生成自动更正建议。我使用 Levenshtein 距离作为决定最接近匹配的指标。
在 jQuery 自动完成没有更多建议后,我的代码在每次按键时运行。这是我写的代码:
// Returns edit distance between two strings
edit_distance : function(s1, s2) {
// Auxiliary 2D array
var arr = new Array(s1.length+1);
for(var i=0 ; i<s1.length+1 ; i++)
arr[i] = new Array(s2.length+1);
// Algorithm
for(var i=0 ; i<=s1.length ; i++)
for(var j=0 ; j<=s2.length ; j++)
arr[i][j] = 0;
for(var i=0 ; i<=s1.length ; i++)
arr[i][0] = i;
for(var i=0 ; i<=s2.length ; i++)
arr[0][i] = i;
for(var i=1 ; i<=s1.length ; i++)
for(var j=1 ; j<=s2.length ; j++)
arr[i][j] = Math.min(arr[i-1][j-1] + (s1.charAt(i-1)==s2.charAt(j-1) ? 0 : 1), arr[i-1][j]+1, arr[i][j-1]+1);
// Final answer
return arr[s1.length][s2.length].toString(10);
},
// This is called at each keypress
auto_correct : function() {
// Make object array for sorting both names and IDs in one go
var objArray = new Array();
for(var i=0 ; i<idArray.length ; i++) {
objArray[i] = new Object();
objArray[i].id = idArray[i];
objArray[i].name = nameArray[i];
}
// Sort object array by edit distance
var out = this;
companyObjArray.sort (
function(a,b) {
var input = jQuery("#inputbox").val().toLowerCase();
var d1 = a.name.toLowerCase();
var d2 = b.name.toLowerCase();
return out.editDistance(input,d1) - out.editDistance(input,d2);
}
);
// Copy some closest matches in arrays that are shown by jQuery
this.suggestions = new Array();
this.data = new Array();
for(var i=0 ; i<5 ; i++) {
this.suggestions.push(companyObjArray[i].name);
this.data.push(companyObjArray[i].id);
}
}
所有名称都有与之相关联的 ID,因此在排序之前,我只是根据它们创建一个对象数组,然后对该数组进行排序。
由于要搜索的列表有数千个,所以速度很慢。我找到了一种称为 BK-tree 的数据结构,它可以加快速度,但我现在无法实现它。我正在寻找优化建议以加快速度。欢迎提出任何建议。提前致谢。
编辑。我决定使用 Sift3作为我的字符串距离度量而不是 Levenshein 距离,它提供了更有意义的结果并且速度更快。
最佳答案
您可以在这里优化很多事情,但大部分可以归结为:每个“较重”的计算只进行一次。您在每次按键、每次排序比较等方面做了大量工作,缓存这些值会有很大帮助。
但是,要显着提高性能,您可以使用另一个非常巧妙的优化技巧。每个主要搜索引擎都使用它,包括 Amazon.com 等网站上的现场搜索引擎。
它利用了这样一个事实,即您实际上不需要对整个列表进行排序,因为您所显示的只是前 10 或 12 个项目。其余数千个列表项的顺序是否正确并不重要。因此,在浏览列表时,您真正需要跟踪的是到目前为止您看到的前 10 或 12 个项目,事实证明,这比完全排序快 很多 .
这是伪代码的想法:
- 用户键入一个字符,创建一个新的搜索词
- 我们定义一个空的
shortlist
数组,长度为 12(或者我们想要的任何建议) - 遍历完整的单词列表(我们将其称为
字典
):- 计算字典词和搜索词之间的(Levenshtein)编辑距离
- 如果距离低于(更好)当前
阈值
,我们:- 将单词添加到
shortlist
的顶部 - 让
入围名单
中的底部单词“溢出”出列表 - 设置我们的
阈值
距离以匹配现在位于候选列表
底部的单词
- 将单词添加到
- 当循环结束时,我们有一个包含一些最佳单词的
候选列表
,但它们是未排序的,所以我们只对这 12 个单词进行排序,这会非常快。
一个小警告:根据数据集和候选列表中的元素数量,候选列表可能与实际的顶级元素略有不同,但这可以减轻通过增加入围名单的大小,例如到 50,并在最后排序完成后删除底部的 38。
至于实际代码:
// Cache important elements and values
var $searchField = $('#searchField'),
$results = $('#results'),
numberOfSuggestions = 12,
shortlistWindowSize = 50,
shortlist,
thresholdDistance;
// Do as little as possible in the keyboard event handler
$searchField.on('keyup', function(){
shortlist = [];
thresholdDistance = 100;
// Run through the full dictionary just once,
// storing just the best N we've seen so far
for (var i=0; i<dictionarySize; i++) {
var dist = edit_distance(this.value, dictionary[i]);
if (dist < thresholdDistance) {
shortlist.unshift({
word: dictionary[i],
distance: dist
});
if (shortlist.length > shortlistWindowSize) {
shortlist.pop();
thresholdDistance = shortlist[shortlistWindowSize-1].distance;
}
}
}
// Do a final sorting of just the top words
shortlist.sort(function(a,b){
return a.distance - b.distance;
});
// Finally, format and show the suggestions to the user
$results.html('<p>' + $.map(shortlist, function(el){
return '<span>[dist=' + el.distance + ']</span> ' + el.word;
}).slice(0,numberOfSuggestions).join('</p><p>') + '</p>').show();
});
试试这个 12.000 word demo on jsFiddle 中的方法
关于javascript - 优化 JavaScript 自动更正实现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17442297/