Pythonの技法：Huffman符号化の実装

　前回の圧縮に関する記事では、Pythonを用いた実行時エンコードの実現方法をお見せした。本稿では、もう一つの種類の圧縮方式「Huffman符号化」の実装方法をお見せする。Huffman符号化は、文字列のような小さなアイテム集合を扱う際に便利な圧縮方式だ。

　Huffman符号化では多種多様なデータ構造を同時に使用するため、大学のアルゴリズムの講義ではHuffman符号化が非常に好まれている。本稿では、Pythonのheapqライブラリを用いて優先順位付きキューを実装するので、もしheapqライブラリになじみがなければ以前の記事を読んで欲しい。

　Huffman符号化は、次のような2つのステップで主に構成されている。

1. 元データに含まれているアイテムをすべて含む二分木を作成する。二分木は、リストに含まれているアイテムの中で、もっとも出現回数の少ないアイテム2つを何度も繰り返し組み合わせることによって作成される。すべてのアイテムをまとめるノード一つのみになったら、その作業は終了である。
2. シーケンスに含まれている各アイテムに対して、ツリーのルートからそのアイテムのノードまでをたどり、左に枝分かれした場合は0を、右に枝分かれした場合は1を、枝分かれの回数だけ追加する。

　この処理が終わると、二進の文字列が得られる。ここで得られた文字列は、先ほどのツリーを用いて、最後の手順を逆に行うことで復号化することが可能だ。Huffman符号化を用いると、より頻繁に出現するアイテムにはより短い二進の文字列が割り当てられる。すべての文字に同じ長さのコードが割り当てられる標準的なASCII文字列の符号化方式との違いが、お分かりいただけると思う。

　まず、最初にすべきことはツリーの構築だ。ツリーのノードは単純なオブジェクトでよいが、4つのこと―（もし存在すれば）格納しているアイテムの種類、自身のノードおよび子ノードの合計の重み、そして左側および右側のノード―を常に把握しておく必要がある。これらの情報を格納できるよう、クラスを次のように実装しよう。

class Node(object):
left = None
right = None
item = None
weight = 0

def __init__(self, i, w):
self.item = i
self.weight = w

def setChildren(self, ln, rn):
self.left = ln
self.right = rn

def __repr__(self):
return "%s - %s -- %s _ %s" % (self.item, self.weight, self.left, self.right)

def __cmp__(self, a):
return cmp(self.weight, a.weight)

　ここでは__repr__関数を定義し、ノードの状態を表示できるようにした（これでツリーのデバッグが可能になる）。また、__cmp__関数も定義し、ノードの順序づけにheapqモジュールを利用できるようにした。

　さて、次はツリーの構築である。ツリーの構築を行うには、まずリスト内の各アイテムに対してノードを作成する必要がある。さらに、最小の重みを持ったノードを2つ見つけて、それらを組み合わせられるようにしなければならない。