← 返回刚才阅读的位置

知识卡片

问题卡 · 4479

前缀树组织候选字符串

理解等级:中级

前缀树让共享前缀的字符串共用从根出发的路径。查询先定位前缀节点,再搜索后代的有效词并排序;树解决前缀定位,不自然保证整棵子树的候选搜索足够快。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 搜索自动补全 · 查看原书依据

      Trie (pronounced “try”) is a tree-like data structure that can compactly store strings. The name comes from the word retrieval, which indicates it is designed for string retrieval operations. The main idea of trie consists of the following: •A trie is a tree-like data structure. •The root represents an empty string. •Each node stores a character and has 26 children, one for each possible character.

    参考来源

    - 位置:《System Design Interview – An insiders guide, Second Edition》第13章《搜索自动补全》(来源项目 book-sources;源文件:extracted/System Design Interview – An insiders guide, Second Edition/_epub-src/text/part0031_split_003.html) - 结论依据:原文在该位置给出所述对象、机制或比较,支持本卡的解释;原书未展开的实现不作为已证明结论,算式与一致性边界在正文明确限定。 - 原始内容:Trie (pronounced “try”) is a tree-like data structure that can compactly store strings. The name comes from the word retrieval, which indicates it is designed for string retrieval operations. The main idea of trie consists of the following: •A trie is a tree-like data structure. •The root represents an empty string. •Each node stores a character and has 26 children, one for each possible character.