1

我也修改了 jQuery Autocomplete 实现以生成自动更正建议。我使用 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 距离，它可以提供更有意义的结果并且速度更快。

4

1 回答 1

3

你可以在这里优化很多东西，但大部分都归结为：每个“较重”的计算只做一次。您在每次按键、每次排序比较等方面都做了很多工作，缓存这些值会有很大帮助。

但是，为了显着提高性能，您可以使用另一个非常漂亮的优化技巧。每个主要搜索引擎都使用它，包括 Amazon.com 等网站上的现场搜索引擎。

它利用了您实际上不需要对整个列表进行排序这一事实，因为您所显示的只是前 10 或 12 个项目。数千个列表项中的其余部分是否按正确顺序排列并不重要。因此，在浏览列表时，您真正需要跟踪的是到目前为止您看到的前 10 或 12 个项目，事实证明，这比完全排序要快得多。

这是伪代码中的想法：

  1. 用户键入一个字符，创建一个新的搜索词
  2. 我们定义一个长度为 12 的空shortlist数组（或者我们想要的许多建议）
  3. 遍历完整的单词列表（我们将其称为dictionary）：
    1. 计算字典词和搜索词之间的（Levenshtein）编辑距离
    2. 如果距离小于（更好）当前threshold，我们：
      • 将单词添加到顶部shortlist
      • 让shortlist'溢出'中的底部单词脱离列表
      • 设置我们的threshold距离以匹配现在位于底部的单词shortlist
  4. 当循环结束时，我们有一个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();
});

在 jsFiddle 上的这个 12.000 字演示中尝试该方法

于 2013-07-03T23:39:32.497 回答