Pythonでハフマン符号化を実装してみた
何番煎じ?と言いたくなるぐらいPythonでやってみた例はたくさんあるけど 勉強に車輪の再発明をするのもよいと思いやってみる。
ハフマン符号 (Huffman encoding)
ハフマン符号はデータを圧縮するための方法の一つ。 HTTP/2とかPNGとかでもつかわれている有名な方法です。 出現の頻度が大きいデータは小さいビット数で表し、 頻度が小さいデータは大きいビット数で表すことでデータを圧縮します。
例としてAABCCDEEE
という文字列をハフマン符号化してみます。
文字の出現回数を求める
まず、この文字列中の文字ごとの出現回数を求めます。
文字 | 回数 |
---|---|
A | 2 |
B | 1 |
C | 2 |
D | 1 |
E | 3 |
ハフマン木を作る
ハフマン木 (Huffman tree)を作ります。 ハフマン木は文字を葉(Node)として使い、 ハフマン木を作るために上で求めた各文字の出現回数を使います。
- 葉の中から出現した回数が一番少ないものと2 番目に少ないものを選ぶ。
- 1で選んだ2つを子として持つ新たな節点を作り、1で選んだ2つの文字の回数を足した値を格納する。
- これを最後の1つになるまで繰り返す。
この例では出現した回数が1番少ないのはBとDの1回です。 なので、BとDを選びます。
文字 | 回数 |
---|---|
B | 1 |
D | 1 |
次に、この2つを子に持ち、2つの回数の合計を持つ、木を作ります。 こんな感じです。
表で表すと、BとDが合体したので下のようになります。
文字 | 回数 |
---|---|
A | 2 |
B+D | 2 |
C | 2 |
E | 3 |
次は、また最初に戻り、上の表(BとDが合体した表)の中から出現した回数が、 一番少ないものと2 番目に少ないものを選びます。 しかし、今回は一番少ない回数である2回出現したものが3つある(B+D, C, A)ため、Aと(B+D)を選んでみます。
文字 | 回数 |
---|---|
A | 2 |
B+D | 2 |
そして、この2つを子に持つ木を作ります。 (B+D)はさっき作った木を子として使います。 これを最後まで繰り返して、ハフマン木を作っていきます。
ハフマン木が完成したら左側の節点には0を、右側の節点には1を割り当てます。 すると、各文字が下の表のように表せます。これが各文字の圧縮結果になります。
文字 | 圧縮結果 | 圧縮後のサイズ |
---|---|---|
A | 01 | 2ビット |
B | 101 | 3ビット |
C | 00 | 2ビット |
D | 100 | 3ビット |
E | 11 | 2ビット |
このように出現頻度の大きいデータほどは少ないビット数で表すことができます。(今回はデータの種類が少なかったので、わかりにくかったですが・・・)
最後にHuffman符号化のPythonのコードです。
class Huffman: def __init__(self): self.tree = None self.pattern = None self.encode_dict = {} self.decode_dict = {} def encode(self, data): unique_data = set(data) nodes = [] for v in unique_data: node_obj = Node(value=v, count=data.count(v)) nodes.append(node_obj) temp = [] while len(nodes) >= 2: for v in range(2): elem = min(nodes, key=lambda x: x.count) temp.append(elem) nodes.remove(elem) n = Node(value=None, count=temp[0].count+temp[1].count, left=temp[0], right=temp[1]) temp = [] nodes.append(n) self.tree = nodes[0] self.recursive_code(self.tree, "") s = "" for v in data: s += self.encode_dict[v] return s def recursive_code(self, node, s): #圧縮結果を取得する if not isinstance(node, Node): return if node.value: self.encode_dict[node.value] = s self.decode_dict[s] = node.value return self.recursive_code(node.right, s+"1") self.recursive_code(node.left, s+"0") def decode(self, data): assert(self.decode_dict) result = "" s = "" for bit in data: s += bit if s in self.decode_dict: result += self.decode_dict[s] s = "" return result class Node: #葉を表すクラス def __init__(self, value=None, count=None, left=None, right=None): self.value = value self.left = left self.right = right self.count = count h = Huffman() x = h.encode("AABCCDEEE") print(x, len(x)) d = h.decode(x) print("decoded:", d)