在线编程在线课堂在线测评Anycodes在线编程

编程论坛

 找回密码
 立即注册

QQ登录

只需一步,快速开始

How to use bs4??
本帖最后由 carry0987 于
Double Queue 问题描述 : The new founded Balkan Investment Group Bank (
John 问题描述 : Little John is playing very funny game
linux-command Linux命令大全搜索工具,内容包含Linux命令
Coati 是一款跨平台的代码查看工具,适用于 C/C++ 和 Java。商业软件。特性:1. 索引
系统可承载海量并发,消息收发确认机制 保障消息必达 系统采用动态智
全平台视频监控,支持安卓苹果以及pcweb,支持海康大华等主流dvr,全部源码以及文档 单聊、群聊、商
如何访问类的私有属性? 下面以 TPathData 为例,
问题:从 XE4 以来,Firemonkey 曲线绘图在移动平台不平滑的问题一直令人诟病,提交到官方的 QC 也是族繁不及备载,官方似乎有意的
操作数据库(RODBC)   odbcConnect(dsn, uid="", p
数据模式:mode函数显示任何对象的模式。常见的单个的
系统可承载海量并发,消息收发确认机制 保障消息必达 系统采用动态智
RabbitMQ与PHP(一) 项
Iease团队扩编预备中,盼望能有Ruby或者java工程师加盟。全职兼职都可以。有爱好的伴侣请与我接洽。 邮件:i
ruby 怎么设置装备摆设GTK2,求教指导下!
#include #include #include #include using namespace std; int main() {
标题如图所示: 有n盏灯,编号1~n。一开端灯都是关着的
成熟的消息收发确认机制,支持万人大群 支持开发自定义的消息sdk接口,扩展性超强 支持单/
成熟的消息收发确认机制,支持万人大群 支持开发自定义的消息sdk接口,扩展性超强 支持单/
1. 注意列表和集合的区别 set 列表表现形式: list_1
Ajax   Ajax即“Asynchronous Javascript And
大师好,我比来在做布谷鸟优
分辨提取A和B图像Harris角点,接下来须要对

[C++分享] 字典树(Trie Tree)

[复制链接]
发表于 2016-3-19 19:04:48 | 显示全部楼层 |阅读模式
基本概念和性质
在计算机科学中,trie,又称前缀树或字典树或单词搜索树,是一种有序树,用于保存关联数组,其中的键通常是字符串。与二叉查找树不同,键不是直接保存在节点中,而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串。一般情况下,不是所有的节点都有对应的值,只有叶子节点和部分内部节点所对应的键才有相关的值。
本文地址:http://www.cnblogs.com/archimedes/p/trie-tree.html,转载请注明源地址。
在图示中,键标注在节点中,值标注在节点之下。每一个完整的英文单词对应一个特定的整数。Trie 可以看作是一个确定有限状态自动机,尽管边上的符号一般是隐含在分支的顺序中的。键不需要被显式地保存在节点中。图示中标注出完整的单词,只是为了演示 trie 的原理。

字典树(Trie Tree)

字典树(Trie Tree)

trie 中的键通常是字符串,但也可以是其它的结构。trie 的算法可以很容易地修改为处理其它结构的有序序列,比如一串数字或者形状的排列。比如,bitwise trie 中的键是一串位元,可以用于表示整数或者内存地址。
Trie树是一种树形结构,是一种哈希树的变种。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:最大限度地减少无谓的字符串比较,查询效率比哈希表高。Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
它有3个基本性质:
(1) 根节点不包含字符,除根节点外每一个节点都只包含一个字符。
(2) 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。
(3) 每个节点的所有子节点包含的字符都不相同。
基本思想(以字母树为例):
1、插入过程
对于一个单词,从根开始,沿着单词的各个字母所对应的树中的节点分支向下走,直到单词遍历完,将最后的节点标记为红色,表示该单词已插入Trie树。
2、查询过程
同样的,从根开始按照单词的字母顺序向下遍历trie树,一旦发现某个节点标记不存在或者单词遍历完成而最后的节点未标记为红色,则表示该单词不存在,若最后的节点标记为红色,表示该单词存在。

Trie树的实现

字母树的插入(Insert)、删除( Delete)和查找(Find)都非常简单,用一个一重循环即可,即第i 次循环找到前i个字母所对应的子树,然后进行相应的操作。实现这棵字母树,至于Trie树的实现,可以用数组,也可以用指针动态分配,平时为了方便就用数组,静态分配空间。
1、trie结构体
  1. struct Trie
  2. {
  3.     Trie *next[26];
  4.     bool isWord;
  5. }Root;
复制代码
2、插入操作
  1. //插入操作(也是构建Trie树)
  2. void insert(char *tar)
  3. {
  4.     Trie* head = &Root;
  5.     int id;
  6.     while(*tar)
  7.     {
  8.         id = *tar - 'a';
  9.         if(head->next[id] == NULL)
  10.             head->next[id] = new Trie();
  11.         head = head->next[id];
  12.         tar++;
  13.     }
  14.     head->isWord = true;
  15. }
复制代码
3、查找操作
  1. //查找
  2. bool search(char *tar)
  3. {
  4.     Trie* head = &Root;
  5.     int id;
  6.     while(*tar)
  7.     {
  8.         id = *tar - 'a';
  9.         if(head->next[id] == NULL)
  10.             return false;
  11.         head = head->next[id];
  12.         tar++;
  13.     }
  14.     if(head->isWord)
  15.         return true;
  16.     else
  17.         return false;
  18. }
复制代码
至于结点对儿子的指向,一般有三种方法:
1、对每个结点开一个字母集大小的数组,对应的下标是儿子所表示的字母,内容则是这个儿子对应在大数组上的位置,即标号;
2、对每个结点挂一个链表,按一定顺序记录每个儿子是谁;
3、使用左儿子右兄弟表示法记录这棵树。
三种方法,各有特点。第一种易实现,但实际的空间要求较大;第二种,较易实现,空间要求相对较小,但比较费时;第三种,空间要求最小,但相对费时且不易写。
下面给出动态开辟内存的实现:
  1. #define MAX_NUM 26
  2. enum NODE_TYPE{ //"COMPLETED" means a string is generated so far.
  3.   COMPLETED,
  4.   UNCOMPLETED
  5. };
  6. struct Node {
  7.   enum NODE_TYPE type;
  8.   char ch;
  9.   struct Node* child[MAX_NUM]; //26-tree->a, b ,c, .....z
  10. };
  11. struct Node* ROOT; //tree root
  12. struct Node* createNewNode(char ch){
  13.   // create a new node
  14.   struct Node *new_node = (struct Node*)malloc(sizeof(struct Node));
  15.   new_node->ch = ch;
  16.   new_node->type == UNCOMPLETED;
  17.   int i;
  18.   for(i = 0; i < MAX_NUM; i++)
  19.     new_node->child[i] = NULL;
  20.   return new_node;
  21. }
  22. void initialization() {
  23. //intiazation: creat an empty tree, with only a ROOT
  24. ROOT = createNewNode(' ');
  25. }
  26. int charToindex(char ch) { //a "char" maps to an index<br>
  27. return ch - 'a';
  28. }

  29. int find(const char chars[], int len) {
  30.   struct Node* ptr = ROOT;
  31.   int i = 0;
  32.   while(i < len) {
  33.    if(ptr->child[charToindex(chars[i])] == NULL) {
  34.    break;
  35.   }
  36.   ptr = ptr->child[charToindex(chars[i])];
  37.   i++;
  38.   }
  39.   return (i == len) && (ptr->type == COMPLETED);
  40. }
  41. void insert(const char chars[], int len) {
  42.   struct Node* ptr = ROOT;
  43.   int i;
  44.   for(i = 0; i < len; i++) {
  45.    if(ptr->child[charToindex(chars[i])] == NULL) {
  46.     ptr->child[charToindex(chars[i])] = createNewNode(chars[i]);
  47.   }
  48.   ptr = ptr->child[charToindex(chars[i])];
  49. }
  50.   ptr->type = COMPLETED;
  51. }
复制代码
Trie树的应用

Trie是一种非常简单高效的数据结构,但有大量的应用实例。
(1) 字符串检索
事先将已知的一些字符串(字典)的有关信息保存到trie树里,查找另外一些未知字符串是否出现过或者出现频率。
举例:
1、给出N个单词组成的熟词表,以及一篇全用小写英文书写的文章,请你按最早出现的顺序写出所有不在熟词表中的生词。
2、给出一个词典,其中的单词为不良单词。单词均为小写字母。再给出一段文本,文本的每一行也由小写字母构成。判断文本中是否含有任何不良单词。例如,若rob是不良单词,那么文本problem含有不良单词。
(2)字符串最长公共前缀
Trie树利用多个字符串的公共前缀来节省存储空间,反之,当我们把大量字符串存储到一棵trie树上时,我们可以快速得到某些字符串的公共前缀。
举例:
给出N 个小写英文字母串,以及Q 个询问,即询问某两个串的最长公共前缀的长度是多少?
解决方案:首先对所有的串建立其对应的字母树。此时发现,对于两个串的最长公共前缀的长度即它们所在结点的公共祖先个数,于是,问题就转化为了离线(Offline)的最近公共祖先(Least Common Ancestor,简称LCA)问题。
而最近公共祖先问题同样是一个经典问题,可以用下面几种方法:
1. 利用并查集(Disjoint Set),可以采用采用经典的Tarjan 算法;
2. 求出字母树的欧拉序列(Euler Sequence )后,就可以转为经典的最小值查询(Range Minimum Query,简称RMQ)问题了;
(3)排序
Trie树是一棵多叉树,只要先序遍历整棵树,输出相应的字符串便是按字典序排序的结果。
举例:
给你N 个互不相同的仅由一个单词构成的英文名,让你将它们按字典序从小到大排序输出。
(4) 作为其他数据结构和算法的辅助结构
如后缀树,AC自动机等
字典树基本模板
  1. #define  MAX   26 //字符集大小

  2. typedef struct TrieNode
  3. {
  4.     int nCount; //记录该字符出现次数
  5.     struct TrieNode *next[MAX];
  6. }TrieNode;

  7. TrieNode Memory[1000000];
  8. int allocp = 0;

  9. /*初始化*/
  10. void InitTrieRoot(TrieNode **pRoot)
  11. {
  12.     *pRoot = NULL;
  13. }

  14. /*创建新结点*/
  15. TrieNode *CreateTrieNode()
  16. {
  17.     int i;
  18.     TrieNode *p;
  19.     p = &Memory[allocp++];
  20.     p->nCount = 1;
  21.     for(i = 0 ; i < MAX ; i++)
  22.         p->next[i] = NULL;
  23.     return p;
  24. }

  25. /*插入*/
  26. void InsertTrie(TrieNode **pRoot , char *s)
  27. {
  28.     int i , k;
  29.     TrieNode *p;
  30.     if(!(p = *pRoot))
  31.         p = *pRoot = CreateTrieNode();
  32.     i = 0;
  33.     while(s[i]) {
  34.         k = s[i++] - 'a'; //确定branch
  35.         if(p->next[k])
  36.             p->next[k]->nCount++;
  37.         else
  38.             p->next[k] = CreateTrieNode();
  39.         p = p->next[k];
  40.     }
  41. }

  42. //查找
  43. int SearchTrie(TrieNode **pRoot , char *s)
  44. {
  45.     TrieNode *p;
  46.     int i , k;
  47.     if(!(p = *pRoot))
  48.         return 0;
  49.     i = 0;
  50.     while(s[i]) {
  51.         k = s[i++] - 'a';
  52.         if(p->next[k] == NULL) return 0;
  53.         p = p->next[k];
  54.     }
  55.     return p->nCount;
  56. }
复制代码



上一篇:C++_系列自学课程_第_9_课_C语言风格字符串_《C++ Primer 第四版》
下一篇:C++_系列自学课程_第_8_课_指针和引用_《C++ Primer 第四版》
在线编程(http://www.anycodes.cn)&编程论坛(http://www.52exe.cn)感谢您的支持!
回复

使用道具 举报

发表于 2016-4-10 11:41:13 | 显示全部楼层
不知所云
在线编程(http://www.anycodes.cn)&编程论坛(http://www.52exe.cn)感谢您的支持!
回复 支持 反对

使用道具 举报

发表于 2016-5-22 00:16:30 | 显示全部楼层
不错不错不错,重要的事情说三遍
在线编程(http://www.anycodes.cn)&编程论坛(http://www.52exe.cn)感谢您的支持!
回复 支持 反对

使用道具 举报

发表于 2017-1-10 06:06:12 | 显示全部楼层
无聊啊,来看看
在线编程(http://www.anycodes.cn)&编程论坛(http://www.52exe.cn)感谢您的支持!
回复 支持 反对

使用道具 举报

发表于 2017-1-16 09:29:08 | 显示全部楼层
在线编程(http://www.anycodes.cn)&编程论坛(http://www.52exe.cn)感谢您的支持!
回复 支持 反对

使用道具 举报

发表于 2017-2-17 07:33:15 | 显示全部楼层
顶一下再说
在线编程(http://www.anycodes.cn)&编程论坛(http://www.52exe.cn)感谢您的支持!
回复 支持 反对

使用道具 举报

发表于 2018-2-20 13:36:00 来自手机 | 显示全部楼层
看不懂啊看不懂啊看不懂啊
在线编程(http://www.anycodes.cn)&编程论坛(http://www.52exe.cn)感谢您的支持!
回复 支持 反对

使用道具 举报

发表于 2018-4-5 16:09:49 来自手机 | 显示全部楼层
额,看不明白
在线编程(http://www.anycodes.cn)&编程论坛(http://www.52exe.cn)感谢您的支持!
回复 支持 反对

使用道具 举报

发表于 2018-4-5 16:38:27 来自手机 | 显示全部楼层
这点数是不是可以查找编程破解密码?
在线编程(http://www.anycodes.cn)&编程论坛(http://www.52exe.cn)感谢您的支持!
回复 支持 反对

使用道具 举报

发表于 6 天前 来自手机 | 显示全部楼层
请教大佬一下,能教一下我java吗?我是新手,想学java,,谢谢!
在线编程(http://www.anycodes.cn)&编程论坛(http://www.52exe.cn)感谢您的支持!
回复 支持 反对

使用道具 举报

发布主题 上个主题 下个主题 快速回复 返回列表 官方QQ群
在线客服
客 服 中 心
群 机 器 人
网站二维码
收 起 客 服

QQ|Archiver|手机版|小黑屋|Anycodes ( ICP14002806Anycodes在线编程

GMT+8, 2018-11-22 01:12 , Processed in 2.559382 second(s), 98 queries .

Powered by Anycodes

© 2001-2013 吉林市群龙科技有限公司 Inc.

快速回复 返回顶部 返回列表