Namazu-devel-ja(旧)

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

New data structure

備忘録を兼ねて。

ここ 1か月ほど Namazu 3.0 の開発を中断して Sary
<http://sary.namazu.org/> の開発に専念していました。

そろそろ Namazu の開発に戻らないといかんなあ、と考えていたと
ころ、Sary で使っているデータ構造 Suffix Array を用いれば、
インデックスの更新を劇的に速くできることに気づきました。

現在の Namazu: (インデックスの更新が遅い)

構造:

  辞書        文書IDのリスト
  ----------  -------------
  ashore      1 3 5 6
  burps       2 4 5 7 9 ...  
  epsilon     1 2 6
  retried     3
  telegraphs  7 8

構成ファイル:

  * NMZ.w  - 辞書 (NMZ.wi を用いて 2分探索できる)
  * NMZ.wi - NMZ.w にアクセスするためのインデックス
  * NMZ.i  - 文書IDのリスト
  * NMZ.ii - NMZ.i にアクセスするためのインデックス

なぜ更新が遅いのか?

  新しい文書を追加してインデックスを更新する際に、新しい単語と
  それに対応する文書IDのリストを既存のインデックスに挟み込んで
  全体を書き直す必要があるから。

  もし NMZ.wi? と NMZ.ii? が合計で 100 MB なら、文書を 1つ追加
  してインデックスを更新するだけで、 100 MB 分のファイルを書き
  換えないといけない。だから遅い。

新しいデータ構造:

構造:

  辞書        文書IDのリスト
  ----------  -------------
  ashore      1 3 4
  burps       2 4 5 7
  epsilon     1 2 6
  retried     3
  telegraphs  5 6

  あれれ、同じじゃないか!?

構成ファイル:

  * NMZ.w  - 辞書 (NMZ.wi を用いて 2分探索できる)
  * NMZ.wi - NMZ.w にアクセスするための Suffix Array (ここだけ違う)
  * NMZ.i  - 文書IDのリスト
  * NMZ.ii - NMZ.i にアクセスするためのインデックス

  新しいデータ構造では、NMZ.w へのアクセスに Suffix Array を用
  います。これまでと同じように NMZ.w は 2分探索で検索できます。
  NMZ.wi の大きさは、従来のそれと同じです。

なぜ更新を速くできるのか?

  新しい文書を追加してインデックスを更新する際には、新しい単語と
  それに対応する文書IDのリストを単純に既存のインデックスの末尾
  に追加します。そして、Suffix Array である NMZ.wi *だけ* を書
  き換えます。

  もし NMZ.wi? と NMZ.ii? が 100 MB だとしても、文書を 1つ追加
  してインデックスを更新する際には NMZ.wi (せいぜい 1MB) だけ
  を書き換えればいい。

  古いデータ構造では「新しい単語とそれに対応する文書IDのリスト
  を既存のインデックスに挟み込んで全体を書き直」すという複雑な
  処理が必要で、未だに微妙なバグが混入しているようですが、新し
  いデータ構造では更新が単純なのでそういった心配はありません。

なぜ NMZ.wi だけを書き換えればいいのか?

  「新しい単語とそれに対応する文書IDのリストを単純に既存のイ
  ンデックスの末尾に追加」すると、次のようなファイルができあ
  がります。見ての通り、辞書の並びが崩れてしまいます。

	    辞書        文書IDのリスト
	    ----------  -------------
	    ashore      1 3 4
	    burps       2 4 5 7
	    epsilon     1 2 6
	    retried     3
	    telegraphs  5 6
    追加→  ashore      8 9
    追加→  burps       8
    追加→  epsilon     9


  では、どうやって検索をすればいいのでしょうか? 簡単です。
  Suffix Array を用いれば、ソートされていない辞書でも 2分探索
  で検索できるのです。重複した単語のエントリは検索時にマージ
  します。

欠点:

  インデックスの更新を繰り返していくと、重複した単語のエントリ
  が増えていきます。 `of' のような頻出単語は特に顕著でしょう。
  例:

    辞書        文書IDのリスト
    ----------  -------------
     :
    of          1 3 4
    of          5 
    of          6 8
    of          9
     :

  注意: 実際の辞書はソートされていないが Suffix Array を通す
  と見かけ上、ソート済みに見える

  検索時には、これらの重複したエントリをマージする必要がありま
  す。これが欠点です。しかし、このコストはそれほど大きくないと
  思います。

  検索速度の低下が気になるようであれば、毎晩あるいは週に 1度と
  いった間隔で「インデックスの掃除 (全体をマージして並べ直す)」
  すればいいでしょう。この処理は Suffix Array を使って簡単に書
  けます。

実験:

  25万行、約3.5 MBの NMZ.w に対して Suffix Array を行単位で作
  成する。Celeron 500 MHz + 256 MB の計算機なら約 1秒強。

    % time mksary -ql NMZ.w
    1.09s user 0.03s system 91% cpu 1.22s total

  その他の処理を含めて、インデックスの更新は数秒でできそうです。
  この速度ならメールを取り込んだタイミングでどんどんインデック
  スを更新していっても平気でしょう。

結論:

  * 新しいデータ構造ではインデックスの更新が劇的に速くなる
  * ただし、更新を繰り返すにつれ検索の性能は徐々に遅くなる
  * 定期的に「インデックスの掃除」をすれば検索性能は回復する
  * 新しいデータ構造は扱いが単純なのでバグが混入しにくい
  * インデックスの大きさは今までのまま

p.s.
このアイディアはシャワーを浴びているときに突然、思いつきまし
た。馬車から降りるときに大発見をした、というポアンカレの逸話
に似ていますね。(僕の場合は大発見でもないが)

--
高林 哲 (Takabayashi, Satoru)
http://namazu.org/~satoru/