`

【串和序列处理 3】Trie Tree 串集合查找

阅读更多

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所示)。   

 

9
0
分享到:
评论
2 楼 ChenxofHit 2011-10-09  
[img][/img][url][/url][flash=200,200][/flash]
引用
1 楼 Heart.X.Raid 2011-08-28  
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++) {
			int pSize = chars[i] - 'a';
			if (curNode.points[pSize] == null) {
				System.out.println(" 【失败】");
				return false;
			} else {
				curNode = curNode.points[pSize];
				System.out.print(curNode.key + " -> ");
			}
		}
		if (curNode.points[26] != null) {
			System.out.print('$');
			System.out.println(" 【成功】");
			return true;
		} else {
			System.out.println(" 【失败】仅为Trie中的某个前缀");
			return false;
		}
	}  

Trie的字符串全字匹配方法的修改

相关推荐

    基于知识图谱和trietree的垃圾分类

    基于知识图谱和trietree的垃圾分类

    Java实现字典树TrieTree

    Java实现字典树TrieTree,可用于计算出四六级试题的高频词.

    Go-trie-单词查找树实现Go实现

    trie - 单词查找树实现Go实现,极快的前缀/模糊字符串搜索的数据结构和相关算法

    POJ2525-Text Formalization【TrieTree】

    北大POJ2525-Text Formalization【TrieTree】 解题报告+AC代码+测试数据 http://hi.csdn.net/!s/XW4FQ3

    PHP-TrieTree-master.zip

    资源链接:https://github.com/AbelZhou/PHP-TrieTree

    POJ2513-Colored Sticks【TrieTree+MergeSet+EulerPath】

    北大POJ2513-Colored Sticks【TrieTree+MergeSet+EulerPath】 解题报告+AC代码

    C# TrieTree介绍及实现方法

    C# TrieTree介绍及实现方法,需要的朋友可以参考一下

    11 TrieTree.rar

    严蔚敏数据结构与算法▲课本算法实现

    【ASP.NET编程知识】TrieTree服务-组件构成及其作用介绍.docx

    【ASP.NET编程知识】TrieTree服务-组件构成及其作用介绍.docx

    TrieTree服务-组件构成及其作用介绍

    上一篇中我们对TrieTree服务有了一个整体的了解,不知道大家下载完之后有没有真正玩过这个TrieTree服务,如果你还没有玩过,没关系,本文将一步步教你配置和使用TrieTree服务。 TrieTree服务由几大组件组成,如下图 ...

    11 TrieTree.zip

    严蔚敏数据结构与算法▲课本算法实现

    C#编写的Trie树操作

    Trie是一种字典树,用于存储文本字符,并利用了单词之间共享前缀的特点,所以叫做前缀树。不像平衡BST,Trie的高度只与最长的文本串的长度s有关系,而与单词的数量n无关。该代码为C#版本。

    trie树的实现(C)

    在trie.c中,关于查找定义了两个函数,一个是find(),一个是search(),二者的区别是,前者仅判断一个字符串是否在树中出现,而后者除了判断字符串是否出现,还会判断待查找的字符串是否是一个合法的单词。

    论文研究-嵌入式系统中基于trie树的拼音输入法的实现 .pdf

    嵌入式系统中基于trie树的拼音输入法的实现,李巧红,,介绍一种中文拼音输入法的实现方式,着重讨论了字库的设计及基于Trie树检索方法的实现。Trie树是基于关键码空间分解的树结构,其内�

    论文研究-一种基于计数器Bloom滤波器和Trie树的IP路由查找算法 .pdf

    一种基于计数器Bloom滤波器和Trie树的IP路由查找算法,王舒荷,袁东明,IP地址路由查找是网络转发技术的核心内容,路由表的组织和快速的路由查找算法是实现高速转发分组的关键。大量的研究表明在现有的以

    基本Trie树的实现

    Trie是一种树型数据结构,用于存储字符串,可以实现字符串的快速查找。Trie的核心思想是空间换时间,利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。 适用范围:统计和排序大量的字符串

    Patricia tree

    PAT tree 在字符串子串匹配 上有这非常优异的表现,这使得它经常成为一种高效的全文检索算法,在自然语言处理领域也有广泛的应用。其算法中最突出的特点就是采用半无限长字串(semi-infinite string 简称 sistring) ...

    Python实现Trie树

    用Python实现Trie树的应用,并可以对英汉词典进行导入和检索、添加和删除,最终可以将导入的英汉词典保存到本地磁盘。内附两个.py文件,分别是tree.py和d_gui.py,tree.py是类和方法,d_gui.py是图形界面;一个.txt...

Global site tag (gtag.js) - Google Analytics