字符串匹配数据结构 --Trie树 高效实现搜索词提示 / IDE自动补全

1. 算法背景

之前我们了解过单模式串匹配的相关高效算法 – BM/KMP，虽难以理解，缺能够给予我们足够的宽度来扩展思维。
1. BF 和 RK 算法实现
2. BM 和 KMP 算法详解

但单模式串的匹配仅仅限于一个模式串从一个主串中查找，实际场景中我们却需要从多个主串中查找模式串，像IDE/文本编辑器甚至搜索引擎这样的庞大的数据量下多模式串中的高效查找却是单模式串查找效率无法满足的。

基于多模式串的高效搜索能力是需要我们重点关注的方向，也就是我们今天要推出的Tire 树 数据结构。

Trie 树能够比较友好得实现搜索词提示功能，接下来详细看看Trie树的原理。

2. Trie 树实现原理

Trie树 的核心目的是为了让拥有公共前缀的主串能够以一个树的形态存在。就像树有主干分支，有叶子分支一样，trie树让公共前缀的部分形成主干分支，没有公共前缀的部分就各自形成叶子分支。

这样的一个字符串树能够极大得方面模式串的查找，顺着主干分支直接移动模式串的下标匹配，非主干分支也能够快速匹配。而不需要像单模式串那样，为了加速匹配的过程还需要考虑前缀/后缀子串。

2.1 Trie 树的构建

Trie 树的大体形态如下：

将:adas,ada,adf,am,ao,aok,dk,dqe,deq 这样的独立主串中的字符组织成一个个树的节点，从树的根节点开始，沿着主干分支即可能够快速确认模式串是否能够匹配。

Trie树中不一定是叶子结点才是一个字符串的结束字符，叶子节点中间也可能有结束字符。

所以构建trie树的过程需要为上下节点之间建立连接关系，从而保证查找能够从上一个节点准确得落到下一个节点。

构建形态如下：

为每一个节点维护一个字符串全集的数组，比如 am这个字符串，在a节点处维护一个26长度的节点数组，其中a字符串所在下标不为空且指向下一个字符数组中的m，而b,c,d…等其他字符的数组为空即可。

ps : 这里大家也能够发现一个问题，就是构建Trie树的过程需要消耗大量的空间，虽然有公共前缀的公共存储，但是对于一个字符存储来说，需要26个额外的指针空间，所以Trie树的内存消耗问题显而易见。

定义TrieNode节点如下：

// Trie nodeinfo
class TrieNode {public:char data_;TrieNode *children_[26];bool isEndingChar_;TrieNode(char data='/') :data_(data),isEndingChar_(false){memset(children_, 0, sizeof(TrieNode *)* 26);};
};

构建的主要过程如下：

• 主串数组逐个交给初始化后的根节点
• 根节点逐个遍历输入主串的字符：
  • 确认每个字符所处下一层的children_数组中的位置（因为这里是26个字母，index = input[i] - ‘a’）
  • 核对下一层的children数组是否为空，不为空则表明是公共前缀，继续处理下一个输入字符
  • 为空 则说明需要为当前input[i]构建一个新的TrieNode添加进来
• 完成将一个输入主串的所有字符添加到Trie树之后 更新结尾标记（表示当前位置为这个主串的结尾标记）。

void Trie::insert(string des) {if (des.size() <= 0) {return;}TrieNode *tmp = root_;int i;// Traverse every character in desfor (i = 0;i < des.size(); i++) {// The des[i] insert position at trie tree.int index = des[i] - 'a';if (tmp->children_[index] == nullptr) {TrieNode *newNode = new TrieNode(des[i]);tmp->children_[index] = newNode; }tmp = tmp->children_[index];}tmp->isEndingChar_ = true;
}

2.2 Trie树的查找

完成了Trie树的构建，剩下的查找就比较容易了。

• 拿着输入的字符串逐个字符遍历，确认每一个字符的index
• 如果这个字符index对应的TrieNode为空，且这个字符不是整个字符串的最后一个字符，则说明不匹配
• 如果不为空，则说明Trie树中有这个节点，那表示当前字符匹配，继续后续字符的处理
• 当最后一个字符对应的TrieNode中的End标记为真，则说明字符串匹配；否则不匹配

代码如下：

// Judge if a string is match with Trie tree
bool Trie::find(string des) {if (des.size() == 0) {return false;}TrieNode *tmp = root_;int i;for (i = 0;i < des.size(); i++) {// The index of the current char's positionint index = des[i] - 'a';if (tmp->children_[index] == nullptr) {return false;}// Move the tmp to the next linetmp = tmp->children_[index];}// End position to ensure wether the input str is match.if (tmp->isEndingChar_ == false) {return false;}return true;
}

2.3 Trie树的遍历

Trie树的遍历就是一个深搜的过程，沿着一个方向直接找到最后一个节点即可。

// Traverse the trie tree recursion
// para1: TrieNode
// Para2: prefix string
// para3: result vector
void Trie::dfs_traverse(TrieNode *p, string buf, vector<string> &tmp_str) {if (p == nullptr) {return;}// if match, just and the result to vectorif (p->isEndingChar_ == true) {tmp_str.push_back(buf);}for (int i = 0; i < 26; i++) {if (p->children_[i] != nullptr) {// Just add the prefix every timedfs_traverse(p->children_[i], buf+(p->children_[i]->data_), tmp_str);}}
}// Print the all trie tree string with dictionary order
void Trie::printTrie() {vector<string> tmp_str;int i, j;for (i = 0;i < 26; i++) {string buff = "";if (root_->children_[i] != nullptr) {// Will be called recursion.// Input with TrieNode, the prefix character and the result vectordfs_traverse(root_->children_[i], buff + root_->children_[i]->data_, tmp_str);}}cout << "Trie string: " << tmp_str.size() << endl;for (j = 0;j < tmp_str.size(); j++) {cout << tmp_str[j] << endl;}
}

2.4 Trie树的时间/空间复杂度

• 空间复杂度：空间消耗不用说，对于总共n个字符的所有主串来说，上仅仅是26个字母，以上为每一个字符都实现了一个26位的指针数组。64位机器下的最坏空间消耗：(26*8 + 1)*n B，显然Trie树的空间消耗是一个非常大的问题。当然对于公共前缀比较多的场景，构建Trie的空间会一定程度的降低。
• 时间复杂度：构建Trie树需要遍历 n个字符中的每一个字符 消耗O(n)；构建好Trie树之后，每一个模式串的匹配同样只需要遍历一次 消耗O(k)，整个时间复杂度是O(k+n)。

2.5 Trie 树 Vs 散列表/红黑树

综上，如果需要多模式串的精确功能，红黑树/散列表等工业实现会更合适；如果需要搜索词提示这样的功能，则Trie树的结构天然适合。

以上完整测试代码：

#include <iostream>
#include <string>
#include <vector>using namespace std;// Trie nodeinfo
class TrieNode {public:char data_;TrieNode *children_[26];bool isEndingChar_;TrieNode(char data='/') :data_(data),isEndingChar_(false){memset(children_, 0, sizeof(TrieNode *)* 26);};
};// Trie tree info with a root node
class Trie {
public: Trie() {root_ = new TrieNode();}~Trie() {destory(root_);}void insert(string des);bool find(string des);void printTrie();void destory(TrieNode *p);void dfs_traverse(TrieNode *p, string buf, vector<string> &tmp_str);private:TrieNode *root_;
};// Delete the TrieNode, and release the space
void Trie::destory(TrieNode *p) {if (p == nullptr) {return;}for (int i = 0;i < 26; i++) {destory(p->children_[i]);}delete p;p = nullptr;
}void Trie::insert(string des) {if (des.size() <= 0) {return;}TrieNode *tmp = root_;int i;for (i = 0;i < des.size(); i++) {// The des[i] insert position at trie tree.int index = des[i] - 'a';if (tmp->children_[index] == nullptr) {TrieNode *newNode = new TrieNode(des[i]);tmp->children_[index] = newNode; }tmp = tmp->children_[index];}tmp->isEndingChar_ = true;
}// Traverse the trie tree recursion
void Trie::dfs_traverse(TrieNode *p, string buf, vector<string> &tmp_str) {if (p == nullptr) {return;}// if match, just and the result to vectorif (p->isEndingChar_ == true) {tmp_str.push_back(buf);}for (int i = 0; i < 26; i++) {if (p->children_[i] != nullptr) {// Just add the prefix every timedfs_traverse(p->children_[i], buf+(p->children_[i]->data_), tmp_str);}}
}// Print the trie tree with dictionary order
void Trie::printTrie() {vector<string> tmp_str;int i, j;for (i = 0;i < 26; i++) {string buff = "";if (root_->children_[i] != nullptr) {// Will be called recursiondfs_traverse(root_->children_[i], buff + root_->children_[i]->data_, tmp_str);}}cout << "Trie string: " << tmp_str.size() << endl;for (j = 0;j < tmp_str.size(); j++) {cout << tmp_str[j] << endl;}
} // Judge if a string is match with Trie tree
bool Trie::find(string des) {if (des.size() == 0) {return false;}TrieNode *tmp = root_;int i;for (i = 0;i < des.size(); i++) {// The index of the current char's positionint index = des[i] - 'a';if (tmp->children_[index] == nullptr) {return false;}// Move the tmp to the next linetmp = tmp->children_[index];}// End position to ensure wether the input str is match.if (tmp->isEndingChar_ == false) {return false;}return true;
}int main() {string s[5] = {"adafs", "dfgh", "amkil", "doikl", "aop"};Trie *trie = new Trie();for (int i = 0; i < 5; i++) {trie->insert(s[i]);}trie->printTrie();string in_str;cout << "Inpunt a string :" << endl;cin >> in_str;if (trie->find(in_str)) {cout << "Trie tree has the str: " << in_str << endl;} else {cout << "Trie tree doesn't have the str : " << in_str << endl;}return 0;
}

输出如下：

> ./trie_alg
Trie string: 5
adafs
amkil
aop
dfgh
doiklInpunt a string :
aoe
Trie tree doesn't have the str : aoe

3. Trie树的应用 – 搜索词提示功能

想要实现搜索词提升这样的功能，需要基于Trie树实现做一些逻辑的添加。比如 用户输入h,则能够返回h为开头的字符串；输入he，则能够返回he开头的字符。。。

类似如下：

source code: https://github.com/BaronStack/DATA_STRUCTURE/blob/master/string/trie_alg.cc

实现逻辑如下：

// Traverse the trie tree recursion
void Trie::dfs_traverse(TrieNode *p, string buf, vector<string> &tmp_str) {if (p == nullptr) {return;}// if match, just and the result to vectorif (p->isEndingChar_ == true) {tmp_str.push_back(buf);}for (int i = 0; i < 26; i++) {if (p->children_[i] != nullptr) {// Just add the prefix every timedfs_traverse(p->children_[i], buf+(p->children_[i]->data_), tmp_str);}}
}// Input the prefix, and search the prefix related string
void Trie::printTrieWithPrefix(string start) {vector<string> tmp_str;int i, j;TrieNode *tmp = root_;// Ensure prefix is existfor (int i = 0;i < start.size(); i++) {int index = start[i] - 'a';if (tmp->children_[index] == nullptr) {cout << "No prefix with " << start << endl;return;} tmp = tmp->children_[index];}// Prefix is a matched stringtmp_str.push_back(start);for (i = 0;i < 26; i++) {string buff = start;if (tmp->children_[i] != nullptr) {// Will be called recursiondfs_traverse(tmp->children_[i], buff + tmp->children_[i]->data_, tmp_str);}}cout << "Trie string: " << tmp_str.size() << endl;for (j = 0;j < tmp_str.size(); j++) {cout << tmp_str[j] << endl;}
}

输出如下：

Trie string: 5
adafs
amkil
aop
dfgh
doikl
Input a prefix :
a
Trie string: 3
adafs
amkil
aop

同样，如果想要为每个字符串增加更多的指标 – 比如公共前缀重合度 这样的属性可以增加到TrieNode数据结构中，在构建Trie树的过程中为每一个TrieNode的这个属性做对应的变更即可。