独立行政法人問題でさらばパトリシア

さて、FreyaSX/0.99.13 から、デフォルトでは形態素辞書を使わないことにしました。 これは、実は昨年の開発当初から気付いていたのですが、これまでのFreya(SX)では、 例えば「行政」とか「法人」で検索ができない(ことがある)という問題があったから です。この問題は、形態素辞書を使うことによって生じます。

それでも、これまで一年間実際にDeleGateのMLアーカイブの検索用に使ってきて、 特に問題を感じることもなかったので実用上構わないんじゃないか、ということと、 形態素辞書を使うことによってたぶん大きなメリットがあり、使わないと罰があたる？ のではないかと思い込んでいたので、気にしないことにしていました（黙ってて ゴメンなさい:p）。

もともと、昨年の 0.99.10 から形態素辞書無しでも構わないようになっては いました。これは移植・インストール面や非日本語用の利用の観点からそうした ものだったと思いますが、その時点では(通常の環境で)日本語文書に対して辞書の 使用を省くという利用法は考えてなかったような気がします。

今月、0.99.12で（2ギガバイト超の）比較的大きめな索引への対応を行ったのですが、 その索引作成テストは高速化のために、この辞書をはずして行いました。その際、 辞書を使わなければ索引の作成が30%程度高速になることがわかりました。 一方、その場合の索引ファイルのサイズ増大は、日本語文書に対しても10%程度の ようでした（日本語を含まない場合は不変）。 そんなわけで、辞書のメリットは、デメリットより小さいだろうということで、 この際公式リリースでも辞書を切っちゃえということになったのでした。

辞書問題について若干詳しく

この問題は、単語辞書を使って単語の単位で索引を作ると、文字列(複合語)の途中に ある検索語への検索がヒットしたりしなかったりする状況が起こるというものです。 （この分野に素人なので、正確にはどう表現するのか知りません）

この問題の原因は、形態素辞書を用いて単語を切り出して作られる索引の内容に あります。例えば、(オリジナル)Freyaでは「独立行政法人」は、「行政法」が ICOT辞書にあるため、「独立」「立行」「行政法」「人」のように分解されて索引化 されます。このため、このように分解された文字列を「行政」でひっかけるには 「行政*」で検索する必要があり、「法人」ではひっかけようがありませんでした。 （検索時の工夫で、たとえば「*法人」のように検索をできるようにすれば、対処 できるだろうとは思います。このような検索もいずれ入れたいとは思っていますが、 実装は多少複雑になるでしょうし、今回この問題の解決のためには、やる気が 起こりません）

一方、辞書を使わないことにすると、「独立行政法人」は「独立」「立行」「行政」 「政法」「法人」と、一様に分解されます。これで検索時のモレは無くなるわけ ですが、単語数・参照数ともに増加するので、索引が大きくなることは想像される 通りです。ですが、憶えている限りでは、昨年 0.99.10 の時点で、辞書が オプショナルになった時点で、辞書を使った場合とそうでない場合の索引ファイル サイズの差を気にかけた記憶がありません。

それで、今回改めて、実際に日本語版DeleGate-MLの13100件の記事を索引化して 比較みたところ、辞書を使う場合に較べて、使わない場合の索引ファイル群の サイズの増大は、たかだか10%強程度でした。一方、索引の作成速度は、25%ほど 高速化しました。これも結構魅力的ですが、なにより、検索にモレが無くなる ことに対する代償としては、まったく安価だと言えましょう。

あるいは、昨年の時点では索引ファイルの大きさを気にかけていて、10%強と いうのは深刻な増大だと思ったのかも知れません。しかし、現時点で思うのは、 そもそもこのディスクがじゃぶじゃぶの時代にFreyaSXが作る索引ファイルの 大きさが気になるような状況はまずないだろうということです。2倍とか3倍とか なら気にもなりますが、10%程度は無視できる程度でしょう。 検索性能も多少低下すると思いますが、深刻な違いも出てくるとも思えません。

さて、今回の測定の詳細は最後に添付しますが、要約すると次のようになります。 処理速度は、MacOSX 10.2 + 1GHz PPC G4 (iMac) でのものです。

  (1) 辞書有りでの索引作成
  ・処理速度は、約150メール/秒、95万語片/秒
　・元データ 1KBあたり、平均 187語片に分解
  ・作成される索引ファイルのサイズは元データとほぼ同等

  (2) 辞書無しでの索引作成
　・処理速度は、約200メール/秒、150万語片/秒
　・元データ 1KBあたり、平均 213語片に分解 (11%増大)
　・作成される索引ファイルは、元データより1割強の肥大
　・辞書有りの場合に較べて、約25%の処理時間短縮

FreyaSX と DeleGate の相互フィードバック

昨年の9月に 0.99.10 をリリースしてFreyaSXの開発は休眠状態に入り、一年以上 が過ぎていましたので、ソースを眺めながらFreyaSXの何がどうできているのか 感覚を取り戻すのに2,3日かかりました。オリジナルFreyaの部分についてよりも、 FreyaSXで自分で拡張した部分が思い出せない。。。

この間佐藤は、DeleGate v8 - v9 の開発に専念していました (updates)。 昨年9月以降は、まず、長年の懸案であった、バッファオーバフロー問題の 根本的・ほぼ完全な解決を行いました。その手始めに、DeleGate v8 を 従来の K&R C から、ANSI/ISO C/C++ に全面的に書き直したのですが、その際には、 FreyaSXでの C++ の経験が大いに役立ちました。

C++ への書換えから、バッファオーバフローの根絶まで、結局3ヶ月近くを要し ました。その後、DeleGate v9 の IPv6 対応やら、SSL関係の拡充やらで今年の 前半を終えました。最近では１ヶ月ばかり、フォームを使ったDeleGateの ビジュアル管理機能にのめっていました。これも10年来の懸案だったのですが、 FreyaSX での検索フォームの作成の経験が役立ちました。それを少し一般化した 形で、ちょとしたフォーム処理記述言語(もどき)を作ったので、これを FreyaSX にもフィードバックできると思います。

0.99.12 以降、今回の一連の開発作業は、FreyaSX-En フィードバックのほうに ドイツ方面から（はじめて）投稿のあった、

  [FreyaSX-En] FreyaSX problem with files > 2GB / compiling on AMD64
  29 Aug 2005 10:05:58 GMT Stefan Grothkopp

おわりに

形態素辞書の使用をやめると、日本語DeleGate-MLの例では、索引ファイルの サイズが1割強大きくなりますが、これはひきかえに高速化する索引作成速度と、 検索精度(というのかな？)の向上で、十分引き合っておつりが来ると思います。 検索速度にはほとんど影響がないと思いますし。

そういえば原作者の原田さんから昨年のFreyaSX開始時に頂いたメールの中で、 「形態素辞書を一切使わないものも作ってみたい」と書かれてました。 お墨付きですね:)

なにより、FreyaSX の最大のウリは、索引作成速度にあると思っています。自分 でも利用者としての立場から、find+grep みたいなノリで使えるインスタントな 簡便索引作成＋検索インターフェイスが欲しいと思っています。 既にFreyaSXは性能面では、find+grepとコンパラと言える索引作成速度です。 あとは、DeleGateのCGI経由で索引作成から検索までを、一連のフォームの中で できるようにすれば、このようなインスタントでアドホックな検索にツカエル と思います。

もちろん、コマンドライン・インターフェイスでも簡便にできると良いのですが、 コマンドラインでの日本語の扱いが非常に環境依存ですし、多少複雑な設定の 繰り返し使用にはフォームによるインターフェイスのほうが向いていると思い ますし、索引をリモートから検索できるという点ではHTTPベースが良いと思います。

今回の形態素辞書の(デフォルトでの使用の)廃止で、辞書を実現している 原田さん作のパトリシア木の処理コードを使用しないことになりました。自分と してはこの部分の移植にも、それなりに手間をかけもしたので、虚しい気も しないでもありません。ですが、これはまたこれで別の用途に活用できるかも 知れません。

また、この変更により若干ですが、検索の面にも影響があります。というのは、 単語辞書を使わないために、索引が単語の先頭から作られることがなくなり、 暗黙的に単語の先頭にマッチすることを期待した検索、特にカタカナ語の検索が、 余計なものをひっかけやすくなりました。そのため、0.99.13 で「＾カタカナ」 検索オペレータというのを導入しました。これについては、またあらためて 書きます。

性能測定の詳細

OS/CPU: MacOSX10.2 / PowerPC G4 1GHz
any2fdif: DeleGate/9.0.6-pre8
findex: FreyaSX/0.99.13

(0) 元データとFDIF
------------------

  % any2fdif
  Any2fdif on DeleGate/9.0.5-pre8 (October 11, 2005)

  % cd /tmp/mail-lists/delegate; ls */*|wc; time wc */*
   13170   13170   92358

→元データは13,170ファイル（メール）あります。

   1380816 4872868 67333860 total
   2.330u 5.510s 0:39.41 19.8%     0+0k 0+107io 0pf+0w

→全体で67メガバイト(平均で5Kバイト/メール)。

  % time any2fdif -q -b dgmlja -r /tmp/mail-lists/delegate
  ...
  Indexed: 13172 (with Author: 13170+0)
  18.110u 22.460s 1:07.31 60.2%   0+0k 0+774io 0pf+0w

→any2fdif は wc の2倍程度の速度です(^^)

  % ls -l bank/dgmlja
  -rw-r--r--  1 yutaka  wheel   3372032 12 Oct 16:09 dgmlja.desc
  -rw-r--r--  1 yutaka  wheel  46177080 12 Oct 16:09 dgmlja.fdif
  -rw-r--r--  1 yutaka  wheel   1014402 12 Oct 16:09 dgmlja.summ

★any2fdif の処理速度は、約200メール/秒、1Mバイト/秒
（やけにぴったりの数字ですが実測値です）

(1) 辞書有りでの索引作成
-------------------------

  % cd /tmp; mkdir bank; time findex -b dgmlja -cNBW=256 -D

→索引ファイルを /tmp/bank に作ります
→開始時の語バッファサイズを256K語に拡大します
（デフォルトの64Kだと、一時分割索引＋索引併合処理が加わって15%ほど処理時間増大）

  #00     73.735 ... Lex 42.1% ( 220734/ 524288) 42.9% coll.(4106136/9571751)
  #00     73.748 scanned  13172 docs ( 175/s)  8662311 words (115497/s).
  #00     73.755 found 220734 words ... build index
  #00     81.553 registered 8662311 words occurrences (9571751 registered).

→約220K語彙 × 8.6M回参照
  ...
  13172 Documents.
          91.428 Ctx literal=5802310 / position=8662311 (67.0%)

  ConTextFile    34649244 bank/dgmlja/dgmlja.ctx
  XMapFile          52688 bank/dgmlja/dgmlja.map
  DescFile        3372032 bank/dgmlja/dgmlja.dsc
  LexiconFile     4526468 bank/dgmlja/dgmlja.lex
  IndexFile      24341033 bank/dgmlja/dgmlja.idx
  SumFile         1014402 bank/dgmlja/dgmlja.sum
  NumFile          318944 bank/dgmlja/dgmlja.num
  total          68274811 7 files
  #### [dgmlja] bank/index.lst
  70.580u 9.060s 1:31.83 86.7%    0+0k 2+39io 0pf+0w

★辞書有り findex の処理速度は、約150メール/秒、95万語片/秒
★作成される索引群は約 68メガバイトで、元データとほぼ同等


(2) 辞書無しでの索引作成
-------------------------

  % cd /tmp; mkdir bank; time findex -b dgmlja -cNBW=256
  ..
  #00     47.901 ... Lex 42.3% ( 221601/ 524288) 54.2% coll.(5842521/10775390)
  #00     47.914 scanned  13172 docs ( 263/s)  9865950 words (197319/s).
  #00     47.920 found 221601 words ... build index
  #00     55.909 registered 9865950 words occurrences (10775390 registered).

→約200K語彙 × 10M回参照

  13172 Documents.
          67.183 Ctx literal=7467052 / position=9865950 (75.7%)
  ...
  ConTextFile    39463800 bank/dgmlja/dgmlja.ctx
  XMapFile          52688 bank/dgmlja/dgmlja.map
  DescFile        3372032 bank/dgmlja/dgmlja.dsc
  LexiconFile     4521269 bank/dgmlja/dgmlja.lex
  IndexFile      27624722 bank/dgmlja/dgmlja.idx
  SumFile         1014402 bank/dgmlja/dgmlja.sum
  NumFile          318944 bank/dgmlja/dgmlja.num
  total          76367857 7 files
  #### [dgmlja] bank/index.lst
  47.380u 9.870s 1:07.52 84.7%    0+0k 44+37io 0pf+0w

★辞書無し findex の処理速度は、約200メール/秒、150万語片/秒
（やけにぴったりの数字ですが実測値です）
★辞書有りの場合に較べて、約25%の処理時間短縮
★作成される索引群は約 76メガバイトで、元データより1割強の肥大