DAWG(3): ID付けの方法変更とDoarからの変換
DAWGのキーに一意なIDをマッピングするために、前回考えた方法は、サイズ的に効率的に実装するのが無理そうなことが分かったので、別の方法に変更することに。
IDへのマッピング
方法概要。
- DAWGはIDのことを考慮せずに普通に構築する
- キーのIDは、完全最小ハッシュ関数を用いて別途キーから算出する
つまり、キーの存在判定はDAWGを用いて行い、キーのIDは完全最小ハッシュ関数を用いて取得する、ということ(概念的には二つは全く独立したプロセス)。
実はこれ(に似たこと)は前回の方法を思いつくよりも前に考えていたのだが、完全最小ハッシュ関数を実装するのが(まず名前からして)難しそうな気がしていたので、とりあえず見送っていた。
ただ、今日少し調べたところ、完全最小ハッシュ関数も簡単なものなら結構すぐ実装できそうな感じだったので、試してみることに。
DoarからDAWGに変換ソース
今回は1の部分のソース。
以下、Doarで作成されたトライ(DoubleArray)をDAWGに変換するコマンドと、そのために修正が必要なDoarのソースのパッチ。
※ DAWGへの変換処理は、一回目に載せたtrie2dawg関数とほぼ同様。
/** * ファイル名: doar2dawg.cc * コンパイル: g++ -O2 -o doar2dawg doar2dawg.cc * * mkdoarコマンドが作成したDoubleArray-TrieインデックスをDAWG形式に変換する * * ※ doar-0.0.12 をカレントディレクトリに解凍しておくこと * $ mv doar-0.0.12 doar * $ patch -p0 < dawg.diff */ #include <iostream> #include "doar/src/doar/double_array.h" int main(int argc, char** argv) { if(argc != 3) { std::cerr << "Usage: doar2dawg <doar-index> <dawg-index>" << std::endl; return 1; } Doar::DoubleArray da; da.load(argv[1]); std::cerr << "key count: " << da.size() << std::endl; da.save_dawg(argv[2]); return 0; }
diff -u doar-src/src/doar/builder.h doar/src/doar/builder.h --- doar-src/src/doar/builder.h 2010-04-23 20:35:38.000000000 +0900 +++ doar/src/doar/builder.h 2010-07-13 02:06:02.000000000 +0900 @@ -7,7 +7,98 @@ #include "shrink_tail.h" #include "node.h" +#include <tr1/unordered_map> + +/** + * DAWGの構築に用いるハッシュ関連のクラス定義 + */ +namespace Doar { + namespace Hash { + // ハッシュのキーとなるノードクラス + struct Node { + // BASEやCHECK、TAIL配列を保持するクラス + struct DA { + DA(const BaseList& b, const ChckList& c, const TindList& t, const Tail& tl) + : base(b), chck(c), tind(t), tail(tl) {} + const BaseList& base; + const ChckList& chck; + const TindList& tind; + const Tail& tail; + }; + + const Base base; // ノード(BASE) + const DA& da; + + Node(Base n, const DA& da) : base(n), da(da) {} + }; + + // ノードのハッシュ値 + struct NodeHash { + std::size_t operator()(const Hash::Node& n) const { + std::size_t hash=7; + + if(n.base.is_leaf()) { + // TAIL文字列 + const char* s = n.da.tail.data()+n.da.tind[n.base.id()]; + for(; *s != '\0'; s++) + hash = hash*37 + (unsigned char)s[0]; + return hash; + } + + // 子ノード + for(Code cd=0; cd < CODE_LIMIT; cd++) { + NodeIndex next = n.base.next_index(cd); + if(n.da.chck[next].trans_by(cd)) { + hash = hash*37 + cd; + hash = hash*37 + operator()(Hash::Node(n.da.base[next], n.da)); + } + } + + return hash; + } + }; + + // ノードの等価性判定 + struct NodeEqual { + bool operator()(const Hash::Node& n1, const Hash::Node& n2) const { + if(n1.base.is_leaf() && n2.base.is_leaf()) { + // 両方が終端ノード + return strcmp(n1.da.tail.data()+n1.da.tind[n1.base.id()], + n2.da.tail.data()+n2.da.tind[n2.base.id()]) == 0; + } + + if(n1.base.is_leaf() || n2.base.is_leaf()) + // 片方が終端ノード + return false; + + for(Code cd=0; cd < CODE_LIMIT; cd++) { + // 子ノードリストが等しいか + NodeIndex next1 = n1.base.next_index(cd); + NodeIndex next2 = n2.base.next_index(cd); + + if(n1.da.chck[next1].trans_by(cd) != n2.da.chck[next2].trans_by(cd)) + return false; + } + + for(Code cd=0; cd < CODE_LIMIT; cd++) { + // 再帰的に子ノードを検査 + NodeIndex next1 = n1.base.next_index(cd); + NodeIndex next2 = n2.base.next_index(cd); + if(n1.da.chck[next1].trans_by(cd)) + if(operator()(Hash::Node(n1.da.base[next1], n1.da), Hash::Node(n2.da.base[next2], n2.da)) == false) + return false; + } + + // 全部合格 + return true; + } + }; + } +} + namespace Doar { + typedef std::tr1::unordered_map<Hash::Node, NodeIndex, Hash::NodeHash, Hash::NodeEqual> NodeSet; + class Builder { typedef StaticAllocator Allocator; friend class DoubleArray; @@ -57,6 +148,21 @@ adjust_nodes(); } + // 既存のDoubleArrayからDAWG構築 + void build_dawg(const BaseList& src_base, const ChckList& src_chck, const TindList& src_tind, const Tail& src_tail) { + Allocator alloca; + init(src_tind.size()); + tind=src_tind; + tail=src_tail; + + Hash::Node::DA da(src_base, src_chck, src_tind, src_tail); + NodeSet set; + + if(src_tind.size()!=0) + build_dawg_impl(src_base,src_chck,alloca,src_base[0],0,da,set); + adjust_nodes(); + } + bool save(const char* filepath, bool do_shrink_tail=true) { return Builder::save(base,chck,tind,tail,filepath,do_shrink_tail); } @@ -119,6 +225,38 @@ build_impl(keys, alloca,end_list[i],end_list[i+1], set_node(cs[i],root_idx,x)); } + void build_dawg_impl(const BaseList& src_base, const ChckList& src_chck, Allocator& alloca, Base old_root, NodeIndex new_root_idx, + const Hash::Node::DA& da, NodeSet& set) { + // DAWG用の処理 + Hash::Node n(old_root,da); + if(set.find(n) != set.end()){ + // 共有可能なノードがある場合 + /* + if(set.size()%100==0) + std::cout << "# " << set.size() << std::endl; + */ + base.at(new_root_idx) = base[set[n]]; // 既に構築済みのノードを流用(共有) + return; + } + set[n] = new_root_idx; // 新規ノードを挿入 + + // ここからは、通常のトライ構築と同様 + if(old_root.is_leaf()) { + base.at(new_root_idx).set_id(old_root.id()); + return; + } + + CodeList cs; + NodeIndex beg = old_root.base(); + for(Code c=0; c < CODE_LIMIT; c++) + if(src_chck[beg+c].trans_by(c)) + cs.push_back(c); + + NodeIndex x = alloca.x_check(cs); + for(std::size_t i=0; i < cs.size(); i++) + build_dawg_impl(src_base, src_chck, alloca, src_base[old_root.next_index(cs[i])], set_node(cs[i],new_root_idx,x), da, set); + } + // Build trie from other DoubleArray trie elements. void build_impl(const BaseList& src_base, const ChckList& src_chck, Allocator& alloca, Base old_root, NodeIndex new_root_idx) { if(old_root.is_leaf()) { diff -u doar-src/src/doar/double_array.h _doar/src/doar/double_array.h --- doar-src/src/doar/double_array.h 2010-04-22 13:03:18.000000000 +0900 +++ doar/src/doar/double_array.h 2010-07-13 01:53:36.000000000 +0900 @@ -67,7 +67,6 @@ template<typename Callback> void each_child(Node parent, const Callback& fn) const { return srch().each_child(parent,fn); } - /*****************/ /* save and load */ bool save(const char* path) { @@ -78,6 +77,13 @@ return bld.save(path,false); } + // DoarインデックスをDAWG形式に変換して保存する + bool save_dawg(const char* path) { + Builder bld; + bld.build_dawg(base,chck,tind,tail); + return bld.save(path,false); + } + const OnMemorySearcher* make_searcher() { ShrinkTail(tail,tind).shrink();
実行例
実行例。
doar2dawgが生成するインデックスは、基本的にDoarのそれと区別せずに使用可能だが、キーのID値には重複があり正しくない。
インデックスサイズはあと何割か減る予定。
######### ## データ # 1) 各国語Wikipediaのタイトル ※ 作成方法はLOUDSの七回目を参照(http://d.hatena.ne.jp/sile/20100620/1277045565) $ wc -l wiki.title 5340378 wiki.title # 530万行 $ ls -lh wiki.title -rw-r--r-- 1 user user 103M 2010-06-23 01:10 wiki.title $ head -4100000 wiki.title | tail -5 データベーストリガ データベースマネジメントシステム データベースマネージメントシステム データベースモデル データベース接続クライアント # 2) 文字三グラム $ wc -l 3gram 7442532 3gram # 700万行 $ ls -lh 3gram -rw-r--r-- 1 user user 68M 2010-07-13 02:37 3gram $ head -1200000 3gram | tail -5 うが簡 うが粒 うが粥 うが精 うが糖 # 3) 文字四グラム $ wc -l 4gram 21139008 4gram # 2100万行 $ ls -lh 4gram -rw-r--r-- 1 user user 251M 2010-07-13 02:37 4gram $ head -20000000 4gram | tail -5 ！熱いハ ！熱いバ ！熱いビ ！熱いホ ！熱い修 ####### ## Doar $ mkdoar --conc-static wiki.idx wiki.title $ mkdoar --conc-static 3gram.idx 3gram $ mkdoar --conc-static 4gram.idx 4gram ####### ## DAWG $ doar2dawg wiki.idx wiki-dawg.idx $ doar2dawg 3gram.idx 3gram-dawg.idx $ doar2dawg 4gram.idx 4gram-dawg.idx $ ls -lh *.idx -rw-r--r-- 1 user user 65M 2010-07-13 00:32 3gram-dawg.idx # テキストサイズ: 68M -rw-r--r-- 1 user user 76M 2010-07-12 23:17 3gram.idx -rw-r--r-- 1 user user 190M 2010-07-13 00:41 4gram-dawg.idx # テキストサイズ: 251M -rw-r--r-- 1 user user 233M 2010-07-12 23:16 4gram.idx -rw-r--r-- 1 user user 85M 2010-07-13 00:51 wiki-dawg.idx # テキストサイズ: 103M -rw-r--r-- 1 user user 94M 2010-07-13 00:44 wiki.idx $ doar 4gram-dawg.idx ！熱いハ # 入力 #0: ！熱いハ # 出力: IDは0 ！熱いバ # 入力 #0: ！熱いバ # 出力: IDは0 $ doar 4gram.idx ！熱いハ # 入力 #19999995: ！熱いハ # 出力: IDは19999995 ！熱いバ # 入力 #19999996: ！熱いバ # 出力: IDは19999996
