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

Javaで整数列圧縮(2)

Java

前回説明した可変バイトコード(Variable Byte Code)は、最小でも1バイトでしか圧縮できませんでした(以下では、VBCodeと表記します)。これは、1や2のような非常に小さな数値でも1バイト必要ということです。つまり、まだ無駄な部分があるのです。例えば、2進数で表現すると以下のようになります。

1 = 00000001
2 = 00000010
3 = 00000011
4 = 00000100
5 = 00000101
...

このとき、1や2の先頭の数ビットは、0しか表現していないため、無駄になります。つまり、うまくやれば、VBCodeよりも圧縮することができます。さて、どうするか?ビット単位で圧縮してやれば良いのです。ビット単位で圧縮する場合に有名な手法には、以下のようなものがあります。

  • Alpha Code(Unary Code) : 1進数コード
  • Gamma Code : γコード
  • Delta Code : δコード

今回は、この中で1進数コード(Alpha Code)とγコード(Gamma Code)について説明したいと思います。

さて、ビット単位のコードについて説明する前に、どこまで圧縮できるのか?という下界を見積もっておきましょう。コンピューターで表現するために、2進数で表現しますが、ある整数値X(> 0)を2進数で表現する時に必要な最小ビット数は、log(X)+1です*1*2。例えば、各整数値に必要なビット数は、以下のようになります。

log(2)   + 1  = 2ビット
log(4)   + 1  = 3ビット
log(8)   + 1  = 4ビット
log(16)  + 1  = 5ビット
...
log(2^n) + 1 = n + 1ビット

つまり、log(X)ビット以下では表現できないので、ここに限りなく近くなるようにすると良いことがわかります。このような状況の時、Gamma Codeは、log(X)の定数倍程度のビット数で表現できることが知られています。これは、最適なものの定数倍なので、効率は良い方です。ちなみに、Alpha Codeは、効率が悪いです。効率が悪いのにAlpha Codeを説明する理由は、Gamma Codeの一部でAlpha Codeを利用するからです。

さて、Alpha CodeとGamma Codeについて説明します。まず、整数値XのAlpha Codeは、0をX-1個出力した後に1を1個出力します。これだけです。実際の例を以下に示します。

1 = 1
2 = 01
3 = 001
4 = 0001
5 = 00001
...

簡単ですね。ただ、やってみるとわかりますが、2^32とかの整数値を表現するとえらいことになります。すでに書きましたが、Alpha Codeは、あまり効率の良い方法ではありません。

さて、Gamma Codeについて説明します。整数値Xを2進数で表現し、その最上位ビット(MSB)を取り除いた2進数(offset)の長さ(length)をAlpha Codeで表現し、その後ろにoffsetをつなげます。言葉で表現するとわかりにくいので、実例を示します。例えば55という数値のoffsetとlengthは、以下のようになります。

55 = 110111

offset = 10111
length = 5

このとき、lengthの5をAlpha Codeで表現し、その後ろにoffsetをつなげるとGamma Codeとなります。以下のようになります。

00001,10111

ここで、「,」はわかりすさのために書いただけです。簡単ですね。実際は、

55 = 0000110111

のようにコード化されます。

さて、次回は、Javaで実際に実装してみましょう。

*1:ここでのlog(X)は、2を底とするXの対数である。

*2:1 = 00000000にコード化すれば、log(X)が最小ビット数になります。