ハフマンツリーをRubyで書く - yarbの日記ハフマン符号化に使うハフマンツリーをRubyで作ってみた。2本のキューを用意して、2つのノードをくっつけたり出し入れするのが簡単というのでそういう方針で。本当は1本はプライオリティ・キューでないとエンキュー時にソートするために効率が悪い。 # Huffman coding # class Node attr_accessor :val, :weight, :left, :right def initialize(val = "", weight = 0) @val, @weight = val, weight end def leaf? !(left and right) end end class HuffmanTree attr_accessor :freq, :que1, :que2, :root def initialize(str) @freq = count_freq(str.
