trie树的特点:
拿内存换取时间,查询效率高
一、结点结构
public class TreeNode { char data;//节点数据 boolean isEnd;//是否是结束 LinkedList<TreeNode>childList;//子节点 int count;//计数; public TreeNode(char c){ this.data=c; isEnd=false; childList=new LinkedList<TreeNode>(); count=0; } //子节点字符 public TreeNode subNode(char c){ if(childList!=null){ for(TreeNode t:childList){ if(t.data==c)return t; } } return null; } }
二、树的生成
public class TrieTree { //根节点根节点为空值 private TreeNode root; //实例化的时候root的数据位空值 public TrieTree(){ root=new TreeNode(' '); } public void insertNode(String word){ if(searchNode(word))return; TreeNode current = root; for(int i = 0; i < word.length(); i++){ TreeNode child = current.subNode(word.charAt(i)); if(child != null){ current = child; } else { current.childList.add(new TreeNode(word.charAt(i))); current = current.subNode(word.charAt(i)); } current.count++; } // Set isEnd to indicate end of the word current.isEnd = true; } //搜索 //由于他的第一个字符是否存在于root的子节点中然后顺藤 public boolean searchNode(String word){ TreeNode tn=root; for(int i=0;i<word.length();i++){ if(tn.subNode(word.charAt(i))==null){ return false; }else{ tn=tn.subNode(word.charAt(i)); } } return tn.isEnd; } }
相关推荐
一个简单的C语言程序:用Trie树实现词频统计和单词查询
对双数纽Trie 树(Double-Array Trie)分词算法进行了优化:在采用Trie 树构造 双数纽Trie 树的过程中,优先处理分支节点多的结点,以减少冲突;构造一个空状态序列; 将冲突的结点放入Hash表中,不需要重新分配...
2、有序HASH(Trie)树SDK中的API支持以下功能 1)插入节点 2)精确删除节点 3)正向模糊匹配 4)反向模糊匹配 5)精确查询节点 6)获取头(尾)节点 7)删除头(尾)节点 8)排序 9)支持多级树 10)...
2、Trie树SDK中的API支持以下功能 1)插入节点 2)精确删除节点 3)正向模糊匹配 4)反向模糊匹配 5)精确查询节点 6)获取头(尾)节点 7)删除头(尾)节点 8)排序 9)支持多级树 10)支持强大的查询节点功能 ...
Trie是一种树型数据结构,用于存储字符串,可以实现字符串的快速查找。Trie的核心思想是空间换时间,利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。 适用范围:统计和排序大量的字符串
Double Array Trie是TRIE树的一种变形,它是在保证TRIE树检索速度的前提下,提高空间利用率而提出的一种数据结构,本质上是一个确定有限自动机(deterministic finite automaton,简称DFA)。 所谓的DFA就是一个能实现...
2、Trie树SDK中的API支持以下功能 1)插入节点 2)精确删除节点 3)正向模糊匹配 4)反向模糊匹配 5)精确查询节点 6)获取头(尾)节点 7)删除头(尾)节点 8)排序 9)支持多级树 10)支持强大的查询节点功能 ...
散列索引多分支Trie树快速路由查找算法路由器的主要任务是转发IP分组,实现高速分组转发的关键是快速的路由查找算法。我们针对IPv4地址,首先建立前 缀长度为8、16和24的3张hash表,在此基础上,再分别针对不同长度...
DoubleArrayTrie 双端trie树的python实现 版本翻译于 将其改写成python3.5版本 ...在存储值很多且多有冲突、字符编码范围较大的情况下,双数组Trie树很可能在序列化到硬盘以及加载到内存的占用空间都远大于字典Trie树
在中间结点之间采用多分支步长查询,中间结点的内部使用二进制trie树来表示。仿真结果表明,改进的多分支trie树具有访存次数少,查询速度快,占用存储空间少,更新开销小等特点,并且对IPv4和IPv6地址都可以适用。
本资源是对基于双数组树Trie的词典查询算法的介绍的课件,希望对大家有帮助。
提出一种基于双数组trie树的多模式复杂事件检测方法,通过构建多模式匹配自动机模型减少查询过程中冗余的检测和计算,并利用双数组trie树充分压缩存储空间,从而提高了复杂事件处理的效率。仿真实验表明,提出的方案...
它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高。 Trie是一种高效的信息检索数据结构。使用Trie,可以将搜索复杂性提高到最佳极限(密钥长度)。如果我们...
Trie树(来自单词retrieval),又称前缀字,单词查找树,字典树,是一种树形结构,是一种哈希树的变种,是一种用于快速检索的多叉树结构。 它的优点是:最大限度地减少无谓的字符串比较,查询效率比哈希表高。 Trie...
2.1 优化双数组 Trie 树的建立过程 2 .1 .1 2 .1 .2 2 .1 .3 分词所需要的查询算法
对双数组Trie树(Double-Array Trie)...然后,利用这些方法构造了一个中文分词系统,并与其他几种分词方法进行对比,结果表明,优化后的双数组Trie树插入速度和空间利用率得到了很大提高,且分词查询效率也得到了提高.
它的插入和查询时间复杂度都为 O(k) ,其中 k 为 key 的长度,与 Trie 中保存了多少个元素无关。Hash 表号称是 O(1) 的,但在计算 hash 的时候就肯定会是 O(k) ,而且还有碰撞之类的问题;Trie 的缺点是空间消耗很高...
链表、双链表、队列、Stack、哈希表、堆 - 最大和最小堆、优先队列、Trie、树、二叉搜索树、AVL树、红黑树、区段树 - 包含最小/最大/总和范围查询示例、Fenwick Tree(二叉索引树)、图形(有向和无向)、 Disjoint ...
使用trie数据结构的低级原始自动完成 特征 该自动完成库具有手动插入单词,根据查询获取单词建议,用单词的字典数组填充数据结构以及删除不需要的单词的能力。 注意:默认情况下,库中不填充任何单词。 插入方式 ...
Trie,又称单词查找树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:最大限度地减少无谓的字符串比较,...