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

Javaで整数列圧縮(3)

Java

さて、JavaでGamma Codeを実装していくわけですが、ビット単位でデータの入出力を行えるクラスが必要です。まずは、そのクラスを作ります。

データは、ビット単位で入力され、ビット単位で出力されることになりますが、Javaではバイト単位でしか管理できません。なので、このギャップを埋めるために、バッファを利用します。以下のようなイメージでビット単位の入出力を扱うこととします。

f:id:ryokkie:20130101174212p:plain

BitBufferというクラスを定義し、クラス内にデータ保管用のbyte型の領域を確保します。ただし、この領域には、バイト単位で格納する必要があるので、バッファ領域を作り、入力されたデータは、一時的にバッファに格納します。ある程度バッファにデータが蓄積された段階で、バイト単位でデータ保管用の領域にデータを格納します。例として、「10」、「19」、「27」、「11」、「14」というデータを格納してみます。まず、それぞれの2進数の表現は、以下のようになります。

10 = 1010
19 = 10011
27 = 11011
11 = 1011
14 = 1110

このとき、「10」をバッファに格納した場合、バッファは、以下のようになります。ただし、バッファは、2バイトとします。

バッファ : 0000000000001010

この時点で、データ保管領域にデータを保管した場合、「00001010」というバイトデータを格納することになります。この場合、下位4ビットには、データが格納されていますが、上位4ビットには、全くデータが格納されないため、無駄になります。このため、この時点では、バッファに対して何もしません。

次に、「19」をバッファに格納した場合は以下のようになります。

バッファ : 0000000100111010

さらに、「27」をバッファに格納した場合は、以下のようになります。

バッファ : 0011011100111010

バッファ内のデータが1バイトよりも大きくなったので、バイト単位でデータ保管領域にデータを格納しても無駄になりません。この時点で、バッファ内の下位8ビットをデータ保管領域に格納し、バッファ内のデータを右に8ビットシフトすると、以下のようになります。

バッファ       : 0000000000110111
データ保管領域 : 00111010

残りの「11」と「22」も同様に格納すると、以下のようになります。

バッファ       : 0000000000111010
データ保管領域 : 00111010,11110111

このようにすることで、データ保管領域を無駄にすることなく、ビット単位でデータを書き込むことができます。データ保管領域からビット単位でデータを取り出す場合は、逆の処理を行えばよい。つまり、バイト単位でデータを取り出しながらバッファに書き込み、データを取得する。

最後に、ざっくりと書いたBitBufferクラスのサンプルコードを以下に示す。

/**
 * 
 * <p>
 * ビット単位の読み込みと書き込みを扱うクラスである。
 * </p>
 *
 */
public class BitBuffer {
	
	// データ保管領域
	private byte [] mData;
	
	// 読み込みと書き込みのためのバッファ
	private long mBuffer = 0;
	// バッファ内のビット位置
	private int mBitNum = 0;
	private int mWriteCurIndex = 0;
	private int mReadCurIndex = 0;
	
	public static final int MASK_TABLE[];
	static {
		MASK_TABLE = new int [] {
			0x00000000,
			0x00000001, 0x00000003, 0x00000007, 0x0000000F,
			0x0000001F, 0x0000003F, 0x0000007F, 0x000000FF,
			0x000001FF, 0x000003FF, 0x000007FF, 0x00000FFF,
			0x00001FFF, 0x00003FFF, 0x00007FFF, 0x0000FFFF,
			0x0001FFFF, 0x0003FFFF, 0x0007FFFF, 0x000FFFFF,
			0x001FFFFF, 0x003FFFFF, 0x007FFFFF, 0x00FFFFFF,
			0x01FFFFFF, 0x03FFFFFF, 0x07FFFFFF, 0x0FFFFFFF,
			0x1FFFFFFF, 0x3FFFFFFF, 0x7FFFFFFF, 0xFFFFFFFF
		};
	}
	
	/**
	 * 
	 * <p>
	 * コンストラクタ
	 * </p>
	 * 
	 */
	public BitBuffer( final int pArraySize ) {
		this.mData = new byte [ pArraySize ];
	}
	
	/**
	 * 
	 * <p>
	 * バッファのデータを出力するメソッドである。
	 * </p>
	 * 
	 */
	public void dump() {
		store();
		this.mData[this.mWriteCurIndex] = (byte) (this.mBuffer & 0x00000000000000FF);
		this.mWriteCurIndex++;
		this.mBitNum = 0;
		this.mBuffer = 0;
	}
	
	/**
	 * 
	 * <p>
	 * 8ビットを超えたデータを出力するメソッドである。
	 * </p>
	 * 
	 */
	private void store() {
		while ( 8 < this.mBitNum ) {
			this.mData[this.mWriteCurIndex] = (byte) (this.mBuffer & 0x00000000000000FF);
			this.mWriteCurIndex++;
			this.mBitNum -= 8;
			this.mBuffer >>= 8;
		}
	}
	
	/**
	 * 
	 * <p>
	 * バッファにデータを格納するメソッドである。
	 * </p>
	 * 
	 * @param pValue 格納するデータ
	 * @param pBitNum 格納するビット数
	 */
	public void push( final int pValue, final int pBitNum ) {
		
		long value = (long) (pValue & MASK_TABLE[ pBitNum ]);
		
		if ( 32 < (this.mBitNum + pBitNum) ) {
			store();
		}
		
		value <<= this.mBitNum;
		this.mBuffer |= value;
		this.mBitNum += pBitNum;
		
	}
	
	/**
	 * 
	 * <p>
	 * データを読み込む前に初期化するメソッドである。
	 * </p>
	 * 
	 */
	public void readInit() {
		this.mBuffer = 0;
		this.mBitNum = 0;
		this.mReadCurIndex = 0;
	}
	
	/**
	 * 
	 * <p>
	 * 指定したビット数分のデータを取得するメソッドである。
	 * </p>
	 * 
	 * @param pBitNum ビット数
	 * @return データ
	 */
	public int get( final int pBitNum ) {
		
		while ( this.mBitNum < pBitNum ) {
			long data = (long) (this.mData[this.mReadCurIndex] & 0xFF);
			this.mBuffer |= (data << this.mBitNum);
			this.mReadCurIndex++;
			this.mBitNum += 8;
		}
		
		int value = (int) (this.mBuffer & MASK_TABLE[ pBitNum ]);
		this.mBuffer >>= pBitNum;
		this.mBitNum -= pBitNum;
		
		return value;
		
	}

}

次回は、このBitBufferクラスを使って、Gamma Codeを実装します。