Trie三兄弟——标准Trie、压缩Trie、后缀Trie

1.Trie导引

Trie树是一种基于树的数据结构,又称单词查找树、前缀树,字典树,是一种哈希树的变种。应用于字符串的统计与排序,经常被搜索引擎系统用于文本词频统计。用于存储字符串以便支持快速模式匹配,主要应用在信息检索中,Trie支持的主要查询操作是模式匹配和前缀匹配。Trie树可以看着是一个确定有限状态自动机,有限状态自动机另一篇博文字符串模式匹配算法——BM、Horspool、Sunday、KMP、KR、AC算法一网打尽 有介绍。

计算机科学中,trie,又称前缀树,是一种有序,用于保存关联数组,其中的键通常是字符串二叉查找树不同,键不是直接保存在节点中,而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串。一般情况下,不是所有的节点都有对应的值,只有叶子节点和部分内部节点所对应的键才有相关的值

Trie 这个术语来自于 retrieval。根据词源学,trie 的发明者 Edward Fredkin 把它读作 /ˈtr/ "tree"。[1][2] 但是,其他作者把它读作 /ˈtr/ "try"。[1][2][3](算法导论也叫做做基数树radix树或retrieval 树)

在图示中,键标注在节点中,值标注在节点之下。每一个完整的英文单词对应一个特定的整数。Trie 可以看作是一个确定有限状态自动机,尽管边上的符号一般是隐含在分支的顺序中的。

键不需要被显式地保存在节点中。图示中标注出完整的单词,只是为了演示 trie 的原理。

trie 中的键通常是字符串,但也可以是其它的结构。trie 的算法可以很容易地修改为处理其它结构的有序序列,比如一串数字或者形状的排列。比如,bitwise trie 中的键是一串位元,可以用于表示整数或者内存地址。

Trie三兄弟——标准Trie、压缩Trie、后缀Trie

2.标准Trie

令S是取自字母表∑的s个集合,满足S中不存在一个串是另一个串的前缀。S的一个标准Trie(standard trie)是一颗有序书T,满足如下性质:

  • 除了根之外,T中的每个结点标记有∑的一个字符。
  • T中一个内部结点的子结点的次序有字母表∑上的规范次序确定。
  • T有s个外部结点(叶结点),每个外部结点关联S中的一个串,满足从根到T中一个外部结点v的路径上标记连接产生S中关联的一个串。

下图是串{bear,bell,bid,bull,buy,sell,stock,stop}的标准Trie

Trie三兄弟——标准Trie、压缩Trie、后缀Trie

#include<algorithm>
#include<iostream>
using namespace std; const int sonnum=,base='a';
struct Trie
{
int num;//to remember how many word can reach here,that is to say,prefix
bool terminal;//If terminal==true ,the current point has no following point
struct Trie *son[sonnum];//the following point
};
Trie *NewTrie()// create a new node
{
Trie *temp=new Trie;
temp->num=;temp->terminal=false;
for(int i=;i<sonnum;++i)temp->son[i]=NULL;
return temp;
}
void Insert(Trie *pnt,char *s,int len)// insert a new word to Trie tree
{
Trie *temp=pnt;
for(int i=;i<len;++i)
{
if(temp->son[s[i]-base]==NULL)
temp->son[s[i]-base]=NewTrie();
else
temp->son[s[i]-base]->num++; temp=temp->son[s[i]-base];
}
temp->terminal=true; } void Delete(Trie *pnt)// delete the whole tree
{
if(pnt!=NULL)
{
for(int i=;i<sonnum;++i)if(pnt->son[i]!=NULL)Delete(pnt->son[i]);
delete pnt;
pnt=NULL;
}
}
Trie* Find(Trie *pnt,char *s,int len)//trie to find the current word
{
Trie *temp=pnt;
for(int i=;i<len;++i)
{
if(temp->son[s[i]-base]!=NULL)
{
cout<<temp->son[s[i]-base]->num<<ends<<s[i]<<endl;//没有打印根节点的num
temp=temp->son[s[i]-base];
}
else return NULL;
}
return temp;
} int main()
{
Trie *root;
root=NewTrie();
Insert(root,"bear",);
Insert(root,"bell",);
Insert(root,"bid",);
Insert(root,"bull",);
Insert(root,"buy",); Trie *res;
res=Find(root,"bear",);
if(res!=NULL)
{
cout<<res->terminal;
}
else
cout<<"not found";
}

输出:

5 b

2 3

1 a

1 r

1 找到了。(代码参考:http://hi.baidu.com/luyade1987/item/7c1977f5e9015cdf6225d224)

存储总长为n,来自大小为d的字母表中s个串的集合S的标准Trie具有如下性质:

  1. T中每个内部结点最多有d个子结点。
  2. T有s个外部结点。(显然,有s个串)
  3. T的高度等于最长串的长度。
  4. T中的结点书为O(n)。

性能:对于有n个英文字母的串来说,在内部结点中定位指针所需要花费O(d)时间,d为字母表的大小,英文为26。由于在上面的算法中内部结点指针定位使用了数组随机存储方式,因此时间复杂度降为了O(1)。但是如果是中文字,下面在实际应用中会提到。因此我们在这里还是用O(d)。 查找成功的时候恰好走了一条从根结点到叶子结点的路径。因此时间复杂度为O(d*n)。但是,当查找集合X中所有字符串两两都不共享前缀时,trie中出现最坏情况。除根之外,所有内部结点都*一个子结点。此时的查找时间复杂度蜕化为O(d*(n^2))

Trie树的特点如下:
1)根节点不包含字符,除根节点外每一个节点都只包含一个字符。
2)从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。
3)每个节点的所有子节点包含的字符都不相同。(也就是孩子都不相同)
 
http://dsqiu.iteye.com/blog/1705697

http://en.wikipedia.org/wiki/Trie

http://blog.csdn.net/v_july_v/article/details/6897097

上一篇:SVN同步出现故障


下一篇:使用HttpClient发送请求接收响应