前缀树

举报
兔老大 发表于 2021/04/22 00:49:16 2021/04/22
【摘要】 是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高。 字典树又称为前缀树或Trie树,是处理字符串常见的数据结构。假设组成所有单词的字符仅是“a”~"z",请实现字典树结构,并包含以下四个主要功能: v...

是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高。

字典树又称为前缀树或Trie树,是处理字符串常见的数据结构。假设组成所有单词的字符仅是“a”~"z",请实现字典树结构,并包含以下四个主要功能:

void insert(String word):添加word,可重复添加。
void delete(String word):删除word,如果word添加过多次,仅删除一次。
boolean search(String word):查询word是否在字典树中。
int prefixNumber(String pre):返回以字符串pre为前缀的单词数量。
思考:

字典树的介绍。字典树是一种树形结构,优点是利用字符串的公共前缀来节约存储空间。

 

基本性质:

字典树的基本性质如下:

  • 根节点没有字符路径。除根节点外,每一个节点都被一个字符路径找到。
  • 从根节点到某一节点,将路径上经过的字符连接起来,为扫过的对应字符串。
  • 每个节点向下所有的字符路径上的字符都不同。

也不需要记,看了实现,很自然的性质就理解了。

每个结点内有一个指针数组,里面有二十六个指针,分别指向二十六个字母。

如果指向某个字母的指针为空,那就是以前没有遇到过这个前缀。

 

搜索的方法为:

(1) 从根结点开始一次搜索;

(2) 取得要查找关键词的第一个字母,并根据该字母选择对应的子树并转到该子树继续进行检索;

(3) 在相应的子树上,取得要查找关键词的第二个字母,并进一步选择对应的子树进行检索。

(4) 迭代过程……

(5) 在某个结点处,关键词的所有字母已被取出,则读取附在该结点上的信息,即完成查找。

其他操作类似处理

插入也一样,只是转到某个子树时,没有子树,那就创建一个新节点,然后对应指针指向新节点即可。

我们给出定义就更清楚了:


      public static class TrieNode {
     	public int path; //表示由多少个字符串共用这个节点
     	public int end;//表示有多少个字符串是以这个节点结尾的
     	public TrieNode[] map;
      //哈希表结构,key代表该节点的一条字符路径,value表示字符路径指向的节点
     	public TrieNode() {
       path = 0;
       end = 0;
       map = new TrieNode[26];
      	}
      }
  
 

path和end都是有用的,接下来会说明

insert:


      public static class Trie {
      private TrieNode root;//头
      public Trie() {
       root = new TrieNode();
       }
      public void insert(String word) {
      if (word == null) {
      return;
       }//空串
      char[] chs = word.toCharArray();
       TrieNode node = root;
      int index = 0; //哪条路
      for (int i = 0; i < chs.length; i++) {
       index = chs[i] - 'a'; //0~25
      if (node.map[index] == null) {
       node.map[index] = new TrieNode();
       }//创建,继续
       node = node.map[index];//指向子树
       node.path++;//经过加1
       }
       node.end++;//本单词个数加1
       }
  
 

      public boolean search(String word) {
      if (word == null) {
      return false;
       }
      char[] chs = word.toCharArray();
       TrieNode node = root;
      int index = 0;
      for (int i = 0; i < chs.length; i++) {
       index = chs[i] - 'a';
      if (node.map[index] == null) {
      return false;//找不到
       }
       node = node.map[index];
       }
      return node.end != 0;//end标记有没有以这个字符为结尾的字符串
       }
  
 

delete: 


      public void delete(String word) {
      //如果有
      if (search(word)) {
      char[] chs = word.toCharArray();
       TrieNode node = root;
      int index = 0;
      for (int i = 0; i < chs.length; i++) {
       index = chs[i] - 'a';
      if (node.map[index].path-- == 1) {//path减完之后为0
       node.map[index] = null;
      return;
       }
       node = node.map[index];//去子树
       }
       node.end--;//次数减1
       }
       }
  
 

prefixNumber:


      public int prefixNumber(String pre) {
      if (pre == null) {
      return 0;
       }
      char[] chs = pre.toCharArray();
       TrieNode node = root;
      int index = 0;
      for (int i = 0; i < chs.length; i++) {
       index = chs[i] - 'a';
      if (node.map[index] == null) {
      return 0;//找不到
       }
       node = node.map[index];
       }
      return node.path;//返回经过的次数即可
       }
  
 

好处:

1.利用字符串的公共前缀来节约存储空间。

2.最大限度地减少无谓的字符串比较,查询效率比较高。例如:若要查找的字符长度是5,而总共有单词的数目是26^5=11881376,利用trie树,利用5次比较可以从11881376个可能的关键字中检索出指定的关键字,而利用二叉查找树时间复杂度是O( log2n ),所以至少要进行log211881376=23.5次比较。可以看出来利用字典树进行查找速度是比较快的。

 

应用:

<1.字符串的快速检索

<2.字符串排序

<3.最长公共前缀:abdh和abdi的最长公共前缀是abd,遍历字典树到字母d时,此时这些单词的公共前缀是abd。

<4.自动匹配前缀显示后缀

我们使用辞典或者是搜索引擎的时候,输入appl,后面会自动显示一堆前缀是appl的东东吧。

那么有可能是通过字典树实现的,前面也说了字典树可以找到公共前缀,我们只需要把剩余的后缀遍历显示出来即可。

 

相关题目:

一个字符串类型的数组arr1,另一个字符串类型的数组arr2。

arr2中有哪些字符,是arr1中出现的?请打印。

arr2中有哪些字符,是作为arr1中某个字符串前缀出现的?请打印。

arr2中有哪些字符,是作为arr1中某个字符串前缀出现的?请打印arr2中出现次数最大的前缀。

文章来源: fantianzuo.blog.csdn.net,作者:兔老大RabbitMQ,版权归原作者所有,如需转载,请联系作者。

原文链接:fantianzuo.blog.csdn.net/article/details/83141560

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。