ハフマン符号化のプログラムで問題

Question

前提・実現したいこと

現在、wikipediaを参考に、ハフマン符号化のプログラムをjavaで作っていました。
しかし、画像を読み込み、符号化するとこのようになってしまいます。

first size 73736   #ファイルのサイズ
size 4194304     # 符号化後

該当のソースコード

package org.jyl.base.io;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.PriorityQueue;

public class Huffman
{
	private BitStream bs;

	public Huffman( byte[] data )
	{
		bs = new BitStream();
		CodeInfo[] cf = createValue2Code( data );

		compress( data, cf );
	}

	CodeInfo[] createValue2Code( byte[] data )
	{
		//	各バイト値の発生回数を数える
		TreeNode[] nodes = new TreeNode[ 256 ];
		for( int l = 0; l < 256; l++ ){
			//	groovy での new TreeNode(value:l)
			nodes[ l ] = new TreeNode();
			nodes[ l ].value = (byte)l;
		}

		//	data の中身分繰り返す
		for( byte v : data ) nodes[ Byte.toUnsignedInt( v ) ].occurrence++;

		//	ハフマン木を作成
		//	配列をリストに変換
		ArrayList<TreeNode> nodeslist = new ArrayList<TreeNode>( 0 );
		for( int l = 0; l < nodes.length; l++ ) nodeslist.add( nodes[ l ] );

		PriorityQueue<TreeNode> queue = new PriorityQueue<TreeNode>( nodeslist );

		while( queue.size() > 1 ){
			TreeNode n1 = queue.poll(), n2 = queue.poll();
			TreeNode tn = new TreeNode();
			tn.occurrence = n1.occurrence + n2.occurrence;
			tn.children = new ArrayList<TreeNode>( 0 );
			tn.children.add( n1 ); tn.children.add( n2 );
			queue.add( tn );
		}

		TreeNode root = queue.poll();

		//	深さ優先探索でバイト値->符号情報を作成
		CodeInfo[] value2Code = new CodeInfo[ 256 ];
		dfs( value2Code, root, 0, 0 );

		return value2Code;
	}

	void dfs( CodeInfo[] value2Code, TreeNode node, int code, int codeSize )
	{
		if( node.children == null ){
			CodeInfo cf = new CodeInfo();
			cf.code = code; cf.codeSize = codeSize;
			value2Code[ Byte.toUnsignedInt( node.value ) ] = cf;
		}else{
			dfs( value2Code, node.children.get( 0 ), code << 1, codeSize + 1 );
			dfs( value2Code, node.children.get( 1 ), ( code << 1 ) + 1, codeSize + 1 );
		}
	}

	/**
	 * 圧縮する
	 */
	void compress( byte[] data, CodeInfo[] value2Code )
	{
		for( byte v : data ){
			CodeInfo codeInfo = value2Code[ Byte.toUnsignedInt( v ) ];
			bs.write( codeInfo.code, codeInfo.codeSize );
		}
	}

	public int getSize()
	{
		return bs.bs.size();
	}

	/**
	 * 符号情報のクラス
	 */
	class CodeInfo
	{
		int code, codeSize;
	}

	class TreeNode implements Comparable<TreeNode>
	{
		byte value = 0; int occurrence = 0;
		ArrayList<TreeNode> children;

		public int compareTo( TreeNode that )
		{
			return this.occurrence - that.occurrence;
		}
	}

	class BitStream
	{
		BitSet bs = new BitSet();
		int len = 0, pos = 0;

		void write( int v, int bits )
		{
			for( int l = 0; l < 256; l++ )
				bs.set( len++, ( ( v >>> l ) & 1 ) != 0 );
		}

		int read( int bits )
		{
			int v = 0;

			for( int l = 0; l < bits; l++ ){
				if( bs.get( pos++ ) ) v |= 1 << l;
			}

			return v;
		}
	}
}

import java.io.FileInputStream;

import java.util.ArrayList;

import org.jyl.base.io.Huffman;

public class Test
{
	public static void main( String[] args ) throws java.io.IOException
	{
		ArrayList<Byte> b = new ArrayList<Byte>( 0 );
		FileInputStream fis = new FileInputStream( new java.io.File( "/home/pi/Downloads/image/nc74842.png" ) );
		int data = 0;
		for( int l = 0; ( data = fis.read() ) != -1; l++ ){
			b.add( (byte)data );
		}

		byte[] by = new byte[ b.size() ];
		for( int l = 0; l < by.length; l++ ){
			by[ l ] = b.get( l );
		}

		System.out.println( "first size " + by.length );

		Huffman hf = new Huffman( by );

		System.out.println( "size " + hf.getSize() / 8 );
	}
}

試したこと

何が原因でこうなっているのか全くわかりません。
Groovyの仕様を確認した

補足情報（FW/ツールのバージョンなど）

Java8 を使っています。

Comments

[momon-ga]

ファイルはpngじゃないと、ダメですか？
ビットマップとかテキストなら大丈夫かと。

[yukkuri]

最初、12バイトくらいのバイト配列で試していました。

Answer 1

いきなり画像データを入れたりせず, 10バイト程度の簡単なバイト配列を作って手作業で結果を算出して, それから実際にコードに通して結果を比較したほうが良いと思います.

Comments

[yukkuri]

すみません、書き忘れですね。最初、12バイトくらいのバイト配列で試していました。
しかし、うまくいかず、データを変えてみた、そして成功しない、というのが現状です。

Answer 2

何が原因でこうなっているのか全くわかりません。

質問者さんへのアドバイスとして間違っている点を示すよりはどうやって期待通りに動作するプログラムを作るかの方が有効に思えます。

ご自分でどのくらいこの論理をデバッグしていますか？「全くわかりません」と言い切れるほどデバッグしておられるでしょうか？失礼ながらそうは思えません。

例えばikadzuchiさんご指摘のバグがなぜ見つけられなかったのか大いに反省するとよいと思います。

ご自分でもっとデバッグできることがあるはずです。変換前後の長さを比べておられますが、おそらく実際はもっといろいろデバッグして今のコードになっているのだろうと想像します。しかしまだデバッグのしかたが浅いと思います。コード中に出現する様々な情報(変数)の内容が妥当になっているかどうか細かく確認していくのがデバッグの基本的アプローチの一つです。「各情報がどうであるべきか」はわかるはずですのでそれをデバッグプリントするなりデバッガーで調べるなりして確認すればよいのです。もし期待と違っていたらその情報をどこで計算しているかさらに調べ犯人（バグ）を追い詰めていきます。

ということで「もっと気を入れてデバッグしましょう」が質問者さんにとって一番申し上げたいアドバイスです。

デバッグは発見的(heuristic)な作業ですので、「これこれの手順でやれば結果が得られる」というような単純な作業ではありません。ご自分で様々なバグと戦っているうちに方法論のあれこれが身についていく、そういうものです。アプローチは色々で「個々の論理が正しいか一つ一つ確認していく」だったり逆に「期待外の結果を見てその直接的な原因になりそうな部分から絞り込んでいく」など場合によって使い分けます。jimbeさんが回答しておられる「単純なケースを試してデバッグ過程で必要となる確認すべき情報量を小さくする」というのも非常に基本的かつ有効な手法と思います。

---

ただデバッグしましょうではコメントのかいがないので、ヒントだけ申し上げますとikadzuchiさんご指摘のバグに加え少なくとももう一点バグがあります。BitSetの仕様を質問者さんが勘違いしているというバグです。前述したようなデバッグをしていけば必ず見つかるはずですよ？見つけたらちょっとショックを受けるかも知れません。それくらい単純なバグです。

---

全てのPNGファイルがハフマン符号化によって短くなるとは限らないかも知れませんが、自分が適当な写真画像をハフマン符号化してみたところほんの少し短くなりました。

Comments

[KSwordOfHaste]

既に解決済みになってましたね。ただ自分が指摘しようとしたバグはまだ見つけておられないかもしれませんのでそれについても調べてみることをお勧めします。

[ikadzuchi]

ああ、やはりまだ何かありましたか。計算が合わない(入力バイト数の256倍ビットになるはずが切り上げたような数)とは思ったもののそれ見つけられなかったんですよね。BitSetですか…。
減ったように報告されていたので大丈夫だったのかなと見逃してましたが、1種類で100->60バイトというのは確かにおかしいですね。
そしてPNGで縮みましたか。意外です。

[KSwordOfHaste]

時間もたちましたし種明かしすると...size()メソッドの意味を勘違いしているのがバグです。実をいえば自分もすぐには気づけませんでした。自分もjimbeさんと同様の考え方で初期デバッグをする習慣ですが、new byte[] { 1, 2, 2, 3, 3, 3 }
あたりのごく単純なものでデバッグしたところ明らかに結果のビット数が大きすぎるので「あれれ」と思ったらBitSet#sizeは「BitSetが内部的に用意しているバッファーのサイズ(ビット数)」を返すメソッドでした(リファレンスを見ないと気づけませんでした)。ご質問のコードではlenという変数に蓄積したビット数が保持されてますがBitSet#sizeの結果はあきらかにlenより大きいのでそのあたりはデバッグしていれば割合すぐに気づると思い、本回答を書いた次第です。

Answer 3

とりあえず一番問題ありそうなのがここで、

void write( int v, int bits )
{
    for( int l = 0; l < 256; l++ )
        bs.set( len++, ( ( v >>> l ) & 1 ) != 0 );
}

入力ビット数によらず256ビット書き込んでいるように見えます。
ただこれでも計算が合わないので他に何かありそうです。

あとpngは既に圧縮されているので、正しいプログラムが書けたとしてもデータサイズは増えます。

Comments

[yukkuri]

たしかに、指摘された箇所を変更したら130000くらいになりました。

[yukkuri]

どうやら、Jimbeさんもおっしゃっていたように、画像データを用いたのが原因だったようです。
100バイトで1種類のバイトに偏らせたデータを使用したところ、100->60バイトになりました。
ソースは、上で指摘されたものが原因だったようです。