はじめに
第2回で、
圧縮の目的
中規模から大規模な索引の場合、
この場合、
圧縮転置リストのディスクからの読み込み時間+復元処理時間 < 非圧縮転置リストのディスクからの読み込み処理
これは、
転置索引の圧縮
転置索引は辞書と転置リストからなるため、
辞書の圧縮
辞書はタームのリストであるため、
たとえば、
転置リストの圧縮
転置リストは文書ID、
この整数列ですが、
このように、
転置リストの圧縮
ここでは、
通常、
以下に、
- unary符号
unary符号は最もシンプルであり、
整数値x (> 0) をx-1個の"1"ビットと末尾の"0"ビットで表現する符号化方法です。 たとえば、
x=10の場合は "1111111110" となります。 - gamma符号、
delta符号 gamma符号は、
整数値x (> 0) を2e + d (e = log2x, 0 ≤ d < 2e) で表現し、 e+1をunary符号で、 dをeビットバイナリ符号で表現する符号化方法です。 たとえば、
x=10の場合、 log210 = 3となるため、 3+1=4をunary表現すると"1110"、 10-23=2を3ビットバイナリで表現すると"010"となるため、 それらを足した"1110" + "010" = "1110010" となります。 delta符号は、
gamma符号でunaryで符号化する部分をgamma符号で置き換えたものとなります。 - variable-byte符号
(byte-aligned符号) variable-byte符号は、
その名の通り"複数のバイト"で符号化する方法となります。各バイトの下位7ビットを使って数値を表現し、 その整数が次のバイトも含むかどうかを最上位ビット (1かどうか) で表す符号化方法です。つまり、 1バイトでは27ビット、 2バイトでは214ビット、 3バイトでは221ビットまで表現できることになります。 たとえば、
x=10の場合、 x < 27 なので1バイトで表現できるので、 "10001010" となります。 x=1030の場合は、
x < 211なので2バイトで表現でき、
"00000100:10000110" となります。
delta符号、
また、
次に、
- golomn符号、
rice符号 golomn符号は、
パラメータm (≥ 1) を用いて、 整数値x (> 0) を、 b*q+r+1 (0 ≤ r < b) で表現し、 q+1をunary符号、 rを以下に従って符号化する方法です。 e = log2b
(切り上げ)、 g = 2e - bとし、 0 ≤ r < gの場合はrをe-1ビットのバイナリ符号で、 g≤ r < bの場合はr+gをe ビットのバイナリ符号で表します。 たとえば、
x=10の場合、 10 = 5・ 1 + 4 + 1 (q=1、 r=4)となり、 - e = log25 ≒ 3
g=2e - b= 23 - 5 = 3 (< r)
となるため、
q+1 (2) のunary符号 + r (4) +g (3) のe (3) ビットバイナリ符号で"10:111" となります。 - e = log25 ≒ 3
golomu符号はm=1の時はunary符号となり、
なぜ圧縮できるのか?
前のセクションで、
4種類の数字
- 1:00
- 2:01
- 3:10
- 4:11
このとき、
- 2(ビット)
* 4 (個) =8ビット
で表現できることになります。たとえば、
- 1:0
- 2:100
- 3:101
- 4:110
このとき、
- 1(ビット)
*3 (個) +3 (ビット) *1 (個) = 6ビット
で表現できます。上の場合と比べて2ビットも小さく同じ数値列を表現することができました。圧縮でやっていることもこれと全く同じになります。
ポスティングリストの整数列はある分布により並んでいると考えることができます
たとえば、
- lx = 1 + 2log2x
ビットで表現できることになります。
整数xの符号長がわかると、
- lx = -log Pr[x]
Pr[x] = 2-lx
Prgamma[x] ≒ 2-(1+2logx)
= 1/2x2
となり、
他の符号化手法も同様に暗黙的に確率分布を持ち、
近年の圧縮手法
上記で紹介した以外にも、
検索エンジンでは検索速度が一番重要である一方、
- Simple9
(S9) Simple9では、
32ビットに可能な限りの整数を格納することで圧縮を実現します。このため、 32ビットを上位4ビットと下位28ビットに分け、 上位4ビットには何ビットの整数を何個格納するのかを表す9通りのステータスのどれかを、 下位28ビットには実際のデータを格納します。 28ビットの具体的な分割パターンは、
28ビット*1個、 14ビット*2個、 9ビット*3個、 7ビット*4個、 5ビット*5個、 4ビット*7個、 3ビット*9個、 2ビット*14個、 1ビット*28個の9通りとなります。たとえば、 7つの整数列がすべて16以下であるなら、 4ビット*7個のパターンが選択され、 7つの整数を32ビットで表すことができます。符号化を行う場合は、 整数列を先頭から見ていきどのパターンに当てはまるかを判定します。 復号はこの9通りのビットオペレーションをハードコードしておき、
上位4ビットからパターンを読み込み該当のコードを実行します。復号が高速に実行できる理由としては、 ビットオペレーションをハードコードしておくことや、 固定長ビットの復号が分岐なしに行えることなどが挙げられます。 - PForDelta
PForDeltaは近年Zukowskiら
(参考文献[4]) により提案された非常に注目された手法です。その後、 Yanら (参考文献[5]) により改良されました。改良案は有効であると考えられ今後の広まりが予想されますので、 今回はこの改良案を紹介します ([5]ではこの改良案をNewPFDと呼んでいます)。 PForDeltaの考え方はS9と同様であり、
複数の整数を固定長ビット配列に押し込むという方法ですが、 より多くの整数を詰め込むところが違っています。 まず、
整数列を32の倍数 (ここでは128) 個ごとに分割し、 各ブロックの全体の90%の値が収まるビット数を求めます。そして、 bビット * 128個の配列 (配列a) に各値を詰め込みます。もちろん10%程度はbビットに収まりきらないため、 これらは例外として扱います。例外である数値は、 128個の配列には下位bビットのみを保存し、 上位ビットは別配列 (配列b) に格納することにより対応します。 また、
どの部分が例外であったかも別の配列(配列c)に格納しておく必要があります。さらに、 配列bと配列cはS9などの別の符号化手法により圧縮することができます。図1に具体的な数値例におけるPForDeltaの符号化方法を示します。 図1 PForDeltaによる符号化例 PForDeltaの特徴は、
復号が非常に高速な点です。[3]の論文で紹介されている復号方法をリスト1に示します。復号は2段階で行われ、 2つのループが実行されます。1つめのループでは、 bの値に基づき各整数を復号し、 2つ目のループでは、 例外に対して上位ビットの補完をします (リスト1は、 オリジナルのPForDeltaであるため、 LOOP2内の処理内容が異なります)。これら各ループ内の処理は独立であるためコンパイラによるloop-unrollingが期待でき、 また、 ループ内で分岐が一切発生しないためSuper-Scalar CPUにおけるパイプラインがフラッシュされずに実行されるため、 非常に高速に実行されます。 この処理を1つのループ
(1段階) で行うことは可能ですが、 上述のことから得られる利益の方が大きいため2段階で実行します。 リスト1 int Decompress<ANY>( int n, int b, ANY *__
restrict__ output, void *__ restrict__ input, ANY *__ restrict__ exception, int *next_ exception ) { int next, code[n], cur = *next_ exception; UNPACK[b](code, input, n); /* bit-unpack the values */ /* LOOP1: decode regardless */ for(int i=0; i<n; i++) { output[i] = DECODE(code[i]); } /* LOOP2: patch it up */ for(int i=1; cur < n; i++, cur = next) { next = cur + output[cur] + 1; output[cur] = exception[-i]; } *next_ exception = cur - n; return i; }
各符号化方法について
Zhangらは参考文献[6]で、
- rice > PForDelta > S9 > variable-byte符号
となり、
- PForDelta > S9 > variable-byte符号 > rice符号
という結果となっています.
PForDeltaやS9がvariable-byte符号よりもどちらも優っていますが、
まとめ
転置リストにおけるさまざまな圧縮方法を紹介しました。
各符号化方法はそれぞれトレードオフの関係にあるため、
- 【参考文献】
- [1] Justin Zobel, Alistair Moffat, Inverted files for text search engines, ACM Computing Surveys (CSUR), 2006
- [2] Ian H. Witten, Alistair Moffat, Timothy C. Bell, Managing Gigabytes: Compressing and Indexing Documents and Images, Morgan Kaufmann Publisher, 1999
- [3] C. D. Manning, P. Raghavan, H. Schutze, Introduction to Information Retrieval, Cambridge University Press, 2008
- [4] M. Zukowski , S. Heman , N. Nes , P. Boncz, Super-Scalar RAM-CPU Cache Compression, Proceedings of the 22nd International Conference on Data Engineering, 2006
- [5]H. Yan, S. Ding, T. Suel, Inverted index compression and query processing with optimized document ordering, , Proceeding of the 17th international conference on World Wide Web, 2009
- [6] J. Zhang , X. Long , T. Suel, Performance of compressed inverted list caching in search engines, Proceeding of the 17th international conference on World Wide Web, 2008