飘逸的python - 实现trie树

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

• 定义
  Trie树中每个单词都是通过character by character方法进行存储，相同前缀单词共享前缀节点.
  
  可以看到,每条路径组成一个单词.上面这颗树存了to/tea/ted/ten/inn这些词.
  
  
  • 性质
    • （1）根节点不包含字符，除根节点外的每个节点只包含一个字符。
    • （2）从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
    • （3）每个节点的所有子节点包含的字符串不相同。
• 应用
  • 词频统计
    比直接用hash节省空间
  • 搜索提示
    输入前缀的时候提示可以构成的词
  • 作为辅助结构
    如后缀树，AC自动机等的辅助结构

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

#coding=utf-8
class 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