首頁  >  問答  >  主體

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

  1. Content assist provides you with a list of suggested completions for partially entered strings.
    內容協助為您提供部分輸入的字串的建議完成清單。

  2. 描述大概如上,我不知道怎麼用一個更精確的字來形容。

  3. sublime中有這個功能,你輸入“不完整的字元”,它會給你返回,包含這些字母的所有結果。譬如:輸入 ds 可以得到 desk ,儘管中間間隔了一個 字母 e。

  4. 我就想知道這是怎麼實現的,原理是什麼?

  5. 而且,這個功能,有名字嗎(我其實不知道這個功能應該叫啥名字,所以也妨礙了在網路上搜尋答案)?

天蓬老师天蓬老师2689 天前782

全部回覆(2)我來回復

  • 迷茫

    迷茫2017-07-03 11:44:19

    @boxsnake 給的是搜尋數組的例子,傳回的結果也應該排序的,「avsdsss」優先權最高,它包含了連續的「ds」。 「everybody」也應該命中,它包含了「d」。

    搜尋數組的時間複雜度太高了,當關鍵字很多的時候,速度基本上不可接受。

    高效可行的方法是用字串搜尋樹。
    海量資料處理之Trie樹(字典樹)

    回覆
    0
  • 女神的闺蜜爱上我

    女神的闺蜜爱上我2017-07-03 11:44:19

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

    示範效果:

    回覆
    0
  • 取消回覆