构建文章编目概要原理Trie树，利用Trie树进行查询，实现仿真(盲目暴力)，实现空间优化
个人资料
树是数据结构，有“字典树”. lqdty这样很棒的中文名字。 字典是为了查单词。 因此，树的主要作用是在给定字符串的集合中查找给定的模式列(集合)。 与KMP算法相比，树的最大特征在于它是
制作原理树的树树树不是我们经常使用的二叉树，而是多叉树。准确地说，它的最大分支数由字典的字符集含有的字符数决定，例如：如果给定的词典都是小写的英语字母，则树是26叉树。 为什么呢，如果画图表生成树的话就是：
图1:如果我们有一本字典叫： apple、apply、app，那么Trie树应该就是这样：
在图2:词典中添加三个单词： able、about和above后，树就这样变成了：
如果将不是以图3: '开头的单词的： be、beat添加到词典中，则Trie树就是这样：
如上图所示，总结Trie树的基本性质:
寻求公共路径，以便覆盖的字符串尽可能多。 如果字符串中的所有字符无法复盖此公共路径，请为多余的字符创建新的分支路径。 在字符串的每个结尾做标记。 根节点不包含任何字符。 把以上性质与我们的图对应起来，很容易理解
/表示根节点，该节点不表示任何字符。 红圈表示字符串的结束，如果查询进行到红圈部分的结束，则查询成功，否则失败。 一般的树可以这样画。 (/表示根节点) ) ) ) ) ) )。
图43:字符集包含n个字符，字符串数不定的树3360
对于使用Trie树进行查询的图3的Trie，查询了以下集合的字符串： {“app”、“ab”、“back”}。 查询的过程和结果如下：
在图：树视图中搜索字符串集合{'app '、' ab '、' back'}的过程：
上图完全涵盖了可能发生Trie查询的情况，共有3种情况，2种状态为：
如情况1(3360 )查询“app”所示，沿着路径下行时，每个都匹配，正好字符串的最后一个字符是结束标签。 情况2 ) 3360查询失败并沿着路径下行，例如查询“ab”，每个查询都匹配，但字符串的最后一个字符不是结束标记。 情况3 ) 3360查询失败，如查询“bb”失败
匹配的字符串都出现在词典里。 匹配字符串的最后一个字符在词典中是结束标记。 模拟的实现(盲目暴力)基于上述原理，可以直接使用模拟方式来实现树形树：
# include iostream # include string # define maxn 26//字符集中包含的字符数大小； using namespace std； struct Trie { char data； //该位置的文字； int num； //统计通过该节点的单词数量； Trie **son； //该位置的所有子节点的根； bool is空值； //判断这里是否是最后一个节点的Trie () ) { num=1； son=new Trie*[26]； for(intI=0； i maxn； I ) son[i]=nullptr； isNull=0； (} ~Trie ) ) for ) intI=0； i maxn； I ) { delete[] son[i]； son[i]=nullptr； } delete[] son； son=nullptr； }； voidinsertnode(trie*t，string str )//插入字典树； Trie *Temp=T； for(intI=0； i str.size (； I ) { int pos=str[i]-'a '； if (！ temp-son[pos](//此分支不存在，创建新分支； Temp-son[pos]=new Trie； Temp-son[pos]-data=str[i]； } else Temp-num； Temp=Temp-son[pos]；
} Temp->isNull = 1;}bool Trie_search(Trie *T,string str) { for(int i = 0; i < str.size(); i++) { int pos = str[i]-'a'; if(!T->son[pos]) return 0; T = T->son[pos]; } if(T->isNull) return 1; //此节点是单词结束,查找成功; return 0;}int main() {//测试标程; int n; cin>>n; string str; Trie *T = new Trie; for(int i = 0; i < n; i++) { cin>>str; insertNode(T,str); } for(int i = 0; i < n; i++) { cin>>str; if(Trie_search(T,str)) cout<<"Yes!"<<endl; else cout<<"No!"<<endl; } return 0;}显然,以上的实现是和原理一一对应的,其好处是代码实现好理解,但是相应的,也有以下不足之处:
Trie树结构复杂,使用了双层指针,插入查询的实现涉及到指针,不易实现.灵活度不高,不能很好地适应比赛千变万化的题目.那么能不能对这种实现进行优化呢?答案是显然且必要的,下面我们来看看优化的算法.
空间优化优化主要是对空间方面的优化,我们可以使用ACM(更加巧妙)的方式,来实现Trie树:
#include<iostream>#include<string>#include<cstring>using namespace std;const int maxn = 2e+5; //maxn近似为单词所有的结点数,尽可能开大;int sc = 'a',cnt = 0,trie[maxn][26]; //字典树;bool flag [maxn]; //判定是否是单词结束;void init() { cnt = 0; memset(trie[0],0,sizeof trie[0]);}void insert_(string str) { int root = 0; for(int i = 0; i < str.size(); i++) { int id = str[i] - sc; if(!trie[root][id]) trie[root][id] = ++cnt; root = trie[root][id]; } flag[root] = true;}bool search_(string str) { int root = 0; for(int i = 0; i < str.size(); i++) { int id = str[i] - sc; if(!trie[root][id]) return false; root = trie[root][id]; } if(flag[root] == true) return true; return false;}int main() {//测试标程; int n; init(); cin>>n; string str; for(int i = 0; i < n; i++) { cin>>str; insert_(str); } for(int i = 0; i < n; i++) { cin>>str; if(search_(str)) cout<<"Yes!"<<endl; else cout<<"No!"<<endl; } return 0;}以上就是一个Trie树的模板,它和模拟实现的最大区别在于: 使用横向空间代替纵向空间,减少Trie树的层数.
上述模板是二维数组存储Trie树,其含义如下:
Trie[][]第一维表示字符串的路径,按照路径可匹配一个字符串.Trie[][]第二维表示某个字符,即对于当前路径下,是否存在一个分支,包含该字符.Trie[][]存储字符串时,其原理如下:
将字符串的每一个字符映射为对应的id,cnt用来记录当前插入到Trie树中的字符总数.
Trie[root][id]的值有两层含义:
若Trie[root][id] > 0,则说明当前映射值为id的字符已经存在Trie树.在1成立的条件下,Trie[root][id]的值表示当前映射值为id的字符的下一个字符在Trie树中的位置.依据上述原理,可以得到插入Trie树的算法:
初始化root = 0,遍历字符串,对于其每一个字符,计算其映射值id,检查:Trie[root][id] == 0是否成立,若成立,则进行插入,Trie[root][id] = ++cnt.若不成立,说明该位置已经有该字符,直接找到下一个字符应插入的位置: root = trie[root][id].重复上述步骤,直到字符串完全插入Trie树.同理,可以得到从Trie树匹配字符串的算法:
初始化root = 0,遍历字符串,对于其每一个字符,计算其映射值id,检查:Trie[root][id] == 0是否成立,若成立,则说明Trie树当前路径不存在该字符,返回匹配失败.若成立,则说明当前路径存在该字符,找到下一个字符的位置: root = trie[root][id],重复2-3步.若顺利匹配完整个字符串,则应该检查字符串结束的位置在Trie树中是否是结束标志:若flag[root] == true成立,表明是结束标志,则返回匹配成功,否则返回匹配失败.以上,就是Trie的入门讲解,有兴趣的话可以去其他地方看看进阶用法.