---------------------------------------------------------------------

next up previous contents
Next: 実験結果 Up: システムの実装 Previous: ルールの評価

---------------------------------------------------------------------

計算量の削減

3.2のPAD図を見れば分かるように、本システムの実行時間のオー ダーは O(グループ数×解析子数×候補文字列数×全文書数 gif ) である。 ここで問題となるのは、候補文字列数である。 単純にシステムを実装した場合、候補文字列集合 S が巨大になりすぎて、実 行時間が極端にかかってしまうことになる。 例えば、解析子として ./atom 3 (空白または改行で区切られる文字列が アトム)を作用させた場合、72個のファイル(590KB) に対して2751個の候補、751 個のファイル(3,240KB)に対して10741個の候補が抽出される。 それぞれグループ数は 6、18 であるので、この中の大部分は無意味な候補とい うことになる。

本システムでは頻度を解析するため、ルールとして導出されうる候補は、多くの 文書に出現していると考えられる。 逆に、ある1つの文書だけに出現している候補からは、ルール導出は期待できな い。 そこで本システムでは、n個の文書を持つグループに対して、 tex2html_wrap1564 回より多く出現した文字列のみを妥当な候補とし、それ以外は考慮しない ようになっている。 その結果、先の2つの文書集合に対して、候補数がそれぞれ 521個(19%)、1544 個(14%) に押えられた。

---------------------------------------------------------------------

吉田 誠一のホームページ に戻る。
Copyright(C) Seiichi Yoshida (comet@aerith.net). All rights reserved.
Sat Mar 8 05:59:11 JST 1997