べき分布する整数データの圧縮方法
今更ながら、Faster and Smaller N-Gram Language Modelsを読んでみました。
この記事については、すでにACL2011論文「Faster and Smaller N-Gram Language Models」を読んだ - EchizenBlog-Zwei やN-gram 言語モデルを圧縮するには - やた＠はてな日記で紹介されているので、自分が興味を持ったところを少しだけ。
上の紹介記事でも言及されているように、この論文では N-gram を [token, context] の形で格納しています。token と context はどちらも ID。この形でソートすると、token も context も前のデータとの差が小さくなるので、差分を取ると小さい数が多い「べき分布」になるから圧縮しやすくていいよね、という話（だと思います）。
その圧縮方法というのは次の通りです。
ある k を決め、基数を 2^k とする。 (対象の数字をその基数で表した時の桁数-1) だけ 0 を置き、続けて 1個の 1 を置く。 (対象の数字をその基数で表した時の桁数*k) ビットを使って、対象の数字を 2進数で表す。
これってちょっとピンと来ないと思いませんか？ 私は最初ピンと来ませんでした。なので、自分でいくつか例を作ってみました。
まず k=3 で基数が 2^3=8 の場合。
対象の数字が 6 の場合、8進数で表すと 6 で、桁数は 1。 1-1=0個の 0 を置き（=置かない）、1個の 1 を置く。 3ビットを使って対象の数字 (6) を 2進数で表すと 110。 合わせて 1 110 になる。 13 の場合、8進数で表すと 15 で、桁数は 2。 2-1=1個の 0 を置き、1個の 1 を置く。 3×2=6ビットを使って対象の数字 (13、8進数で 15) を 2進数で表すと 001101。 合わせて 01 001101 になる。 93 の場合、8進数で表すと 135 で、桁数は 3。 3-1=2個の 0 を置き、1個の 1 を置く。 3*3=9ビットを使って対象の数字(93、8進数で 135) を 2進数で表すと 001011101。 合わせて 001 001011101 になる。
この表現方法では、ビット列には「桁数部」と「数字部」があります。「桁数部」は、その基数で表した時の桁数-1 の 0 と 1個の 1。「数字部」は 2進数で表した数字、ただし k の倍数になるように上の桁に 0 をパディングしたもの。
k を小さくすると桁数部が増え、その代わりに数字部のパディングが減ります。大きくするとその逆になります。k をいくつにするのがいいかはデータによりますが、小さいところに固まっているほど小さめの k が、大きい数まで分布しているほど大きめの k がいい結果になります。
たとえば、上の例で k=4 としてみます。基数は 16 になります。
6 の場合、16進数で表すと 6 で、桁数は 1。 1-1=0個の 0 を置き（=置かない）、1個の 1 を置く。 4ビットを使って対象の数字 (6) を 2進数で表すと 0110。 合わせて 1 0110 になる。 13 の場合、16進数で表すと d で、桁数は 1。 1-1=0個の 0 を置き（=置かない）、1個の 1 を置く。 4ビットを使って対象の数字 (13、16進数で d) を 2進数で表すと 1101。 合わせて 1 1101 になる。 93 の場合、16進数で表すと 5d で、桁数は 2。 2-1=1個の 0 を置き、1個の 1 を置く。 4*2=8ビットを使って対象の数字(93、16進数で 5d) を 2進数で表すと 01011101。 合わせて 01 01011101 になる。
k=3 で 6, 13, 93 を表した時はそれぞれ 4, 8, 12 ビットだったのに対し、k=4 にすると5, 5, 10 ビットになっています。このように、k を変えると数字によってビット数が増えたり減ったりします。
数字ごとに必要なビット数は、(対象の数字をその基数で表した時の桁数)×(1+k) になります。k=3 の時にはビット数が 4の倍数で、k=4 の時には 5の倍数になっているのがわかると思います。
どのぐらいの k が最適かを調べるための Perl ワンライナーを書いてみました。
perl -F/\\t/ -nale 'BEGIN{$max_k=15;} $b=sprintf("%b", $F[0]); $blen=length($b); for $k(1..$max_k) { $digits=int(($blen-1)/$k)+1; $bits=$digits*(1+$k); $bits_all[$k]+=($bits*$F[1]); } END{ print "k\tbits"; print "$_\t$bits_all[$_]" for 1..$max_k; }' < input.txt > output.txt
入力は、
0 1272601 1 641833 2 393896 3 289281 4 223322 5 179366 6 154094 7 133384 8 112478 9 101182 10 91299 11 81311 12 74106 ...
のような、数字とその出現回数をタブ区切りで並べたものです。
出力は、
k bits 1 128217222 2 104358054 3 100212788 4 100983695 5 104240334 6 107949016 7 113001552 8 118689750 9 124995330 10 131009912 11 136483572 12 141806821 13 147092792 14 153086880 15 159444240
のように、それぞれの k を使った場合に必要となるビット数です。
このデータの場合、k=3 が最適だということです。
ここからは論文の内容から離れますが、これを実際に使うことを考えるなら、実装の楽さということも一つの要素になるでしょう。この方法では k=7 の時にデータがバイト単位になるため、処理が非常に簡単になります。対象となる数の上限が決まっているなら、決め打ちができるため、さらに簡単に書けます。ここで挙げた例のような場合では、最適な k=3 の場合と k=7 の場合の差が 1.13倍程度と大きくないため、考える余地があるでしょう。
たとえば、k=7 として、数の上限が 2^21-1=2097151 以下の場合は、次のように書けます。
int Encode(int x, unsigned char *p) { int len = 0; if (x < (1 << 7)) { p[0] = (1 << 7) | x; len = 1; } else if (x < (1 << 14)) { p[0] = (1 << 6) | (x >> 8); p[1] = x; len = 2; } else if (x < (1 << 21)) { p[0] = (1 << 5) | (x >> 16); p[1] = x >> 8; p[2] = x; len = 3; } return len; } int Decode(int *x, unsigned char *p) { int len = 0; if (p[0] & (1 << 7)) { *x = p[0] & ((1 << 7) - 1); len = 1; } else if (p[0] & (1 << 6)) { *x = ((p[0] & ((1 << 6) - 1)) << 8) | p[1]; len = 2; } else if (p[0] & (1 << 5)) { *x = ((p[0] & ((1 << 5) - 1)) << 16) | (p[1] << 8) | p[2]; len = 3; } return len; }
UTF-8 のエンコード・デコードに似ていますが、最初のバイトかどうかという情報を持たなくてもよいため、UTF-8 よりは効率的です。UTF-8では 127 まで 1バイト、2047 まで 2バイト、65535 まで 3バイトなのに対し、k=7 のこの方式では 127まで 1バイト、16383 まで 2バイト、2097151 まで 3バイトで表せることになります。
