Yihang

Have a nice day!

前缀树

发表于 更新于 分类于

🌲前缀树的核心思想是用空间换时间，利用字符串的公共前缀来降低查询的时间开销。

Note: 这里先总结一个简化版本，更完善的可以参见[《算法4》-5.2 单词查找数]

基于208. 实现Trie（前缀树）

简介

前缀树也称 字典树 Trie，典型的应用场景有基于前缀的模糊搜索 i.e. 在谷歌搜索时，输入“卷积”，搜索栏会给出“卷积”、“卷积神经网络”、“卷积运算公式等”。此外，经典的应用场景还有自动补全和拼写检查等

  • 基本操作: 插入和查询
    • 插入：构建前缀树
    • 查询：完整查询 或 前缀查询，而基于前缀查询是前缀树的灵魂，也是其名字的来源
    • 删除：很少使用

Trie结点

  • 前缀树根节点无实际意义
  • 每个结点一个存储域，用来存储一个字符
  • 每个结点还有控制域可以根据实际问题自定义 i.e.， 是否是对应单词，该前缀出现的次数

如用于判断给定单词是否

1
2
3
4
class TrieNode:
    def __init__(self):
        self.children = {}
        self.isword = False

Trie 插入

构建前缀🌲的核心，即：将单词全部依次插入到前缀树中

  • 将单词的结尾字符对应结点标记为True：从根结点出发到某一标记结点所经过的字符组成的单词，在单词列表中出现过
  • 插入新单词的时候就从根结点出发一个字符一个字符插入，有对应的字符节点就更新对应的属性，没有就创建新的结点
1
2
3
4
5
6
7
8
9
10
def insert(self, word: str) -> None:
    """
    Inserts a word into the trie.
    """
    node = self.root
    for ch in word:
        if ch not in node.children:
            node.children[ch] = TrieNode()
        node = node.children[ch]
    node.isword = True

Trie查找

对于前缀🌲Trie， 给定一个单词，和插入的过程类似，一个字符一个字符找

  • 若中途有个字符没有对应结点，则不含该单词
  • 若字符串遍历完了，都有对应节点，但最后一个字符对应的结点没有被标记为True，也不含该单词
1
2
3
4
5
6
7
8
9
10
11
def search(self, word: str) -> bool:
    """
    Returns if the word is in the trie.
    """
    node = self.root
    for ch in word:
        if ch not in node.children:
            return False
        node = node.children[ch]
    if not node.isword: return False
    return True

根据特定功能修改添加代码 ——— 以208为例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class TrieNode:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.children = {}
        self.isword = False


class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.isword = True

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        node = self.root
        for ch in word:
            if ch not in node.children:
                return False
            node = node.children[ch]
        if not node.isword: return False
        return True


    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return True



# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

Lucifer: “如何知道该使用前缀树优化是一个难点，不过大家只要牢牢记一点即可，那就是算法的复杂度瓶颈在字符串查找，并且字符串有很多公共前缀，就可以用前缀树优化。”