読者です 読者をやめる 読者になる 読者になる

IIR5章まとめ

5章は、インデックス圧縮について。

主に、辞書の圧縮と、ポスティングの圧縮に焦点をあてる。

ターム統計

そもそもどの程度のタームがあるのか。ターム数に上限はあるのか。

以下に2つの法則を挙げる。

ヒープの法則

ボキャブラリサイズを M、ターム数を Tとすると、以下の式が成立。

 $M=KT^\beta


したがって、ボキャブラリサイズにが大きくなるにつれてターム数も大きくなり続けるといえる。

ジップの法則

出現頻度がi番目に大きい要素が全体に占める割合が1/iに比例するという経験則。

以上の2つの法則から、圧縮の重要性が分かる。

辞書の圧縮

メモリに辞書を載せるには、圧縮が不可欠である。

辞書構造を順に見ていく。

fixed-width

以下の表を見てみよう。

タームが400000語あるとすると、メモリの使用量は以下のようになる。

(20+4+4)*400,000 = 11.2MB

これは以下の点が問題である。

  • 全てのタームに20バイト使用するわけではなく、無駄が多い。
  • 20バイトを超えるタームを扱うことができない。
Dictionary-as-a-string

タームをつなげて境界のポインタを保持する。

ターム長は平均8バイトなので、メモリの使用量は以下のようになる。

(4+4+3+8)*400,000 = 7.6MB

Dictionary as a string with blocking

k語ごとにポインタを保持する。(上図ではk=4)

ストリング中にターム長を保持。

k=4の場合だと0.5MBのメモリ節約となる。

ただし、kを大きくすると探索コストも大きくなるので、kは大きければよいというものではない。

Front coding

共通した接頭辞をまとめる。

8 a u t o m a t a 8 a u t o m a t e 9 a u t o m a t i c 10 a u t o m a t i o n

は、

8 a u t o m a t * a 1 ◇ e 2 ◇ i c 3 ◇ i o n

となる。

これで更に1.2MBのメモリ節約となる。

ポスティングの圧縮

ドキュメントidは20バイト。

しかし、ドキュメントidをそのまま保持するのではなく、ドキュメントid同士のを保持してあげるとより少ないbitで表現できる。

例えば、

283047 283154 283159 2832202

をそのまま保持するのではなく、その差である

107 5 43

を保持してあげるとメモリが節約できる。