Trie树_字典树(字符串排序)简介及实现_

1、Trie树_字典树(字符串排序)简介及实现_ 1.综述 又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以常常被搜索引擎系统用于文本词频统计。 它的优点是：利用字符串的公共前缀来节约存储空间，最大限度地削减无谓的字符串比较，查询效率比哈希表高。 Trie树结构的优点在于： 1） 不限制子节点的数量； 2） 自定义的输入序列化，突破了具体语言、应用的限制，成为一个通用的框架； 3） 可以进行最大Tokens序列长度的限制； 4） 依据已定阈值输出重复的字符串； 5） 供应单个字符串频度查找功能； 6） 速度快，在两

2、分钟内完成1998年1月份人民日报（19056行）的重复字符串抽取工作。 2.性质 它有3个基本性质： 1) 根节点不包含字符，除根节点外每一个节点都只包含一个字符。 2) 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。 3) 每个节点的全部子节点包含的字符都不相同。 3.基本操作 其基本操作有:查找、插入和删除,当然删除操作比较少见.我在这里只是实现了对整个树的删除操作,至于单个word的删除操作也很简洁. 4.实现方法 搜索字典项目的方法为： (1) 从根结点开头一次搜索； (2) 取得要查找关键词的第一个字母，并依据该字母选择对应的子树并转到该子树连续进行检索； (

3、3) 在相应的子树上，取得要查找关键词的其次个字母,并进一步选择对应的子树进行检索。 (4) 迭代过程 (5) 在某个结点处，关键词的全部字母已被取出，则读取附在该结点上的信息，即完成查找。 其他操作类似处理 5. Trie原理Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。 6.代码实现 代码如下: const int branchNum = 26; /声明常量 int i; struct Trie_node boolisStr; /记录此处是否构成一个串。 Trie_node*nextbranchNum;/指向各个子树的指针,下标0-25代表2

4、6字符 Trie_node():isStr(false) memset(next,NULL,sizeof(next); ; class Trie public: Trie(); voidinsert(const char* word); boolsearch(char* word); voiddeleteTrie(Trie_node *root); / voidprintTrie(Trie_node *root); /new add private: Trie_node* root; ; Trie:Trie() root =new Trie_node(); void Trie:insert(c

5、onst char* word) Trie_node*location = root; while(*word) if(location-next*word-a = NULL)/不存在则建立 Trie_node *tmp = new Trie_node(); location-next*word-a = tmp; location = location-next*word-a; /每插入一步，相当于有一个新串经过，指针要向下移动 word+; location-isStr = true; /到达尾部,标记一个串 bool Trie:search(char *word) Trie_node*lo

6、cation = root; while(*word location) location= location-next*word-a; word+; return(location!=NULL location-isStr); void Trie:deleteTrie(Trie_node *root) for(i =0; i branchNum; i+) if(root-nexti!= NULL) deleteTrie(root-nexti); deleteroot; void main() /简洁测试 Trie t; t.insert(a); t.insert(abandon); char

7、 * c= abandoned; t.insert(c); t.insert(abashed); if(t.search(abashed) printf(truen); /已经插入了 有时，我们会碰到对字符串的排序，若采纳一些经典的排序算法，则时间简单度一般为O(n*lgn)，但若采纳Trie树，则时间简单度仅为O(n)。 Trie树又名字典树，从字面意思即可理解，这种树的结构像英文字典一样，相邻的单词一般前缀相同，之所以时间简单度低，是由于其采纳了以空间换取时间的策略。 下图为一个针对字符串排序的Trie树(我们假设在这里字符串都是小写字母)，每个结点有26个分支，每个分支代表一个字母，结点

8、存放的是从root节点到达此结点的路经上的字符组成的字符串。 将每个字符串插入到trie树中，到达特定的结尾节点时，在这个节点上进行标记，如插入afb，第一个字母为a，沿着a往下，然后其次个字母为f，沿着f往下，第三个为b，沿着b往下，由于字符串最终一个字符为0，因而结束，不再往下了，然后在这个节点上标记afb.count+，即其个数增加1. 之后，通过前序遍历此树，即可得到字符串从小到大的挨次。 实现代码如下（g+、VC+都编译通过）： 代码如下: #include iostream #include string.h using namespace std; #define NUM 26

9、class Node public: int count; /记录该处字符串个数 Node* char_arrNUM; /分支 char* current_str; /记录到达此处的路径上的全部字母组成的字符串 Node(); ; class Trie public: Node* root; Trie(); void insert(char* str); void output(Node* node, char* str, int count); ; /程序未考虑delete动态内存 int main() char* str = new char*12; str0 = zbdfasd; str

10、1 = zbcfd; str2 = zbcdfdasfasf; str3 = abcdaf; str4 = defdasfa; str5 = fedfasfd; str6 = dfdfsa; str7 = dadfd; str8 = dfdfasf; str9 = abcfdfa; str10 = fbcdfd; str11 = abcdaf; /建立trie树 Trie* trie = new Trie(); for(int i = 0; i 12; i+) trie-insert(stri); int count = 0; trie-output(trie-root, str, count

11、); for(int i = 0; i 12; i+) coutstriendl; return 0; Node:Node() count = 0; for(int i = 0; i NUM; i+) char_arri = NULL; current_str = new char100; current_str0 = 0; Trie:Trie() root = new Node(); void Trie:insert(char* str) int i = 0; Node* parent = root; /将stri插入到trie树中 while(stri != 0) /假如包含stri的分支

12、存在，则新建此分支 if(parent-char_arrstri - a = NULL) parent-char_arrstri - a = new Node(); /将父节点中的字符串添加到当前节点的字符串中 strcat(parent-char_arrstri - a-current_str, parent-current_str); char str_tmp2; str_tmp0 = stri; str_tmp1 = 0; /将stri添加到当前节点的字符串中 strcat(parent-char_arrstri - a-current_str, str_tmp); parent = parent-char_arrstri - a; else parent = parent-char_arrstri - a; i+; parent-count+; /采纳前序遍历 void Trie:output(Node* node, char*