本記事では、C++を用いてTrie辞書木を作成し、文字列の挿入と全単語の巡回を実現する方法を説明します。

最終的な挿入テスト結果は以下のとおりです。

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

辞書木の構造体は以下のとおりです。

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 charValue;
17     int wordId;
18     unordered_map<string, shared_ptr<DictElem>> children;
19 };
20 
21 typedef shared_ptr<DictElem> pDictElem;
22 
23 }
24 
25 #endif

辞書機能を実装するためのDictionaryクラスの定義は以下のとおりです。

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     public:
19         Dictionary();
20         void insert(const string & word);
21         void insert(const vector<string> & words);
22         void traverse();
23         void reset();
24         bool isComplete();
25         string getCurrentChar();
26         string getCurrentWord();
27 
28     private:
29         void splitString(const string & s, vector<string> & chars);
30         void nextNode();
31         pDictElem current;
32         list<pDictElem> dictStack;
33         list<unordered_map<string, pDictElem>::iterator> wordStack;
34 };
35 
36 }
37 
38 #endif

辞書木の初期化を行うコンストラクタです。

1 Dictionary::Dictionary()
2 : current(new DictElem)
3 {
4     current->wordId = 0;
5     current->charValue = "ROOT";
6 }

文字列をUTF-8エンコードされた個別文字に分割する関数です。

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

単語を辞書木に挿入する関数です。

1 void Dictionary::insert(const string & word)
2 {
3     vector<string> chars;
4     splitString(word, chars);
5     
6     pDictElem root = current;
7     for(const auto & c : chars)
8     {
9         auto it = root->children.find(c);
10         if(it == root->children.end())
11         {
12             pDictElem newNode(new DictElem);
13             newNode->charValue = c;
14             newNode->wordId = 0;
15             root->children[c] = newNode;
16             root = newNode;
17         }else{
18             root = it->second;
19         }
20     }
21     if(root->wordId == 0)
22     {
23         root->wordId = ++current->wordId;
24     }
25 }

複数の単語を一括挿入する関数です。

1 void Dictionary::insert(const vector<string> & words)
2 {
3     for(const auto & word : words)
4     {
5         insert(word);
6     }
7 }

辞書木の巡回を制御する関数です。

1 void Dictionary::nextNode()
2 {
3     if(current)
4     {
5         if(current->children.size() > 0)
6         {
7             dictStack.push_back(current);
8             wordStack.push_back(current->children.begin());
9             current = wordStack.back().second;
10         }else{
11             wordStack.back()++;
12         }
13         while(wordStack.back() == dictStack.back()->children.end())
14         {
15             dictStack.pop_back();
16             wordStack.pop_back();
17             if(dictStack.empty())
18             {
19                 current = nullptr;
20                 break;
21             }
22             wordStack.back()++;
23         }
24         if(current)
25         {
26             current = wordStack.back().second;
27         }
28     }
29 }

巡回の起点をリセットする関数です。

1 void Dictionary::reset()
2 {
3     current = current;
4     dictStack.clear();
5     wordStack.clear();
6     nextNode();
7 }

巡回完了を判断する関数です。

1 bool Dictionary::isComplete()
2 {
3     return current == nullptr;
4 }

現在の文字を取得する関数です。

1 string Dictionary::getCurrentChar()
2 {
3     return current->charValue;
4 }

現在の単語を取得する関数です。

1 string Dictionary::getCurrentWord()
2 {
3     string result;
4     for(auto it = wordStack.begin(); it != wordStack.end(); ++it)
5     {
6         result += it->first;
7     }
8     return result;
9 }

以下は辞書機能をテストするためのメインプログラムです。

 1 #include "Dictionary.h"
 2 #include <iostream>
 3 #include <string>
 4 #include <vector>
 5 
 6 using namespace std;
 7 
 8 int main()
 9 {
10     Dictionary dict;
11     vector<string> testWords = {
12         "编程入门",
13         "编程软件",
14         "编程学习",
15         "编程学习网站"
16     };
17     
18     dict.insert(testWords);
19     dict.reset();
20     
21     while(!dict.isComplete())
22     {
23         cout << "char : " << dict.getCurrentChar() << endl;
24         cout << "word : " << dict.getCurrentWord() << endl;
25         dict.nextNode();
26     }
27 }