飘逸的python - 实现trie树

时间:2022-09-11 18:46:08

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

  • 定义
    Trie树中每个单词都是通过character by character方法进行存储,相同前缀单词共享前缀节点.
    飘逸的python - 实现trie树
    可以看到,每条路径组成一个单词.上面这颗树存了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