你的分享就是我们的动力 ---﹥

萌新笔记——C++里创建 Trie字典树(中文词典)(一)(插入、遍

时间:2016-12-06 12:44来源:www.chengxuyuans.com 点击:

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

  写了一个词典,用到了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 }
View Code

 

转载注明地址:http://www.chengxuyuans.com/code/C++/105424.html