`
kmplayer
  • 浏览: 508933 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

Tire树

阅读更多
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 只要在这颗树上查找 一遍就能找到得到该子串出现的次数。

仍段代码先:
#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;
}
分享到:
评论

相关推荐

    CQ V2.0分词bates(基于双数组tire树)

    《CQ V2.0分词系统:基于双数组Tire树解析》 在信息技术领域,文本处理是一项至关重要的任务,而分词是文本处理的第一步。CQ V2.0是一个专门针对中文文本的分词系统,它采用了一种高效的数据结构——双数组Tire树,...

    关于tire树

    ### 关于Trie树 #### 一、Trie树简介 Trie树,又称为前缀树或字典树,是一种用于存储字符串的树形数据结构。Trie树的优势在于可以高效地支持字符串的查找操作,尤其是在处理大量词汇时表现尤为突出。在搜索引擎、...

    什么是Tire树1

    Trie树,又称字典树或单词查找树,是一种用于高效存储和检索大量字符串的数据结构。它的设计目的是通过共享公共前缀来节省空间,并支持快速模式匹配。Trie树主要应用于信息检索、文本处理等领域。 Trie树有三种基本...

    TIRE 字典树 论文

    在论文“Tire树”中,可能探讨了Trie树的不同实现方式、优化策略、在特定问题上的应用案例,以及与其他数据结构(如平衡二叉搜索树、B树、哈希表等)的性能比较。论文可能会深入研究如何减少空间占用,比如使用压缩...

    tire树分析

    **Trie树分析** 在计算机科学中,Trie树(又称前缀树或字典树)是一种用于存储关联数组的数据结构,特别适用于字符串查询。它通过将字符串的公共前缀组织在一起,使得查找效率得以显著提升。Trie树的主要特点是能够...

    基于NLP的常用工具封装

    * √ 双数组tire树 * √ 文本断句 * √ html标签清理 * √ Viterbi算法增加 &gt; 组件 * √ 汉字转拼音 * √ 简繁体转换 * √ bloomfilter * √ 指纹去重 * √ SimHash文章相似度计算 * √ 词共现统计 * √ 基于...

    CSC148 A2 Students.7z

    5. **两棵Tire树的合并**:Trie树的合并通常是指将两个已经构造好的Trie树合并成一个新的,以合并它们包含的所有字符串。这个操作在处理大量数据,如合并不同来源的词库时非常有用。 6. **自动纠错**:自动纠错功能...

    多叉树做的实现字典功能

    利用Tire树实现一个音域单词辅助记忆系统,完成相应的建表和查表程序。 程序主要实现对单词的插入、删除和查找。其中查找部分又分精确查找和模糊查找。 利用文件对单词进行保存和读取操作以增强程序的可用行性。

    DoubleArrayTrie:双端trie树的python实现

    DoubleArrayTrie 双端trie树的python实现 ...其与双数组Tire可以说在功能上互补; 在存储值很多且多有冲突、字符编码范围较大的情况下,双数组Trie树很可能在序列化到硬盘以及加载到内存的占用空间都远大于字典Trie树

    搜索引擎开发培训课程提纲PPT学习教案.pptx

    12. **查找词典算法**:Trie树是构建词典和进行快速查找的高效数据结构,包括数字搜索树和Tire树,它们的生成、API使用和优化过程都是需要掌握的。 13. **隐码模型**:在信息检索中,发射概率和转移概率用于建模词...

    acm从入门到放弃

    - Tire树:即字典树,用于快速检索字符串。 - Manacher算法:用于寻找字符串中所有回文子串的算法。 - 后缀数组:一种用于处理字符串相关问题的数据结构。 - 括号匹配问题:涉及到括号正确匹配的算法问题。 - Hash...

    一个小型的全文检索引擎的DEMO

    里面基本包含了全文检索引擎的所有技术,包括词典分词,索引,检索等,其中词典分词采用的是基于双数组tire树的最大匹配法,索引部分参考了lucene的部分实现,检索部分应用了布尔检索和向量模型的排名算法,基本可以...

    trie_suffix.rar_suffix tire_suffix tr_tire_串匹配_后缀树

    后缀树,也被称为字典树或Trie,是一种数据结构,主要应用于字符串搜索和处理。在计算机科学中,特别是文本处理和信息检索领域,后缀树是一种非常重要的工具,它能够高效地解决多字符串匹配问题。这个压缩包中的内容...

    脏字屏蔽 中文 Tire Tree

    首先,我们要理解什么是Tire Tree(也称为Trie树或字典树)。Tire Tree是一种特殊的树形数据结构,用于存储字符串集合,特别适合于快速查找和插入操作。在脏字屏蔽的应用中,所有可能的脏字都会被预先插入到Tire ...

    经典AC自动机.cpp

    ac自动机,就是在tire树的基础上,增加一个fail指针,如果当前点匹配失败,则将指针转移到fail指针指向的地方,这样就不用回溯,而可以路匹配下去了

    java8集合源码分析-pangdan:面试相关技能

    红黑树、AVL树、Hash树、Tire树、B树、B+树。 图算法(比较少,也就两个最短路径算法理解吧) 计算机网络 OSI7层模型(TCP4层)等 数据库 数据库(最多的还是mysql,Nosql有redis) 索引(包括分类及优化方式,失效...

    JavaStudy:一角钱技术 All in One

    Tire树的基本实现和特性 并查集的基本实现和特性 剪枝的实现和特性 双向BFS的实现和特性 启发式搜索的实现和特性 AVL树和红黑树的实现和特性 位运算基础与实战要点 布隆过滤器的实现及应用 LRU Cache的实现及应用 ...

    基于双数组Trie_树中文分词研究

    ### 基于双数组Trie树中文分词研究 #### 概述 本文献针对中文信息处理中的分词问题,研究了一种基于双数组Trie树(Double-Array Trie, DAT)的优化方法。传统的分词算法面临着空间利用率低、插入速度慢等问题,...

Global site tag (gtag.js) - Google Analytics