首页 > > 程序设计 > C/C++ >

C++里创建 Trie字典树（中文词典）（一）（插入…

2018-06-17 23:32:29来源：未知阅读 ()

　　萌新做词典第一篇，做得不好，还请指正，谢谢大佬！

　　写了一个词典，用到了Trie字典树。

　　写这个词典的目的，一个是为了压缩一些数据，另一个是为了尝试搜索提示，就像在谷歌搜索的时候，打出某个关键字，会提示一串可能要搜索的东西。

　　首先放上最终的结果：

input:

1 编程入门
2 编程软件
3 编程学习
4 编程学习网站

output:

1 char : 件
2 word : 编程软件
3 char : 习
4 word : 编程学习
5 char : 网
6 word : 编程学习网
7 char : 门
8 word : 编程入门

　　其实这里不应该用input，因为全是直接写死在main中进行测试的--！

　　对于这个output，char表示此时指向的字，word表示从根到指向的字的路径遍历（原谅菜鸟的我想不到恰当的词）。

　　“编程”两字因没有输入，故不会当做一个词，如果不这样设定，“编”也会被当作一个词打出来的。

　　然后来说说做这个的过程吧。

　　首先，我选择struct与unordered_map结合才表示树，具体代码如下：

 1 #ifndef __DICTIONARYDATA_H__
 2 #define __DICTIONARYDATA_H__
 3 
 4 #include <string>
 5 #include <unordered_map>
 6 #include <memory>
 7 
 8 namespace ccx{
 9 
10 using std::string;
11 using std::unordered_map;
12 using std::shared_ptr;
13 
14 struct DictElem
15 {
16     string _word;//如果是根结点，则填ROOT
17     int _wordId;//如果是根结点，则为总词数
18     unordered_map<string, shared_ptr<DictElem> > _words;
19 };
20 
21 typedef shared_ptr<DictElem> pDictElem;
22 
23 }
24 
25 #endif

　　这里的typedef是为了后面书写的方便而设的。

　　然后，是设计Dictionary类，使它具有添加一个词、添加一组词、遍历所有词的功能，当然我比较菜暂时没想怎么删除一个词的事。以下是最初的Dictionary

Dictionary.h

 1 #ifndef __DICTIONARY_H__
 2 #define __DICTIONARY_H__
 3 
 4 #include "DictionaryData.h"
 5 
 6 #include <memory>
 7 #include <vector>
 8 #include <list>
 9 
10 namespace ccx{
11 
12 using std::shared_ptr;
13 using std::vector;
14 using std::list;
15 
16 class Dictionary
17 {
18     typedef unordered_map<string, pDictElem>::iterator WordIt;
19     public:
20         Dictionary();
21         void push(const string & word);
22         void push(vector<string> & words);
23     private:
24         void splitWord(const string & word, vector<string> & characters);//把词拆成字
25         pDictElem _dictionary;
26 
27 //遍历
28     public:
29         void next();
30         string getCurChar();
31         string getCurWord();
32         void resetPoint();
33         bool isEnd();
34     private:
35         void nextWord();
36         pDictElem _pcur;
37         WordIt _itcur;
38 
39 //用list实现栈，遍历时方便
40         list<WordIt> _stackWord;
41         list<pDictElem> _stackDict;
42 };
43 
44 }
45 
46 #endif

　　有了类结构，就可以去实现它了。构造函数做了一个初始化的工作：

1 Dictionary::Dictionary()
2 : _dictionary(new DictElem)
3 {
4     _dictionary->_wordId = 0;
5     _pcur = _dictionary;
6 }

　　首先，要把一个string分解成单个的字。在做这个的时候，一开始是天真地认为中国就是占两个字节（gbk编码），总是出现迷之乱码。后来是发现我用的是utf-8编码，才解决了问题（上一篇就是讲这个）。实现代码如下：

 1 void Dictionary::splitWord(const string & word, vector<string> & characters)
 2 {
 3     int num = word.size();
 4     int i = 0;
 5     while(i < num)
 6     {
 7         int size = 1;
 8         if(word[i] & 0x80)
 9         {
10             char temp = word[i];
11             temp <<= 1;
12             do{
13                 temp <<= 1;
14                 ++size;
15             }while(temp & 0x80);
16         }
17         string subWord;
18         subWord = word.substr(i, size);
19         characters.push_back(subWord);
20         i += size;
21     }
22 }

　　得到了单个字的集合，并存在vector中，就可以生成Trie字典数了。插入一个词的代码如下：

 1 void Dictionary::push(const string & word)
 2 {
 3     vector<string> characters;
 4     splitWord(word, characters);
 5     
 6     vector<string>::iterator it_char;
 7     it_char = characters.begin();    
 8     pDictElem root;
 9     root = _dictionary;
10     for(; it_char != characters.end(); ++it_char)
11     {
12         WordIt it_word;
13         it_word = root->_words.find(*it_char);
14         
15         if(it_word == root->_words.end())
16         {
17             pair<string, pDictElem> temp;
18             temp.first = *it_char;
19             pDictElem dictemp(new DictElem);
20             dictemp->_word = *it_char;
21             dictemp->_wordId = 0;
22             temp.second = dictemp;
23             root->_words.insert(temp);
24             root = dictemp;
25         }else{
26             root = it_word->second;
27         }
28     }
29     if(!root->_wordId)
30     {
31         ++(_dictionary->_wordId);
32         root->_wordId = _dictionary->_wordId;
33     }
34 }

　　这里有用到的wordId，其实是给插入的词进行编号。在遍历的时候，如果发现编号是0，则说明并没有插入这个词，可以跳过。

　　然后是插入一组词的代码：

1 void Dictionary::push(vector<string> & words)
2 {
3     int size = words.size();
4     for(int i = 0; i < size; ++i)
5     {
6         push(words[i]);
7     }
8 }

　　直接复用了插入一个词的代码，简单粗暴。

　　接着是写遍历。想到二叉树的遍历既可以用递归，又可以用栈来实现，由于递归要产生额外的开销，我就采用了栈的方法。但是，要把迭代器入栈呢，还是把智能指针入栈的问题又卡着了。由于我这里是专门写了一个next函数，遍历不是在一个函数里“一条龙”一样地完成，于是会有以下两个可能的问题（对本萌新来说）：

　　1、只有智能指针入栈，可以轻松打出一个词，但是怎么让它知道下一个应该指向谁？

　　2、如果只有迭代器入栈，又要怎么知道什么时候应该出栈（end）？对于这个问题有一个解决方案，就是每次处理的时候先出栈，然后再用此时的栈顶元素（它的父节点）来进行判断。不过觉得这样太麻烦了，于是没有这样做。

　　于是选择了两个都入栈的处理方法，结合使用，智能指针栈的栈顶元素永远是迭代器栈的父节点，并且对于root结点，迭代器栈中不存。从而有了以下代码：

 1 void Dictionary::nextWord()
 2 {
 3     if(_pcur)
 4     {
 5         if(_pcur->_words.size())
 6         {
 7             _stackDict.push_back(_pcur);
 8             _stackWord.push_back(_pcur->_words.begin());
 9             _pcur = _stackWord.back()->second;
10         }else{
11             ++(_stackWord.back());
12         }
13         while(_stackWord.back() == _stackDict.back()->_words.end())
14         {
15             _stackDict.pop_back();
16             _stackWord.pop_back();
17             if(!_stackDict.size())
18             {
19                 _pcur = NULL;
20             }
21             ++(_stackWord.back());
22         }
23         if(_pcur)
24         {
25             _pcur = _stackWord.back()->second;
26         }    
27     }
28 }

 1 void Dictionary::next()
 2 {
 3     while(_pcur)
 4     {
 5         nextWord();
 6         if(!_pcur || _pcur->_wordId)
 7         {
 8             break;
 9         }
10     }
11 }

　　这个next()是后来加的，因为发现如果不加这个，会把并没有输入的词也打出来，比如最开始的例子“编程软件”，会输出四个词：”编“、”编程“、”编程软“、”编程软件“，这并不是我想要结果，于是加了这么一个判断，跳过所有未输入的词。

　　当然，还要一个初始化的函数：

 1 void Dictionary::resetPoint()
 2 {
 3     _pcur = _dictionary;
 4     if(_stackDict.size())
 5     {
 6         _stackDict.clear();
 7     }
 8     if(_stackWord.size())
 9     {
10         _stackWord.clear();
11     }
12     next();
13 }

　　和判断是否读取完毕的函数：

1 bool Dictionary::isEnd()
2 {
3     return _pcur == NULL;
4 }

　　最后，就是获取一个词的函数了：

 1 string Dictionary::getCurWord()
 2 {
 3     string temp;
 4     list<WordIt>::iterator it_word;    
 5     it_word = _stackWord.begin();    
 6 
 7     for(; it_word != _stackWord.end(); ++it_word)
 8     {
 9         temp += (*it_word)->first;
10     }
11     return temp;
12 }

　　并且额外写了一个用于测试的，获得当前节点存的什么字的函数

1 string Dictionary::getCurChar()
2 {
3     return _pcur->_word;
4 }

　　实现完了所有函数，就开始进行测试了。我专门写了一个test.cc来使用这个类：

 1 #include "Dictionary.h"
 2 #include <iostream>
 3 #include <string>
 4 #include <vector>
 5 using std::cout;
 6 using std::endl;
 7 using std::string;
 8 using std::vector;
 9 
10 int main()
11 {
12     ccx::Dictionary words;
13     string word1 = "编程入门";    
14     string word2 = "编程软件";    
15     string word3 = "编程学习";    
16     string word4 = "编程学习网站";    
17     
18     words.push(word1);    
19     words.push(word2);    
20     words.push(word3);    
21     words.push(word4);    
22 
23     words.resetPoint();
24     
25     while(!words.isEnd())
26     {
27         cout << "char : " << words.getCurChar() << endl;
28         cout << "word : " << words.getCurWord() << endl;
29         words.next();
30     }
31 }

　　测试结果就在开头部分。于是，一个简单的可以插入与遍历的词典就做好了。后来又想应该给它添加查找、导入与导出的功能，想想干脆再开一篇好了。

　　0。0 感觉方法好low啊~~~~

Dictionary.cc

  1 #include "Dictionary.h"
  2 #include <iostream>
  3 #include <string>
  4 
  5 namespace ccx{
  6 
  7 using std::endl;
  8 using std::cout;
  9 using std::pair;
 10 
 11 Dictionary::Dictionary()
 12 : _dictionary(new DictElem)
 13 {
 14     _dictionary->_wordId = 0;
 15     _pcur = _dictionary;
 16 }
 17 
 18 void Dictionary::splitWord(const string & word, vector<string> & characters)
 19 {
 20     int num = word.size();
 21     int i = 0;
 22     while(i < num)
 23     {
 24         int size = 1;
 25         if(word[i] & 0x80)
 26         {
 27             char temp = word[i];
 28             temp <<= 1;
 29             do{
 30                 temp <<= 1;
 31                 ++size;
 32             }while(temp & 0x80);
 33         }
 34         string subWord;
 35         subWord = word.substr(i, size);
 36         characters.push_back(subWord);
 37         i += size;
 38     }
 39 }
 40 
 41 void Dictionary::push(const string & word)
 42 {
 43     vector<string> characters;
 44     splitWord(word, characters);
 45     
 46     vector<string>::iterator it_char;
 47     it_char = characters.begin();    
 48     pDictElem root;
 49     root = _dictionary;
 50     for(; it_char != characters.end(); ++it_char)
 51     {
 52         WordIt it_word;
 53         it_word = root->_words.find(*it_char);
 54         
 55         if(it_word == root->_words.end())
 56         {
 57             pair<string, pDictElem> temp;
 58             temp.first = *it_char;
 59             pDictElem dictemp(new DictElem);
 60             dictemp->_word = *it_char;
 61             dictemp->_wordId = 0;
 62             temp.second = dictemp;
 63             root->_words.insert(temp);
 64             root = dictemp;
 65         }else{
 66             root = it_word->second;
 67         }
 68     }
 69     if(!root->_wordId)
 70     {
 71         ++(_dictionary->_wordId);
 72         root->_wordId = _dictionary->_wordId;
 73     }
 74 }
 75 
 76 void Dictionary::push(vector<string> & words)
 77 {
 78     int size = words.size();
 79     for(int i = 0; i < size; ++i)
 80     {
 81         push(words[i]);
 82     }
 83 }
 84 
 85 //遍历用
 86 
 87 void Dictionary::resetPoint()
 88 {
 89     _pcur = _dictionary;
 90     if(_stackDict.size())
 91     {
 92         _stackDict.clear();
 93     }
 94     if(_stackWord.size())
 95     {
 96         _stackWord.clear();
 97     }
 98     next();
 99 }
100 
101 void Dictionary::next()
102 {
103     while(_pcur)
104     {
105         nextWord();
106         if(!_pcur || _pcur->_wordId)
107         {
108             break;
109         }
110     }
111 }
112 
113 void Dictionary::nextWord()
114 {
115     if(_pcur)
116     {
117         if(_pcur->_words.size())
118         {
119             _stackDict.push_back(_pcur);
120             _stackWord.push_back(_pcur->_words.begin());
121             _pcur = _stackWord.back()->second;
122         }else{
123             ++(_stackWord.back());
124         }
125         while(_stackWord.back() == _stackDict.back()->_words.end())
126         {
127             _stackDict.pop_back();
128             _stackWord.pop_back();
129             if(!_stackDict.size())
130             {
131                 _pcur = NULL;
132             }
133             ++(_stackWord.back());
134         }
135         if(_pcur)
136         {
137             _pcur = _stackWord.back()->second;
138         }    
139     }
140 }
141 
142 string Dictionary::getCurChar()
143 {
144     return _pcur->_word;
145 }
146 
147 string Dictionary::getCurWord()
148 {
149     string temp;
150     list<WordIt>::iterator it_word;    
151     it_word = _stackWord.begin();    
152 
153     for(; it_word != _stackWord.end(); ++it_word)
154     {
155         temp += (*it_word)->first;
156     }
157     return temp;
158 }
159 
160 bool Dictionary::isEnd()
161 {
162     return _pcur == NULL;
163 }
164 
165 }