Nグラム
Nグラムを取り出すC++のクラスを作成したのでメモ。
UTF-8のみ対応。
/* * ファイル名: ngram.hh */ #ifndef TOKENIZER_NGRAM_HH #define TOKENIZER_NGRAM_HH #include <algorithm> #include <vector> #include <cstring> namespace Tokenizer { class Ngram { public: Ngram(unsigned min, unsigned max) : min(std::max(min, 1u)), max(std::min(max, 32u)) {} template<class Callback> void each_token(const char* text, Callback& fn) const { std::vector<unsigned> char_start_pos; const unsigned len = strlen(text); for(unsigned i=0; i < len; i++) { if(!(text[i]&0x80)) char_start_pos.push_back(i); // ascii else if (text[i]&0x40) char_start_pos.push_back(i); // start of a UTF-8 character byte sequence } char_start_pos.push_back(len); for(unsigned i=0; i < char_start_pos.size(); i++) for(unsigned n=min; n <= max; n++) if(i+n < char_start_pos.size()) fn(text+char_start_pos[i], text+char_start_pos[i+n]); } private: const unsigned min; const unsigned max; }; } #endif
使用例:
/* * ファイル名: ngram.cc */ #include <string> #include <iostream> #include <cstdlib> #include "ngram.hh" void print_ngram(const char* beg, const char* end) { std::cout << std::string(beg,end) << std::endl; }; int main(int argc, char** argv) { if(argc != 3) { std::cerr << "Usage: ngram <min> <max>" << std::endl; return 1; } Tokenizer::Ngram ngram(atoi(argv[1]), atoi(argv[2])); std::string line; while(std::getline(std::cin, line)) ngram.each_token(line.c_str(), print_ngram); return 0; }
実行例:
$ g++ -o ngram ngram.cc $ echo '「そりゃまたなぜです」' | ./ngram 1 3 「 「そ 「そり そ そり そりゃ り りゃ りゃま ゃ ゃま ゃまた ま また またな た たな たなぜ な なぜ なぜで ぜ ぜで ぜです で です です」 す す」 」 $ echo '「そりゃまたなぜです」' | ./ngram 4 9 「そりゃ 「そりゃま 「そりゃまた 「そりゃまたな 「そりゃまたなぜ 「そりゃまたなぜで そりゃま そりゃまた そりゃまたな そりゃまたなぜ そりゃまたなぜで そりゃまたなぜです りゃまた りゃまたな りゃまたなぜ りゃまたなぜで りゃまたなぜです りゃまたなぜです」 ゃまたな ゃまたなぜ ゃまたなぜで ゃまたなぜです ゃまたなぜです」 またなぜ またなぜで またなぜです またなぜです」 たなぜで たなぜです たなぜです」 なぜです なぜです」 ぜです」
デーモン化
任意のコマンドをデーモンプロセスとして実行するようなコマンドが欲しかったので実装してみた。
/*** * ファイル名: daemonize.c * コンパイル: gcc -o daemonize daemonize * * 概要: * 引数で渡したコマンドをデーモンプロセスとして実行する。 * * 使い方: * $ daemonize [-p PID] [--nochdir] [--noclose] cmd arg* * -p PID: cmdのプロセスIDをファイルPIDに書き込む ※ PIDには絶対パスを指定する必要がある * --nochdir: 指定されていない場合は、'/'にカレントディレクトリを移して、cmdを実行する * --noclose: 指定されていない場合は、標準入力/標準出力/標準エラー出力、を/dev/nullにリダイレクトして、cmdを実行する */ #include <stdio.h> #include <string.h> #include <unistd.h> #include <errno.h> #include <sys/types.h> #include <sys/stat.h> int main(int argc, char** argv) { char* pid=NULL; char** args; int arg_i = 1; int nochdir=0; int noclose=0; // show usage if(argc < 2) { ARG_ERROR: puts("Usage: daemonize [-p PID] [--nochdir] [--noclose] cmd arg*"); return 1; } // parse arguments for(; arg_i < argc && argv[arg_i][0]=='-'; arg_i++) { char* opt = argv[arg_i]; if(strncmp(opt,"-p",2)==0) pid = opt[2]=='\0' ? argv[++arg_i] : argv[arg_i]+2; else if (strcmp(opt, "--nochdir")==0) nochdir = 1; else if (strcmp(opt, "--noclose")==0) noclose = 1; else goto ARG_ERROR; // unknown option } if(arg_i == argc) goto ARG_ERROR; // too few arguments args = argv+arg_i; // daemonize if(daemon(nochdir, noclose)==-1) return errno; // write PID if(pid) { FILE *f = fopen(pid,"w"); if(!f) return 0; fprintf(f, "%d", getpid()); fclose(f); } // exec execvp(args[0], args); // delete PID on error remove(pid); return 0; } /* // daemon関数の自作版 (若干いい加減) // linuxには(?)、デーモンプロセスを作成するための関数(daemon関数)が備わっていたので、そちらを使用するように変更 #include <stdlib.h> int daemon(int nochdir, int noclose) { int ret; ret = fork(); if(ret==-1) return -1; if(ret!= 0) exit(0); setsid(); ret = fork(); if(ret==-1) return -1; if(ret!= 0) exit(0); if(nochdir==0) if(chdir("/")==-1) return -1; umask(0); { int fd; int fd_limit = sysconf(_SC_OPEN_MAX); for(fd=3; fd < fd_limit; fd++) close(fd); if(noclose==0) { freopen("/dev/null", "w", stdout); freopen("/dev/null", "w", stderr); freopen("/dev/null", "r", stdin); } } return 0; } */
実行例
適切な例ではないけど、一応動かしてみた結果。
$ echo $PWD /tmp $ ./daemonize sh -c 'echo $PWD' $ ./daemonize --noclose sh -c 'echo $PWD' / $ ./daemonize --nochdir --noclose sh -c 'echo $PWD' /tmp $ ./daemonize -p/tmp/sleep.pid sleep 1000 $ cat sleep.pid 17069 $ ps alx | grep 17069 F UID PID PPID PRI NI VSZ RSS WCHAN STAT TTY TIME COMMAND 0 1000 17069 1 20 0 2868 728 - Ss ? 0:00 sleep 1000
nohup, disown
上記コマンド作成後に、同じようなことを行うためのnohupやdisownというコマンドがあることを知った。
それらを使った方が良さそう...。
daemonizeコマンドの(ささいな)利点は、プロセスIDをファイルに保存できることくらいかな。
DAWG(4-3): MPHFライブラリ
前回までで最小完全ハッシュ関数(MPHF)の実装方法(の一つ)が分かったので、C++から使いやすくするためにライブラリ(と云う程の規模ではないけど)としてまとめておいた。
・mphf-0.0.1
実装の大枠は、前回のcommon lisp版のものと同様なので略*1。
ハッシュ関数の数は二個に固定*2。
例:
コマンドの実行例。
参照: wikipedia各国語タイトルの取得方法
# ビルド $ cd mphf-0.0.1 $ make # データ: wikipediaの各国語タイトル $ ls -lh wiki.title -rw-r--r-- 1 user user 103M 2010-06-23 01:10 wiki.title $ wc -l wiki.title 5340378 wiki.title # 約530万語 # MPHF生成 $ time ./mkmphf mphf.wiki.idx ~/dev/cc/louds/wiki.title = Initialize == key count: 5340378 # キー数 == hash value limit: 11161390 # ハッシュ値の上限 (キー数*2.09) DONE = Mapping Step: == loop: 1/32 # Mapping Stepのグラフ生成/チェックループ == loop: 2/32 # ハッシュ値計算方法がいいかげんなためか期待値(三割前後)よりも成功率が低い == loop: 3/32 == loop: 4/32 == loop: 5/32 == loop: 6/32 == loop: 7/32 == loop: 8/32 == loop: 9/32 Done = Assigning Step: Done = Ranking Step: Done = Save: mphf.wiki.idx Done real 0m31.833s user 0m31.346s sys 0m0.488s $ ls -lh mphf.wiki.idx -rw-r--r-- 1 user user 2237164 2010-07-21 03:56 mphf.wiki.idx # 2.2MB: キー1つにつき約3.4bit # ハッシュ値計算 $ head wiki.title ! !! !!! !!!Fuck_You!!! !!!_(album) != !? !Avast !Kwi !LOUD! $ head wiki.title | ./mphf mphf.wiki.idx 3459282 5311644 984391 2303434 5104951 450980 450982 3505548 2184885 1526653 $ ./mphf mphf.wiki.idx < wiki.title | sort -n | head 0 1 2 3 4 5 6 7 8 9 $ ./mphf mphf.wiki.idx < wiki.title | sort -n | tail 5340368 5340369 5340370 5340371 5340372 5340373 5340374 5340375 5340376 5340377 $ ./mphf mphf.wiki.idx < wiki.title | sort -n | uniq | wc -l 5340378
*1:本質的に差異があるのは次の二点のみ:
1] phfからmphfへの変換方法:
- 上のライブラリでは『Simple and Space-Efficient Minimal Perfect Hash Functions』の4.1節(「Imporveing the space」)の最後で示唆されている方法を採用している。
- 使用ハッシュ関数を決定してからrankしていたのを、rankしてから使用ハッシュ関数を決めるように。
- 若干処理は多くなるが、省スペース。詳細は省略。
2] Mapping Stepでのグラフの循環チェック(and Assigning Step用の並び替え):
- 前回は、各頂点(ハッシュ値)が接続する全ての枝をリストとして保持する配列をチェックのために用意していた。
-- 循環性のチェックは、枝リストのサイズが一の頂点の削除を繰り返すことで行う。
-- 処理ステップ的には効率が良さそうな気がするけど、結構スペースを消費する。
-- オリジナルのグラフ(キーごとのハッシュ値セット) + リストの配列 + 削除順に並び替えを行ったグラフ 分の領域が必要。
-- Mapping Stepが全体を通して一番スペースを要する。
- 今回(?)は、チェック用に補助的なデータ構造は用意しない。
-- 枝の片方の頂点でソート、ユニークな頂点を持つ枝(= 末端の枝)の除去(実際には先頭との入れ替え)、除去分を除いてもう片方の頂点でソート、... を繰り返すことでチェック(and 並び替え)を行う。
-- 全て削除できたのなら非循環。
-- 複数回ソート及び走査を行う必要があるが、作業領域はグラフ一個分 = キーセットのサイズ x sizeof(unsigned) x Nで済む。※ Nはハッシュ関数の数、ハッシュ値の型はunsigned intと仮定
*2:二個の方が実装が簡単になるため。ハッシュ関数を三個にした方が非循環グラフの生成は容易(Mapping Stepでのループ回数を減らせる)で、最終的なデータサイズも節約できるので、いつか変更するかもしれない。
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
Micterの単語分割部の高速化を試してみた結果
tkngさんが作成したMicterという単語分割器の分割部を高速化できるような気がしたので試してみた。
そのメモ。
試した結果のソース一式はmimicという名前でgithubに保存しておくことにする*1。
結果
まず、結果から*2。
# 分割対象のテキスト(のサイズ) $ ls -lh /tmp/test.data -rw-r--r-- 1 user user 41M 2010-07-05 22:48 /tmp/test.data # MeCab $ time mecab -Owakati /tmp/test.data > /dev/null real 0m10.843s # 10秒 user 0m10.777s sys 0m0.068s # Micter $ ls -lh micter.model -rw-r--r-- 1 user user 1.8M 2010-07-06 08:30 micter.model $ time micter -m micter.model < /tmp/test.data > /dev/null real 0m31.283s # 31秒 user 0m31.198s sys 0m0.088s # mimic $ ls -lh mimic.index -rw-r--r-- 1 user user 4.0M 2010-07-06 07:59 mimic.index # DoubleArrayインデックス + α $ time ./mimic-split mimic.idx /tmp/test.data > /dev/null real 0m3.980s # 4秒 user 0m3.908s sys 0m0.072s
条件を全く合わせていないし、計時に用いたデータの情報もオープンにしていないので、細かい点に関しては全く参考にならない数値だが、おおまかにmimicがMeCabよりも高速に単語分割が行えていることは分かる。
高速化は成功。
修正点
mimicがMicterに対して何を修正したか。
基本的には、分割時に分割可否の判断を行うために必要な、素性群を取り出す方法を変えただけ*3。
Micterでの単語分割処理を擬似コードで記すと(多分)以下のようになる。
※ かなり単純化している。ちゃんと知りたい人は、(当たり前だけど)オリジナルのソースコードを参照のこと。
# Ruby風 # # 入力文字列の各文字位置で、素性群を取り出し、スコアを算出し、分割するかどうかを決定 def word_split(line) # lineは文字列 ※バイト列ではい line.length.times do |i| fs = get_feature_list(line, i) # 位置iの素性群を取得する score=0; fs.each{|f| score += f.score} # 各素性のスコア(?)の合計を求める if score >= 0.0 # 0.0以上なら、ここで分割を行う # 分割! end end end # 位置iに紐付く素性群を取得する def get_feature_list(line, i) ary = Array.new ary += get_unigram_feature_list(line, i) # 一文字素性を取り出して、配列に追加 ary += get_bigram_feature_list(line, i) # 二文字素性を取り出して、配列に追加 ary += get_trigram_feature_list(line, i) # 三文字素性を取り出して、配列に追加 ary += get_char_type_bigram_feature_list(line, i) # 文字カテゴリ素性を取り出して、配列に追加 return ary end def get_bigram_feature_list(line, i) word = line[i,2] # 現在位置のバイグラム取得 feature = feature_table[word] # 素性取得 ※ feature_tableはハッシュ return [feature] end
対して、mimic。
※ こっちもかなり単純化している
## 前処理 # 各素性(Nグラム文字列)のスコアを格納したDoubleArrayインデックスを読み込む # トライのキー: 素性文字列 # トライの値 : 素性の分割スコア TRIE = DoubleArrayTrie.load "モデルデータのパス" def word_split(line) score_array = (0..line.length-1).to_a.map{|i| 0.0} line.length.times do |i| # 入力文字列の全位置に対して、common-prefix-search(素性文字列の検索)を行う TRIE.common_prefix_search(line, i) do |match_pos, score| score_array[match_pos] += score # マッチした場合は、その文字位置の分割スコアを修正する end end line.length.times do |i| if score_array[i] >= 0.0 # 分割! end end end
学習時に取得した全素性(文字列)をDoubleArrayに登録してしておき、分割時にはそれを用いて入力文字列の各位置でcommon-prefix-searchを行うだけで、分割のためのスコアが算出可能なので高速、というわけ。
注意
mimicは分割部の実装を簡潔にするために、学習部もMicterのものから若干変更している。
そのため、mimicの分割結果はMicterのそれとは同一ではなく、分割精度が劣化している可能性もある。
あと、あくまでも高速化案を試すことが目的だったので実装はテキトウ*4、かつ、今後の改善の予定もなし。
追記(2010/07/06)
ちなみに、僕の環境ではテンプレート周りでエラーが発生してしまい、Micterのビルドが出来なかった。
util.hppに以下のコードを追加したら、(原因は不明だが)一応解決した。
namespace std { namespace tr1 { template<class T> struct hash { }; template <> struct hash<feature> : public std::unary_function<feature, std::size_t> { // これはfeature_hash構造体の、operator()メソッドと同じ内容 size_t operator()(feature val) const { size_t __length = val.len_; const char *__first = val.str_; size_t __result = static_cast<size_t>(2166136261UL); __result ^= static_cast<size_t>(val.ftype_); // __result += static_cast<size_t>(val.ftype_ << 8); __result *= static_cast<size_t>(16777619UL); for (; __length > 0; --__length) { __result ^= static_cast<size_t>(*__first++); __result *= static_cast<size_t>(16777619UL); } return __result; } }; } }
*1:コンパイルや実行方法はREADMEに記載。実装言語はcommon lispとC++。
*2:学習データには、手元にあったテキスト約100MBをMeCabで形態素解析したものを使用
*3:細かい部分はいろいろ変えているし、学習部はcommon lispになっているけど、分割部の素性取り出し方法以外は、本質的なロジックに差異はない
*4:動けば良い、というレベル
DoubleArray + AC法
AC法(エイホ-コラシック法)というものを知ったのでDoubleArrayで試してみた。
概要
入力テキストから、辞書(= 文字列セット)に登録されている文字列を効率的に検索するための方法らしい*1。
詳細は、Wikipediaの『エイホ-コラシック法』の項目を参照。
自分の理解としては、基本的には通常のトライと同じだけど、各ノードが自身が表す文字列(ルートからのパス)のサフィックス(接尾文字列)に対応するノードへのリンクを有する点が異なる、といった感じ。
以下は、既存のトライに対して、上述のリンクを付加するための擬似コード。
# Ruby形式の擬似コード trie.traverse_all_node do |path, node| # 全ノードを探索: path = ルートからnodeまでの文字を繋げた文字列 suffix_link = trie.root_node # 接尾文字列に対応するノード (初期値はルートノード) # 接尾文字列の内で、対応するノードがある最長のものを探す while path.size > 1 && suffix_link == trie.root_node path = path[1..-1] # 先頭の文字を除去した接尾文字列を作成する suffix_link = trie.search_node(path) # 接尾文字列に対応するノードを探す (見つからなければ、trie.root_nodeが返る) end node.suffix_link = suffix_link end
サフィックスリンクがない通常のトライの場合、入力テキストにマッチする全ての文字列を検索しようとすると、次のようにテキスト内の各位置でcommon-prefix-searchを行う必要がある。
このため最悪の場合は、入力テキストの長さ x トライ内の最大の文字列の長さ、の処理ステップ(?)が必要となる(おそらく)。
# 入力文字列が"abcdefg"の場合 1] "abcdefg"で検索 ※ 一回の検索で、何文字辿る必要があるかは、トライの内容に左右される 2] "bcdefg"で検索 3] "cdefg"で検索 4] "defg"で検索 5] "efg"で検索 6] "fg"で検索 7] "g"で検索 終了
対して、サフィックスリンク付きのトライでは、検索処理は次のようになる。※ かなり単純化している
# 入力文字列が"abcdefg"の場合 1] ルートノードから"a"に対応するノードに遷移 => サフィックスリンク※1を辿り、マッチングがあるかを調べる 2] 上のノードから"b"に対応するノードに遷移※2 => サフィックスリンクを辿り、マッチングがあるかを調べる 3] 上のノードから"c"に対応するノードに遷移 => サフィックスリンクを辿り、マッチングがあるかを調べる 4] 上のノードから"d"に対応するノードに遷移 => サフィックスリンクを辿り、マッチングがあるかを調べる 5] 上のノードから"e"に対応するノードに遷移 => サフィックスリンクを辿り、マッチングがあるかを調べる 6] 上のノードから"f"に対応するノードに遷移 => サフィックスリンクを辿り、マッチングがあるかを調べる 7] 上のノードから"g"に対応するノードに遷移 => サフィックスリンクを辿り、マッチングがあるかを調べる 終了 # ※1 Wikipediaの記事では、ここで辿るサフィックスリンクを「辞書サフィックスリンク」と呼んでいる # # ただのサフィックスリンクは、末尾文字列に対応する(最長の)トライ内の任意のノードへのリンクであるのに対して、 # 辞書サフィックスリンクにはさらに、辞書に登録されている文字列に対応するノード、へのリンクでなければならないという制限がつく。 # # この制限のために、上でリンクを辿る回数は、マッチングがあるノードの数と等しくなり、必要最小限に抑えられる。 # # 上の擬似コードには「辞書サフィックスリンク」用の記述が抜けている # ※2 実際には対応する遷移先にノードがないため遷移できないことがある # その場合は、遷移元ノードのサフィックスリンクを辿り、そこから再度遷移が可能かどうかを試す必要がある # # 下の処理ステップに関する記述では、このための処理に掛かるコストは無視している
この場合の処理ステップ(?)は、入力テキストの長さ + マッチングの数、となりリンクなしの場合に比べて低く抑えることが可能となる(おそらくこれで大きくは間違っていないはず...)。
これがAC法の利点(多分)。
実装1: 比較用トライ検索
ここから実装に入る。
まずは比較用に通常のトライ(DoubleArray)を用いた辞書検索コマンドを作成する。
マッチする文字列を取り出す(or 取り出し表示する)処理は、そのためのオーバヘッドが大きくなる可能性があるので、今回はマッチ数をカウントするだけにする。
※ ここで使用しているDoubleArrayの実装やmkdaコマンドに関しては『基本となるDoubleArrayの実装』を参照
/*** * ファイル名: count-word.cc * コンパイル: g++ -O2 -o count-word count-word.cc * * 入力テキスト内で辞書(= mkdaコマンドが作成したDoubleArrayインデックス)にマッチする文字列の数をカウントする */ #include <iostream> #include <sys/time.h> #include "double_array.h" #include "char_stream_vector.h" // 計時用関数 inline double gettime(){ timeval tv; gettimeofday(&tv,NULL); return static_cast<double>(tv.tv_sec)+static_cast<double>(tv.tv_usec)/1000000.0; } // マッチ数カウント用のクラス struct Counter { Counter() : count(0) {} void operator()(const char* key, unsigned length, int id) { //std::cout << id << "#" << std::string(key, length) << std::endl; count++; } unsigned count; }; int main(int argc, char** argv) { if(argc != 3) { std::cerr << "Usage: count-word <index> <text>" << std::endl; return 1; } DoubleArray da(argv[1]); CharStreamVector csv(argv[2]); Counter fn; // 入力テキストの各行を読み込み、辞書に登録されている文字列の数をカウントする double beg_t = gettime(); for(unsigned i=0; i < csv.size(); i++) { const char* line = csv[i].rest(); for(; *line != '\0'; line++) da.each_common_prefix(line, fn); } std::cerr << "Matched word count: " << fn.count << std::endl; std::cerr << "Elapsed: " << gettime()-beg_t << " sec" << std::endl << std::endl; return 0; }
実行。
辞書にはWikipediaの各国語のタイトル(取得方法はここを参照)とMeCabのサイトより配布されているIPADICから単語名を抽出したものを使用。
# データ準備 $ mkda wiki.idx wiki.title $ nkf -w mecab-ipadic-2.7.0-20070801/*.csv | cut -d',' -f1 | LC_ALL=C sort | LC_ALL=C uniq > ipa.word $ mkda ipa.idx ipa.word $ ls *.idx -rw-r--r-- 1 user user 11M 2010-07-03 18:29 ipa.idx -rw-r--r-- 1 user user 391M 2010-07-03 18:26 wiki.idx # カウント: 入力テキストには、夏目漱石の『こころ』(青空文庫より入手. UTF-8に変換)を使用 $ ./count-word wiki.idx kokoro Word count: 202732 Elapsed: 0.013299 sec $ ./count-word ipa.idx kokoro Word count: 269405 Elapsed: 0.0121629 sec
実装2: AC法
AC法。
トライの部分は通常のDoubleArrayと同様で、各ノードに追加情報を付与する、という実装になっている。
まずは、追加情報を付与するコマンドから作成する。
/*** * ファイル名: double_array.h * * DoubleArray検索部分。 * AC法を実装するために必要な箇所を修正。 * 修正箇所のみ記述。 */ #include <string> // 追加: class DoubleArray { private: unsigned node_size_; // 追加: ノード数 public: DoubleArray(const char* filepath) { FILE* f = fopen(filepath, "rb"); unsigned node_size; fread(&node_size, sizeof(unsigned), 1, f); base = new int [node_size]; chck = new int [node_size]; fread(base, sizeof(int), node_size, f); fread(chck, sizeof(int), node_size, f); fclose(f); node_size_ = node_size; // 追加: } // 追加: unsigned node_size() const { return node_size_; } // 追加: トライの全てのノードを探索する template<class Callback> void traverse_all_node(Callback& fn) const { std::string path; traverse_all_node(fn, path, 0); } // 追加: 入力文字列にマッチするノードを返す int search_node(const char* key) const { int node=0; CharStream in(key); for(int len=0;; len++) { if(in.peek()=='\0') return node; // マッチノード int next_node = base[node] + in.read(); if(chck[next_node] == node) node = next_node; else return 0; // ルートノード } } // 追加: 入力文字列にマッチするノードを返す // 入力文字列にマッチするトライ内のキーが存在しない場合は、ルートノードが返される int search_key_node(const char* key) const { int node=0; CharStream in(key); for(int len=0;; len++) { if(in.peek()=='\0') return chck[base[node]+'\0']==node ? node : 0; // キーが存在するかどうか int next_node = base[node] + in.read(); if(chck[next_node] == node) node = next_node; else return 0; // ルートノード } } // 追加: ノードの深さを求める unsigned depth(int node) const { unsigned dep=0; for(; node != 0; node = chck[node]) dep++; return dep; } // 追加: const int* base_ptr() const { return base; } const int* chck_ptr() const { return chck; } private: // 追加: トライの全てのノードを探索する template<class Callback> void traverse_all_node(Callback& fn, std::string& path, int parent_node) const { for(unsigned child=1; child < 0x100; child++) { // 終端ノード(='\0')は飛ばす int child_node = base[parent_node] + child; if(parent_node == chck[child_node]) { path += static_cast<char>(child); fn(path.c_str(), child_node); traverse_all_node(fn, path, child_node); path.resize(path.size()-1); } } } protected: // 修正: 継承したクラスから参照可能なようにしておく int *base; int *chck;
/*** * ファイル名: mkac.cc * コンパイル: g++ -O2 -o mkac mkac.cc * * mkdaが作成したインデックスに、AC法のための情報を付与する */ #include <iostream> #include <cstdio> #include "double_array.h" class AC_Builder { public: AC_Builder(const DoubleArray& da) : da(da) { suffix_link = new int[da.node_size()]; key_suffix_link = new int[da.node_size()]; node_depth = new short[da.node_size()]; // 初期化 for(unsigned i=0; i < da.node_size(); i++) { suffix_link[i] = 0; // ルートノード key_suffix_link[i] = 0; // ルートノード node_depth[i] = 0; // ルートノードの深さ } } ~AC_Builder() { delete [] suffix_link; delete [] key_suffix_link; delete [] node_depth; } // traverse_all_nodeメソッドのコールバック void operator()(const char* path, int node) { //if(node%10000 == 0) // std::cout << node << "#" << path << std::endl; int suffix_node=0; do { if(*(++path)=='\0') break; } while(0 == (suffix_node=da.search_node(path))); int key_suffix_node = da.search_key_node(path); while(0 == key_suffix_node) { if(*(++path)=='\0') break; key_suffix_node=da.search_key_node(path); } suffix_link[node] = suffix_node; key_suffix_link[node] = key_suffix_node; node_depth[node] = da.depth(node); } void save(const char* filepath) const { FILE *f = fopen(filepath, "wb"); unsigned size = da.node_size(); fwrite(&size, sizeof(unsigned), 1, f); fwrite(da.base_ptr(), sizeof(int), size, f); fwrite(da.chck_ptr(), sizeof(int), size, f); fwrite(suffix_link, sizeof(int), size, f); fwrite(key_suffix_link, sizeof(int), size, f); fwrite(node_depth, sizeof(short), size, f); fclose(f); } private: const DoubleArray& da; int* suffix_link; // サフィックスのリンク int* key_suffix_link; // 辞書サフィックスのリンク short* node_depth; // ノードの深さ: 予め計算/保持しておくことで、検索時のコストを抑える }; int main(int argc, char** argv) { if(argc != 3) { std::cerr << "Usage: mkac <ac-index> <da-index>" << std::endl; return 1; } DoubleArray da(argv[2]); AC_Builder acb(da); da.traverse_all_node(acb); acb.save(argv[1]); return 0; }
実行。
$ ./mkac ipa-ac.idx ipa.idx $ ./mkac wiki-ac.idx wiki.idx $ ls -lh *.idx -rw-r--r-- 1 user user 24M 2010-07-03 19:28 ipa-ac.idx -rw-r--r-- 1 user user 11M 2010-07-03 18:29 ipa.idx -rw-r--r-- 1 user user 879M 2010-07-03 19:29 wiki-ac.idx -rw-r--r-- 1 user user 391M 2010-07-03 18:26 wiki.idx
次は、AC法を用いたワードカウントコマンド(と、そのための検索クラス)。
/*** * ファイル名: double_array_ac.h * * DoubleArray検索のAC法版 */ #ifndef DOUBLE_ARRAY_AC_H #define DOUBLE_ARRAY_AC_H #include <cstdio> #include "char_stream.h" #include "double_array.h" #include <string> #include <cassert> // DoubleArray(AC法版)検索用のクラス class DoubleArrayAC : public DoubleArray { public: DoubleArrayAC(const char* filepath) : DoubleArray(filepath) { suffix_link = new int[node_size()]; key_suffix_link = new int[node_size()]; node_depth = new short[node_size()]; FILE *f = fopen(filepath, "rb"); fseek(f, node_size()*sizeof(int)*2+sizeof(unsigned), SEEK_SET); // DoubleArrayクラスのデータ格納部分は飛ばす fread(suffix_link, sizeof(int), node_size(), f); fread(key_suffix_link, sizeof(int), node_size(), f); fread(node_depth, sizeof(short), node_size(), f); fclose(f); } ~DoubleArrayAC() { delete [] suffix_link; delete [] key_suffix_link; delete [] node_depth; } // 入力文字列にマッチする全てのキーを検索する template<class Callback> void each_match(const char* text, Callback& fn) const { int node=0; CharStream in(text); for(;; in.read()) { // このノードに対応するキーがあるか int terminal = base[node]+'\0'; if(chck[terminal] == node) fn(in.rest()-node_depth[node], node_depth[node], -base[terminal]); // このノードの辞書サフィックスリンクを辿ってキーを探す for(int tmp=key_suffix_link[node]; tmp!=0; tmp=key_suffix_link[tmp]) fn(in.rest()-node_depth[tmp], node_depth[tmp], -base[base[tmp]+'\0']); // 次のノードに遷移する for(;;) { if(in.peek()=='\0') return; // 検索終了 int next = base[node] + in.peek(); if(chck[next] == node) { node = next; // 遷移 break; } // 現在のノードからの有効な遷移がない場合 if(node==0) in.read(); // ルートノードなら遷移文字を読み進める else node = suffix_link[node]; // サフィックスリンクを辿って、遷移をやり直す } } } private: int* suffix_link; // サフィックスのリンク int* key_suffix_link; // 辞書サフィックスのリンク short* node_depth; // ノードの深さ: 予め計算/保持しておくことで、検索時のコストを抑える }; #endif
/*** * ファイル名: ac-count-word.cc * コンパイル: g++ -O2 -o ac-count-word ac-count-word.cc * * 入力テキスト内で辞書(= mkacコマンドが作成したDoubleArray(AC法版)インデックス)にマッチする文字列の数をカウントする */ #include <iostream> #include <sys/time.h> #include "double_array_ac.h" #include "char_stream_vector.h" inline double gettime(){ timeval tv; gettimeofday(&tv,NULL); return static_cast<double>(tv.tv_sec)+static_cast<double>(tv.tv_usec)/1000000.0; } struct Counter { Counter() : count(0) {} void operator()(const char* key, unsigned length, int id) { //std::cout << id << "#" << std::string(key, length) << std::endl; count++; } unsigned count; }; int main(int argc, char** argv) { if(argc != 3) { std::cerr << "Usage: ac-count-word <index> <text>" << std::endl; return 1; } DoubleArrayAC da(argv[1]); CharStreamVector csv(argv[2]); Counter fn; double beg_t = gettime(); for(unsigned i=0; i < csv.size(); i++) { const char* line = csv[i].rest(); da.each_match(line, fn); } std::cerr << "Matched word count: " << fn.count << std::endl; std::cerr << "Elapsed: " << gettime()-beg_t << " sec" << std::endl << std::endl; return 0; }
実行。
$ ./ac-count-word wiki-ac.idx ~/kokoro Matched word count: 202732 Elapsed: 0.01694 sec $ ./ac-count-word ipa-ac.idx ~/kokoro Matched word count: 269405 Elapsed: 0.0136041 sec
AC法版の方が遅い結果となった。
感想とか
検索時のループ数*2は、AC法版の方が少なく、通常版の(今回のデータでは)1/2程度であった。
ループ数は少なくなったのに処理時間が長くなっているのは、多分検索時に使用する配列が増えてメモリキャッシュの効率が(結構大幅に)下がったためではないかと思う。
加えて、AC法版の方が検索メソッドが行う処理が複雑になっているということも(どの程度かは分からないが)関係していると思う。
いずれにせよ、AC法を用いたトライは-説明を読んだ時には速そうに感じたけど-実際に実装してみると(少なくとも常には)通常のトライに対して速度的に優れているわけではない、ということは分かった*3。
あと、データサイズが大きくなる、という欠点もある*4。
*1:入力テキスト/辞書の文字列の長さ/検索マッチ数 に対して線形
*2:DoubleArray.common_prefix_searchの場合は、内部のforループの回数。DoubleArrayAC.each_matchの場合は、内部の三つのforループの総数
*3:僕の実装が悪い、という可能性は残っているけど
*4:AC法のための追加する情報(= 配列)を減らすことで、データサイズをある程度切り詰めることは可能。ただし、そうした場合、AC法を利用するそもそもの動機であった処理速度が遅くなる可能性がある。また、AC法はその性質上、トライの全ての要素をノードとして表現する必要があるので、DoubleArrayのTAIL配列のような(ノード数自体を少なくすることによる)データ圧縮方法が使えず、サイズ縮小には限界がある。
