[盖楼抽奖] ShowMeBug 自动补全功能原理大揭秘

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 1259 天前的主题，其中的信息可能已经有所发展或是发生改变。

经常有读者问小编，说用 ShowMeBug 做笔面试编程题时代码自动补全功能体验特别好，想知道是怎么实现的。问的人多了，小编就安排了一篇文章来说明自动补全的原理。

我们日常生活中最常见的自动补全场景是搜索引擎的搜索框，比如下图：

最简单粗暴的方式肯定是将用户输入的搜索词依次与列表中的字符串进行前缀匹配，如果前缀匹配，就在搜索结果中显示。当要搜索的字符串集合较小时，这么做可以接受，但如果搜索对象集较大，就不那么高效了。

const texts = ["show", "me", "bug", "money"];

const createFilter = (queryString) => {
  return (text) => {
    return (
      text.toLowerCase().indexOf(queryString.toLowerCase()) ===
          0
    );
  };
};

texts.find(createFilter('sh')) // return show

如果不用这种方式，那就要考虑字典树了。引用维基百科中关于字典树的定义：

字典树是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。

因为是树，其查询效率非常高，如果要查询的字符串长度是 k，则查找的时间复杂度为 O(k)。

不过字典树比较耗费空间，虽然可以通过三向字典树来进一步节省空间，但对于目前这个需求来说，字典树就够了。

首先，我们要构建一棵字典树，那该怎么构建呢？

和二叉树不同，字典树有多个分叉，常见的实现是通过多层数组映射来构建，假设输入的字符串只有 26 个小写英文字母，第一层节点是一个包含 26 个元素的数组 A，数组 A 下标 0 表示 a，依次类推；如果输入的字符 s 后面还有字符 h，则此时数组 A 中 s 的值会保存另一个包含 26 个元素的数组 B，并在数组 B 中表示字符 s 的下标中再存储一个数组 C，依次类推。

class TrieNode {
    data;
    children = Array(26);
    isEndingChar = false;
    constructor(data) {
        this.data = data;
    }
}

class Trie {
    root = new TrieNode('/');

    insert(text) {
        let p = this.root;
        for (let i = 0; i < text.length; i++) {
            const idx = text[i].charCodeAt() - 'a'.charCodeAt();

            if (!p.children[idx]) {
                const newNode = new TrieNode(text[i]);
                p.children[idx] = newNode;
            }
            p = p.children[idx];
        }
        p.isEndingChar = true;
    }

    find(pattern) {
        let p = this.root;
        for (let i = 0;i < pattern.length; i++) {
            const idx = pattern[i].charCodeAt() - 'a'.charCodeAt();
            if (!p.children[idx]) {
                return false;
            }
            p = p.children[idx];
        }

        return p.isEndingChar;
    }
}

function main() {
    const trie = new Trie();
    trie.insert("show");
    trie.insert("me");
    trie.insert("bug");
    console.log(trie.find('sh')) // return false
    console.log(trie.find('show')) // return true
}

main()

相信你现在已经理解自动补全的原理了，下次再用 ShowMeBug 进行笔面试时，可以考虑出字典树的题目哦～

抽奖啦！抽奖规则

评论抽 5 个人

截止日期为：2021.7.20 12:00

从回复楼层中随机抽取

中奖结果会以附言形式公布于本帖，并 @ 各位中奖用户

奖品为 PingCAP DevCon 2021 年度技术大会单日票

价值 588 元，还包午餐，是真的香~

function createRandom(num,from,to)
{
    var arr=[]; 
    var json={};  
    while(arr.length<num)
    {
        var ranNum=Math.round(Math.random()*(to-from))+from;
        if(!json[ranNum])
        {
            json[ranNum]=1;
            arr.push(ranNum); 
        }
    }
    return arr;
}

createRandom(10,0,回复楼层) //抽奖

源码引自 yedanbo/createRandom().js

第 1 条附言 · 2021-07-14 18:37:55 +08:00

这次的重点是抽奖哇[狗头保命]，PingCap DevCon 送票啦，帮忙盖盖楼就完事啦哈哈哈~

看来大佬们对 LSP 更感兴趣，我这边跟技术同学联系一下，下次让他们聊聊我们怎么做 Language Server Protocol 补全服务的哇~

字符

数组

return

idx

6 条回复 • 2021-07-22 18:29:52 +08:00