5章は、インデックス圧縮について。
主に、辞書の圧縮と、ポスティングの圧縮に焦点をあてる。
ターム統計
そもそもどの程度のタームがあるのか。ターム数に上限はあるのか。
以下に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
を保持してあげるとメモリが節約できる。
