Trie树,又称字典树,单词查找树或者前缀树,是一种用于快速检索的多叉树结构,例如,英文字母的字典树是一个26叉树,数字的字典树是一个10叉树。
Trie的核心思想是用空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。当然,如果系统中存在大量字符串且这些字符串基本没有公共前缀,则相应的trie树将非常消耗内存,这也是trie树的一个缺点。
Trie树的性质
Trie树的基本性质可以归纳为:
- 根节点不包含字符,除根节点意外每个节点只包含一个字符。
- 从根节点到某一个节点,路径上经过的字符连接起来,为该节点对应的字符串。
- 每个节点的所有子节点包含的字符串不相同。
Trie树的基本实现
字典树的插入和查找操作都非常简单,只需遍历一遍字符串。
- 当进行插入操作时,对于第i个字符,先找到相应的子树,若不存在则插入一个新节点。对于字符串的最后一个字符,在插入完成后,标记这是一个词的结尾。
- 当进行查找操作时,从根节点开始,读取字符串中的字符,然后找相应的子树。在读完所有的字符后,如果该节点被标记为词尾,则查找成功,否则查找失败。
实现代码
public class TrieTree {
private Node root;
public TrieTree() {
root = new Node();
}
public void insert(String str) {
Node t = root;
for (int i = 0; i < str.length(); i++) {
if (t.nodes[str.charAt(i) - 'a'] == null) {
Node node = new Node();
t.nodes[str.charAt(i) - 'a'] = node;
}
t = t.nodes[str.charAt(i) - 'a'];
}
t.isStr = true;
}
public boolean find(String str) {
Node t = root;
int i;
for (i = 0; i < str.length() && t != null; i++) {
t = t.nodes[str.charAt(i) - 'a'];
}
return (t != null && t.isStr);
}
private class Node {
boolean isStr;
Node[] nodes;
Node() {
isStr = false;
nodes = new Node[26];
}
}
}
Trie树的高级实现
可以采用双数组(Double-Array)实现。利用双数组可以大大减小内存使用量。
Trie树的应用
Trie是一种非常简单高效的数据结构,但有大量的应用实例。
(1) 字符串检索
事先将已知的一些字符串(字典)的有关信息保存到trie树里,查找另外一些未知字符串是否出现过或者出现频率。
举例:
- 给出N 个单词组成的熟词表,以及一篇全用小写英文书写的文章,请你按最早出现的顺序写出所有不在熟词表中的生词。
- 给出一个词典,其中的单词为不良单词。单词均为小写字母。再给出一段文本,文本的每一行也由小写字母构成。判断文本中是否含有任何不良单词。例如,若rob是不良单词,那么文本problem含有不良单词。
(2) 字符串最长公共前缀
Trie树利用多个字符串的公共前缀来节省存储空间,反之,当我们把大量字符串存储到一棵trie树上时,我们可以快速得到某些字符串的公共前缀。
举例:
- 给出N 个小写英文字母串,以及Q 个询问,即询问某两个串的最长公共前缀的长度是多少?
解决方案:
首先对所有的串建立其对应的字母树。此时发现,对于两个串的最长公共前缀的长度即它们所在结点的公共祖先个数,于是,问题就转化为了离线(Offline)的最近公共祖先(Least Common Ancestor,简称LCA)问题。
而最近公共祖先问题同样是一个经典问题,可以用下面几种方法:
- 利用并查集(Disjoint Set),可以采用采用经典的Tarjan 算法;
- 求出字母树的欧拉序列(Euler Sequence )后,就可以转为经典的最小值查询(Range Minimum Query,简称RMQ)问题了;
(3) 排序
Trie树是一棵多叉树,只要先序遍历整棵树,输出相应的字符串便是按字典序排序的结果。
举例:
- 给你N 个互不相同的仅由一个单词构成的英文名,让你将它们按字典序从小到大排序输出。
(4) 作为其他数据结构和算法的辅助结构
如后缀树,AC自动机等。
Trie树复杂度分析
- 插入、查找的时间复杂度均为O(N),其中N为字符串长度。
- 空间复杂度是26^n级别的,非常庞大(可采用双数组实现改善)。
原文地址:http://dongxicheng.org/structure/trietree/
分享到:
相关推荐
一个简单的C语言程序:用Trie树实现词频统计和单词查询
trie.c中定义了trie树的操作函数; trie.h为相应的头文件; test.c用于测试相关的函数。 在trie.c中,关于查找定义了两个函数,一个是find(),一个是search(),二者的区别是,前者仅判断一个字符串是否在树中出现,...
用Python实现Trie树的应用,并可以对英汉词典进行导入和检索、添加和删除,最终可以将导入的英汉词典保存到本地磁盘。内附两个.py文件,分别是tree.py和d_gui.py,tree.py是类和方法,d_gui.py是图形界面;一个.txt...
用C实现的数据结构Trie树算法 实验的函数的trie树的插入 搜索和删除
Trie 树实现的源码,用C++编写实现,做自然语言处理的朋友可以参考一下
很容易上手的Trie树入门,特别适合于acm初学者
基于Trie树模仿谷歌百度搜索框提示。写的比较简单、代码漏洞之处欢迎指正。
通过基于划分位构建无冲突哈希函数,实现对片上存储器有效的控制,攻击特征平均分配到trie树每层的多个组中。该结构可以在同一个芯片中实现流水并行地执行,获得比较大的吞吐量。理论及实验表明该方法在片上存储器一...
这是一个ACM算法,Trie树,他能很好的解决字符问题
对双数纽Trie 树(Double-Array Trie)分词算法进行了优化:在采用Trie 树构造 双数纽Trie 树的过程中,优先处理分支节点多的结点,以减少冲突;构造一个空状态序列; 将冲突的结点放入Hash表中,不需要重新分配...
Trie树是搜索树的一种,来自英文单词"Retrieval"的简写,可以建立有效的数据检索组织结构,是中文匹配分词算法中词典的一种常见实现。它本质上是一个确定的有限状态自动机(DFA),每个节点代表自动机的一个状态。在...
2、Trie树SDK中的API支持以下功能 1)插入节点 2)精确删除节点 3)正向模糊匹配 4)反向模糊匹配 5)精确查询节点 6)获取头(尾)节点 7)删除头(尾)节点 8)排序 9)支持多级树 10)支持强大的查询节点功能 ...
Double Array Trie是TRIE树的一种变形,它是在保证TRIE树检索速度的前提下,提高空间利用率而提出的一种数据结构,本质上是一个确定有限自动机(deterministic finite automaton,简称DFA)。 所谓的DFA就是一个能实现...
网上大神的总结,从trie树谈到后缀树,常用的字符串匹配算法
2、Trie树SDK中的API支持以下功能 1)插入节点 2)精确删除节点 3)正向模糊匹配 4)反向模糊匹配 5)精确查询节点 6)获取头(尾)节点 7)删除头(尾)节点 8)排序 9)支持多级树 10)支持强大的查询节点功能 ...
ACM Trie树 模板,字典树模板,数据结构
散列索引多分支Trie树快速路由查找算法路由器的主要任务是转发IP分组,实现高速分组转发的关键是快速的路由查找算法。我们针对IPv4地址,首先建立前 缀长度为8、16和24的3张hash表,在此基础上,再分别针对不同长度...
Trie是一种树型数据结构,用于存储字符串,可以实现字符串的快速查找。Trie的核心思想是空间换时间,利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。 适用范围:统计和排序大量的字符串
trie树模板,acm竞赛,可以进行适当的修改就可以解决问题,在进行字符串处理的时候尤其能用到。
hash trie树 字典树,完整的sdk开发包 具有说明文档