Patrica Trieに挑戦したものの…
しばらくTinyJSに実装するためのインメモリDBを作ってました。
単純にメモリに格納するだけの構造は１週間くらいで出来たのですがせっかくやるんだから
indexなどつけようとPatricia Trieに挑戦してました。Patricia TrieはTrieの一種です。Trieとはデータ構造の一種で文字列を接頭辞で分解する方法です。詳しくはググってください。
で１文字ずつ分解するTrieのうち共通部分を一つのノードにするのがPatricia Trieです。
これを例題から魔改造しまして作ったところめちゃくちゃ早い。
全国住所データ２２カラム１８万行をインサートしてみたところ５秒かからなかったのです。
大体１件の挿入に1.2μ秒です。
これはいいと思い実装を進めたところ、実はメモリをドカ食いする仕様だったというオチです。
まあ速けりゃいいじゃないという方も多いと思うのでソースは載せておきます。
320px-Patricia_trie.svg
特徴としては辞書順と入力順をどちらも保持しているところです。なのでデータベースとしてはそのまま値を入れておけばインデックス有り無しを気にせずに色々な事ができます。
欠点はとにかくメモリ食います。全国住所データは２０ＭＢくらいなのですが実質２００ＭＢくらいメモリを取ってしまいます。
この原因としてはノードデータ数が多いこともあるんですがVectorの自動要素追加が常に倍々であることに起因します。そうかと思い自作のVectorもどきでやってみたんですが如何せん、元の構造を凌駕する結果にはならなかったですね。なのでメモリを数百Ｇくらい用意して大量データを処理するには向いてると思います。ここでは記載してませんが数値もインデックス化できます。
Patricia Trie無しの既定クラスも用意してあるので要素により切り替えたりするといい感じかもしれません。
取り敢えずこのコードについてはこれ以上触らないようにしようかなと思ってます。今は1ノードを２ビットで表現できるLOUDSツリーを魔改造してPatricia trieに対応させようとしてます。
恐らく２０ＭＢのデータなら同じくらいで表現できるんじゃないかな。
思ったより道程が長くて凹んでます。
コンパイルは今更ながらBorland C++Builderでやってますが、C++の基本機能しか使ってないので大体のところで動くと思います。多少編集してるので動かなかったらコメントください。
//---------------------------------------------------------------------------
#include <string>
#include <vector>
#include <iostream>
using namespace std;
//---------------------------------------------------------------------------
class Node{
public:
//登録する文字列
vector<string> data;
//完了フラグ
vector<int> terminated;
//枝
vector<int> children;
vector<int> brothers;
vector<int> parents;
vector<int> index;
//コンストラクタ
Node(void);
void print(int ptr=0);
int contains(string letters, int parent = 0);
int addNode(string letters,int child,int brother,int parent,int terminate);
void insertChild(string letters,int parent=0);
string sprint(int ptr=0);
};
//コンストラクタ
Node::Node(void)
{
data.push_back("");
children.push_back(-1);
brothers.push_back(-1);
parents.push_back(-1);
terminated.push_back(0);
}
//Terminatedで示されるノードの文字列取得
void Node::print(int ptr)
{
if( terminated[ptr] ){
string word = data[ptr];
while( parents[ptr]>=0 ){
ptr = parents[ptr];
word = data[ptr] + word;
}
printf( "%s,",word);
}
}
//Terminatedで示されるノードの文字列取得
string Node::sprint(int ptr)
{
if( terminated[ptr] ){
string word = data[ptr];
while( parents[ptr]>=0 ){
ptr = parents[ptr];
word = data[ptr] + word;
}
return word;
}
return "";
}
//文字が格納されているか？
int Node::contains(string letters, int parent)
{
//子供を検索
int bros = children[parent];
while( bros >= 0 ){
//１文字目を比較
if ( letters[0]-data[bros][0] == 0 ){
//長さ比較
int n = min(letters.length(), data[bros].length());
//合致数計算
int i = 0;
while(i < n && (letters[i] == data[bros][i])) i++;
if( i == n ){
//完全一致の場合
if( letters.length() == data[bros].length() ){
return terminated[bros];
//登録文字の方が長いので子ノードに再帰的に登録
}else{
//登録する文字の方が長いので必ず子供が出来る
return contains( letters.substr(i),bros);
}
}
}
bros = brothers[bros];
}
return -1;
}
int Node::addNode(string letters,int child,int brother,int parent,int terminate)
{
int ptr = data.size();
data.push_back(letters);
parents.push_back(parent);
children.push_back(child);
brothers.push_back(brother);
terminated.push_back(terminate);
if( terminate ){
index.push_back(ptr);
}
//登録場所を返す
return ptr;
}
//文字を枝登録。親となるノードを返す
void Node::insertChild(string letters, int parent)
{
int child;
int previous;
int bros;
int ptr;
//子供に要素を挿入
bros = children[parent];
previous = bros;
while( bros >= 0 ){
//１文字目を比較
int c = letters[0]-data[bros][0];
//先頭または途中挿入
if( c < 0 ){
//先頭
if( bros == children[parent] ){
//新規子無、先頭指定の兄弟、親は引数
//親ノードの子順番変更。ここは変更可能
children[parent] = addNode(letters,-1,bros,parent,1);
return;
//途中挿入
}else{
//新規子無、先頭指定の兄弟、親は引数
//先頭でないので兄弟を変更
brothers[previous] = addNode(letters,-1,bros,parent,1);
return;
}
}else if ( c == 0 ){
//長さ比較
int n = min(letters.length(), data[bros].length());
//合致数計算
int i = 0;
while(i < n && (letters[i] == data[bros][i])) i++;
if( i == n ){
//一致
//より短い一致の挿入
//より長い文字の挿入
//完全一致の場合
if( letters.length() == data[bros].length() ){
if( terminated[bros] == 0 ){
terminated[bros] = 1;
index.push_back(bros);
}else if( children[bros] >= 0 ){
ptr = addNode("",-1,children[bros],bros,1);
children[bros] = ptr;
}else{
ptr = addNode("",-1,-1,bros,1);
children[bros] = ptr;
}
return;
//登録文字の方が短い
}else if( letters.length() < data[bros].length()){
int c1 = addNode(letters,bros,brothers[bros],parents[bros],1);
//子供、兄弟の情報は保持
data[bros] = data[bros].substr(i);
if( bros == previous ){
children[parents[bros]] = c1;
}else{
brothers[previous] = c1;
}
parents[bros] = c1;
brothers[bros] = -1;
return;
//登録文字の方が長いので子ノードに再帰的に登録
}else{
//登録する文字の方が長いので必ず子供が出来る
letters = letters.substr(i);
insertChild( letters,bros);
//parents[children[bros]] = bros;
return;
}
}else{
//先頭だけ合致。２つの子ノードが出来る
string newLetter1 = data[bros].substr(0, i);
string newLetter2 = data[bros].substr(i);
string newLetter3 = letters.substr(i);
data[bros] = newLetter2;
//自ノードの方が先頭
if(newLetter2[0] < newLetter3[0]){
//接頭辞
int c1 = addNode(newLetter1,-1,brothers[bros],parents[bros],0);
//自ノードの兄弟はc2
brothers[bros] = addNode(newLetter3,-1,-1,c1,1);
//元ノードが先頭の場合
if( previous == bros ){
//接頭辞の親の子供はc1
children[parents[bros]] = c1;
//先頭でなければ兄弟を設定
}else{
brothers[previous] = c1;
}
//自ノードの親はc1
parents[bros] = c1;
//接頭辞の子供はbros
children[c1] = bros;
//自ノードの方が後方
}else{
//接頭辞
int c1 = addNode(newLetter1,-1,brothers[bros],parents[bros],0);
//接頭辞の子供はc2
children[c1] = addNode(newLetter3,-1,bros,c1,1);
//元ノードが先頭の場合
if( previous == bros ){
//接頭辞の親の子供はc1
children[parents[bros]] = c1;
//先頭でなければ兄弟を設定
}else{
brothers[previous] = c1;
}
//自ノードの親はc1
parents[bros] = c1;
//自ノードは終端になるので兄弟なし
brothers[bros] = -1;
}
return;
}
}
previous = bros;
bros = brothers[bros];
if( bros < 0 ){
//末尾に挿入
brothers[previous] = addNode(letters,-1,-1,parent,1);
return;
}
}
//ループしなかった子供なし
children[parent] = addNode(letters,-1,-1,parent,1);
return;
}
//テーブルクラステスト
int main()
{
Node* test= new Node();
test->insertChild("testa");
test->insertChild("test");
test->insertChild("test");
test->insertChild("test");
delete test;
}