寫了一個詞典,用到了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