当前位置:   article > 正文

Trie树(字典树、前缀树) (小白整理)_prefix tree

prefix tree

此处大佬文章引路:

 

字典树(Trie)详解 - Seaway-Fu - 博客园 (cnblogs.com)

Trie树(Prefix Tree)介绍_神奕的专栏-CSDN博客_prefix tree

目录

0.初遇字典树

1.用处:

2.性质:

3.作用扩展:

4.优缺点:

5.代码实现(建树、查询):


0.初遇字典树

Trie树,又叫字典树前缀树(Prefix Tree)单词查找树 或 键树,是一种多叉树结构。空间换时间:开的空间大,但查询效率快

 可以发现,这棵字典树用边来代表字母,而从根结点到树上某一结点的路径就代表了一个字符串。举个例子,1→4→8→12 表示的就是字符串 caa。(图片摘自OI Wiki)

宽度:范围(例:小写英文字母->26)

深度:最长的字母长度加1(root根节点独占顶层)

1.用处:

维护字符串,存储 字典 的一种数据结构。

2.性质:

1根节点不包含字符,除根节点外的每一个子节点都包含一个字符。

2从根节点到某一个节点,路径上经过的字符连接起来,为该节点对应的字符串。

3每个节点的所有子节点包含的字符互不相同。

注:

<1>在建树的时候,每个结点放个标记,看它能不能构成单词。

<2>两个有公共前缀的关键字,在Trie树中前缀部分路径相同,所以又叫前缀树。

3.作用扩展:

(1)字符串检索:

检索/查询功能是Trie树最原始的功能。思路就是从根节点开始一个一个字符进行比较

<1>如果沿路比较,发现不同的字符,则表示该字符串在集合中不存在。

<2>如果所有的字符全部比较完并且全部相同,还需判断最后一个节点的标志位(标记该节点是否代表一个关键字)。

struct trie_node

{

    bool trie_flag;   // 标记该节点是否代表一个关键字/单词

    trie_node_next [26]; // 各个子节点

};

(2) 词频统计:Trie树常被搜索引擎系统用于文本词频统计。

struct trie_node

{

    int words_count;   // 记录该节点代表的单词的个数

    trie_node_next [26]; // 各个子节点

};

思路:为了实现词频统计,我们修改了节点结构,用一个整型变量count来计数。对每一个关键字执行插入操作,若已存在,计数加1,若不存在,插入后count置1。

(3) 字符串排序:

思路:遍历一次所有关键字,将它们全部插入trie树,树的每个结点的所有儿子很显然地按照字母表排序,然后先序遍历输出Trie树中所有关键字即可。

(4)前缀匹配:

例如:找出一个字符串集合中所有以ab开头的字符串。我们只需要用所有字符串构造一个trie树,然后输出以a->b->开头的路径上的关键字即可。

trie树前缀匹配常用于搜索提示。如当输入一个网址,可以自动搜索出可能的选择。当没有完全匹配的搜索结果,可以返回前缀最相似的可能。

(5)如后缀树,AC自动机等。

4.优缺点:

优点:插入、查询O(n) (n:点的个数) 的复杂度,不用求hash值,字典序排序。

缺点:hash函数很好时,trie树的查找效率比不过哈希搜索,空间消耗比较大。

5.代码实现(建树、查询):

代码如下(改自OI Wiki):

  1. struct trie {
  2.   int next[100000][26], cnt; //前一维表示存的结点,后一维表示宽度,如果想添加其它功能,可以把int型改为结构体类型
  3.   bool exist[100000];  //判断此结点能否构成单词
  4.   void insert(char *s, int l) {  // 插入字符串s,l为字符串s的长度
  5.     int p = 0;
  6.     for (int i = 0; i < l; i++) {
  7.       int c = s[i] - 'a'; //这里是把char型换成int型0~25储存起来
  8.       if (!next[p][c]) next[p][c] = ++cnt;  // 如果没有,就添加结点
  9.       p = next[p][c];
  10.     }
  11.     exist[p] = 1;
  12.   }
  13.   bool find(char *s, int l) {  // 查找字符串  //可根据具体情况返回bool/int型
  14.     int p = 0;
  15.     for (int i = 0; i < l; i++) {
  16.       int c = s[i] - 'a';
  17.       if (!next[p][c]) return 0;
  18.       p = next[p][c];
  19.     }
  20.     return exist[p];
  21.   }};

板子题:P2580 于是他错误的点名开始了 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路:此例题就需要根据find返回的int型判断点到的次数,将exist数组类型改为int型

注:next数组前一维是所有字符串中字母的总个数,如字符串长度100以内,个数1e5,那nxet[N][26]中的前一维需要开到1e6~1e7(有前缀重叠情况),即 N的大小<=字符串长度*字符串个数

AC代码如下:

  1. /*
  2. trie树 板子题 洛谷P2580 于是他错误的点名开始了
  3. https://www.luogu.com.cn/problem/P2580
  4. */
  5. #include<bits/stdc++.h>
  6. using namespace std;
  7. typedef long long ll;
  8. const int N=1e6+10;
  9. int n,m;
  10. char s[100];
  11. struct trie{
  12. int next[N][26],cnt=0; //前一维存的结点,后一位宽度
  13. int exist[N]; //判断此结点能否构成单词
  14. void insert(char *s){
  15. int p=0;
  16. //printf("strlen(s)=%d\n",strlen(s));
  17. for(int i=0;i<strlen(s);i++)
  18. {
  19. int c=s[i]-'a';
  20. if(!next[p][c])
  21. {
  22. next[p][c]=++cnt;
  23. }
  24. p=next[p][c];
  25. }
  26. exist[p]=1;
  27. }
  28. int find(char *s){
  29. int p=0;
  30. for(int i=0;i<strlen(s);i++)
  31. {
  32. int c=s[i]-'a';
  33. if(!next[p][c])
  34. {
  35. return 0;
  36. }
  37. p=next[p][c];
  38. }
  39. if(exist[p]==1)
  40. {
  41. exist[p]=2;
  42. return 1;
  43. }
  44. else
  45. return 2;
  46. }
  47. }trie_tree;
  48. int main()
  49. {
  50. scanf("%d",&n);
  51. for(int i=1;i<=n;i++)
  52. {
  53. scanf(" %s",s);
  54. trie_tree.insert(s);
  55. }
  56. scanf("%d",&m);
  57. for(int i=1;i<=m;i++)
  58. {
  59. scanf(" %s",s);
  60. if(trie_tree.find(s)==1)
  61. {
  62. printf("OK\n");
  63. }
  64. else if(trie_tree.find(s)==2)
  65. {
  66. printf("REPEAT\n");
  67. }
  68. else
  69. {
  70. printf("WRONG\n");
  71. }
  72. }
  73. return 0;
  74. }

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/空白诗007/article/detail/994785
推荐阅读
相关标签
  

闽ICP备14008679号