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

Javaで整数列圧縮(4)

Java

前回作成したBitBufferクラスを使って、Gamma Codeを実装します。

Gamma Code自体は、すでに説明したので、そのコードを以下に示します。

/**
 * 
 * <p>
 * Gamma Codeによる整数値圧縮を実装するクラスである。
 * </p>
 *
 */
public class GammaCode {
	
	/** 圧縮対象の整数列 */
	private int [] mIntegerDiffArray;
	
	private int mValueNum = 0;
	
	private BitBuffer mGammaCode;
	
	/** 1バイトの値のrank値 */
	static final int RANK_TABLE[];
	static {
		RANK_TABLE = new int [] {
				0, 1, 1, 2, 1, 2, 2, 3,
				1, 2, 2, 3, 2, 3, 3, 4,
				1, 2, 2, 3, 2, 3, 3, 4,
				2, 3, 3, 4, 3, 4, 4, 5,
				1, 2, 2, 3, 2, 3, 3, 4,
				2, 3, 3, 4, 3, 4, 4, 5,
				2, 3, 3, 4, 3, 4, 4, 5,
				3, 4, 4, 5, 4, 5, 5, 6,
				1, 2, 2, 3, 2, 3, 3, 4,
				2, 3, 3, 4, 3, 4, 4, 5,
				2, 3, 3, 4, 3, 4, 4, 5,
				3, 4, 4, 5, 4, 5, 5, 6,
				2, 3, 3, 4, 3, 4, 4, 5,
				3, 4, 4, 5, 4, 5, 5, 6,
				3, 4, 4, 5, 4, 5, 5, 6,
				4, 5, 5, 6, 5, 6, 6, 7,
				1, 2, 2, 3, 2, 3, 3, 4,
				2, 3, 3, 4, 3, 4, 4, 5,
				2, 3, 3, 4, 3, 4, 4, 5,
				3, 4, 4, 5, 4, 5, 5, 6,
				2, 3, 3, 4, 3, 4, 4, 5,
				3, 4, 4, 5, 4, 5, 5, 6,
				3, 4, 4, 5, 4, 5, 5, 6,
				4, 5, 5, 6, 5, 6, 6, 7,
				2, 3, 3, 4, 3, 4, 4, 5,
				3, 4, 4, 5, 4, 5, 5, 6,
				3, 4, 4, 5, 4, 5, 5, 6,
				4, 5, 5, 6, 5, 6, 6, 7,
				3, 4, 4, 5, 4, 5, 5, 6,
				4, 5, 5, 6, 5, 6, 6, 7,
				4, 5, 5, 6, 5, 6, 6, 7,
				5, 6, 6, 7, 6, 7, 7, 8
		};
	}
	
	/**
	 * 
	 * <p>
	 * コンストラクタ
	 * </p>
	 * 
	 * @param pIntegerDiffArray 圧縮対象の数値の差分の配列
	 */
	public GammaCode( final int [] pIntegerDiffArray ) {
		this.mIntegerDiffArray = pIntegerDiffArray;
	}
	
	/**
	 * 
	 * <p>
	 * 32bitのWORDから1のrank値を計算するメソッドである。
	 * </p>
	 * 
	 * @param pWord 32bitのWORD
	 * @return 32bitのWORD内の1のrank値
	 */
	private static int getWordRankFromTable( final int pWord ) {
		// 32bit分のrank値を計算する。
		return RANK_TABLE[ (pWord >> 24) & 0xff ]
				+ RANK_TABLE[ (pWord >> 16) & 0xff ]
				+ RANK_TABLE[ (pWord >> 8) & 0xff ]
				+ RANK_TABLE[ pWord & 0xff ];
	}
	
	/**
	 * 
	 * <p>
	 * MSBを求めるメソッドである。
	 * </p>
	 * 
	 * @param pWord 整数値
	 * @return 指定された整数値のMSB
	 */
	private static int getWordMSB( final int pWord ) {
		int rank = 0;
		int word = pWord;
		if ( 0 < pWord ) {
			word |= (word >> 1);
			word |= (word >> 2);
			word |= (word >> 4);
			word |= (word >> 16);
			word |= (word >> 32);
			
			// MSB以下は、すべて1が立っているので、その数を数える。
			rank = getWordRankFromTable(word);
		}
		return rank;
	}
	
	/**
	 * 
	 * <p>
	 * γ符号化するための前処理を行うメソッドである。
	 * </p>
	 * 
	 */
	public void preprocess() {
		
		int totalEstimateBitNum = 0;
		
		for ( int i = 0; i < this.mIntegerDiffArray.length; i++ ) {
			assert( 0 < this.mIntegerDiffArray[i] );
			
			// +1しておく。
			int value = this.mIntegerDiffArray[i] + 1;
			
			// MSBを計算する。
			int msb = getWordMSB( value );
			
			assert( 1 < msb );
			
			// 最上位ビットは不要なので、MSBから-1をする。
			msb--;
			
			// Alpha Codeのビット数を加算する。
			int estimateBitNum = msb;
			// 最上位ビットを取り除いたビット数を加算する。
			estimateBitNum += msb;
			
			totalEstimateBitNum += estimateBitNum;
		}
		
		// bit数からバイト数を計算する。
		int byteNum = (totalEstimateBitNum + 8 - 1) / 8;
		
		// ビットバッファを初期化する。
		this.mGammaCode = new BitBuffer(byteNum);
		
	}
	
	/**
	 * 
	 * <p>
	 * γ符号にエンコードするメソッドである。
	 * </p>
	 * 
	 * @param pValue γ符号化する対象の整数値
	 */
	private void encodeGammaCode( final int pValue ) {
		int value = pValue + 1;
		
		int msb = getWordMSB( value );
		
		assert( 1 < msb );
		
		// 最上位ビットは不要なので、MSBから-1をする。
		msb--;
		
		// Alpha CodeをBitBufferに格納する。
		if ( 1 < msb ) {
			this.mGammaCode.push( 0, msb - 1 );
		}
		this.mGammaCode.push( 1, 1 );
		
		// 最上位ビットを取り除いたビット列を格納する。
		this.mGammaCode.push( value, msb );
	}
	
	/**
	 * 
	 * <p>
	 * γ符号に圧縮するメソッドである。
	 * </p>
	 * 
	 */
	public void compress() {
		
		for ( int i = 0; i < this.mIntegerDiffArray.length; i++ ) {
			encodeGammaCode( this.mIntegerDiffArray[i] );
		}
		this.mGammaCode.dump();
		
		this.mValueNum = this.mIntegerDiffArray.length;
		
		return;
		
	}
	
	/**
	 * 
	 * <p>
	 * γ符号をデコードするメソッドである。
	 * </p>
	 * 
	 */
	public void decode() {
		
		this.mGammaCode.readInit();
		
		for ( int i = 0; i < this.mValueNum; i++ ) {
			
			int alphaCodeValue = 1;
			
			// Alpha CodeをBitBufferから取り出す。
			while ( true ) {
				int tmpValue = this.mGammaCode.get(1);
				if ( 1 == tmpValue ) {
					break;
				}
				// 0の数を数える。
				alphaCodeValue++;
			}
			
			int gammaCodeValue = this.mGammaCode.get(alphaCodeValue);
			
			// 最上位ビットを復元する。
			gammaCodeValue |= (1 << alphaCodeValue);
			
			// 最初に+1しているので、元に戻す。
			gammaCodeValue--;
			
			assert( this.mIntegerDiffArray[i] == gammaCodeValue );
		}
		
	}

}

BitBufferクラスを利用すれば、Gamma Codeのロジックをそのまま実装するだけです。ここで、整数値XをAlpha Codeで表現する場合に、以下の2つの方法があります。

  1. X個の0と1個の1で合計X+1ビットで表現する方法
  2. X-1個の0と1個の1で合計Xビットで表現する方法

この場合、1つ目の方法では0をAlpha Codeで表現することができますが、2つ目の方法では表現することができません。その代わり、2つ目の方法の方が1ビットだけ削減することができます。今回は、2つ目の方法でGamma Codeを実装しているため、Gamma Codeで表現する整数値に+1をしています。これは、1をGamma Codeで表現しようとすると、

2進数 : 1
offset = 0
length = 0

となるため、lengthが0となり、Alpha Codeで表現できないためです。

Gamma Codeは、ユニバーサル符号であるため、使いやすい符号化方式です。ユニバーサル符号とは、Gamma Codeを適用したい整数値がどのような分布に従っていても、最適な符号化の定数倍以内となる符号化方式のことです。また、パラメーター自由であるという特徴もある。これは、Rice符号のように、パラメーターによって生成されるコードが変わるということがないということです。これは、動的に整数値が追加されていくような状況において、とても使いやすい性質です。

Gamma Codeは、検索インデックスで実際に実験してみるとわかりますが、VBCodeよりもインデックスサイズが小さくなりやすいです。ただし、復号は、VBCodeの方が高速です。また、適用する整数値が、大きい場合は、VBCodeの方が圧縮されたりもします。どちらを選択するかは、実験しながら決定する必要があります。

次回は、Delta Codeについて説明します。