ロードトップ参照元逆検索検索ヘルプ

メールの検索について

過去1ヵ月分ぐらいのメールの検索をしたいことがよくある。 mh 形式で保存しているんだけれども、grep つかっても凄く遅い上にあんまりうまく見付けられない。

全文検索のシステムを構築してやれば良いと思うのだが、構築する時間が結構かかる上、Disk Space も結構取るみたいなので、導入をためらっている。

ここでは、全文検索のデータベースを構築しないで grep のようなツールでメールを検索することについていろいろ考えてみたい。

私が検索したと思うメールの数は、せいぜい 1万個ぐらいで、容量にして、たぶん数十 MB ぐらい。

( いまちょっと見たら、7200 個、85 MB、1547 K lineだった。)

最近の CPU や Disk はかなり速く、メインメモリもたくさんあるわけで、これぐらいの検索は 10秒以内で終ってもおかしくないように思える。

根拠:
1 回目に検索するときのボトルネックは Disk 性能だろう。最近の Disk では、30MB/sec 程度でるようなのだ。AT A66 以上に対応している 普通の Disk なら、最低でも 10MB/sec ぐらいは期待できる。
ちなみに 2.5inch ハードディスク上にある、 110MB ほどのファイルを cat してみたら、 8.5 秒ほどで終った(13MB/sec) 。

特に 2 回目からは、メモリに全部載っているかもしれない。この場合、1 秒以内に終ってもおかしくないように思える。

根拠: どうも、検索するときのボトルネックは CPU 性能ではなく、メモリ性能のようなのだ。どういうことかというと、最近の CPU では、キャッシュ性能は、メモリ性能より 1桁ぐらいは高く、少しぐらいの演算は問題にならないようにできるはずだと思うからだ。
別の CPU(Pentium III) で、8.6MB のファイルを cat してみた。 1回目は、15MB/sec だったが、2 回目は、146MB/sec だった。
例としてあまり適切ではないかもしれないが、100MB/sec 以上の性能で検索することは可能だと思われる。
というか、実際 grep で 40MB のファイルを検索したら、109MB/sec だった。 ( wc はそれより 2倍ぐらい遅い... コードが適当なんだろう)

検索が 1桁秒で終るのなら、全文検索いらないじゃんと思うのだが... 性能を維持しつつ、大幅に機能が拡張されていないとメールの検索に使えない。

欲しい機能としては、次のようなもの。

MIME に対応して、なおかつ添付ファイルの中まで検索できるもの
word のフォーマットに対応しているもの。
( 添付ファイルに word が入っていることが結構あって、これが一番欲しかったりする。)
バイナリフォーマットは検索しないこと。 ( ゴミ出されるとやっぱり困る。)

これだけの機能をサポートして、なおかつメモリ性能に比較できるだけのものってのは、はたして存在するのか...(ってたぶん存在しないよなぁ。)

Word 文書を Text に変換できるツールとして、catdoc がある。こういうツールは他にもあるのだが、catdoc には、漢字パッチが存在する。 ( patch は、fj.source に流れた次のもの )

    Subject: catdoc-0.91.4-2byte.patch
    Message-ID: <3A96A919.8EE8BDE6@yama-ga.com>

これのソースコードは、全部で 3000 行ぐらいしかない。いろいろいじれるかも知れない。

本当に速い高機能 grep を作るには..

ここからが本題かも知れない。
(こういうのが作りたいとは思っているんだけども、実際に作るのは面倒なんで、ずっとアイディアだけを眠らせていた。ここでアイディアを書いてみたい。)

前提が高機能であるから、検索エンジンとファイルのデコード部分は独立していないとたぶん作っていられない。

そして、それぞれの機能は、ある程度連続して動かないと i-cache や table などの静的データの d-cache の効率が悪くなったりするんじゃないかと思う。しかも粒度があまりに大きいと中間データが d-cache から溢れてしまい、余計なメモリトランザクションが発生し、性能が低下しそう。

というわけで、データを 10KB ぐらいに分割して、

    1. ファイルのデコードをする。
    2. 検索する

という機能が交互に動くってのが理想ではないだろうか。

交互に動かすわけで、スレッドライブラリを使うと割と楽に作れるかもしれない。

しかし、システムで提供されるスレッドライブラリを使って性能が維持できるかどうかは不安がある。

へたに、マルチプロセッサなマシンで並列に動いてくれると逆に性能が低下する。なぜなら、プロセッサ間でキャッシュは共有できず、キャッシュの性能を意識するようなプログラムは、1 プロセスで動いた方が速いから。

シングルプロセッサでも、カーネルでサポートされたスレッドだとスレッド切替えの際の性能が気になる。
( 100MB/sec での性能だと 10KB で 100us ということになる。スレッド切替えは、この1処理で 2 回おきる。許容できるスレッド切替え性能は、3us ぐらいかなぁ。)

ほとんどのファイルは、10KB もないので、通常は、ファイルを全部デコードして、それに対する検索というパターンになるはず。
スレッドを使うまでもないという気もする。

コード変換はどこでやるのか？

UNICODE 変換なんか相当重いと思う。それを全部の入力に対して行うのが適切かというとそうじゃないと思う。

やはり、検索する文字列を入力データに合わせるというのが正しいように思う。そうすることができれば、ファイルのデコード部分は単純にできる。

というわけで...

   SJIS
   EUC + JIS
   UTF-8

ぐらいにモードを分けるのが良いのかも知れない。

高機能化することによりどれぐらい遅くなるはずか。

遅くなる要素としては、

    d-cache から読んで来る。
    単純な コード変換をする。
    d-cache に書き込む

というシーケンスのみのように思う。

EUC か SJIS の場合は、コード変換自身が必要ないから、無視できるぐらい速いということになると思う。( .. というより無視できる構造になっていれば良いわけだ)

JIS の場合は、EUC に変換してということになりそうなんで、ちょっと遅くなりそう。どれぐらい遅くなるかは、これはシミュレーションしてみるべきかも知れない。

UNICODE の場合はどうか... たぶんこれを使うのは word の中身みるときとか限定されるように思う。word の中身がどうなっているか知らないが、なんとなく、JIS -> EUC 変換と大差ない性能になるんじゃないかという気もする。

NetBSD の pkg にある ja-grep を見てみた。これは、正規表現から正規表現 (を分解したトークン)に変換するタイプらしい。( = regcomp の動作のみを変えて漢字対応した。)
性能も確認したが、GNU grep とほぼ同じ性能のようだ。
.. というわけで、なにを作るにせよ、ja-grep の regex を使えばいいわけだ。 ( SJS, EUC にしか対応していないので、utf-8 に対応するには、改造しないといけないが、そんなに苦労しないと思う。)

ところで.. nkf は期待したより遅い。
13MB のファイルを EUC から JIS に変換する( write 先は /dev/null) のに、 3.6 秒。3.9MB/sec しか出ていない。
同じ条件で、ja-grep は、ほぼ 100MB/sec, cat は、ほぼ 45MB/sec ( CPU は CyrixIII 。cat が遅いのは、メモリcopy性能が低いせいだと思う。)
あと、-j ( なにもしないオプション) でも 16MB/sec

code 変換で nkf のコードを流用するのはかなり厳しいわけだ。 .. うーん。どうしようかな。

ここから先は、高速なJIS-EUCコード変換についてへ

どんな機能が必要か？(検索オプション)

あまりイメージできていないが、普通の全文検索システムが持っている機能は実現可能であって欲しい。

しぼり込み or AND 演算子

マッチしたファイルのリストを出力するオプションがあって、それを入力とすることができれば、実現できるように思う。

まあスクリプトで作れそうだから、 grep 自体の機能である必要はないかも知れないのだが...
実は MBOX フォーマットや添付ファイルなどに拡張したい。その場合は、スクリプトで作るのは面倒かも知れない。

あと、しぼり込んだ結果が、1万ファイルぐらいということを仮定すると grep 自体は、1 ファイル数十 us ということになりそうだから、スクリプトがボトルネックになる可能性がある。

行間をまたぐ文字列の検出

これはメールとかでは特に必要だけど、regex のオプションにあるみたいだから心配する必要はなさそう。

空白を含むパターンの検出

正規表現のパターンを生成してやればいいんだが、任意の正規表現からというのは難しいか..

near 演算子

ちゃんと作るのは面倒そうだが... どうせ適当でいいのだろう。
2つのパターンの間に100文字入っても良いとかそういうのでいいのかも。

その他のはなし

EUC か SJIS かを高速に判定するには。

ちょっと思いついたので書いてみる。
EUC コードでは、ひらがなのパターンは、2 バイト中上のバイトが 0xa4 カタカナの場合は、0xa5 になる。バイト列としてみたとき上位 4bit が 0xa のパターンはどれぐらいあるか...
総量 13MB のメールをサンプルにして頻度を見てみた。

                            EUC    SJIS
0xa0 - 0xaf の頻度          9.8 %  1.3 %
0x20 - 0x7f の頻度          78 %    80 %

お、明らかな差があるじゃん.. ってことで別のファイル 28MB

                            EUC    SJIS
0xa0 - 0xaf の頻度          11.1 %  1.2 %
0x20 - 0x7f の頻度          73 %    77 %

お、傾向がおなじだ。じゃあ 218 MB の別のファイル。

                            EUC    SJIS
0xa0 - 0xaf の頻度          3.5%   0.4 %
0x20 - 0x7f の頻度          91 %    92 %

頻度は 10 倍ぐらいあるが、絶対値で比較するのはちょっと無理か。

では、0x80 が立っているうち 0xa0 -0xaf はどれぐらいか。

データ１   51.8 %    8.3 %
データ２   46.2 %    6.2 %
データ３   48.7 %    7.6 %

確率としては、1/8 だから 12.5 % 。SJIS は確率よりかなり低いし、 EUC は、確率より相当高い率で 0xa0 - 0xaf が出現する。

確かさよりも、高速に判定したい場合。このアイディアは使えるかも知れない。

0x80 の bit が立っている数をカウントするのは高速にできる。データを 4 バイト単位でとってきて

    int data,*buf,i ...
    for (i=0; i< 255; i++)  {      
      data = *buf++;
      data &= ~0x80808080;
      data >>= 7;

      total += data;
    }
    real_total += (total >> 24) + ((total >> 16) & 0xff)
                   ((total >> 8) & 0xff) + (total & 0xff);

とかやればいいわけだ。

0xa0 - 0xaf の合計もそれよりは落ちるが... 高速なJIS-EUCコード変換についてでかいたのと同じ手法が使える。

    int data,*buf,i ...
    for (i=0; i< 255; i++)  {      
      data = *buf++;
      data = 0xf0f0f0f0;
      data ^= 0x50505050;  /* a -> f */
      data >>= 4;          /* 下位4bit にする */
      data += 0x01010101;  /* 1 を足す */
      data &= 0x0f0f0f0f;  /* 桁溢れを 1 にする。*/
      data >>= 3;
      total += data;
    }
    real_total += (total >> 24) + ((total >> 16) & 0xff)
                   ((total >> 8) & 0xff) + (total & 0xff);

なんか無駄がありそうだけども...まあいいや。

で、total が計算できるから、上の割合で 0xa0 - 0xaf の出現率がある値を越えたら EUC と判断する。

かなりいやなのは、適当なバイナリが SJIS と判断されてしまうこと。今は、これ以上追求しないことにする。

これぜんぜんダメだということが分かった。

あるブロック単位でやってみたら、誤判定率が 10% 近くになった。 ... というわけでこのアイディアだめ。

... でもなんか悔しいから 1 バイト単位の判定をもう少し追求。

     SJIS          EUC
82  1324959          0
81   517624          0
83   480625          0
93   123882          0
8e   112900          0
cc   105604      48649
8d    91722          0
8a    84486          0
8b    82146          0
97    79424          0
96    77813          0
95    76194          0
a2    75944     140626
8f    75437         0

なーんと。EUC は、0x80 - 0xa0 まで出現数 0 (あれ文字コードがないのか？) 逆に SJIS ではこのエリア上位を占める。じゃあここだ。 0x80 - 0xff の数に対する 0x80- 0x9f の割合を見ればよいわけだ。

(最終更新 Thu Mar 30 19:16:23 2006)