详解用Python代码实现字典树Trie的结构技巧

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了详解用Python代码实现字典树Trie的结构技巧，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2393字，纯文字阅读大概需要4分钟。

内容图文

Trie 的强大之处就在于它的时间复杂度。它的插入和查询时间复杂度都为 O(k) ，其中 k 为 key 的长度，与 Trie 中保存了多少个元素无关。Hash 表号称是 O(1) 的，但在计算 hash 的时候就肯定会是 O(k) ，而且还有碰撞之类的问题；Trie 的缺点是空间消耗很高。
至于Trie树的实现，可以用数组，也可以用指针动态分配，我做题时为了方便就用了数组，静态分配空间。
Trie树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。
Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
Trie树中每个单词都是通过character by character方法进行存储，相同前缀单词共享前缀节点.
可以看到,每条路径组成一个单词.上面这颗树存了to/tea/ted/ten/inn这些词.

Trie树的基本性质可以归纳为：
（1）根节点不包含字符，除根节点意外每个节点只包含一个字符。
（2）从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
（3）每个节点的所有子节点包含的字符串不相同。

性质
（1）根节点不包含字符，除根节点外的每个节点只包含一个字符。
（2）从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
（3）每个节点的所有子节点包含的字符串不相同。

基本思想（以字母树为例）：
1、插入过程
对于一个单词，从根开始，沿着单词的各个字母所对应的树中的节点分支向下走，直到单词遍历完，将最后的节点标记为红色，表示该单词已插入Trie树。
2、查询过程
同样的，从根开始按照单词的字母顺序向下遍历trie树，一旦发现某个节点标记不存在或者单词遍历完成而最后的节点未标记为红色，则表示该单词不存在，若最后的节点标记为红色，表示该单词存在。

应用
（1）词频统计
比直接用hash节省空间
（2）搜索提示
输入前缀的时候提示可以构成的词
（3）作为辅助结构
如后缀树，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

更多详解用Python代码实现字典树Trie的结构技巧相关文章请关注PHP中文网！

内容总结

以上是互联网集市为您收集整理的详解用Python代码实现字典树Trie的结构技巧全部内容，希望文章能够帮你解决详解用Python代码实现字典树Trie的结构技巧所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端