Wonder Code

プログラミングとか、PCについてが多いかな

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

何番煎じ?と言いたくなるぐらいPythonでやってみた例はたくさんあるけど 勉強に車輪の再発明をするのもよいと思いやってみる。

ハフマン符号 (Huffman encoding)

ハフマン符号はデータを圧縮するための方法の一つ。 HTTP/2とかPNGとかでもつかわれている有名な方法です。 出現の頻度が大きいデータは小さいビット数で表し、 頻度が小さいデータは大きいビット数で表すことでデータを圧縮します。

ハフマン符号 - Wikipedia

例としてAABCCDEEEという文字列をハフマン符号化してみます。

文字の出現回数を求める

まず、この文字列中の文字ごとの出現回数を求めます。

文字 回数
A 2
B 1
C 2
D 1
E 3

ハフマン木を作る

ハフマン木 (Huffman tree)を作ります。 ハフマン木は文字を葉(Node)として使い、 ハフマン木を作るために上で求めた各文字の出現回数を使います。

  1. 葉の中から出現した回数が一番少ないものと2 番目に少ないものを選ぶ。
  2. 1で選んだ2つを子として持つ新たな節点を作り、1で選んだ2つの文字の回数を足した値を格納する。
  3. これを最後の1つになるまで繰り返す。

この例では出現した回数が1番少ないのはBとDの1回です。 なので、BとDを選びます。

文字 回数
B 1
D 1

次に、この2つを子に持ち、2つの回数の合計を持つ、木を作ります。 こんな感じです。 f:id:k_yuya:20180717232703p:plain

表で表すと、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)はさっき作った木を子として使います。 f:id:k_yuya:20180718224227p:plain これを最後まで繰り返して、ハフマン木を作っていきます。

ハフマン木が完成したら左側の節点には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)