javascript - 求原理與實作: 部分字元的建議補全

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

示範效果：