- 浏览: 509976 次
- 性别:
- 来自: 北京
文章分类
最新评论
-
jkxydp:
算法运行的结果根本就不对。
BM算法. -
soarwindzhang:
感谢博主的分享,我今天看了您的UFSET非递归的路径压缩时感觉 ...
并查集 -
zhangning290:
楼主好像只考虑了坏字符规则,。没有考虑好后缀
BM算法. -
lsm0622:
文字描述有错误 误导新学者
求有向图的强连通分量(scc):Tarjan算法 -
knightchen:
博主,你太强了!这篇文章对我学习C++多线程很有帮助!谢谢
并发学习之一_windows下ZThread在CodeBlocks上的安装与配置
Tire树:
先简单解释一下Trie。“Trie”这个单词来自于"retrieve",可见它的用途主要是字符串查询。Trie不发tree的音,而发try的音。
应用
题目大意:
统计子串出现的次数,规定子串的长度不超过8.
http://acm.scs.bupt.cn/onlinejudge/showproblem.php?problem_id=1302
trie算法的思路大概如下:
对输入的长串S 想将所有长度位1-8的子串存入trie树,并在子串末节点上记录下字串出现的次数,然后针对每个输入的查询串s 只要在这颗树上查找 一遍就能找到得到该子串出现的次数。
仍段代码先:
这个题目也可以用hash做.
基本思路:
这里采用的最简单的26进制的函数对子串进行hash,由于26^8 会超出int的范围所以在计算hash值时需要64位的整数。在算出每个子串的 hash值后就将相应的slot标记好,并记录下这个slot被标记过几次,然后对各查询子串也用相同的hash函数来处理,然后查询子串所在的slot 的计数器就行了。
先简单解释一下Trie。“Trie”这个单词来自于"retrieve",可见它的用途主要是字符串查询。Trie不发tree的音,而发try的音。
应用
题目大意:
统计子串出现的次数,规定子串的长度不超过8.
http://acm.scs.bupt.cn/onlinejudge/showproblem.php?problem_id=1302
trie算法的思路大概如下:
对输入的长串S 想将所有长度位1-8的子串存入trie树,并在子串末节点上记录下字串出现的次数,然后针对每个输入的查询串s 只要在这颗树上查找 一遍就能找到得到该子串出现的次数。
仍段代码先:
#include <iostream> using namespace std ; class trie { private : int count[26] ; trie * child[26] ; public : trie () { int i ; for ( i = 0 ; i < 26 ; i++ ) { count[i] = 0 ; child[i] = NULL ; } } ~trie () { int i ; for ( i = 0 ; i < 26 ; i++ ) { delete child[i] ; } } void insert ( const char *key , const int & leng ) //生成了字典树,这次操作统计的次数全部以*key开头 { if ( leng == 0 ) return ; int index = *key - 'a' ; if ( child[index] == NULL ) child[index] = new trie ; count[index]++ ; child[index] -> insert ( key + 1 , leng - 1 ) ; } int quary ( const char *key ) //返回子串出现的次数 { if ( * ( key + 1 ) == '\0' ) //最后一个字符 return count[*key - 'a'] ; if ( child[*key - 'a'] == NULL ) //只有遇到不存在的部分子串,必定返回0. return 0 ; return child[*key - 'a'] ->quary ( key + 1 ) ; //递归寻找下一个字符 } } ; char s[32768 + 10] ; int main () { int stringLength , quaryNumber , left , right , substringLength , test = 1 ;; while ( scanf ( "%s" , s ) != EOF ) { trie stringTrie ; substringLength = 8 ; stringLength = strlen ( s ) ; for ( left = 0 ; left + substringLength <= stringLength ; left++ ) stringTrie.insert ( s + left , substringLength ) ; //生成了字典树 for ( substringLength = 7 ; left < stringLength ; left ++ , substringLength-- ) stringTrie.insert ( s + left , substringLength ) ; //添加最后7个开头子串的统计数 scanf ( "%d" , &quaryNumber ) ; printf ( "Case %d:\n" , test++ ) ; while ( quaryNumber -- ) { scanf ( "%s" , s ) ; printf ( "%d\n" , stringTrie.quary ( s ) ) ; } } return 0 ; }
这个题目也可以用hash做.
基本思路:
这里采用的最简单的26进制的函数对子串进行hash,由于26^8 会超出int的范围所以在计算hash值时需要64位的整数。在算出每个子串的 hash值后就将相应的slot标记好,并记录下这个slot被标记过几次,然后对各查询子串也用相同的hash函数来处理,然后查询子串所在的slot 的计数器就行了。
#include<iostream> using namespace std ; typedef long long __int64 ; char s[1<<16] ; const int HASH_SIZE = 1<<18 ; __int64 mark[HASH_SIZE] ; int counter[HASH_SIZE] ; int getHashVal ( __int64 tmp ) { return tmp&(HASH_SIZE-1) ; } void insert ( __int64 tmp ) { int val = getHashVal ( tmp ) ; int index = val ; //index代表下标和tmp的值不是对应的,因此每次都需要需要tmp对应的index. while ( mark[index] != -1 && mark[index] != tmp ) { index++ ; if ( index == HASH_SIZE ) index = 0 ; } counter[index]++ ; mark[index] = tmp ; } int query ( __int64 tmp ) { int val = getHashVal ( tmp ) ; int index = val ; while ( mark[index] != -1 && mark[index] != tmp ) { index++ ; if ( index == HASH_SIZE ) index = 0 ; } return counter[index] ; } int main() { __int64 tmp ; int t , Q ; for ( t = 1 ; scanf ( "%s" , s ) != EOF ; ++t ) { memset ( mark , -1 , sizeof ( mark ) ) ; memset ( counter , 0 , sizeof ( counter ) ) ; printf ( "Case %d:\n" , t ) ; for ( int i = 0 ; s[i] != '\0' ; ++i ) //s[i] != '\0',因此所有的子串都可以遍历到. { tmp = 0 ; for ( int k = 0 ; k < 8 && s[i + k] != '\0'; ++k ) //转化为27进制的一个数 { tmp = tmp * 27 + s[i + k] - 'a' + 1 ; insert ( tmp ) ; } } scanf ( "%d" , &Q ) ; while ( Q-- ) { scanf ( "%s" , s ) ; tmp = 0 ; for ( int i = 0 ; s[i] != '\0' ; ++i ) { tmp = tmp * 27 + s[i] - 'a' + 1 ; } printf ( "%d\n" , query ( tmp ) ) ; } } return 0; }
发表评论
-
为什么堆排比快排慢
2010-12-16 15:25 3023[节选]http://mindhacks.cn/200 ... -
使用map和hash_map的效率问题
2010-12-09 19:49 68931,选择map容器,是为了更快的从关键字查找到相关的对象。 与 ... -
斐波那契堆
2010-07-04 11:37 181, http://kmplayer.iteye.com/ad ... -
斐波那契堆
2010-07-04 11:36 1429学习的地方: http://en.wikipedia.org/ ... -
Sunday算法
2010-07-02 11:38 89851,Sunday算法是Daniel M.Sunday于1990 ... -
BM算法.
2010-07-02 10:53 77081,BM算法是Boyer-Moore算法的简称,由Boyer ... -
优先级队列
2010-06-17 23:15 12001,优先级队列是不同于 ... -
计数排序
2010-05-04 16:59 7871,计数排序是一个非基于比较的线性时间排序算法。 它对输入的数 ... -
归并排序
2010-05-04 16:47 9061,归并排序是建立在归并操作上的一种有效的排序算法。该算法是采 ... -
求大数阶层
2010-05-04 16:40 13471,思想类似于大数的加减乘法. 数组的每个元素维护一个4位数. ... -
基数排序
2010-05-03 16:45 892详细解释参考:http://en.wikipedia.org/ ... -
求两个数组的中位数
2010-05-02 12:08 41141,题目 有两个数组,均已经按升序排列好,编程序计算这两个数组 ... -
imba的bit向量
2010-04-22 17:30 9391,先给出一个模板. #include <iostr ... -
编写自己的malloc
2010-04-19 17:03 15161,如果一个程序大量调用malloc,程序的很多时间将会消耗在 ... -
快速排序
2010-04-01 13:50 7431,给出一个实现实例. #include <iost ... -
md5算法
2010-03-31 10:35 2670Message Digest Algorithm MD5( ... -
堆排序
2010-03-23 10:48 8961,"堆"定义 n个关 ... -
改进的线性筛法_寻找素数
2010-03-03 10:41 16161,实例代码: #include <iostream ... -
求有向图的强连通分量(scc):Tarjan算法
2010-02-28 15:41 143141,在有向图G中,如果两个顶点间至少存在一条路径,称两个顶点强 ... -
最近公共祖先LCA:Tarjan算法
2010-02-28 15:25 178451,并查集+dfs 对整个树进行深度优先遍历,并在遍历的过程中 ...
相关推荐
《CQ V2.0分词系统:基于双数组Tire树解析》 在信息技术领域,文本处理是一项至关重要的任务,而分词是文本处理的第一步。CQ V2.0是一个专门针对中文文本的分词系统,它采用了一种高效的数据结构——双数组Tire树,...
### 关于Trie树 #### 一、Trie树简介 Trie树,又称为前缀树或字典树,是一种用于存储字符串的树形数据结构。Trie树的优势在于可以高效地支持字符串的查找操作,尤其是在处理大量词汇时表现尤为突出。在搜索引擎、...
Trie树,又称字典树或单词查找树,是一种用于高效存储和检索大量字符串的数据结构。它的设计目的是通过共享公共前缀来节省空间,并支持快速模式匹配。Trie树主要应用于信息检索、文本处理等领域。 Trie树有三种基本...
在论文“Tire树”中,可能探讨了Trie树的不同实现方式、优化策略、在特定问题上的应用案例,以及与其他数据结构(如平衡二叉搜索树、B树、哈希表等)的性能比较。论文可能会深入研究如何减少空间占用,比如使用压缩...
**Trie树分析** 在计算机科学中,Trie树(又称前缀树或字典树)是一种用于存储关联数组的数据结构,特别适用于字符串查询。它通过将字符串的公共前缀组织在一起,使得查找效率得以显著提升。Trie树的主要特点是能够...
* √ 双数组tire树 * √ 文本断句 * √ html标签清理 * √ Viterbi算法增加 > 组件 * √ 汉字转拼音 * √ 简繁体转换 * √ bloomfilter * √ 指纹去重 * √ SimHash文章相似度计算 * √ 词共现统计 * √ 基于...
5. **两棵Tire树的合并**:Trie树的合并通常是指将两个已经构造好的Trie树合并成一个新的,以合并它们包含的所有字符串。这个操作在处理大量数据,如合并不同来源的词库时非常有用。 6. **自动纠错**:自动纠错功能...
利用Tire树实现一个音域单词辅助记忆系统,完成相应的建表和查表程序。 程序主要实现对单词的插入、删除和查找。其中查找部分又分精确查找和模糊查找。 利用文件对单词进行保存和读取操作以增强程序的可用行性。
DoubleArrayTrie 双端trie树的python实现 ...其与双数组Tire可以说在功能上互补; 在存储值很多且多有冲突、字符编码范围较大的情况下,双数组Trie树很可能在序列化到硬盘以及加载到内存的占用空间都远大于字典Trie树
12. **查找词典算法**:Trie树是构建词典和进行快速查找的高效数据结构,包括数字搜索树和Tire树,它们的生成、API使用和优化过程都是需要掌握的。 13. **隐码模型**:在信息检索中,发射概率和转移概率用于建模词...
- Tire树:即字典树,用于快速检索字符串。 - Manacher算法:用于寻找字符串中所有回文子串的算法。 - 后缀数组:一种用于处理字符串相关问题的数据结构。 - 括号匹配问题:涉及到括号正确匹配的算法问题。 - Hash...
里面基本包含了全文检索引擎的所有技术,包括词典分词,索引,检索等,其中词典分词采用的是基于双数组tire树的最大匹配法,索引部分参考了lucene的部分实现,检索部分应用了布尔检索和向量模型的排名算法,基本可以...
后缀树,也被称为字典树或Trie,是一种数据结构,主要应用于字符串搜索和处理。在计算机科学中,特别是文本处理和信息检索领域,后缀树是一种非常重要的工具,它能够高效地解决多字符串匹配问题。这个压缩包中的内容...
首先,我们要理解什么是Tire Tree(也称为Trie树或字典树)。Tire Tree是一种特殊的树形数据结构,用于存储字符串集合,特别适合于快速查找和插入操作。在脏字屏蔽的应用中,所有可能的脏字都会被预先插入到Tire ...
ac自动机,就是在tire树的基础上,增加一个fail指针,如果当前点匹配失败,则将指针转移到fail指针指向的地方,这样就不用回溯,而可以路匹配下去了
红黑树、AVL树、Hash树、Tire树、B树、B+树。 图算法(比较少,也就两个最短路径算法理解吧) 计算机网络 OSI7层模型(TCP4层)等 数据库 数据库(最多的还是mysql,Nosql有redis) 索引(包括分类及优化方式,失效...
Tire树的基本实现和特性 并查集的基本实现和特性 剪枝的实现和特性 双向BFS的实现和特性 启发式搜索的实现和特性 AVL树和红黑树的实现和特性 位运算基础与实战要点 布隆过滤器的实现及应用 LRU Cache的实现及应用 ...
### 基于双数组Trie树中文分词研究 #### 概述 本文献针对中文信息处理中的分词问题,研究了一种基于双数组Trie树(Double-Array Trie, DAT)的优化方法。传统的分词算法面临着空间利用率低、插入速度慢等问题,...