Trie树(字典树)_实现模糊查找(支持中文)

搜索功能一般都有根据你的输入快速显示对应关键字的功能，比如你输入”刘”, 搜索框的下拉列表会显示“刘德华”,”刘若英”,”刘欢”等，你继续输入‘德’，将查询关键字变成”刘德”,显示的候选字列表会显示”刘德华”,”刘德华专辑”,”刘德华演唱会”等。下面将使用Trie树（字典树）来实现此功能。

一、什么是Trie树

Trie书又名字典树，字典是由一组词组成的集合，而字典树对这个集合进行了结构化的组织，将字典用另一种表达方式进行了表达。
首先字典书对一些具有公共前缀的词进行了“压缩”，大大减小了它占用的空间。同时对于字典内词的前缀检索也十分迅速，下面看一个图来理解下字典树：

上面的图就是字典树，字典树通过从根节点到子节点的路径来表达一个此，图中红色节点为一个词的最后一个节点，也就是说上面的树代表的单词有abc、ab、bd、dda,也就是红色节点的个数。其中，根节点不表示任何字符。字典树使用公共前缀压缩了存储结构，同时对于模糊匹配提供了很好的支持。

二、实现搜索词的模糊查找

（1）完整可运行的代码：

#include<iostream>
#include<string>
#include<map>
#include<vector>
using namespace std;
//字典树节点
class trieNode
{
public:
	trieNode() :count(0) {};
	//以当前节点结尾的字符串的个数
	int count;
	map<char16_t, trieNode*> child;
};
//字典树
class Trie
{
public:
	Trie() { root = new trieNode(); };
	void insert_string(const u16string& str);
	vector<u16string> get_str_pre(const u16string& str);
private:
	//辅助函数
	void add_str(trieNode* preNode, u16string str, vector<u16string>& ret);
	trieNode* search_str_pre(const u16string& str);

	trieNode* root;
};
//插入字符串，构建字典树
void Trie::insert_string(const u16string& str)
{
	if (!root || str.empty())
		return;

	trieNode* currentNode = root;

	for (auto& chr : str)
	{
		auto Iter = currentNode->child.find(chr);
		if (Iter == currentNode->child.end())
		{
			//如果当前字符不在字典树中，新建一个节点插入
			trieNode* newNode = new trieNode();
			currentNode->child.insert(make_pair(chr, newNode));
			currentNode = newNode;
		}
		else
		{
			//如果当前字符在字典书中，则将当前节点指向它的孩子
			currentNode = Iter->second;
		}
	}
	currentNode->count++;
}
//查找以str为前缀的节点
trieNode* Trie::search_str_pre(const u16string& str)
{
	if (!root || str.empty())
		return nullptr;

	trieNode* currentNode = root;
	for (auto& chr : str)
	{
		auto Iter = currentNode->child.find(chr);
		if (Iter != currentNode->child.end())
		{
			currentNode = Iter->second;
		}
		else
			return nullptr;
	}

	return currentNode;
}
//查找以str为前缀的所有字符串，保存在vector中返回
vector<u16string> Trie::get_str_pre(const u16string& str)
{
	vector<u16string> ret;
	trieNode* pre = search_str_pre(str);
	if (pre)
	{		
		add_str(pre, str, ret);
	}
	return ret;
}
//将preNode的所有子节点中字符串加入str前缀，然后插入到vector中
void Trie::add_str(trieNode* preNode, u16string str, vector<u16string>& ret)
{
	for (auto Iter = preNode->child.begin(); Iter != preNode->child.end(); ++Iter)
	{
		add_str(Iter->second, str + Iter->first, ret);
	}
	if (preNode->count != 0)
		ret.push_back(str);
}


int main()
{
	//为了终端能打印出中文
	setlocale(LC_ALL, "");
	//测试字符串用于构建字典树，utf-16编码，能同时保存中英文
	vector<u16string> hotworlds = { u"杨文婷",u"联系",u"杨洋洋",u"杨sir大警官",u"杨y文w婷t",u"杨文婷是小学生",
		u"杨钰莹",u"杨文婷ywt是小学生",u"联系a群众",u"阳光么",u"阳光明媚",u"ywt是小学生",u"联系ywt",u"杨文t爱吃面",u"杨文婷妹妹",
		u"杨光明眉",u"小学生",u"杨文婷爱吃面",u"我是小学生",u"我是中国人",u"ywt要吃面",u"y杨文婷",u"有问题" };
	Trie trie;
	for (auto& maString : hotworlds)
	{
		trie.insert_string(maString);
	}

	//输入“杨文婷”，返回所有以“杨文婷”为前缀的词
	vector<u16string> res = trie.get_str_pre(u"杨文婷");

	//打印结果
	for (auto& resString : res)
	{
		for (auto& chr : resString)
		{
			printf("%lc", chr);
		}
		printf("\n");
	}

	system("pause");
	return 0;
}

（二）运行结果：