UNF-0.0.4: サイズ削減
今日は久しぶりにUNF(ユニコード正規化ライブラリ)に手を加えていた。
大きな変更点は、正規化用変換テーブルを実現していたTRIEをDAWGにしたこと。
もともとは正規分解と互換分解用に、内容がほぼ等しいTRIEを別々に持っていたので、それを一つDAWGにして共有することでだいぶサイズが節約できた。
# unf-0.0.3 $ ls -lh unf-0.0.3/bin/unf -rwxrwxr-x 1 user user 596K 2011-11-19 17:54 unf-0.0.3/bin/unf # 596KB # unf-0.0.4 $ ls -lh unf-0.0.4/bin/unf -rwxrwxr-x 1 user user 411K 2011-11-19 20:20 unf-0.0.4/bin/unf # 411KB
処理速度も、ごく僅かだけど新しいバージョンの方が速くなっているように見える。
# 17MBのテキストデータの正規化時間 # unf-0.0.3 $ unf-0.0.3/bin/unf-time < 17MB.txt = read: == 172090 lines == average(line length): 99 byte = time: == NFD : 0.203354 sec == NFC : 0.109814 sec == NFKD: 0.215196 sec == NFKC: 0.137385 sec DONE # unf-0.0.4 $ unf-0.0.4/bin/unf-time < 17MB.txt = read: == 172090 lines == average(line length): 99 byte = time: == NFD : 0.199866 sec == NFC : 0.104912 sec == NFKD: 0.206675 sec == NFKC: 0.137277 sec DONE
SA-IS: C++版
以前にcommon lispで実装したSA-ISアルゴリズムを、C++でも実装したのでその計時結果など。
ソースコード(github): sais-0.0.1
計時
対象データには以下のサイズのテキストファイル群を使用。
$ ls sa.txt.* -rw-r--r-- 1 user user 10000 2010-12-23 19:25 sa.txt.10000 # 約10KB -rw-r--r-- 1 user user 100000 2010-12-23 19:25 sa.txt.100000 # 約100KB -rw-r--r-- 1 user user 1000000 2010-12-23 19:25 sa.txt.1000000 # 約1MB -rw-r--r-- 1 user user 10000000 2010-12-23 19:25 sa.txt.10000000 # 約10MB -rw-r--r-- 1 user user 100000000 2010-12-23 19:25 sa.txt.100000000 # 約100MB
計時結果.
表の二番目のSA-ISの実装には『Two Efficient Algorithms for Linear Suffix Array Construction』に載っているC++のソースコードを使用。
※ 末尾の計時用プログラムも参照
| 構築時間/最大使用メモリ | sa.txt.10000 | sa.txt.100000 | sa.txt.1000000 | sa.txt.10000000 | sa.txt.100000000 |
| std::sort関数 | 0.007秒/49KB | 0.094秒/488KB | 4.246秒/4883KB | 394.3秒/48828KB | 計測不能*1 |
| SA-IS(論文の実装) | 0.002秒/57KB | 0.020秒/543KB | 0.215秒/5382KB | 3.542秒/53010KB | 40.34秒/530268KB |
| SA-IS(sais-0.0.1) | 0.002秒/90KB | 0.019秒/781KB | 0.192秒/7035KB | 3.406秒/65036KB | 38.31秒/644434KB |
SuffixArrayの構築に必要なメモリは、std::sort関数を用いた場合が一番少なく「入力データ分 + SuffixArray分(対象データ x sizeof(int))」のバイト数となっている。
SA-ISアルゴリズムの場合は、構築時にさらに余分な領域が必要になるが、(論文の実装の場合は)一割程度の増分で済んでいる。
メモリ使用量
今回作成したsais-0.0.1でのメモリ使用量の概略。
- 1) 入力データ用のメモリ
- 2) SuffixArray用のメモリ: 入力データサイズ x sizeof(int) バイト
- この領域はinduced-sortで使用するバケツの領域としても利用される
- SA-ISの再帰的な呼び出し時には、一つ上のレベルのSuffixArray用のメモリ領域が共有されるため追加で確保されることはない
- 3) 入力データの各文字(or suffix)のタイプを保持する配列用のメモリ: 入力データサイズ x 1 ビット
- SA-ISの(再帰)呼び出しのたびに、新たに確保
- 4) induced-sort時に用いる各文字用のバケツのインデックスを保持する配列用のメモリ: (入力データ中の最大要素の値+1) x 3xsizeof(unsigned) バイト
- SA-ISの(再帰)呼び出しのたびに、新たに確保
この内で３と４は、SA-ISの再帰的呼び出しの回数とその際の入力データによって変動する。
SA-IS再帰呼び出しの際の入力データのサイズは、一つ上のレベルでのそれの半分以下となることが保証されているので、３用のメモリ使用量は多くても、入力データサイズ*2 ビット == 入力データサイズ/4 バイト、となる(おそらく)。
４の方は、一番最初の(もともとの入力データに対する)SA-IS呼び出し時には、256 x 12 バイト*2 *3、必要となる。そして残りの各SA-IS再帰呼び出しでは最大で、入力データサイズ x 12 バイト*4、の領域が消費されるので、最悪の場合の使用メモリ量はだいたい、(100 + 入力データサイズ) x 12 バイト、となる(おそらく)。
論文にある実装では、よりメモリ使用量が少ないので、もっと節約できる箇所がある*5のだろうけど、特に差し迫って何かに使いたいということもないので、当面は改良の予定はなし。
計時プログラム
計時に用いたプログラムのソースコード。
汎用ソート用:
※ util.hhファイルに関してはsais-0.0.1を参照
/*** * ファイル名: sa-sort.cc * コンパイル: g++ -O3 -o sa-sort sa-sort.cc * 使用方法: sa-sort <対象ファイル> */ #include <iostream> #include <algorithm> #include <cstring> #include "util.hh" struct SAcmp { SAcmp(const char* s) : s(s) {} bool operator()(const int i1, const int i2) const { return strcmp(s+i1, s+i2) < 0; } const char* s; }; void sa_sort(const char* s, unsigned length, int* sa) { for(unsigned i=0; i < length; i++) sa[i] = i; SAcmp cmp(s); std::sort(sa, sa+length, cmp); } int main(int argc, char** argv) { if(argc != 2) { std::cerr << "Usage: sa-sort FILEPATH" << std::endl; return 1; } double beg_t = gettime(); FileData fd(argv[1]); if(!fd) { std::cerr << "Can't open file: " << argv[1] << std::endl; return 1; } std::cerr << "Read file data:\t\t took " << gettime()-beg_t << " sec" << std::endl; beg_t = gettime(); const char* text = fd.c_str(); int* sa = new int[fd.size()+1]; sa_sort(text, fd.size()+1, sa); std::cerr << "Construct Suffix-Array:\t took " << gettime()-beg_t << " sec" << std::endl; beg_t = gettime(); for(unsigned i=1; i <= fd.size(); i++) std::cout << sa[i] << std::endl; std::cerr << "Print SA elements:\t took " << gettime()-beg_t << " sec" << std::endl; return 0; }
SA-IS(論文の実装):
/*** * ファイル名: sais-orig.cc * コンパイル: g++ -O3 -o sais-orig sais-orig.cc * 使用方法: sais-orig <対象ファイル> */ #include <iostream> #include <cstdlib> #include "util.hh" // ※ 'sais-orig.hh'の中身は『Two Efficient Algorithms for Linear Suffix Array Construction』に載っているC++のソースコード #include "sais-orig.hh" int main(int argc, char** argv) { if(argc != 2) { std::cerr << "Usage: sa FILEPATH" << std::endl; return 1; } double beg_t = gettime(); FileData fd(argv[1]); if(!fd) { std::cerr << "Can't open file: " << argv[1] << std::endl; return 1; } std::cerr << "Read file data:\t\t took " << gettime()-beg_t << " sec" << std::endl; beg_t = gettime(); const char* text = fd.c_str(); int* SA = new int[fd.size()+1]; SA_IS((unsigned char*)text, SA, fd.size()+1, 0x100, sizeof(char)); std::cerr << "Construct Suffix-Array:\t took " << gettime()-beg_t << " sec" << std::endl; beg_t = gettime(); for(unsigned i=1; i <= fd.size(); i++) std::cout << SA[i] << std::endl; std::cerr << "Print SA elements:\t took " << gettime()-beg_t << " sec" << std::endl; return 0; }
*1:処理終了までの時間が長すぎるため
*2:'256'は、char型で表現可能な文字の数
*3:2010/12/25: コメントにて指摘を受けたため修正。もともとは「256 x 3バイト」と記載していたが掛けるバイト数は、3 x sizeof(unsigned)バイト == 12バイト、が正しい。
*4:SA-ISの再帰呼び出し時には、一つ上のレベルの各LMS部分文字列(の最初の要素)の先頭からの順番(ソート順)が、入力として用いられる。そのため新たな入力データ中の要素の最大の値は'入力データサイズ-1'(添字の最大値)となる※ 簡略化し過ぎで若干不正確だけど、大きくは間違ってはいない。
*5:バケツの表現方法に工夫がある？
マルチキークイックソートとstd::sortの比較
以前にCommon Lispで実装したマルチキークイックソートをC++で書き直して、STLのstd::sortと速度を比較してみた。
使用データ
Wikipediaの記事タイトル約500万行を使用。
データ作成方法などはここを参照。
$ wc -l wiki.title.500 5340378 wiki.title.500 $ ls -lh wiki.title.500 -rw-r--r-- 1 user user 103M 2010-10-27 02:14 wiki.title.500
# ファイル名: shuffle.rb lines=open(ARGV[0]).read.split("\n") 2.times{|k| lines.size.times{|i| j = rand(lines.size) tmp = lines[i] lines[i] = lines[j] lines[j] = tmp } } lines.each{|l| puts l }
$ ruby shuffle.rb wiki.title.500 > wiki.shuffle
$ head wiki.shuffle
西村知道
カービィのピンボール
Hudson_K〓rfezi
De_Sanctis-Cacchionen_syndrooma
倍数性
Arto_Kulmala
比較結果
実行速度の比較結果。
比較に用いたソースコードは末尾に掲載。
# マルチキークイックソート $ ./mqsort 0 < wiki.shuffle > /dev/null MULTIKEY QUICK SORT: Elapsed: 4.58632 sec # std::sort $ ./mqsort 1 < wiki.shuffle > /dev/null std::sort: Elapsed: 9.90535 sec
この例ではマルチキークイックソートの方がニ倍程度早かった。
ソースコード
実装ソースコード。
以前のCommon LispのそれをC++に直訳したもの。
チューニングすればもう少し早くなるかも*1。
/** * ファイル名: mqsort.cc * コンパイル: g++ -O2 -o mqsort mqsort.cc # gcc version 4.4.3 (Ubuntu 4.4.3-4ubuntu5) * * 標準入力から行を読み込み、ソートした結果を出力する。 * ソート方法はマルチキークイックソートかstd::sort。 * ※ コマンドの第一引数に0を渡せば前者、それ以外なら後者。 * * Usage: mqsort [0 or 1] < [入力ファイル] > [出力ファイル] */ #include <iostream> #include <vector> #include <string> #include <cstring> #include <algorithm> /** * 計時用関数 */ #include <sys/time.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 Range { Range(const char** b, const char** e) : begin(b), end(e) {} const char** begin; const char** end; }; inline void swap_range(const char** beg1, const char** beg2, int count) { for(int i=0; i < count; i++) std::swap(beg1[i], beg2[i]); } inline unsigned char code(const char** ptr, int depth) { return (unsigned char)(*ptr)[depth]; } inline void set_pivot_at_front(const char** beg, const char** end, int depth) { const char** mid = beg + (end-beg)/2; const char** las = end-1; unsigned char a = code(beg,depth); unsigned char b = code(mid,depth); unsigned char c = code(las,depth); if(a<b) { if(a<c) { b<c ? std::swap(*beg,*mid) : std::swap(*beg,*las); } } else { if(b<c) { std::swap(*beg,*mid); } else { if(a<c) std::swap(*beg,*las); } } } Range partition(const char** beg, const char** end, int depth) { set_pivot_at_front(beg, end, depth); unsigned char pivot = code(beg,depth); const char** ls_front = beg+1; const char** ls_last = beg+1; const char** gt_front = end-1; const char** gt_last = end-1; for(;;) { for(; ls_last <= gt_front && code(ls_last,depth) <= pivot; ls_last++) if(pivot == code(ls_last,depth)) { std::swap(*ls_front, *ls_last); ls_front++; } for(; ls_last <= gt_front && code(gt_front,depth) >= pivot; gt_front--) if(pivot == code(gt_front,depth)) { std::swap(*gt_front, *gt_last); gt_last--; } if(ls_last > gt_front) break; std::swap(*ls_last, *gt_front); ls_last++; gt_front--; } const char** ls_beg = ls_front; const char** ls_end = ls_last; const char** gt_beg = ls_last; const char** gt_end = gt_last+1; int len1 = std::min(ls_beg-beg, ls_end-ls_beg); swap_range(beg, ls_end-len1, len1); int len2 = std::min(end-gt_end, gt_end-gt_beg); swap_range(gt_beg, end-len2, len2); return Range(ls_end-(ls_beg-beg), gt_beg+(end-gt_end)); } inline void swap_if_greater(const char*& x, const char*& y, int depth) { if(strcmp(x+depth, y+depth) > 0) std::swap(x, y); } void mqsort_impl(const char** begin, const char** end, int depth) { int len = end-begin; if(len <= 2) { if(len == 2) swap_if_greater(*begin, *(begin+1), depth); } else { Range r = partition(begin, end, depth); mqsort_impl(begin, r.begin, depth); if(code(r.begin,depth) != '\0') mqsort_impl(r.begin, r.end, depth+1); mqsort_impl(r.end, end, depth); } } void mqsort(const char** begin, const char** end) { mqsort_impl(begin, end, 0); } // std::sortに渡す比較関数 inline bool str_less_than(const char* a, const char* b) { return strcmp(a,b) < 0; } /** * main関数 */ int main(int argc, char** argv) { // 標準入力から行読み込み std::vector<std::string> lines; std::string line; while(getline(std::cin,line)) lines.push_back(line); // char*の配列に変換 const char** words = new const char*[lines.size()]; for(int i=0; i < lines.size(); i++) words[i] = lines[i].c_str(); // ソート double beg_t = gettime(); if(strcmp(argv[1],"0")==0) { std::cerr << "MULTIKEY QUICK SORT:" << std::endl; mqsort(words, words+lines.size()); } else { std::cerr << "std::sort:" << std::endl; std::sort(words, words+lines.size(), str_less_than); } std::cerr << "Elapsed: " << gettime()-beg_t << " sec" << std::endl; // 結果出力 for(int i=0; i < lines.size(); i++) std::cout << words[i] << std::endl; return 0; };
DAWG2(2.5): DAWG構築時のハッシュ値用の領域節約
前回にソート済みファイルからDAWGを構築する際には、個々のノードのハッシュ値をO(1)で(簡単に)算出可能にするために、ノードにハッシュ値用のフィールドを持たせていた。
;;;; 再掲 ;; DAWGのノード用の構造体 (defstruct node (label 0 :type octet) (sibling nil :type (or null node)) (child nil :type (or null node)) (hash -1 :type fixnum)) ; 一度計算したハッシュ値をキャッシュしておく ;; ノードのハッシュ値算出 (defun sxhash-node (node) (if (null node) (sxhash nil) (with-slots (hash) node (when (= -1 hash) ;; キャッシュされていない場合だけ再帰的に計算を行う (setf hash (logxor (sxhash (node-label node)) (* (sxhash-node (node-child node)) 7) (* (sxhash-node (node-sibling node)) 13)))) hash)))
この方法は手軽かつ高速なのだけど、フィールドが一つ余分に必要になるのが難点。
キーセットのサイズが大きくなってくると若干気になりだす...。
そこで、O(1)でハッシュ値を算出可能な別の方法も候補に挙げておく。
こっちは若干遅い(多分)けど、余分なフィールドが不要。
;; 補助関数 ;; オブジェクトのアドレス(ポインタの値)を取得する (defun get-obj-address (obj) #+SBCL (sb-kernel:get-lisp-obj-address obj) ; SBCLのみ対応 #-SBCL (error "error")) ;; 三回のハッシュ値計算(sxhash呼び出し)でノードのハッシュ値を求める方法 ;; - 子供や兄弟の構造が同一なら、既に共有されている(ポインタの値が等しい)はずなので、中身を見る必要はない (defun sxhash-node (node) (if (null node) #.(sxhash nil) (logxor (sxhash (node-label node)) ; ラベルのハッシュ値 (* 7 (sxhash (get-obj-address (node-child node)))) ; 最初の子供へのポインタのハッシュ値 (* 13 (sxhash (get-obj-address (node-sibling node))))))) ; 最初の兄弟へのポインタのハッシュ値
おそらくこれで大丈夫なはず。
※ logxorとか*7とか*13とかの、ハッシュ値の計算方法自体が適切か(均一にバラつかせることが可能か)どうか、という問題はあるけど
ただし、GCによってオブジェクトのポインタの値が変わってしまうような言語では、危険なので実用上は使えない。
(おそらく大抵のCommon Lisp処理系は無理？)
この方法を使うとしたらC++で、かな。
// 特に意味はないけど、C++版も載せてみる。 int node_hash (node* n) { if(n==NULL) return hash(0); else return hash(n->label)^(hash(n->child)*7)^(hash(n->sibling)*13); }
UNF : Unicode正規化ライブラリ
UNFという名前*1で、C++でUnicode正規化を行うライブラリを実装 (ver 0.0.1)。
ついでに、それを利用したRuby拡張ライブラリも作成。
C++やRubyで使える、軽くて高速なUnicode正規化ライブラリは、一年以上前から欲しい(作りたい)と思っていたので、作り終えてみると少し人心地ついた感じがする。
特徴(?)
計時
他のUnicode正規化ライブラリなどと処理速度を比較。
参考までに。
対象テキスト:
正規化対象テキストにはhamの時にも用いた青空文庫の作家別書籍とYahoo!ブログのカテゴリ別ブログ記事を使用。
※ 以下で使われているrubyスクリプトに関しては、上のリンク先を参照
# 青空文庫から夏目漱石の作品を取得 $ ruby -Ku download.rb http://www.aozora.gr.jp/index_pages/person148.html souseki $ ls souseki/ | wc -l 88 $ cat souseki/* > souseki.txt $ head -2 /tmp/souseki.txt 公園の片隅に通りがかりの人を相手に演説をしている者がある。向うから来た釜形の尖った帽子を被ずいて古ぼけた外套を猫背に着た爺さんがそこへ歩みを佇めて演説者を見る。演説者はぴたりと演説をやめてつかつかとこの村夫子のたたずめる前に出て来る。二人の視線がひたと行き当る。演説者は濁りたる田舎調子にて御前はカーライルじゃないかと問う。いかにもわしはカーライルじゃと村夫子が答える。チェルシーの哲人と人が言囃すのは御前の事かと問う。なるほど世間ではわしの事をチェルシーの哲人と云うようじゃ。セージと云うは鳥の名だに、人間のセージとは珍らしいなと演説者はからからと笑う。村夫子はなるほど猫も杓子も同じ人間じゃのにことさらに哲人などと異名をつけるのは、あれは鳥じゃと渾名すると同じようなものだのう。人間はやはり当り前の人間で善かりそうなものだのに。と答えてこれもからからと笑う。 $ ls -lh souseki.txt -rw-r--r-- 1 user user 9.3M 2010-08-20 19:34 souseki.txt # Yahoo!ブログから"ビジネスと経済"カテゴリに属する記事を取得 $ mkdir keizai $ ruby -Ku download_yahoo_blog.rb ビジネスと経済 keizai $ ls keizai/ | wc -l 2331 $ cat keizai/* > keizai.txt $ head keizai.txt ブログ素材−わ〜い♪その２♪−顔文字 お持ち帰りはコメント等をよろしくお願いいたします♪ﾐ★(*^▽ﾟ)v 直リンクではなくＰＣに落としてお使いくださいませ♪( *＾艸＾) トラブルを避ける為、二次配布はお断りいたします♪(*_ _)ﾍﾟｺﾘ 使用は転載元よりお願いいたします♪ n.e.oプレミアムジンジャーエール…♪ 皆さま♪ハロハロ〜♪ 暑さ…ハンパじゃないですね〜〜〜♪（;´▽｀A`` $ ls -lh keizai.txt -rw-r--r-- 1 user user 3.3M 2010-08-20 19:41 keizai.txt
計時結果:
上述のファイルの各行*3に対して、正規化を施し、終了までの時間を計測した結果。
計時に用いたプログラムは、末尾に掲載。
java.text.Normalizerはコンスタントに良好な結果を出している*4。
unfは全体的にそれよりは劣っているが悪くもなく、keizei.txtのNFKCに関して云えば、この中で最速となっている。
unf-rubyはC++のchar*型からRubyのString型に変換するコストが掛かるためか、いずれもunfの結果に0.07〜0.10秒を足したくらいの処理時間となっている。
計時用プログラムと実行例
計時に用いた各プログラムとその実行例。
unf-0.0.1:
$ g++ -v gcc version 4.4.3 (Ubuntu 4.4.3-4ubuntu5) $ tar zxvf unf-0.0.1.tar.gz $ cd unf-0.0.1 $ make $ bin/unf-time < souseki.txt = read: == 33072 lines == average(line length): 293 byte = time: == NFD : 0.157628 sec == NFC : 0.089492 sec == NFKD: 0.16303 sec == NFKC: 0.091775 sec DONE
unf-ruby-0.0.1:
$ ruby -v ruby 1.8.7 (2010-01-10 patchlevel 249) [i486-linux] $ tar zxvf unf-ruby-0.0.1.tar.gz $ cd unf-ruby-0.0.1 $ ruby extconf.rb $ make $ sudo make install $ ruby unf-time.rb souseki.txt # unf-time.rbの中身は後述 nfd: 0.224087 sec nfc: 0.153629 sec nfkd: 0.237982 sec nfkc: 0.157734 sec >|| >|ruby| # ファイル名: unf-time.rb $KCODE='u' require 'unf' Norm = UNF::Normalizer.new def norm_time(text, form) beg = Time.now text.each{|line| Norm.normalize(line,form) } puts "#{form}:\t#{Time.now-beg} sec" end text = open(ARGV[0]).read norm_time(text,:nfd) norm_time(text,:nfc) norm_time(text,:nfkd) norm_time(text,:nfkc)
java.text.Normalizer:
$ java -version java version "1.6.0_18" OpenJDK Runtime Environment (IcedTea6 1.8.1) (6b18-1.8.1-0ubuntu1) OpenJDK Server VM (build 16.0-b13, mixed mode) $ javac -g:none Normalize.java # Normalize.javaの中身は後述 $ java -server Normalize < souseki.txt NFD: 0.067 sec NFC: 0.043 sec NFKD: 0.068 sec NFKC: 0.073 sec
// ファイル名: Normalize.java import java.text.Normalizer; import java.text.Normalizer.Form; import java.io.IOException; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; public class Normalize { public static void main(String args[]) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); ArrayList<String> lines = new ArrayList<String>(); for(String line=br.readLine(); line!=null; line=br.readLine()) lines.add(line); for(int i=0; i < 10; i++) { normalizeTime(lines, Normalizer.Form.NFC, false); normalizeTime(lines, Normalizer.Form.NFD, false); normalizeTime(lines, Normalizer.Form.NFKC, false); normalizeTime(lines, Normalizer.Form.NFKD, false); } normalizeTime(lines, Normalizer.Form.NFD, true); normalizeTime(lines, Normalizer.Form.NFC, true); normalizeTime(lines, Normalizer.Form.NFKD, true); normalizeTime(lines, Normalizer.Form.NFKC, true); } private static void normalizeTime(ArrayList<String> lines, Normalizer.Form form, boolean print) { long beg_t = System.currentTimeMillis(); for(String line : lines) Normalizer.normalize(line, form).length(); long end_t = System.currentTimeMillis(); if(print) System.out.println(form+":\t"+(end_t-beg_t)/1000d+" sec "); } }
Ruby-GLib2:
$ sudo apt-get install libglib2-ruby $ ruby glib2-time.rb souseki.txt # glib2-time.rbの中身は後述 nfd: 0.791289 sec nfc: 1.055483 sec nfkd: 0.777088 sec nfkc: 1.028141 sec
# ファイル名: glib2-time.rb $KCODE='u' require 'glib2' def norm_time(text, form, name) beg = Time.now text.each{|line| GLib::UTF8.normalize(line, form) } puts "#{name}:\t#{Time.now-beg} sec" end text = open(ARGV[0]).read norm_time(text, GLib::NormalizeMode::NFD, :nfd) norm_time(text, GLib::NormalizeMode::NFC, :nfc) norm_time(text, GLib::NormalizeMode::NFKD, :nfkd) norm_time(text, GLib::NormalizeMode::NFKC, :nfkc)
senna-nfkc:
sennaで使われているnfkc。
デフォルトでは、独自に拡張した正規化処理を行うようなので、それを抑止してコンパイル。
使い方がいまいち分かっていないので不適切な可能性がある...。
$ sudo apt-get install libicu-dev # sennaがnfkc.c(NFKC正規化用ソースファイル)を自動生成するのに必要 $ tar zxvf senna-1.1.5.tar.gz $ cd senna-1.1.5 $ cd util/unicode $ ruby nfkc.rb -s -c # 独自拡張を抑止して、NFKC正規化用ソースファイルを生成 $ cp nfkc.c ../../lib/ $ cd ../../ $ ./configure $ make $ g++ -O2 -o senna-nfkc-time senna-nfkc-time.cc lib/*.o `mecab-config --libs` # senna-nfkc-time.ccの中身は後述 $ ./senna-nfkc-time < souseki.txt Elapsed: 0.18836 sec
// ファイル名: senna-nfkc-time.cc // 以下、型が定義されていないというエラーが出たので、それらしいものを自前で定義 typedef unsigned size_t; typedef unsigned uint_least8_t; typedef short int16_t; typedef long long int64_t; #include "config.h" #include "senna.h" #include "lib/str.h" #include <iostream> #include <string> #include <vector> #include <cstring> #include <sys/time.h> inline double gettime(){ timeval tv; gettimeofday(&tv,NULL); return static_cast<double>(tv.tv_sec)+static_cast<double>(tv.tv_usec)/1000000.0; } int main(int argc, char** argv) { std::string line; std::vector<std::string> lines; while(std::getline(std::cin, line)) lines.push_back(line); double beg_t = gettime(); for(unsigned i=0; i < lines.size(); i++) sen_nstr* psn = sen_nstr_open(lines[i].data(), lines[i].size(), sen_enc_utf8, 0); std::cerr << "Elapsed: " << gettime()-beg_t << " sec" << std::endl; return 0; }
*1:Unicode Normalization Formsの略
*2:実装を一通り終え、このテストにはパスした段階で、大量テキストに対してJavaのUnicode正規化メソッドを適用した結果と比べてみたところ、数は多くないが相違点(バグ)がいくつか見つかったので、NormalizationTest.txt内のテストを網羅するだけでは、完全ではないよう
*3:IOの影響を除外するために、全ての行はあらかじめメモリ上に読み込んでおく
*4:ちなみに、java.text.Normalizerは何故かNFKCの場合だけ、テキストサイズが大きくなると性能が顕著に劣化していた。例えば、10MB程度のテキストを投げると、結果が返ってこない感じとなる
ham: 文字NグラムとバイトNグラム
ham(0.0.2)。
Nグラムベースのベイジアンフィルタ。
必要な分だけ実装してサクッと終わらせたかったけど、いくつか試したことが出てきたのでもう少し続ける。
UTF-8以外の文字コード
hamは0.0.1ではUTF-8にのみ対応し、その文字Nグラム(N〜Mグラム)*1を素性として扱っていた。
0.0.2では、それ以外にバイトNグラムも扱えるように拡張してみた*2。
この方法だと文字コードごとに個別に対応する必要がないのが楽。
以下は、そのバイトNグラムと文字Nグラムとの比較結果。
比較
バイトNグラムと文字Nグラムの比較。
まずは比較用データの準備。
※ データ取得スクリプト(download.rb,download_yahoo_blog.rb,half_cp.rb)及びその詳細に関しては前回を参照のこと
#################### ## 青空文庫データ ## # ルートディレクトリ作成 $ mkdir book $ cd book # データダウンロード $ ruby -Ku download.rb http://www.aozora.gr.jp/index_pages/person1154.html kishida_kunio $ ruby -Ku download.rb http://www.aozora.gr.jp/index_pages/person183.html makino_shinniti $ ruby -Ku download.rb http://www.aozora.gr.jp/index_pages/person76.html okamoto_kanoko $ ruby -Ku download.rb http://www.aozora.gr.jp/index_pages/person154.html tanaka_koutarou # 文字Nグラム用ディレクトリ作成 $ mkdir -p {learn,test}_data/{ham,spam} # 学習/評価用データ作成 $ ruby half_cp.rb kishida_kunio learn_data/ham 0 # ham $ ruby half_cp.rb okamoto_kanoko learn_data/spam 0 # spam $ ruby half_cp.rb makino_shinniti learn_data/spam 0 # spam $ ruby half_cp.rb tanaka_koutarou learn_data/spam 0 # spam $ ruby half_cp.rb kishida_kunio test_data/ham 1 # ham $ ruby half_cp.rb okamoto_kanoko test_data/spam 1 # spam $ ruby half_cp.rb makino_shinniti test_data/spam 1 # spam $ ruby half_cp.rb tanaka_koutarou test_data/spam 1 # spam # バイトNグラム用ディレクトリ作成 # ※ バイトNグラム用の文字コードにはShift_JISを使うことにする $ mkdir -p sjis_{learn,test}_data/{ham,spam} # 文字コード変換 $ for f in {learn,test}_data/*/*; do nkf -s $f > sjis_${f}; done # $ ls *_data/ learn_data/: ham spam test_data/: ham spam sjis_learn_data/: ham spam sjis_test_data/: ham spam $ cd .. ######################## ## Yahoo!ブログデータ ## # ルートディレクトリ作成 $ mkdir blog $ cd blog # データダウンロード $ mkdir keizai bunka $ ruby -Ku download_yahoo_blog.rb ビジネスと経済 keizai # "ビジネスと経済"カテゴリ $ ruby -Ku download_yahoo_blog.rb 生活と文化 bunka # "生活と文化"カテゴリ # 文字Nグラム用ディレクトリ作成 $ mkdir -p {learn,test}_data/{ham,spam} # 学習/評価用データ作成 $ ruby half_cp.rb keizai learn_data/ham 0 $ ruby half_cp.rb bunka learn_data/spam 0 $ ruby half_cp.rb keizai test_data/ham 1 $ ruby half_cp.rb bunka test_data/spam 1 # バイトNグラム用ディレクトリ作成 $ mkdir -p sjis_{learn,test}_data/{ham,spam} # 文字コード変換 $ for f in {learn,test}_data/*/*; do nkf -s $f > sjis_${f}; done # $ ls *_data/ learn_data/: ham spam test_data/: ham spam sjis_learn_data/: ham spam sjis_test_data/: ham spam $ cd ..
学習と分類。
※ 0.0.1と0.0.2では、hampのprecision計算方法を若干変更したので、前回の結果とは異なっている
########## ## 学習 ## # 青空文庫: 文字2〜5グラム $ hamt book/learn_data 2 5 > book-char.txt $ hamc --lower-frequency-limit=4 book-char.idx < book-char.txt # 青空文庫: バイト2〜10グラム $ hamt book/sjis_learn_data 2 10 > book-octet.txt $ hamc --lower-frequency-limit=4 book-octet.idx < book-octets.txt # Yahoo!ブログ: 文字2〜5グラム $ hamt blog/learn_data 2 5 > blog-char.txt $ hamc --lower-frequency-limit=4 blog-char.idx < blog-char.txt # Yahoo!ブログ: バイト2〜10グラム $ hamt --octet blog/sjis_learn_data 2 10 > blog-octet.txt $ hamc --lower-frequency-limit=4 blog-octet.idx < blog-octet.txt # 素性定義サイズ $ ls -lh *.txt -rw-r--r-- 1 user user 61M 2010-07-29 00:56 blog-char.txt -rw-r--r-- 1 user user 196M 2010-07-29 00:56 blog-octet.txt # バイトN〜Mグラムの方が、範囲(M-N)が広い分、サイズが大きい -rw-r--r-- 1 user user 100M 2010-07-29 00:55 book-char.txt -rw-r--r-- 1 user user 376M 2010-07-29 00:55 book-octet.txt # こっちも。大体三倍ちょっとくらい。 $ wc -l *.txt 2052870 blog-char.txt # 205万行 7696562 blog-octet.txt # 770万行 3308562 book-char.txt # 331万行 10361063 book-octet.txt # 1040万行 # インデックスサイズ $ ls -lh *.idx -rw-r--r-- 1 user user 2.0M 2010-07-29 00:50 blog-char.idx -rw-r--r-- 1 user user 4.5M 2010-07-29 00:52 blog-octet.idx # 低頻度素性を切り捨てているので、文字Nグラムとあまり差がない -rw-r--r-- 1 user user 3.0M 2010-07-29 00:39 book-char.idx -rw-r--r-- 1 user user 1.4M 2010-07-29 00:40 book-octet.idx # こっちは文字Nグラムよりも小さい ########## ## 分類 ## # 青空文庫 $ hamp book-char.idx book/test_data # 文字Nグラム In 'book/test_data/ham', 204 files were classified as HAM (total 234 files) In 'book/test_data/spam', 154 files were classified as SPAM (total 154 files) precision: 1.0 recall : 0.871794871794872 f-measure: 0.931506849315069 # 93.2% $ hamp book-octet.idx book/sjis_test_data # バイトNグラム In 'book/sjis_test_data/ham', 209 files were classified as HAM (total 234 files) In 'book/sjis_test_data/spam', 154 files were classified as SPAM (total 154 files) precision: 1.0 recall : 0.893162393162393 f-measure: 0.943566591422122 # 94.4% # Yahoo!カテゴリ $ hamp blog-char.idx blog/test_data # 文字Nグラム In 'blog/test_data/ham', 1058 files were classified as HAM (total 1221 files) In 'blog/test_data/spam', 962 files were classified as SPAM (total 1689 files) precision: 0.592717086834734 recall : 0.866502866502866 f-measure: 0.703925482368596 # 70.3% $ hamp blog-octet.idx blog/sjis_test_data # バイトNグラム In 'blog/sjis_test_data/ham', 1020 files were classified as HAM (total 1221 files) In 'blog/sjis_test_data/spam', 1003 files were classified as SPAM (total 1689 files) precision: 0.5978898007034 recall : 0.835380835380835 f-measure: 0.696959344038265 # 69.7%
上の結果では、分類性能的にはバイトNグラムと文字Nグラムの間にほとんど違いはない。
バイトNグラムの方が素性定義ファイルが大きくなるのは難点*3だけど、汎用性を考えるとバイトNグラムに統一してしまっても良いかもしれない*4。
*1:UTF-8の文字N〜Mグラム取り出しに関してはここも参照
*2:これに関連して変更したのは入力テキスト群から素性を取り出す処理を担当している'hamt.cc'のみ。素性抽出後は、文字NグラムもバイトNグラムも同様に扱われる。
*3:加えて云うなら、バイトN〜Mグラムは、そのMを適切に決定するのが難しいという問題もあるように思う。例えば、Mを12とした場合でも、(平均的な日本語テキストの場合)asciiテキストなら文字12個分、Shift_JISなら文字6個分、UTF-8なら文字4個分、といったように文字のエンコーディングによって、情報量が変化してしまう。Mをある程度機械的に適切に設定する仕組みが必要かな。
*4:でもそうするとユーザが人手で素性定義ファイルを弄れなくなるか...
ham: 分類性能評価的なもの
hamの分類性能評価的なもの。
そんなに本格的なことは行わない。
hamでは、基本的に『Practical Common Lisp』にて説明されているスパムフィルタリングの方法(ベイジアンフィルタの一種)をそのまま使わせてもらっている。
このベイジアンフィルタによる分類ロジック自体は、それなりの性能を有するということを前提とし、(hamの)実際の実装上の問題により性能が大幅に悪化していることがないか、ということの確認を行うのが今回の趣旨。
大きな懸念点は以下の二つ:
- 素性にNグラムを使っていることにより、性能が大幅に悪化していることがないか
- プログラムのバグにより、性能が大幅に悪化していることがないか
本当は、いくつかの実装方法を比較/検討でもして、性能が最も良いのを採用するようにした方がいいのだろうが*1、前回も書いたように二値分類器が急遽必要(かつそこまで時間を掛けたくない)なので、分類性能が酷く悪くなければ良しとする。
評価1: サイズが大きいテキストの分類
一つ目。
青空文庫から取得した作家別の作品(テキスト)群の分類を行う(作家Aの作品かどうかの判定)。
まずはデータ準備。
作品取得用スクリプトとその実行。
# ファイル名: download.rb # # 青空文庫の作家別作品リストページから、 # その作家の公開中作品を全てダウンロードする # # ダウンロードテキストからは、以下の項目が除外されている # - ヘッダ部分 # -- 著者名 # -- 作品名 # - 本文 # -- HTMLタグ # -- ルビ # - フッタ部分編 # -- 作品情報 # -- 入力者情報 # -- その他 require 'rubygems' require 'kconv' require 'hpricot' require 'open-uri' require 'uri' if ARGV.size != 2 puts "Usage: ruby -Ku download.rb <作家別作品リストページURL> <保存ディレクトリ>" exit 1 end PersonURL = ARGV[0] SaveDir = ARGV[1] `mkdir -p #{SaveDir}` open(PersonURL) do |root| root_doc = Hpricot(Kconv.toutf8(root.read)) (root_doc/"ol > li").each do |li| next if li.at(:a).nil? title = li.at(:a).inner_html puts "= #{title}" book_uri = root.base_uri.merge(li.at(:a)[:href]) open(book_uri) do |book| book_doc = Hpricot(Kconv.toutf8(book.read)) (book_doc/:a).each do |a| if (a[:href]||'') =~ /\/files\/.+html$/ xhtml_uri = book.base_uri.merge(a[:href]) puts " == #{xhtml_uri}" begin filename = xhtml_uri.path.split("/")[-1].sub(/html$/,'txt') text = Hpricot(Kconv.toutf8(open(xhtml_uri).read)).at('div.main_text').inner_html open("#{SaveDir}/#{filename}",'w'){|f| f.write text.gsub(/<(rp|rt)>.*?<\/\1>/,'').gsub(/<.*?>/,'').gsub(/[\r\n]+/m,"\n") } break rescue => ex # 作品xhtmlの構造にはいくつか種類があり # <div class="main_text">を含まないものの場合は、nilエラーがでる。 # # 取得数が若干減るだけで特に問題はないので、スルーする puts " == #{ex.class}: #{ex.message}" end end end end end end
# 作家別作品ダウンロード # 対象となる作家は、作品数が適度に多い人の中から、てきとうに選択 $ ruby -Ku download.rb http://www.aozora.gr.jp/index_pages/person1154.html kishida_kunio $ ruby -Ku download.rb http://www.aozora.gr.jp/index_pages/person183.html makino_shinniti $ ruby -Ku download.rb http://www.aozora.gr.jp/index_pages/person76.html okamoto_kanoko $ ruby -Ku download.rb http://www.aozora.gr.jp/index_pages/person154.html tanaka_koutarou # 作品数 $ ls kishida_kunio | wc -l # 岸田 国士 ※ この人をham、それ以外をspamとする 468 $ ls makino_shinniti | wc -l # 牧野 信一 77 $ ls okamoto_kanoko | wc -l # 岡本 かの子 102 $ ls tanaka_koutarou | wc -l # 田中 貢太郎 131 # ファイルサイズ $ ls -lh kishida_kunio | head 合計 6.7M -rw-r--r-- 1 user user 11K 2010-07-27 02:40 43579_17337.txt -rw-r--r-- 1 user user 17K 2010-07-27 02:40 43580_17339.txt -rw-r--r-- 1 user user 5.2K 2010-07-27 02:40 43581_17340.txt -rw-r--r-- 1 user user 9.4K 2010-07-27 02:40 43582_17341.txt -rw-r--r-- 1 user user 3.6K 2010-07-27 02:40 43593_17335.txt -rw-r--r-- 1 user user 14K 2010-07-27 02:40 43594_17336.txt -rw-r--r-- 1 user user 27K 2010-07-27 02:40 43595_17338.txt -rw-r--r-- 1 user user 7.5K 2010-07-27 02:40 44303_21829.txt -rw-r--r-- 1 user user 16K 2010-07-27 02:39 44304_21827.txt $ ls -lh makino_shinniti | head 合計 2.7M -rw-r--r-- 1 user user 42K 2010-07-27 02:40 1890_19617.txt -rw-r--r-- 1 user user 12K 2010-07-27 02:40 1891_7611.txt -rw-r--r-- 1 user user 42K 2010-07-27 02:40 1892_7609.txt -rw-r--r-- 1 user user 12K 2010-07-27 02:40 1893_7615.txt -rw-r--r-- 1 user user 5.6K 2010-07-27 02:40 1895_22534.txt -rw-r--r-- 1 user user 2.6K 2010-07-27 02:40 45207_28593.txt -rw-r--r-- 1 user user 39K 2010-07-27 02:40 45214_18527.txt -rw-r--r-- 1 user user 48K 2010-07-27 02:40 45216_23057.txt -rw-r--r-- 1 user user 62K 2010-07-27 02:40 45217_23162.txt # 中身 $ head -5 kishida_kunio/44304_21827.txt 一代の人気女優、ド・リュジイ嬢は、給料の問題で、作者にも金を払はなければならないと云ふことを聞いて、「何だつて。一体作者なんて云ふものを、なしにするわけには行かないかね」と、やつつけた。ラ・カメラニイ夫人もまた、オペラ座の化粧部屋に納つて、「作者なんぞゐるうちは、芝居の繁昌するわけはない」と宣言した。それが、仏蘭西のことである。しかも、そんなに旧いことではない。 モリエール、マリヴォオを先輩と仰ぐ仏蘭西劇作家である。それくらゐのことを云はれても腹は立てまい。まして、相手は男に非ず。たゞ、さう云はれながらも、書いたものが舞台に上り、舞台に上つたものが相当の金になり、金にならずとも、いくらか見てくれ手があればまだいゝのであるが、実際さうなるまでの手数が大変である。先づ脚本を書く、勿論傑作である。成る可くなら原稿はタイプライタアで打つ。人に打たせるなら、それは大抵、若い女だ。批評の悪からう筈はない。原稿は、自分で持つて行くよりも「彼女」に持つて行かせた方がいゝ。なぜなら、劇場の門番は、おほかた無名の天才に対して冷酷だからである。反感さへ持つてゐるらしい。「これをどうぞ」「今、大将は忙しいんだがなあ」「こつちは別に急ぎませんから」門番はにやりと笑ふのである。四十日経つと、返事を聞きに行くのである。勿論、原稿を返して貰ひに行くのと同じことである。「まだ見てなさうですが、もつとお預りして置きますか、それとも持つてお帰りになりますか」――持つて帰りますと云ふ元気ありや。「わが原稿は眠れり」――無名作家の嘆声である。脚本の原稿は劇場に持ち込むときまつてゐる。雑誌社なぞでは受けつけてくれない。（ミュッセは大方その戯曲を舞台に掛けないつもりで雑誌に発表した） 「あゝ、××さんですか、お作を拝見しました。結構だと思ひますが、あの第三幕ですがね」劇場主の注文が出る。
コメントにもある通り「岸田国士」をhamとして、それ以外の人をspamとして扱うことにする(つまり与えられた作品の著者が岸田国士かどうかを判定する)。
次は、学習用データと評価用データの作成。
# ファイル名: half_cp.rb # # ディレクトリ内のファイルのコピーを行うスクリプト # 引数に応じて、偶数番目か奇数番目かのどちらかのファイルだけをコピーする # ※ 学習用と評価用に、ファイルを振り分けるために使用する if ARGV.size != 3 puts "Usage: ruby half_cp.rb <コピー元ディレクトリ> <コピー先ディレクトリ> <0 or 1. 0なら偶数番目, 1なら奇数番目のファイルがコピーされる>" exit 1 end FROM_DIR = ARGV[0] TO_DIR = ARGV[1] n = ARGV[2].to_i `mkdir -p #{TO_DIR}` Dir.glob("#{FROM_DIR}/*") do |path| name = path.split("/")[-1] if (n+=1)%2==1 open(path){|fin| open("#{TO_DIR}/#{name}",'w'){|fout| fout.write fin.read } } end end
# 学習用データ用意 $ mkdir learn_data $ ruby half_cp.rb kishida_kunio learn_data/ham 0 # ham $ ruby half_cp.rb okamoto_kanoko learn_data/spam 0 # spam $ ruby half_cp.rb makino_shinniti learn_data/spam 0 # spam $ ruby half_cp.rb tanaka_koutarou learn_data/spam 0 # spam $ ls learn_data/ham | wc -l 234 $ du -hs learn_data/ham 3.4M learn_data/ham $ ls learn_data/spam/ | wc -l 156 $ du -hs learn_data/spam 3.7M learn_data/spam # 評価用データ用意 $ mkdir test_data $ ruby half_cp.rb kishida_kunio test_data/ham 1 # ham $ ruby half_cp.rb okamoto_kanoko test_data/spam 1 # spam $ ruby half_cp.rb makino_shinniti test_data/spam 1 # spam $ ruby half_cp.rb tanaka_koutarou test_data/spam 1 # spam
学習。
## 作成 # バイグラム $ hamt learn_data 2 2 2>/dev/null | hamc --lower-frequency-limit=5 book-2-2-5.idx 2>/dev/null # 1〜4グラム $ hamt learn_data 1 4 2>/dev/null | hamc --lower-frequency-limit=5 book-2-4-5.idx 2>/dev/null # 3〜6グラム hamt learn_data 3 6 2>/dev/null | hamc --lower-frequency-limit=5 book-3-6-5.idx 2>/dev/null ## サイズ $ ls -lh *.idx -rw-r--r-- 1 user user 434K 2010-07-27 03:10 book-2-2-5.idx -rw-r--r-- 1 user user 1.9M 2010-07-27 03:11 book-1-4-5.idx -rw-r--r-- 1 user user 2.2M 2010-07-27 03:25 book-3-6-5.idx ## $ hamt learn_data 2 6 2>/dev/null | head 000000ea 0000009c ==TOTAL== 00000001 00000000 が同じ卓 00000000 00000001 、寝呆けて 00000000 00000002 からそう 00000000 00000001 焼火 00000001 00000000 容を細 00000001 00000000 まふつてい 00000000 00000001 安府では五 0000000e 00000002 の日常 00000001 00000000 の母がゐ
分類。
## hamとspamの境界スコアがデフォルト(0.5)の場合 # バイグラム $ hamp book-2-2-5.idx test_data In 'test_data/ham', 173 fil〜es were classified as HAM (total 234 files) In 'test_data/spam', 154 files were classified as SPAM (total 154 files) precision: 1.0 recall : 0.739316239316239 f-measure: 0.85012285012285 # 85.0% # 1〜4グラム $ hamp book-1-4-5.idx test_data In 'test_data/ham', 201 files were classified as HAM (total 234 files) In 'test_data/spam', 154 files were classified as SPAM (total 154 files) precision: 1.0 recall : 0.858974358974359 f-measure: 0.924137931034483 # 92.4% # 3〜6グラム $ hamp book-3-6-5.idx test_data In 'test_data/ham', 213 files were classified as HAM (total 234 files) In 'test_data/spam', 153 files were classified as SPAM (total 154 files) precision: 0.992916818016709 recall : 0.91025641025641 f-measure: 0.949791521890201 # 95.0% ## 境界スコアを最適(に近い)ものに設定した場合 ## hamをspamとして分類してしまうケースが多いようなので、hamの範囲を広げる # バイグラム $ hamp --min-spam-score=0.9 book-2-2-5.idx test_data In 'test_data/ham', 214 files were classified as HAM (total 234 files) In 'test_data/spam', 151 files were classified as SPAM (total 154 files) precision: 0.979143145760295 recall : 0.914529914529915 f-measure: 0.945734209544581 # 94.6% # 1〜4グラム $ hamp --min-spam-score=0.9 book-1-4-5.idx test_data In 'test_data/ham', 223 files were classified as HAM (total 234 files) In 'test_data/spam', 149 files were classified as SPAM (total 154 files) precision: 0.967053390403244 recall : 0.952991452991453 f-measure: 0.959970928607369 # 96.0% # 3〜6グラム $ hamp --min-spam-score=0.9 book-3-6-5.idx test_data In 'test_data/ham', 227 files were classified as HAM (total 234 files) In 'test_data/spam', 147 files were classified as SPAM (total 154 files)ruby half_cp.rb keizai learn_data/ham 0 precision: 0.955241009946442 recall : 0.97008547008547 f-measure: 0.96260601387818 # 96.3% ## $ head -5 kishida_kunio/44304_21827.txt | ham book-3-6-5.idx 0.092976 HAM
グラムの範囲と分類境界スコアを適切に設定すれば、それなりに分類できる感じ。
評価2: サイズが小さいテキストの分類
二つ目。
Yahoo!ブログの記事カテゴリを利用し、'ビジネスと経済'と'生活と文化'へのブログ記事の分類を行う。
データ取得:
# ファイル名: download_yahoo_blog.rb # # Yahoo!ブログから、引数で渡された大カテゴリに属する新着ブログ記事を取得する require 'open-uri' require 'rubygems' require 'hpricot' require 'kconv' require 'rss' require 'cgi' def each_category_id (category_name) open("http://blogs.yahoo.co.jp/FRONT/cat.html"){|top| doc = Hpricot(Kconv.toutf8(top.read)) (doc/"h2 > a").each do |a| if a.inner_html == category_name pdoc = a.parent.next_sibling while pdoc.name == 'dl' (pdoc/"dd a").each do |dd_a| category_id = dd_a[:href].scan(/cid=(\d+)/)[0][0] yield category_id end pdoc = pdoc.next_sibling end break end end } end def each_rss_item(rss_url) open(rss_url) do |f| RSS::Parser.parse(f.read).items.each do |item| yield item end end end if ARGV.size != 2 puts "Usage: ruby -Ku download_yahoo_blog.rb <大カテゴリ> <保存ディレクトリ>" exit 1 end CategoryName = ARGV[0] SaveDir = ARGV[1] # カテゴリに属する新着記事を書いたブロガー(のRSS)を取得する puts "= root category: #{CategoryName}" user_rss_set = Array.new each_category_id(CategoryName) do |cid| puts " == category: #{cid}" each_rss_item("http://blogs.yahoo.co.jp/DIRECTORY/rss.xml?cid=#{cid}") do |item| user_rss_set << item.source.url.sub(/^.+\*/,'') end end # 上で取得したブロガーの最新ブログ記事を取得/保存する # ※ カテゴリAに属する新着記事を書いたブロガーの他の記事もカテゴリAに属しているはず、と仮定している puts "" puts "= user: #{user_rss_set.uniq.size}" user_rss_set.uniq.each_with_index do |rss_url,i| puts " == #{i}" each_rss_item(rss_url) do |item| id = item.link.sub(/^.+http:\/\/blogs.yahoo.co.jp\//,'').gsub('/','_') title = CGI.unescapeHTML(item.title) desc = CGI.unescapeHTML(item.description).gsub(/ /,' ').gsub(/<[^>]*>/,'').gsub(/[\r\n]+/,"\n").gsub(/[ \t]/,' ') # puts " === #{id}" open("#{SaveDir}/#{id}",'w'){|f| f.write "#{title}\n#{desc}" } end end
# 評価1とは別のディレクトリ ## データダウンロード # "ビジネスと経済"のブログ記事を取得 $ mkdir keizai $ ruby -Ku download_yahoo_blog.rb ビジネスと経済 keizai # "生活と文化"のブログ記事を取得 $ mkdir bunka $ ruby -Ku download_yahoo_blog.rb 生活と文化 bunka # 個数とサイズ $ ls keizai | wc -l 2342 $ du -hs keizai 9.7M keizai $ ls bunka | wc -l 1175 $ du -hs bunka 4.9M bunka ## 学習/評価データ用意 # 学習 $ ruby half_cp.rb keizai learn_data/ham 0 $ ruby half_cp.rb bunka learn_data/spam 0 # 評価 $ ruby half_cp.rb keizai test_data/ham 1 $ ruby half_cp.rb bunka test_data/spam 1
学習。
## 作成 # バイグラム $ hamt learn_data 2 2 2>/dev/null | hamc blog-2-2-2.idx 2>/dev/null # 1〜3グラム $ hamt learn_data 1 3 2>/dev/null | hamc blog-1-3-2.idx 2>/dev/null # 2〜6グラム $ hamt learn_data 2 6 2>/dev/null | hamc blog-2-6-2.idx 2>/dev/null ## サイズ $ ls -lh *.idx -rw-r--r-- 1 user user 550K 2010-07-27 05:49 book-2-2-2.idx -rw-r--r-- 1 user user 1.7M 2010-07-27 05:50 book-1-3-2.idx -rw-r--r-- 1 user user 4.0M 2010-07-27 05:50 book-2-6-2.idx
分類。
# バイグラム $ hamp blog-2-2-2.idx test_data In 'test_data/ham', 821 files were classified as HAM (total 1171 files) In 'test_data/spam', 485 files were classified as SPAM (total 587 files) precision: 0.801383177383603 recall : 0.701110162254483 f-measure: 0.747900672436617 # 74.8% # 1〜3グラム $ hamp blog-1-3-2.idx test_data In 'test_data/ham', 835 files were classified as HAM (total 1171 files) In 'test_data/spam', 487 files were classified as SPAM (total 587 files) precision: 0.807161853946924 recall : 0.713065755764304 f-measure: 0.757201716022128 # 75.7% # 2〜6グラム $ hamp blog-2-6-2.idx test_data In 'test_data/ham', 917 files were classified as HAM (total 1171 files) In 'test_data/spam', 442 files were classified as SPAM (total 587 files) precision: 0.76020161734508 recall : 0.783091374893254 f-measure: 0.771476748377406 # 77.1% ## 境界スコアを変えると、途端に偏りが激しくなる $ hamp --min-spam-score=0.55 blog-2-6-2.idx test_data In 'test_data/ham', 1146 files were classified as HAM (total 1171 files) In 'test_data/spam', 91 files were classified as SPAM (total 587 files) precision: 0.536651248725587 recall : 0.97865072587532 f-measure: 0.693187421266993 $ hamp --min-spam-score=0.45 blog-2-6-2.idx test_data In 'test_data/ham', 351 files were classified as HAM (total 1171 files) In 'test_data/spam', 576 files were classified as SPAM (total 587 files) precision: 0.941160617217406 recall : 0.299743808710504 f-measure: 0.454679767625332
学習用/評価用データの質があまり良くないこと*2もあってか、精度等は(青空文庫の場合に比べ)かなり下がっている。
一応、7割強は正しく分類*3できているが、この数字が良いのか悪いのかは不明。
すごく悪いということはなさそうだけど。
結論
取り合えず冒頭で書いたような問題はなさそう。
余裕があれば既存のパッケージなども調べてみても良いけど、学習データに気をつければhamでも十分間に合いそうに思う。
