namazu-dev(ring)

[Satoru Takabayashi <satoru-t@xxxxxxxxxxxxxxxxxx>]

小関 吉則 (KOSEKI Yoshinori) <kose@xxxxxxxxxxxxxxxxxx> wrote:

>1. 複数の INDEX をマージする機能  (mknmzの後処理)

この機能は TODO です。:-)

[namazu-dev 1088] に書いた「インデックスを効率よく作成する方
法」と深く関わるので、じっくり方法を検討してから実装したいと
思います。

[namazu-dev 1088]より
|  * 文書をどんどん読み込んでいって、$ON_MEMORY_MAX の値 (標
|    準では 5 MB) を越えた時点で NMZ.{i,ii,w,wi} を作業ファイ
|    ルに書き出す
|  * もし、すでに作業ファイルが存在するときは単純に連結し、連
|    結地点を配列に記録しておく
|    - それぞれ別個のファイルにした方が単純だが、数が多くなる
|      とマージするときにファイルの open/close の管理が面倒
|  * 最後にまとめてマージする (k-way merging)
|
|       初回 ooooo (長さOMM)
|        2回 ooooo
|        3回 ooooo
|        4回 ooooo
|         :  
|    n/OMM回 ooooo
|       最後 ooooooooooooooooooooooooo...oo (長さn)
|
|  * 効率が良い: O(n * log n) のアルゴリズム

この、「すでに作業ファイルが存在するときは単純に連結し、連結
地点を配列に記録しておく」方法はよく考えると駄目な気がしてき
ました。ディスクの seek が頻繁に発生するでしょうから。

ディスクの seek には時間がかかるので、できるだけ線形にデータ
を読み込める方法で実装したいと思います。とすると、単純に別個
のファイルに分割した方がよさそうです。分割したファイルは単純
に先頭から線形に読み込めばいいわけですから。

マージする単純な方法は、 2つのペアを 1つにまとめていく方法で
す。直感的にはこんな感じ:

  oooooooooooooooo
  oooooooo
  oooo
  oo
  o

`o' が 1つのファイルを表わします。最初の行の o の数を n とす
ると、 o の数の合計は 2n - 1になります。しかし、それぞれの行
では n に比例した処理を要するので全体の計算量は n * log_2 n 
になります。直感的にはこんな感じ:

  x x x x x x x x x x x x x x x x
  xx  xx  xx  xx  xx  xx  xx  xx
   xxxx    xxxx    xxxx    xxxx
     xxxxxxxx        xxxxxxxx
         xxxxxxxxxxxxxxxx

GNU の sort コマンドでは 2つのペアではなく、複数個 (16個) を
まとめてマージしています (logの底が大きくなる)。しかし、 
Namazu では処理すべきファイルが多いので、たくさんの unit を
まとめてマージするのは難しいです。同時に open できるファイル
数の制限に引っ掛かってしまうでしょうから。


>2. 複数の INDEX から検索できる機能 (namzuの機能)

こちらは大昔から実現しています。:)

-- Satoru Takabayashi