欲張りアルゴリズム-ハフマン符号化ハフマン

ハフマン符号化:
データファイルの圧縮によく用いられる文字符号化方式.圧縮率は通常20%~90%である.
主な考え方:
可変長符号化方式を採用し、ファイルに出現回数の多い文字に対して比較的短い符号化を採用し、出現回数の少ない文字に対して比較的長い符号化を採用し、全体の符号化長を効果的に低減することができる.
例えば、英語ではeの出現頻度が最も高く、zの出現頻度が最も低いので、最短の符号化でeを表し、最長の符号化でzを表すことができる.
例:
1つのファイルに100,000文字が含まれ、a,b,c,d,e,fの6文字のみが含まれている場合、3ビットbitで6文字を符号化することができ、定長符号と呼ばれます.
では、固定長コードを採用するのに必要なビット数は3*100,000=600,000ビットです.
この6文字の出現頻度は図に示すように、aが最も多く、fが最も少ない.したがって、図に示す変長符号を採用する場合、必要なビット数は以下の通りである.
(45*1 + 13*3 + 12 * 3 + 16*3 + 9*4 + 5*4) * 1000 = 224 000.
圧縮は25%であり,aの符号化長が最も短く,1ビットであり,fの符号化長が最も長く,4ビットであることがわかる.
プレフィックスコード:
ファイルを読み取ると、定長コードファイルについては、各文字の符号化長が分かっているので、順番に1つずつ文字を読み取るだけでよい.
変長符号ファイルでは、各文字の符号化長が異なるため、各文字の符号化を注意深く設計し、混同する必要がある.
例えば、aの符号化が0、bの符号化が01、cの符号化が1であれば、復号時に‘001’に遭遇すれば‘aac’に復号してもよいし‘ab’に復号してもよい.
bの符号化にはaの符号化が含まれているため、すなわちaの符号化はbの符号化のプレフィックスである.
従って、変長符号化の設計では、各文字の符号化は他の文字符号化のプレフィックスではなく、これをプレフィックス符号と呼ぶ.
各文字の符号化は、左を0、右を1とするツリーで表すことができ、各リーフノードのパスが異なり、他のリーフノードの接頭辞とも呼ばない.
このように各リーフノードのパスは、各文字の符号化である.
図に形成された符号化は表と若干異なるが,各文字符号化の長さは同じであり,これは左サブツリーと右サブツリーの違いであるが,符号化長には影響しない.
コード実装:

/**
 * Huffman code
 * @author xuefeng
 *
 */
public class Huffman {

	/**
	 * ignore exception
	 * @param cs : characters
	 * @param freqs : frequency of each character
	 */
	public static void huffman(char[] cs, double[] freqs) {
		int n = cs.length;
		MinHeap heap = new MinHeap(cs.length);
		Code[] codes = new Code[n];
		for (int i = 0; i < n; i++) {
			Code c = new Code(cs[i], freqs[i]);
			heap.add(c); //                 
			codes[i] = c; //          
		}

		Code c, c1, c2;
		while (heap.size() > 1) {
			c1 = heap.removeMin();
			c2 = heap.removeMin();//        

			c = new Code('\0', c1.freq + c2.freq);
			c.left = c1;
			c.right = c2;
			c1.parent = c;
			c2.parent = c;
			heap.add(c); //          ，     ，    

			System.out.println(c1.val + "+" + c2.val + " : " + c1.freq + "+" + c2.freq + " = " + c.freq);
		}
		c = heap.removeMin(); //       

		StringBuffer sb;
		for (int i = 0; i < n; i++) {
			c = codes[i]; //        ，    ，     ，         
			sb = new StringBuffer();
			while (c != null) {
				if (c.parent != null) {
					if (c == c.parent.left) {
						sb.insert(0, 0); //       ，   1
					} else {
						sb.insert(0, 1); //       ，   1
					}
				}
				c = c.parent;
			}
			System.out.println(codes[i].val + " : " + sb.toString());
		}
	}

	public static void main(String[] args) {
		char[] cs = { 'a', 'b', 'c', 'd', 'e', 'f' };
		double[] freqs = { 45, 13, 12, 16, 9, 5 };// %

		huffman(cs, freqs);

		// http://zh.wikipedia.org/wiki/%E5%AD%97%E6%AF%8D%E9%A2%91%E7%8E%87
		char[] cs2 = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k',
				'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w',
				'x', 'y', 'z' };
		double[] freqs2 = { 8.167, 1.492, 2.782, 4.253, 12.702, 2.228, 2.015,
				6.094, 6.966, 0.153, 0.772, 4.025, 2.406, 6.749, 7.507, 1.929,
				0.095, 5.987, 6.327, 9.056, 2.758, 0.978, 2.360, 0.150, 1.974,
				0.074 };

		huffman(cs2, freqs2);
	}
}

class Code implements Comparable {

	public char val;

	public double freq;

	public Code left, right, parent;

	public Code(char val, double freq) {
		this.val = val;
		this.freq = freq;
	}

	@Override
	public int compareTo(Code c) {
		double d = freq - c.freq;
		return d > 0 ? 1 : (d == 0 ? 0 : -1);
	}
}

出力:

f+e : 5.0+9.0 = 14.0
c+b : 12.0+13.0 = 25.0
#+d : 14.0+16.0 = 30.0
#+# : 25.0+30.0 = 55.0
a+# : 45.0+55.0 = 100.0
a : 0
b : 101
c : 100
d : 111
e : 1101
f : 1100
z+q : 0.074+0.095 = 0.16899999999999998
x+j : 0.15+0.153 = 0.303
#+# : 0.16899999999999998+0.303 = 0.472
#+k : 0.472+0.772 = 1.244
v+# : 0.978+1.244 = 2.222
b+p : 1.492+1.929 = 3.4210000000000003
y+g : 1.974+2.015 = 3.989
#+f : 2.222+2.228 = 4.45
w+m : 2.36+2.406 = 4.766
u+c : 2.758+2.782 = 5.54
#+# : 3.4210000000000003+3.989 = 7.41
l+d : 4.025+4.253 = 8.278
#+# : 4.45+4.766 = 9.216000000000001
#+r : 5.54+5.987 = 11.527000000000001
h+s : 6.094+6.327 = 12.421
n+i : 6.749+6.966 = 13.715
#+o : 7.41+7.507 = 14.917
a+# : 8.167+8.278 = 16.445
t+# : 9.056+9.216000000000001 = 18.272
#+# : 11.527000000000001+12.421 = 23.948
e+# : 12.702+13.715 = 26.417
#+# : 14.917+16.445 = 31.362000000000002
#+# : 18.272+23.948 = 42.22
#+# : 26.417+31.362000000000002 = 57.779
#+# : 42.22+57.779 = 99.999
a : 1110
b : 110000
c : 01001
d : 11111
e : 100
f : 00101
g : 110011
h : 0110
i : 1011
j : 001001011
k : 0010011
l : 11110
m : 00111
n : 1010
o : 1101
p : 110001
q : 001001001
r : 0101
s : 0111
t : 000
u : 01000
v : 001000
w : 00110
x : 001001010
y : 110010
z : 001001000

#は、リーフノードではありません.
MinHeapのコード実装については、前の記事を参照してください:欲張りアルゴリズム-最小生成ツリーKruskalアルゴリズム