首页 > 编程语言 >C++ 树进阶系列之深度剖析字典（trie）树

C++ 树进阶系列之深度剖析字典（trie）树

时间：2023-03-21 19:32:49浏览次数：42  
标签：word 进阶 trie C++ int 字符串 节点 字典

1. 前文

本文和大家一起聊聊字典树，从字典二字可知，于功能而言，字典树是类似于英汉字典的一棵信息树。字典树有 2 大特点：

  • 有容乃大。能存储大量的数据信息。
  • 提供有基于关键字的查询、检索机制。

常用字典树存储字符串（单词）信息，使用字典树能方便实现字符串的存储、查询、统计、排序……一系列操作。

2. 字典树特点

字典树是树结构的典型应用，如下图所示，为一棵字典树。字典树的叶节点起标志性作用，标记字符串的结束，类似于C++字符串的结束符号\0。

1.png

通过对结构的观察，可以大致了解字典树的几个特点：

  • 字典树不是二叉树，字典树的每一个节点可以有多个子节点，除根节点外每个节点存储一个字符信息(常用于字符信息存储，但不仅限于字符信息)。
  • 顺着根节点向子节点连接，可以找到一个字符串信息。正因为这个特性，字典树如其名，可存储大量的单词。如从根节点开始，找到它的第一个子节点a，然后找到a的子节点c，再顺着 c找到e。这样就能得到子符串ace。
  • 具有公共前缀的字符串不需要重复存储，公用共同的祖先，如ace和act的公共祖先节点是ac。这也是字典树的一大特点，相比较其它的存储方案，具有高度的空间利用率。

3. 字典树的物理存储

字典树常用的API有插入和查询，其它可根据应用场景的需要进行扩展。

字典树的物理实现可以使用矩阵和链式存储 2 种方案，本文分别探讨这 2 种方案的实现过程。

3.1 链式存储

为了简化操作，实现过程中使用了STL的vector容器存储任一节点的子节点，当然，也可以使用带有头节点的链表。

3.1.1 结构类型

节点类型： 存储字典树的节点信息。

#include <iostream>
#include <vector>
using namespace std;
/*
*字典树节点
*/
struct TrieNode {
	//节点对应字符
	char data;
	//所有子节点指针
	vector<TrieNode*> childs;
    TrieNode(){
		this->data='#';
	} 
};

字典类： 维护字典的常用API，此处先提供基本的API，后面根据需要再扩展。

/*
*字典树类
*/
class Trie {
	private:
		//根节点
		TrieNode* root;
		//字典树上所有字符串(单词)
		vector<string> words;
	public:
		/*
		*构建函数
		*/
		Trie() {
			//初始化节结点
			this->root=new TrieNode();
		}
		/*
		*返回节结点
		*/
		TrieNode* getRoot() {
			return this->root;
		}
		/*
		* 查询节点是否包括值为 ch 的子节点
		*/
		TrieNode* findChild(TrieNode* parent,char ch);
		/*
		*插入新的单词（字符串）
		*/
		void insert(string word);
		/*
		*查询字典树是否存在指定的字符串（单词）
		*/
		TrieNode* search(string word);
		/*
		* 查询字典树上所有字符串（单词）
		*/
		void getAllWords(TrieNode *node,string word);
		/*
		*显示字典树上的所有单词
		*/
		void showAllWords()
}

3.1.2 常规 API

3.1.2.1 insert函数

功能描述： 提供添加字符串（单词）的功能，是构建字典树的第一重要环节。

**实现流程：**现以添加abc字符串为例，讲解添加函数的实现过程。

  • 首先构建根节点。根节点不需要存储具体的数据信息。

2.png

  • 分解字符串abc，先读入字符a，以根节点为当前节点，查询当前节点是否存在值为a的子节点。

3.png

  • 因字典树刚创建，此子节点不存在，则为节结点新建值为a的子节点，并且当前节点指针指向新建的节点。

4.png

  • 继续从字符串中分割出字符b，检查当前节点是否存在值为b的子节点。没有则为当前节点创建值为b的新节点，重设当前节点的指针为新建节点。 5.png

  • 同理，分割出c，因当前节点不存在值为c的子节点，为当前节点构建新节点。且重设当前节点的指针。

6.png

  • 当字符串分割完毕后，最后添加值为#的叶节点作为结束标志符。

7.png

  • 在现有字典树上继续添加abd字符串（单词）时，当前节点需要重置为根结点。分割abd字符串时，因为值为a和b的节点已经存在，则仅让当前节点向下滑动。

8.png

  • 分割出d字符，因当前节点不存在值为d的子节点，新建值为d的子节点。字符串分割完毕，为d节点添加结束子节点。如下图所示。

9.png

编码实现：

实现辅助函数findChild：

/*
* 查询节点是否包括值为 ch 的子节点
*/
TrieNode* Trie::findChild(TrieNode* parent,char ch){
    //获取当前节点的所有子节点
    vector<TrieNode*> childs= parent->childs;
    //遍历查询
    for(int i=0; i<childs.size(); i++) {
        if( childs[i]->data==ch  ) {
            //存在
            return childs[i];
        }
    }
    //不存在
    return NULL;
}

实现insert函数：

/*
* 插入新的单词（字符串）
* 参数：word 需要添加的字符串
*/
void Trie::insert(string word) {
    //从根节点开始
    TrieNode* currentNode=this->root;
    //分割字符串
    for(int i=0; i<word.size(); i++  ) {
        //查询子节点是否存在
        TrieNode* childNode= Trie::findChild(currentNode,word[i]);
        if(childNode==NULL  ) {
            //子节点不存在，构建新节点
            TrieNode* newNode=new TrieNode();
            newNode->data=word[i];
            //成为当前节点的子节点
            currentNode->childs.push_back(newNode);
            //重设当前节点
            currentNode= newNode;
        } else {
            //节点存在
            currentNode= childNode;
        }
    }
    //分割完毕，添加标志性节点
    TrieNode* flagNode=new TrieNode();
    currentNode->childs.push_back(flagNode);
}

测试插入函数：

int main(int argc, char** argv) {
	Trie* trie=new Trie();
	trie->insert("abc");
	trie->insert("abd");
	TrieNode* root=trie->getRoot();
	cout<<"根节点的子节点："<<root->childs[0]->data<<endl;
	cout<<"根节点的子节点的子节点："<<root->childs[0]->childs[0]->data<<endl;
	cout<<"节点的子节点的子节点的子节点:"<<root->childs[0]->childs[0]->childs[0]->data<<endl;
	cout<<"节点的子节点的子节点的子节点:"<<root->childs[0]->childs[0]->childs[1]->data<<endl;
	return 0;
}

输出结果：

10.png

3.1.2.2 search函数

功能描述： 查询给定的字符串（单词）是否存在于字典树中。

实现流程： 查询和插入流程相似。如果检查到存在与分割出来的字符值相等的子节点便继续向下查询，否则，认为查询失败。

不要求一定的是完整字符串（单词），仅是前缀也可以。

如下图所示，虽然字典树中不存在ab字符串（单词），因为存在ab前缀，也认为是存在的。

11.png

编码实现：

/*
* 查询字典树是否存在指定的字符串（单词）
*/
TrieNode* Trie::search(string word) {
    //从节结点开始
    TrieNode* currentNode=this->root;
    //分割需要查询的字符串
    for(int i=0; i<word.size(); i++) {
        //子节点是否存在
        TrieNode* childNode= Trie::findChild(currentNode,word[i]);
        if(childNode!=NULL) {
            //继续查询
            currentNode=childNode;
        } else {
            //不存在
            return NULL;
        }
    }
    //查询成功，只要字符串和字典树上的字符一一对应便可
    return currentNode;
}

测试查询：

int main(int argc, char** argv) {
	Trie* trie=new Trie();
	trie->insert("abc");
	trie->insert("abd");
	TrieNode* root=trie->getRoot();
	TrieNode* node= trie->search("ab");
	if(node!=NULL){
		cout<<"字典树中存在 ab"<<endl; 
	}else{
		cout<<"字典树上不存 ab"<<endl;
	}
	return 0;
}

输出结果：

12.png

3.1.2.3 getAllWords函数

功能描述： 返回字典树上的所有字符串（单词）。

实现流程： 对于整棵树的搜索常用的方案有深度和广度搜索。针对此需求使用深度搜索便能查询出树上的所有单词。

13.png

编码实现：

实现辅助函数 showAllWords：显示字典树上的所有单词。

/*
*显示所有单词
*/
void showAllWords() {
    cout<<"字典树上的所有单词:"<<endl; 
    for(int i=0; i<this->words.size(); i++) {
        cout<<this->words[i]<<endl;
    }
}

实现getAllWords函数：

/*
* 显示字典树上所有字符串
*/
void Trie::getAllWords(TrieNode *node,string word) {
    //当前节点
    TrieNode* currentNode=node;
    //当前节点的子节点
    vector<TrieNode*> childs=currentNode->childs;
    for(int i=0; i<childs.size(); i++) {
        if(childs[i]->data=='#') {
            //如果节点值为结束符号，则获取到了完整单词
            this->words.push_back(word);
        } else {
            //否则，继续递归
            string word_=word;
            word_.append( {childs[i]->data} );
            getAllWords(childs[i], word_ );
        }
    }
}

测试代码：

int main(int argc, char** argv) {
	Trie* trie=new Trie();
	trie->insert("abc");
	trie->insert("abd");
	TrieNode* root=trie->getRoot();
	trie->getAllWords(root,"");
	trie->showAllWords();
	return 0;
}

输出结果：

14.png

3.2 矩阵存储

使用矩阵存储树节点之间的关系也是一种常见方案。

基本存储思想：

  • 对每一个节点进行编号。

  • 以父节点的编号为矩阵的行号，子节点的编号为列号，行与列对应的单元格中存储节点的关系描述（或值、权重）。

15.png

在存储字典树信息时，对上述的存储方案可以稍加改进一下。

  • 如先确定根节点的编号为0，子节点a在矩阵中的列号由其对应的ASCII码决定，当然，会对其范围缩小。

    对应单元格中存储字符出现的顺序编号，并以此编号为此结点的唯一标志符号（类似于主键）。

    这个编号与字符添加顺序有关，与字符本身无关。如下图所示：

16.png

  • 字符b是字符a的子节点。添加过程如下图所示。

17.png

  • 继续完成其它节点关系的存储。

18.png

上述存储的优点：

  • 可以把矩阵的列数限制在 26 之内。
  • 查询任一节点的子节点时，可以根据字符本身所携带信息找到其存储位置。如果b节点下还有字符w的子节点，便能轻易知道其存储位置是 [2]['w'-'a']并能获取w节点的编号。

编码实现：

与前文的链式存储相毕较，仅是改变了存储方式，逻辑是没有发生任何变化。

#include <iostream>
#include <vector>
using namespace std;
/*
* 字典树类
*/
class Trie {
	private:
		/*
		* 矩阵：存储结点之间的关系
		* 1、矩阵的行数由结点数量决定， 简化问题，此处设置为 100
		* 2、矩阵的列数由字符数量决定
		*/
		int matrix[100][26];
		//所有节点由内部统一编号
		int number;
		//字符串的节束标志
		char endFlag[100];
		//存储字典树上的所有单词
		vector<string> allWords;
	public:
        /*
        * 初始化
        */
		Trie() {
			this->number=0;
			for(int i=0; i<100; i++)
				for(int j=0; j<26; j++)
					matrix[i][j]=0;
		}
		/*
		* 插入函数
		*/
		int insert(string word) {
			//当前节点指向节结点
			int current=0;
			//遍历字符串
			for(int i=0; i<word.size(); i++) {
				//检查当前节点下是否存在值为 word[i] 的子节点
				if( matrix[current][ word[i]-'a' ]==0 ) {
					//不存在
					matrix[current][ word[i]-'a' ]=++this->number;
				}
				//重设当前节点
				current=matrix[current][ word[i]-'a' ];
			}
			//添加结束标志
			endFlag[current]='#';
		}

		/*
		*查询指定的字符串是否存在字典树中
		*/
		int search(string word) {
			//从根节点开始
			int current=0;
			//遍历字符串
			for(int i=0; i<word.size(); i++) {
				if( matrix[current][ word[i]-'a' ]==0 ) {
					//没找到
					return -1;
				}
				//继续
				current= matrix[current][ word[i]-'a' ];
			}
			return current;
		}

		/*
		* 使用深度搜索算法获取树上的所有单词
		*/
		void getAllWords(int parent,string word) {
			int current=parent;
			//查询所有子节点
			for(int i=0; i<26; i++) {
				if(matrix[current][i]!=0  ) {
					if( endFlag[matrix[current][i]]=='#'  ) {
                         //注意此处需要添加一下
						word.append( {  char(i+'a')  } );
						this->allWords.push_back(word);
                          //恢复
						word.pop_back();
					} else {
						string word_=word;
						word_.append( {  char(i+'a')  } );
                          //递归调用
						getAllWords( matrix[current][i], word_);
					}
				}
			}
		}
		/*
		*显示字典树上的所有单词
		*/
		void showAllWords() {
			cout<<"字典树上的所有单词:"<<endl;
			for(int i=0; i<this->allWords.size(); i++ )
				cout<<this->allWords[i]<<endl;
        }
};
//测试
int main() {
	Trie*  trie=new Trie();
	trie->insert("abc");
	trie->insert("abd");
	int res= trie->search("ab");
	cout<<res<<endl;
	trie->getAllWords(0,"");
	trie->showAllWords();
	return 0;
}

输出结果：

19.png

使用数组存储的优点：

  • 在查询所有单词时，会自动对其按字典进行排序。
  • 实现起来较直观，易理解。

4. 字典树的应用

至此，想必对字典树有了较好的理解，下文再提供 2 个案例 ，深入体会字典树的神奇之处。

4.1 自动补全

所谓自动补全：指当用户输入单词前缀，则会显示所有与此前缀有关联的单词。此功能在关键字搜索应用中经常可以看到。

如果字典树中存在单词集["cat","caton","cater","this"]，当用户输入cat时，则自动显示所有以cat为前缀的单词：caton、cater。

实现原理：

  • 在字典树中查找前缀是否存在。
  • 如果存在，以此前缀最后一个字符的节点为当前节点进行深度搜索。

20.png

编码实现：

在前文的矩阵实现方案中添加如下函数。

class Trie{
    //省略…… 
    /*
    *自动补全函数
    */
    void autoComplete(string prefix) {
        //查询前缀字符串在字典树中是存在
        int nodeId= this->search(prefix);
        if(nodeId==-1) {
            return;
        }
        //存在，则从此节点开始进行深度搜索
        this->getAllWords(nodeId,prefix);
    }
    //省略……
}
//测试
int main() {
	Trie*  trie=new Trie();
	trie->insert("cat");
	trie->insert("caton");
	trie->insert("cater");
	trie->insert("this");
	trie->autoComplete("cat");
	trie->showAllWords();
	return 0;
}

输出结果：

21.png

4.2 求 2 个字符串的最长公共前缀

所谓字符串的公共前缀指字符串前面相同的部分。如caton和cater的公共前缀是cat。与自动补全功能是相逆的操作。

基本思想：

  • 使用字典树存储所有字符串。
  • 两个字符串的最长公共前缀的长度即他们所在的节点的公共祖先个数，于是，问题就转化为求公共祖先问题。

在树中求解节点的公共祖先问题可以有多种方案，本文侧重于字典树的理解，仅提供下面的穷举算法。其它方案可以自行查阅相关书籍。

/*
* 穷举算法求解 2 个字符串的求公共前缀
*/
string getMaxPrefix(string word,string word_) {
    string prefix="";
    //指向根结点
    int current=0;
    int idx=0;
    //最多查询结点数
    int len=word.size()>word_.size()?word_.size():word.size();
    while(idx<len) {
        int ok=false;
        //查询当前结点的子结点
        for(int i=0; i<26; i++) {
            if(matrix[current][i]==0)continue;
            //存在子结点，且为同一个结点
            if( matrix[current][ word[idx]-'a' ]!=0 &&  matrix[current][ word[idx]-'a' ]==matrix[current][ word_[idx]-'a' ]  ) {
                ok=true;
                prefix.append({ word[idx] });
                current=matrix[current][ word[idx]-'a' ];
                break;
            }
        }
        if(!ok)
            break;
        idx++;
    }
    return prefix;
}

测试：

int main() {
	Trie*  trie=new Trie();
	trie->insert("cat");
	trie->insert("caten");
	trie->insert("cater");
	trie->insert("this");
	string prefix=trie->getMaxPrefix("caten","cater");
	cout<<"公共前缀："<<prefix;
	return 0;
}

输出结果：

22.png

5. 总结

本文介绍了字典树的逻辑结构，并且使用链式和矩阵2种方案实现了字典的物理存储。并且通过 2个具有代表性的案例让大家更深入理解字典树的实际应用。

标签：word,进阶,trie,C++,int,字符串,节点,字典
From： https://blog.51cto.com/gkcode/6139740

相关文章

  • 【C/C++动态内存 or 柔性数组】——对动态内存分配以及柔性数组的概念进行详细解读（张
    前言（栈区、堆区、静态区）请耐心看完，看完后就会对内存中的空间划分有了更深刻的认识！我们知道，任何一个变量的创建都会向内存申请空间用来存放，而在内存中的空间又划分为几个区域......
  • 玩转Serverless架构 概念篇+开发基础篇+开发进阶篇+场景案例篇
    你好，我是老蒋，一个在前端摸爬滚打7年的老兵，目前是国内某一线大厂的资深软件工程师。2017年国内Serverless技术刚刚兴起，我就开始使用和推广Serverless了，当时，我的团......
  • Serverless从入门到进阶：架构、原理与实践
    腾讯云Serverless项目早期参与者撰写，基于腾讯云、阿里云和亚马逊云等多个云厂商的产品和技术；从产品和技术两个维度展开，讲解Serverless的架构设计、技术原理、开发流程、......
  • Python——字符串进阶（六）
    1.字符串格式化#coding=utf-8#字符串格式化#%格式化i="python"s="我来学习%s"%iprint(s)"""%s:这里是一个占位符，后边江会使用一个参数进行替代......
  • 01、执行单个c/c++文件
    使用clion执行单个c/c++文件，本案例使用的msvc编译器。正常执行单文件配置需要配置编译选项，工具链、源文件（执行的目标文件）和编译器点击运行后，会在根目录生成main.exe和m......
  • C++温故补缺(一):引用类型
    引用类型c++增加引用类型的概念,定义方法int&b=a;表示引用类型,引用类型相当于变量的别名,地位和被引用的变量相同,int&b=a;,执行后,变量a和b有相同的值和地址,相当于一......
  • C++温故补缺(五):移动构造函数
    移动构造函数[C11新增]参考:知乎:C++11右值引用和移动构造函数详解.知乎:什么是POD数据类型.C++11之前，对象的拷贝由三个函数决定：拷贝构造函数，拷贝赋值运算符和析构函数......
  • C++温故补缺(四):构造函数和复制构造函数
    构造函数和复制构造函数构造函数对于需要传值的构造函数,如classbox{protected:intX;intY;intZ;public:box(int,in......
  • C++温故补缺(三):基本输入输出
    基本输入输出输出:cout<<输入:cin>>错误:cerr<<日志:clog<<在功能和调用上,cout,cerr和clog看上去无差别,cerr对象是非缓冲的,每个流插入到cerr后会立即输出,而clog......
  • C++温故补缺(二):lambda函数
    Lambda函数参考:CSDNC++11开始,提供了对匿名函数的支持,成为Lambda函数(表达式)通常,lambda函数用于封装传递给算法或异步方法的几行代码,对应不需要复用,且短小的函数,......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99