求原理和实现: 部分字符的建议补全

juedui0769
  • 97
  1. Content assist provides you with a list of suggested completions for partially entered strings.
    内容协助为您提供部分输入的字符串的建议完成列表。

  2. 描述大概如上,我不知道怎么用一个更精确的词来形容。

  3. sublime中有这个功能,你输入“不完整的字符”,它会给你返回,包含这些字母的所有结果。譬如:输入 ds 可以得到 desk ,尽管中间间隔了一个 字母 e。

  4. 我就想知道这是怎么实现的,原理是什么?

  5. 而且,这个功能,有名字吗(我其实不知道这个功能应该叫啥名字,所以也妨碍了在网上搜寻答案)?

回复
阅读 2.7k
2 个回答

@boxsnake 给的是搜索数组的例子,返回的结果还应该排序的,“avsdsss”优先级最高,它包含了连续的“ds”。“everybody”也应该命中,它包含了“d”。

搜索数组的时间复杂度太高了,当关键字很多的时候,速度基本不可接受。

高效可行的方法是用字符串搜索树。
海量数据处理之Trie树(字典树)

boxsnake
  • 6.7k
  1. 这个功能,应该叫“搜索智能提示”

  2. 实现办法有很多种,但是我只知道最简单最容易理解的一种,复杂的对查询算法做了优化,效率更高,可能涉及到动态规划问题。

  3. 如果是最简单的方法,就是把字符串拆开,然后向每两个字中间放入一个.*,再将其生成正则,用这个正则去匹配列表

  4. JS伪代码:

var list = [ ... ];
var text = 'ds';
var result = [];

if(text != '') {
    var pattern = new RegExp(text.split('').join('.*'));

    result = list.filter(function(item) {
        return pattern.test(item);
    });
}

演示效果:

clipboard.png

宣传栏