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

Javaで整数列圧縮(1)

Java

整数列圧縮について、Variable Byte CodeからNew PForまで実装してみて、実験してみようと思います。

整数列の圧縮はいろんなところで使われていて、身近なところでは、検索エンジンの文書IDの圧縮に使われることが多い。

なぜ、圧縮が必要かと言うと、通常、int型(4バイト)の配列を使って整数列を表現すると、以下のように無駄な領域がたくさんできるからである。

f:id:ryokkie:20121216194223p:plain

これらの数値は、すべて1バイトで表現できるため、残りの3バイトは0で埋められており、すべて無駄である。これは、このように固定長のバイトによって数値を表現していることで発生する問題である。ただし、固定長のバイトで表現することには、大きなメリットもある。それは、ランダムアクセスが可能であり、任意の位置の数値を簡単に取得することができる。しかし、圧縮の観点で考えた場合は、デメリットとなる。

Variable Byte Code(可変バイトコード)は、固定長のバイトで表現した場合の無駄を取り除く方法である。1バイト(=8bit)のうち、上位の1bitをフラグとして用いて、残りの7bitで数値を表現する方法である。以下に例を示す。

f:id:ryokkie:20121216205648p:plain

この例の場合、4バイトで表現されていた数値を3バイトで表現することができた。一般的に整数列の圧縮であるため、数値は複数ある。それぞれの数値をVariable Byte Codeで表現する場合、バイト配列を定義し、そこに詰め込んでいく。この時、バイト配列を先頭から読み込んでいき、先頭の1bitが1の場合は、そこで実際の数値を復元することができる。Variable Byte Codeは、UTF-8のエンコーディングにも似ている。

さて、Variable Byte Codeを使うことで、数値を表現する時の無駄なバイトを削減することができた。ここでさらに圧縮を行う方法について説明する。Variable Byte Codeは、数値が小さければ、小さいほど少ないバイト数で表現することができる。例えば、1という数値なら1バイトで良いが、128という数値なら2バイト必要である。ここで、以下のような昇順の整数列を考える。

100001, 100002, 100005, 100010, 100011, 100015, 100030, 100051, 100075, 100083, 100097, 100115, 100155, ...

この整数列は、このままVariable Byte Codeで表現してもあまり圧縮効果はない。なぜなら、それぞれの数値を表現するのに3バイトが必要であり、1バイトしか削減できていない。この時、簡単な前処理として、直前の数値との差分を計算することで、圧縮効果が高くなる。例えば、以下のようにする。

100001, 1, 3, 5, 1, 4, 15, 21, 24, 8, 14, 18, 40, ...

このように、差分を計算することで、小さい数値が出現しやすくなり、Variable Byte Codeで表現した時に、より小さなバイト数で表現できるようになる。一般的に、整数列の圧縮は、小さな値の方が圧縮されやすいため、数値の差分を計算することが多い。

数バイトを減らすことになぜそこまでしなければならないのか?と考える人もいると思うが、検索エンジンなどで大量の文書を扱う場合は、各文書に文書IDを割り当てて、整数として扱うことが多い。この時、固定長のバイト表現でデータを保持すると、検索インデックスのサイズがかなり大きくなってしまう。こういった場合に、Variable Byte Codeは有効である。実際に実験してみるとわかるが、検索インデックスのサイズをかなり削減できる。

最後に、Javaでの実装を以下に示す。

/**
 * 
 * Variable Byte Codeによる整数値圧縮を実装する。
 * 
 */
public class VariableByteCode {
	
	/** 圧縮対象の整数列 */
	private int [] mIntegerDiffArray;
	
	/** 可変バイトコーディングされた配列 */
	private byte [] mVariableByteCodingArray;
	
	private int mOffset = 0;
	
	/**
	 * 
	 * コンストラクタ
	 * 
	 * @param pIntegerDiffArray 圧縮対象の数値の差分の配列
	 */
	public VariableByteCode( final int [] pIntegerDiffArray ) {
		this.mIntegerDiffArray = pIntegerDiffArray;
	}
	
	/**
	 * 
	 * 整数値の可変バイトコードでのサイズを取得するメソッドである。
	 * 
	 * @param pNumber 整数値
	 * @return 可変バイトコードでのサイズ
	 */
	private int estimateByteNum( final int pNumber ) {
		
		int num = 0;
		
		if ( (1 << 7) > pNumber ) {
			num = 1;
		} else if ( (1 << 14) > pNumber ) {
			num = 2;
		} else if ( (1 << 21) > pNumber ) {
			num = 3;
		} else if ( (1 << 28) > pNumber ) {
			num = 4;
		} else {
			num = 5;
		}
		
		return num;
	}

	/**
	 * 
	 * VBCodeに変換するメソッドである。
	 * 
	 * @param pNumber 整数値
	 */
	private void encodeVBCodeNumber( final int pNumber ) {
		
		int num = estimateByteNum( pNumber );
		int lastOffset = 0;
		
		switch ( num ) {
		case 1:
			break;
		case 2:
			this.mVariableByteCodingArray[this.mOffset] = (byte) ((pNumber >> 7) & 0x7F);
			lastOffset = 1;
			break;
		case 3:
			this.mVariableByteCodingArray[this.mOffset] = (byte) ((pNumber >> 14) & 0x7F);
			this.mVariableByteCodingArray[this.mOffset + 1] = (byte) ((pNumber >> 7) & 0x7F);
			lastOffset = 2;
			break;
		case 4:
			this.mVariableByteCodingArray[this.mOffset] = (byte) ((pNumber >> 21) & 0x7F);
			this.mVariableByteCodingArray[this.mOffset + 1] = (byte) ((pNumber >> 14) & 0x7F);
			this.mVariableByteCodingArray[this.mOffset + 2] = (byte) ((pNumber >> 7) & 0x7F);
			lastOffset = 3;
			break;
		case 5:
			this.mVariableByteCodingArray[this.mOffset] = (byte) ((pNumber >> 28) & 0x7F);
			this.mVariableByteCodingArray[this.mOffset + 1] = (byte) ((pNumber >> 21) & 0x7F);
			this.mVariableByteCodingArray[this.mOffset + 2] = (byte) ((pNumber >> 14) & 0x7F);
			this.mVariableByteCodingArray[this.mOffset + 3] = (byte) ((pNumber >> 7) & 0x7F);
			lastOffset = 4;
			break;
		}
		
		this.mVariableByteCodingArray[this.mOffset + lastOffset] = (byte) ((pNumber & 0x7F) | 0x80);
		
		this.mOffset += num;
		
		return;
	}
	
	/**
	 * 
	 * 前処理を行うメソッドである。
	 * 
	 */
	public void preprocess() {
		
		int byteNum = 0;
		int arraySize = 0;
		
		for ( int i = 0; i < this.mIntegerDiffArray.length; i++ ) {
			byteNum = estimateByteNum(this.mIntegerDiffArray[i]);
			arraySize += byteNum;
		}
		
		this.mVariableByteCodingArray = new byte[arraySize];
		
		return;
		
	}
	
	/**
	 * 
	 * 可変バイトに圧縮するメソッドである。
	 * 
	 */
	public void compress() {
		
		for ( int i = 0; i < this.mIntegerDiffArray.length; i++ ) {
			encodeVBCodeNumber( this.mIntegerDiffArray[i] );
		}
		
		assert( this.mOffset == this.mIntegerDiffArray.length );
		
		return;
		
	}
	
	/**
	 * 
	 * 可変バイトをデコードするメソッドである。
	 * 
	 */
	public void decode() {
		
		int value = 0;
		int byteValue = 0;
		int integerNum = 0;
		
		for ( int i = 0; i < this.mVariableByteCodingArray.length; i++ ) {
			byteValue = this.mVariableByteCodingArray[i];
			value <<= 7;
			value |= (byteValue & 0x7F);
			if ( 0 != (byteValue & 0x80) ) {
				assert( this.mIntegerDiffArray[integerNum] == value );
				this.mIntegerDiffArray[integerNum] = value;
				integerNum++;
				value = 0;
			}
		}
		
		return;
		
	}

}

このクラスを使う時は、以下のようにして利用する。

// Variable Byte Code
VariableByteCode vbcode = new VariableByteCode( integerDiffArray );
vbcode.preprocess();
vbcode.compress();
vbcode.decode();

Variable Byte Codeは、最も基本的な整数列の圧縮方法なので、理解しやすいと思う。次回は、さらに圧縮する方法として、γ符号について説明する。