赞
踩
常关注本blog的读者朋友想必看过此篇文章:从B树、B+树、B*树谈到R 树,这次,咱们来讲另外两种树:Tire树与后缀树。不过,在此之前,先来看两个问题。
第一个问题: 一个文本文件,大约有一万行,每行一个词,要求统计出其中最频繁出现的前10个词,请给出思想,给出时间复杂度分析。之前在此文:海量数据处理面试题集锦与Bit-map详解中给出的参考答案:用trie树统计每个词出现的次数,时间复杂度是O(n*le)(le表示单词的平均长度),然后是找出出现最频繁的前10个词。也可以用堆来实现(具体的操作可参考第三章、寻找最小的k个数),时间复杂度是O(n*lg10)。所以总的时间复杂度,是O(n*le)与O(n*lg10)中较大的哪一个。
第二个问题:找出给定字符串里的最长回文。例子:输入XMADAMYX。则输出MADAM。这道题的流行解法是用后缀树(Suffix Tree),但其用途远不止如此,它能高效解决一堆复杂的字符串编程问题(当然,它有它的弱点,如算法实现复杂以及空间开销大),概括如下:
Trie树,即字典树,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:最大限度地减少无谓的字符串比较,查询效率比哈希表高。
Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
它有3个基本性质:
举个在网上流传颇广的例子,如下:
题目:给你100000个长度不超过10的单词。对于每一个单词,我们要判断他出没出现过,如果出现了,求第一次出现在第几个位置。
分析:这题当然可以用hash来解决,但是本文重点介绍的是trie树,因为在某些方面它的用途更大。比如说对于某一个单词,我们要询问它的前缀是否出现过。这样hash就不好搞了,而用trie还是很简单。
现在回到例子中,如果我们用最傻的方法,对于每一个单词,我们都要去查找它前面的单词中是否有它。那么这个算法的复杂度就是O(n^2)。显然对于100000的范围难以接受。现在我们换个思路想。假设我要查询的单词是abcd,那么在他前面的单词中,以b,c,d,f之类开头的我显然不必考虑。而只要找以a开头的中是否存在abcd就可以了。同样的,在以a开头中的单词中,我们只要考虑以b作为第二个字母的,一次次缩小范围和提高针对性,这样一个树的模型就渐渐清晰了。
好比假设有b,abc,abd,bcd,abcd,efg,hii 这6个单词,我们构建的树就是如下图这样的
当时第一次看到这幅图的时候,便立马感到此树之不凡构造了。单单从上幅图便可窥知一二,好比大海搜人,立马就能确定东南西北中的到底哪个方位,如此迅速缩小查找的范围和提高查找的针对性,不失为一创举。
ok,如上图所示,对于每一个节点,从根遍历到他的过程就是一个单词,如果这个节点被标记为红色,就表示这个单词存在,否则不存在。
那么,对于一个单词,我只要顺着他从根走到对应的节点,再看这个节点是否被标记为红色就可以知道它是否出现过了。把这个节点标记为红色,就相当于插入了这个单词。
这样一来我们查询和插入可以一起完成(重点体会这个查询和插入是如何一起完成的,稍后,下文具体解释),所用时间仅仅为单词长度,在这一个样例,便是10。
我们可以看到,trie树每一层的节点数是26^i级别的。所以为了节省空间。我们用动态链表,或者用数组来模拟动态。空间的花费,不会超过单词数×单词长度。
上文中提到”比如说对于某一个单词,我们要询问它的前缀是否出现过。这样hash就不好搞了,而用trie还是很简单“。下面,咱们来看看这个前缀查询问题:
已知n个由小写字母构成的平均长度为10的单词,判断其中是否存在某个串为另一个串的前缀子串。下面对比3种方法:
下面解释下上述方法3中所说的为什么hash不能将建立与查询同时执行,而Trie树却可以:
Trie树是简单但实用的数据结构,通常用于实现字典查询。我们做即时响应用户输入的AJAX搜索框时,就是Trie开始。本质上,Trie是一颗存储多个字符串的树。相邻节点间的边代表一个字符,这样树的每条分支代表一则子串,而树的叶节点则代表完整的字符串。和普通树不同的地方是,相同的字符串前缀共享同一条分支。下面,再举一个例子。给出一组单词,inn, int, at, age, adv, ant, 我们可以得到下面的Trie:
可以看出:
查询操纵非常简单。比如要查找int,顺着路径i -> in -> int就找到了。
搭建Trie的基本算法也很简单,无非是逐一把每则单词的每个字母插入Trie。插入前先看前缀是否存在。如果存在,就共享,否则创建对应的节点和边。比如要插入单词add,就有下面几步:
Trie树的单词查询实现
以下是trie树的简单实现。下图所示的测试只是做了一个非常简单的检测而已,先插入j而后查找j,再删除再查找,目的主要是看删除函数是否有效。日后再好好写下trie树用于单词频率统计的实现(单词统计hash表当然也可以实现,只不过如果用trie树统计单词出现频率,想象一下,当树中已有某个单词,再次遍历到同样的单词,便可以迅速高效的查询找到某个单词,为其出现计数+1,这得益于查找高效的所带来的好处)。
- #include <iostream>
- #include <cstring>
- #include <string>
- using namespace std;
-
- const int num_of_letters = 26;
- const int max_word_length = 20;
-
- // 定义trie树节点
- struct Trie
- {
- int cnt;
- Trie *next[num_of_letters];
- Trie() {
- cnt = 0;
- for(int i=0; i < num_of_letters; i++)
- next[i] = 0;
- }
- };
- // 定义根节点
- Trie *root = new Trie;
-
- /**
- * 建立trie树,同时保存单词频率
- */
- void create_trie(string str)
- {
- Trie *t = root;
- Trie *node = NULL;
- int len = str.length();
- int pos = 0;
-
- // 深度为单词长度
- for(int i = 0; i < len; ++i) {
- // 将字母范围映射到0-25之间
- pos = str[i] - 'a';
- // 如果当前字母没有对应的trie树节点则建立,否则处理下一个字母
- if(t->next[pos] == NULL) {
- node = new Trie;
- // 添加到next数组
- t->next[pos] = node;
- }
- t = t->next[pos];
- // 单词频率加1
- t->cnt++;
- }
- }
-
- /**
- * 遍历trie,输出所求前缀出现次数
- * @param str 所求前缀
- */
- void display(string str){
- Trie *t = root;
- int len = str.length();
- int pos = 0;
- for(int i = 0; i < len; ++i){
- pos = str[i] - 'a';
- if(t->next[pos] == NULL){
- printf("0\n");
- return ;
- }
- t = t->next[pos];
- }
- cout << t->cnt << endl;
- }
-
- /**
- * 释放内存
- */
- void del(Trie *root){
- for(int i = 0; i < max_word_length; ++i)
- if(root->next[i])
- del(root->next[i]);
- delete(root);
- }
-
- int main()
- {
- string str;
- for(int i=0; i < 3; i++) {
- cin >> str;
- create_trie(str);
- }
- create_trie("abcde");
- display("abc");
- del(root);
- return 0;
- }
除了本文引言处所述的问题能应用Trie树解决之外,Trie树还能解决下述问题(节选自此文:海量数据处理面试题集锦与Bit-map详解)。
(1) 请描述你解决这个问题的思路;(2) 请给出主要的处理流程,算法,以及算法的复杂度。
文章转载自:https://blog.csdn.net/v_JULY_v/article/details/6897097
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。