- 浏览: 570391 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (253)
- java (84)
- python (22)
- 设计模式 (12)
- 数据结构和算法 (7)
- ibatis (1)
- 数据挖掘 (2)
- 集体智慧读书笔记 (1)
- ubuntu (4)
- lucene (11)
- 算法 第4版 (11)
- apache mina (16)
- memcached (1)
- android (9)
- netty (6)
- mongodb (2)
- maven (2)
- openfire (2)
- 服务端 (21)
- 产品 (0)
- apache (1)
- 选择 (2)
- 构架WEB高性能站点 (7)
- redis (8)
- 诗词歌赋 (3)
- 源代码阅读 (5)
- 前端 (1)
- javascript (3)
- guice (1)
- 分布式 (5)
- 总结-2014 (4)
- jvm (1)
最新评论
-
liu_jiaqiang:
写的挺好
maven多项目管理 -
H972900846:
我想知道哪里整的,如果是自己写的,那有点牛呀如果是抄的请说明出 ...
SSL身份认证原理 -
春天好:
博主写的很好,赞一个,多谢分享 *(^-^*)分享一个免费好用 ...
定向网站爬虫---初级例子 -
fenglingabc:
经过测试,parameterType="java.u ...
mybatis获取主键和存储过程返回值 -
jyghqpkl:
[u][/u] ...
Cookie的secure 属性
【串和序列处理 3】Trie Tree 串集合查找
- 博客分类:
- java
转载:http://hxraid.iteye.com/blog/618962
Trie 树, 又称字典树,单词查找树。它来源于retrieval(检索)中取中间四个字符构成(读音同try)。用于存储大量的字符串以便支持快速模式匹配。主要应用在信息检索领域。
Trie 有三种结构: 标准trie (standard trie)、压缩trie、后缀trie(suffix trie) 。 最后一种将在《字符串处理4:后缀树》中详细讲,这里只将前两种。
1. 标准Trie (standard trie)
标准 Trie树的结构 : 所有含有公共前缀的字符串将挂在树中同一个结点下。实际上trie简明的存储了存在于串集合中的所有公共前缀。 假如有这样一个字符串集合X{bear,bell,bid,bull,buy,sell,stock,stop}。它的标准Trie树如下图:
上图(蓝色圆形结点为内部结点,红色方形结点为外部结点),我们可以很清楚的看到字符串集合X构造的Trie树结构。其中从根结点到红色方框叶子节点所经历的所有字符组成的串就是字符串集合X中的一个串。
注意这里有一个问题: 如果X集合中有一个串是另一个串的前缀呢? 比如,X集合中加入串bi。那么上图的Trie树在绿色箭头所指的内部结点i 就应该也标记成红色方形结点。这样话,一棵树的枝干上将出现两个连续的叶子结点(这是不合常理的)。
也就是说字符串集合X中不存在一个串是另外一个串的前缀 。如何满足这个要求呢?我们可以在X中的每个串后面加入一个特殊字符$(这个字符将不会出现在字母表中)。这样,集合X{bear$、bell$、.... bi$、bid$}一定会满足这个要求。
总结:一个存储长度为n,来自大小为d的字母表中s个串的集合X的标准trie具有性质如下:
(1) 树中每个内部结点至多有d个子结点。
(2) 树有s个外部结点。
(3) 树的高度等于X中最长串的长度。
(4) 树中的结点数为O(n)。
标准 Trie树的查找
对于英文单词的查找,我们完全可以在内部结点中建立26个元素组成的指针数组。如果要查找a,只需要在内部节点的指针数组中找第0个指针即可(b=第1个指针,随机定位)。时间复杂度为O(1)。
查找过程:假如我们要在上面那棵Trie中查找字符串bull (b-u-l-l)。
(1) 在root结点中查找第('b'-'a'=1)号孩子指针,发现该指针不为空,则定位到第1号孩子结点处——b结点。
(2) 在b结点中查找第('u'-'a'=20)号孩子指针,发现该指针不为空,则定位到第20号孩子结点处——u结点。
(3) ... 一直查找到叶子结点出现特殊字符'$'位置,表示找到了bull字符串
如果在查找过程中终止于内部结点,则表示没有找到待查找字符串。
效率:对于有n个英文字母的串来说,在内部结点中定位指针所需要花费O(d)时间,d为字母表的大小,英文为26。由于在上面的算法中内部结点指针定位使用了数组随机存储方式,因此时间复杂度降为了O(1)。但是如果是中文字,下面在实际应用中会提到。因此我们在这里还是用O(d)。 查找成功的时候恰好走了一条从根结点到叶子结点的路径。因此时间复杂度为O(d*n)。
但是,当查找集合X中所有字符串两两都不共享前缀时,trie中出现最坏情况。除根之外,所有内部结点都自由一个子结点。此时的查找时间复杂度蜕化为O(d*(n^2))
标准 Trie树的Java代码实现:
- package net.hr.algorithm.stroper;
- import java.util.ArrayList;
- enum NodeKind{LN,BN};
- /**
- * Trie结点
- */
- class TrieNode{
- char key;
- TrieNode[] points=null;
- NodeKind kind=null;
- }
- /**
- * Trie叶子结点
- */
- class LeafNode extends TrieNode{
- LeafNode(char k){
- super.key=k;
- super.kind=NodeKind.LN;
- }
- }
- /**
- * Trie内部结点
- */
- class BranchNode extends TrieNode{
- BranchNode(char k){
- super.key=k;
- super.kind=NodeKind.BN;
- super.points=new TrieNode[27];
- }
- }
- /**
- * Trie树
- * @author heartraid
- */
- public class StandardTrie {
- private TrieNode root=new BranchNode(' ');
- /**
- * 想Tire中插入字符串
- */
- public void insert(String word){
- //System.out.println("插入字符串:"+word);
- //从根结点出发
- TrieNode curNode=root;
- //为了满足字符串集合X中不存在一个串是另外一个串的前缀
- word=word+"$";
- //获取每个字符
- char[] chars=word.toCharArray();
- //插入
- for(int i=0;i<chars.length;i++){
- //System.out.println(" 插入"+chars[i]);
- if(chars[i]=='$'){
- curNode.points[26]=new LeafNode('$');
- // System.out.println(" 插入完毕,使当前结点"+curNode.key+"的第26孩子指针指向字符:$");
- }
- else{
- int pSize=chars[i]-'a';
- if(curNode.points[pSize]==null){
- curNode.points[pSize]=new BranchNode(chars[i]);
- // System.out.println(" 使当前结点"+curNode.key+"的第"+pSize+"孩子指针指向字符: "+chars[i]);
- curNode=curNode.points[pSize];
- }
- else{
- // System.out.println(" 不插入,找到当前结点"+curNode.key+"的第"+pSize+"孩子指针已经指向字符: "+chars[i]);
- curNode=curNode.points[pSize];
- }
- }
- }
- }
- /**
- * Trie的字符串全字匹配
- */
- public boolean fullMatch(String word){
- //System.out.print("查找字符串:"+word+"\n查找路径:");
- //从根结点出发
- TrieNode curNode=root;
- //获取每个字符
- char[] chars=word.toCharArray();
- for(int i=0;i<chars.length;i++){
- if(curNode.key=='$'){
- System.out.println('&');
- // System.out.println(" 【成功】");
- return true;
- }else{
- System.out.print(chars[i]+" -> ");
- int pSize=chars[i]-'a';
- if(curNode.points[pSize]==null){
- // System.out.println(" 【失败】");
- return false;
- }else{
- curNode=curNode.points[pSize];
- }
- }
- }
- // System.out.println(" 【失败】");
- return false;
- }
- /**
- * 先根遍历Tire树
- */
- private void preRootTraverse(TrieNode curNode){
- if(curNode!=null){
- System.out.print(curNode.key+" ");
- if(curNode.kind==NodeKind.BN)
- for(TrieNode childNode:curNode.points)
- preRootTraverse(childNode);
- }
- }
- /**
- * 得到Trie根结点
- */
- public TrieNode getRoot(){
- return this.root;
- }
- /**
- * 测试
- */
- public static void main(String[] args) {
- StandardTrie trie=new StandardTrie();
- trie.insert("bear");
- trie.insert("bell");
- trie.insert("bid");
- trie.insert("bull");
- trie.insert("buy");
- trie.insert("sell");
- trie.insert("stock");
- trie.insert("stop");
- trie.preRootTraverse(trie.getRoot());
- trie.fullMatch("stoops");
- }
- }
中文词语的 标准 Trie树
由于中文的字远比英文的26个字母多的多。因此对于trie树的内部结点,不可能用一个26的数组来存储指针。如果每个结点都开辟几万个中国字的指针空间。估计内存要爆了,就连磁盘也消耗很大。
一般我们采取这样种措施:
(1) 以词语中相同的第一个字为根组成一棵树。这样的话,一个中文词汇的集合就可以构成一片Trie森林。这篇森林都存储在磁盘上。森林的root中的字和root所在磁盘的位置都记录在一张以Unicode码值排序的有序字表中。字表可以存放在内存里。
(2) 内部结点的指针用可变长数组存储。
特点:由于中文词语很少操作4个字的,因此Trie树的高度不长。查找的时间主要耗费在内部结点指针的查找。因此将这项指向字的指针按照字的Unicode码值排序,然后加载进内存以后通过二分查找能够提高效率。
标准Trie树的应用和优缺点
(1) 全字匹配:确定待查字串是否与集合的一个单词完全匹配。如上代码fullMatch()。
(2) 前缀匹配:查找集合中与以s为前缀的所有串。
注意:Trie树的结构并不适合用来查找子串。这一点和前面提到的PAT Tree以及后面专门要提到的Suffix Tree的作用有很大不同。
优点: 查找效率比与集合中的每一个字符串做匹配的效率要高很多。在o(m)时间内搜索一个长度为m的字符串s是否在字典里。
缺点:标准Trie的空间利用率不高,可能存在大量结点中只有一个子结点,这样的结点绝对是一种浪费。正是这个原因,才迅速推动了下面所讲的压缩trie的开发。
2. 压缩Trie (compressed trie)
压缩Trie类似于标准Trie,但它能保证trie中的每个内部结点至少有两个子节点(根结点除外)。通过把单子结点链压缩进叶子节点来执行这个规则。
压缩Trie的定义
冗余结点(redundant node):如果T的一个非根内部结点v只有一个子结点,那么我们称v是冗余的。
冗余链(redundant link):如上标准Trie图中,内部结点e只有一个内部子结点l,而l也只有一个叶子结点。那么e-l-l就构成了一条冗余链。
压缩(compressed):对于冗余链 v1- v2- v3- ... -vn,我们可以用单边v1-vn来替代。
对上面标准Trie的图压缩之后,形成了Compressed Trie的字符表示图如下:
压缩Trie的性质和优势:
与标准Trie比较,压缩Trie的结点数与串的个数成正比了,而不是与串的总长度成正比。一棵存储来自大小为d的字母表中的s个串的结合T的压缩trie具有如下性质:
(1) T中的每个内部结点至少有两个子结点,至多有d个子结点。
(2) T有s个外部结点。
(3) T中的结点数为O(s)
存储空间从标准Trie的O(n)降低到压缩后的O(s),其中n为集合T中总字符串长度,s为T中的字符串个数。
压缩Trie的压缩表示
上面的图是压缩Trie的字符串表示。相比标准Trie而言,确实少了不少结点。但是细心的读者会发现,叶子结点中的字符数量增加了,比如结点ell,那么这种压缩空间的效率当然会打折扣了。那么有什么好办法呢,这里我们介绍一种压缩表示方法。即把所有结点中的字符串用三元组的形式表示如下图:
其中三元组(i,j,k)表示S[i]的从第j个位置到第k个位置间的子串。比如(5,1,3,)表示S[5][1...3]="ell"。
这种压缩表示的一个巨大的优点就是:无论结点需要存储多长的字串,全部都可以用一个三元组表示,而且三元组所占的空间是固定有限的。但是为了做到这一点,必须有一张辅助索引结构(如上图右侧s0—s7所示)。
发表评论
-
protobuf-dt插件
2015-03-24 13:16 1365protobuf-dt: 安装前先安装xtext 可 ... -
java循环标签
2015-03-20 16:13 558今天看 源码的时候 看到 一个小语法 参考: ... -
java程序性能优化 --阅读
2014-10-14 17:56 663闲着,真实无聊; 发现一本好书《java程序性能优 ... -
jetty invalid entry CRC问题
2014-08-04 11:42 15171: http://stackoverflow.com/qu ... -
guice注入
2014-05-24 12:13 9392Google Guice3.0: http://code. ... -
eclipse快捷键
2014-05-21 16:01 5271: clrl+alt+r : 最常用,快速定位到文件 2 ... -
java clone
2014-05-16 17:04 484转:http://www.blogjava.net/ora ... -
ThreadLocal
2014-05-13 18:39 727简单介绍一下ThreadLocal的原理:1.Thread ... -
hession
2014-04-30 12:33 654一、首先先说Hessian是什么? Hessian:he ... -
冒泡和快速排序java
2014-04-19 18:01 7091: 冒泡最简单一种: /** * 算法效率o ... -
java生产者和消费者模型三种实现
2014-04-19 17:51 13311: 生产者和消费者的问题,生产者生产产品到缓冲区,消费者 ... -
单例模式
2014-03-14 16:06 708今天看到群里,关于单例模式的多线程下的安全问题: 1:最 ... -
freemarker的使用
2014-02-28 16:42 7931:freemarker eclipse插件安装方法:ht ... -
java 引用类型和内存泄露
2013-11-21 17:48 551http://blog.csdn.net/luoshenfu ... -
java泛型
2013-11-07 13:52 398Class<T>在实例化的时候,T要替换成具体 ... -
filter执行顺序
2013-10-12 11:16 1090多个筛选器的运行顺序取决于下列规则: 将 filt ... -
spring rmi远程调用
2013-09-09 11:48 11411:以前用jmi发布服务,实现分布式的一种方式,远程调用, ... -
spring mvc返回204状态码
2013-07-24 09:27 38731:204是没内容 不跳转的 代表请求成功的意思 ... -
editplus去掉多余空行
2013-07-19 21:05 6871: ^[ \t]*\n 用正则表达式替换 -
spring3 aop 使用详细
2013-06-06 11:10 01:目标:拦截所有的@Controller中的方法 ...
相关推荐
C#,单词查找树(Trie Tree)的插入与搜索算法与源代码 又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统...
基于知识图谱和trietree的垃圾分类
Java实现字典树TrieTree,可用于计算出四六级试题的高频词.
trie - 单词查找树实现Go实现,极快的前缀/模糊字符串搜索的数据结构和相关算法
北大POJ2525-Text Formalization【TrieTree】 解题报告+AC代码+测试数据 http://hi.csdn.net/!s/XW4FQ3
资源链接:https://github.com/AbelZhou/PHP-TrieTree
北大POJ2513-Colored Sticks【TrieTree+MergeSet+EulerPath】 解题报告+AC代码
C# TrieTree介绍及实现方法,需要的朋友可以参考一下
严蔚敏数据结构与算法▲课本算法实现
【ASP.NET编程知识】TrieTree服务-组件构成及其作用介绍.docx
上一篇中我们对TrieTree服务有了一个整体的了解,不知道大家下载完之后有没有真正玩过这个TrieTree服务,如果你还没有玩过,没关系,本文将一步步教你配置和使用TrieTree服务。 TrieTree服务由几大组件组成,如下图 ...
C#,动态规划问题中基于单词搜索树(Trie Tree)的单词断句分词( Word Breaker)算法与源代码 1 分词 分词是自然语言处理的基础,分词准确度直接决定了后面的词性标注、句法分析、词向量以及文本分析的质量。英文...
严蔚敏数据结构与算法▲课本算法实现
Trie是一种字典树,用于存储文本字符,并利用了单词之间共享前缀的特点,所以叫做前缀树。不像平衡BST,Trie的高度只与最长的文本串的长度s有关系,而与单词的数量n无关。该代码为C#版本。
在trie.c中,关于查找定义了两个函数,一个是find(),一个是search(),二者的区别是,前者仅判断一个字符串是否在树中出现,而后者除了判断字符串是否出现,还会判断待查找的字符串是否是一个合法的单词。
嵌入式系统中基于trie树的拼音输入法的实现,李巧红,,介绍一种中文拼音输入法的实现方式,着重讨论了字库的设计及基于Trie树检索方法的实现。Trie树是基于关键码空间分解的树结构,其内�
一种基于计数器Bloom滤波器和Trie树的IP路由查找算法,王舒荷,袁东明,IP地址路由查找是网络转发技术的核心内容,路由表的组织和快速的路由查找算法是实现高速转发分组的关键。大量的研究表明在现有的以
Trie是一种树型数据结构,用于存储字符串,可以实现字符串的快速查找。Trie的核心思想是空间换时间,利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。 适用范围:统计和排序大量的字符串