Trie树原理和实现

介绍Trie树的原理并实现。

搜索引擎项都有搜索提示功能，通过前缀提示相关的搜索项。今天介绍的Trie-Tree可以满足此功能。当然实际工程落地往往涉及更对的处理，甚至使用到NLP技术。

Trie树称为单词查找树，因为我们可以根据单词的前缀部分查找词库中所遇匹配给定前缀的所有单词，所有又称为字典树。Trie树的一个特点是存储字符串节省空间，它通过公用字符串集合中的前缀来减少字符出现的冗余度，同时树形结构并没有把字符串的序列信息丢失，因而空间复杂度低。由于逻辑上字符串集合的存储结构是树形（多叉树），因为查找和插入下来非常高。可以类比到BST。

Trie树的性质

Trie树有三个性质：
（1）根结点不保存字符，孩子结点有且只有一个字符
（2）从根结点沿着树的某一路径到指定结点，把字符连接起来为该结点的字符串
（3）每个结点的孩子结点保存的字符都不一样

相关操作：

• 查找

• 插入

• 删除

实现

实用Python容易实现，

_sentinel = object()

class Node:

    def __init__(self, value):
        self._children = {}
        self._value = value

    def _add_child(self, char, value, overwrite=False):
        child = self._children.get(char)
        if child is None:
            child = Node(value)
            self._children[char] = child
        elif overwrite:
            child._value = value
        return child

    def find(self, key):
        state = self
        for char in key:
            state = state._children.get(char)
            if state is None:
                break
        return state

class Trie(Node):
    """简单实现的Trie"""

    def __init__(self):
        super(Trie, self).__init__(_sentinel)

    def __contains__(self, key):
        return self[key] is not None

    def __getitem__(self, key):
        state = self
        for char in key:
            state = state._children.get(char)
            if state is None:
                return None
        return state._value

    def __setitem__(self, key, value):
        state = self
        for i, char in enumerate(key, start=0):
            if i < len(key) - 1:
                state = state._add_child(char, None, False)
            else:
                state = state._add_child(char, value, True)

    def __delitem__(self, key):
        self[key] = None

    def add(self, key):
        self[key] = _sentinel

    def pop(self, key):
        del self[key]

    def update(self, keys):
        for key in keys:
            self[key] = _sentinel

转载请包括本文地址：https://allenwind.github.io/blog/5570
更多文章请参考：https://allenwind.github.io/blog/archives/