計算量の削減

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

計算量の削減

図 3.2のPAD図を見れば分かるように、本システムの実行時間のオーダーは O(グループ数×解析子数×候補文字列数×全文書数 ) である。ここで問題となるのは、候補文字列数である。単純にシステムを実装した場合、候補文字列集合 S が巨大になりすぎて、実行時間が極端にかかってしまうことになる。例えば、解析子として ./atom 3 (空白または改行で区切られる文字列がアトム)を作用させた場合、72個のファイル(590KB) に対して2751個の候補、751 個のファイル(3,240KB)に対して10741個の候補が抽出される。それぞれグループ数は 6、18 であるので、この中の大部分は無意味な候補ということになる。
本システムでは頻度を解析するため、ルールとして導出されうる候補は、多くの文書に出現していると考えられる。逆に、ある1つの文書だけに出現している候補からは、ルール導出は期待できない。そこで本システムでは、n個の文書を持つグループに対して、回より多く出現した文字列のみを妥当な候補とし、それ以外は考慮しないようになっている。その結果、先の2つの文書集合に対して、候補数がそれぞれ 521個(19%)、1544 個(14%) に押えられた。