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

Question

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

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

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

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

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

Answer 1

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

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

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

Answer 2

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);
    });
}

演示效果：