ハフマン符号化を実装してみた

ふと、圧縮アルゴリズムとして有名なハフマン符号を実装してみました。

知らない人のために、まずはハフマン符号化について簡単に説明。詳しい方からお叱りを受けそうな適当な説明ですが。

テキストなどのデータはすべて、それぞれの文字が特定の符号化方式（UTF-8とか、Shift_JISなど・・・）に従って表されており、それらの並びでデータが表現されているわけです。UTF-8だと、1~3バイトの可変長だったりしますが、最低、どれも8bit=1byte以上の幅があります。
この、それぞれの文字を表すのに使われる幅は、各文字コード（＝文字集合…Unicodeなど）中で定義された文字を一意に表すのに必要な幅であって、そのファイル中の文字だけを表そうとしたら、そんな長い幅は必要ないです。
たとえば、「abcdede」とある時、これをテキストデータで表すと、

でも、そのファイルにある文字の集合が「abcde」の５種類だけと分かっていたら、それらの並びさえわかればいいのですから、８ビットもの幅は必要ありません。
さらに、可変長ビットで、頻繁に出てくる文字に対してより短い幅を割り当ててやれば、さらにその文字列を表すのに必要な幅は小さくて済みます。
もちろん、常にどの文字がどの符号か、を表すテーブルが必要なので、合計容量が必ずしも小さくなる、という訳ではありませんが（今回のたかだか５文字だと絶対無理ですね）データが長くなればなるほど、この方法は確実にデータを圧縮出来る傾向があるわけです。

さて、以下でRubyでちゃちゃっと実装してみたものを載せてみます。
主な流れは、
１、文字列を走査し、どの文字が何度出てくるかカウント
２、それらの出てくる回数の少ないものから、二つずつをまとめて、ツリーを形成。ツリーの分岐点を表すのが、In_Node(Internal_Nodeの略)。ルートが一意に決まるまでこれを繰り返します。
３、最後に、ルートの左右に０と１の符号を振り、再帰的に、文字へ符号を振っていって、テーブルを作成していきます。そしてそれに従って文章にハフマン符号化。

#!ruby -Ks
def encode(string)
	include HuffmanUtils
	bit = 0
	root = maketree( char_count(string) )
	table = givecode(root)

	ret_str = String.new
	string.each_char do |char|
		ret_str << table[char]
		bit += 1
	end
	bit += 1
	return ret_str, table, bit
end

def decode(encoded, table)
	rev_table = {}
	table.each do |key, val|
		rev_table[val] = key
	end

	temp = ""
	ret_str = ""
	encoded.each_char do |char|
		temp << char
		if rev_table.has_key?(temp)
			ret_str << rev_table[temp]
			temp = ""
		end
	end
	return ret_str

end

#encodeするための関数群など
module HuffmanUtils
	class Node
		def initialize(count = 0)
			@count = count
			@code = ""
		end

		def count
			return @count
		end

		def count= (count)
			@count = count
		end

		def code= (code)
			@code = code
		end

		def code
			return @code
		end
	end

	class Ex_Node < Node
		def initialize(char = nil, count = 0)
			super(count)
			@char = char
		end

		def char
			return @char
		end
	end

	class In_Node < Node
		def initialize(left = nil, right = nil, count = 0)
			super(count)
			@left = left
			@right = right
		end

		def left
			return @left
		end

		def right 
			return @right
		end
	end

	def char_count(string)
		charcount = {}
		vecter_ex_node = Array.new

		string.each_char do |char|
			if charcount[char]
				charcount[char] += 1
			else
			 	charcount[char] = 1
			end
		end

		charcount.each do |char, count|
			vecter_ex_node << Ex_Node.new(char, count)
		end
		return vecter_ex_node
	end

	#木構造を形成。この実装は正直効率悪いです。。。いちいちソートしたりとか。
	def maketree(vecter)
		while vecter.size != 1
			vecter = vecter.sort_by {|node| node.count}
			tmp1 = vecter.shift
			tmp2 = vecter.shift
			vecter << In_Node.new(tmp1, tmp2, tmp1.count + tmp2.count)
		end
		return vecter[0]
	end

	#符号を振っていく関数。
	def givecode(root)
		table = {}
		root.left.code = '0'
		if root.left.class != Ex_Node
			table = givecode2(root.left, table)
		else
			table[root.left.char] = root.left.code
		end
	
		root.right.code = '1'
		if root.right.class != Ex_Node
			table = givecode2(root.right, table)
		else
			table[root.right.char] = root.right.code
		end

		return table
	end

	#符号化の為の補助関数。こっちを再帰的に呼び出す。
	def givecode2(node, table)
		node.left.code = node.code + '0'
		if node.left.class != Ex_Node
			table = givecode2(node.left, table)
		else
			table[node.left.char] = node.left.code
		end

		node.right.code = node.code + '1'
		if node.right.class != Ex_Node
			table = givecode2(node.right, table)
		else
			table[node.right.char] = node.right.code
		end

		return table
	end

end	#module

あとは、これでもどってきたものをpackしたりしてやれば、バイナリに変換できるので、確実にデータが軽くなります。