飘逸的python - 实现trie树，,trie，又称前缀树

飘逸的python - 实现trie树，,trie，又称前缀树

trie，又称前缀树或字典树. 它利用字符串的公共前缀来节约存储空间.

定义
Trie树中每个单词都是通过character by character方法进行存储，相同前缀单词共享前缀节点.

可以看到,每条路径组成一个单词.上面这颗树存了to/tea/ted/ten/inn这些词.

性质（1）根节点不包含字符，除根节点外的每个节点只包含一个字符。（2）从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。（3）每个节点的所有子节点包含的字符串不相同。应用词频统计
比直接用hash节省空间搜索提示
输入前缀的时候提示可以构成的词作为辅助结构
如后缀树，AC自动机等的辅助结构

实现
虽然python没有指针,但是可以用嵌套字典来实现树结构.对于非ascii的单词,统一用unicode编码来插入与搜索.

#coding=utf-8class Trie:    root = {}    END = '/'    def add(self, word):        #从根节点遍历单词,char by char,如果不存在则新增,最后加上一个单词结束标志        node = self.root        for c in word:            node=node.setdefault(c,{})        node[self.END] = None    def find(self, word):        node = self.root        for c in word:            if c not in node:                return False            node = node[c]        return self.END in node

飘逸的python - 实现trie树