Huffman符号 - 曖昧

ハフマン符号とは，1952年にデビッド・ハフマンによって考案された符号化手法です．対象のデータの出現する値の偏りによって割り当てるビット数を変更することで冗長性を排除する手法です．ハフマン木と呼ばれる木構造のデータを構築することでエンコードし，根から葉へ辿ることでデコードできる仕組みになっています．

非常に古い手法ですが，今でもバリバリ現役で使用されている手法です．

ハフマン木

ハフマン符号化において重要かつ，難しいのは木を構築する部分です．これを説明します．ハフマン木を構築する流れは以下のようになっています．

対象データから，各値の出現頻度を求め，出現テーブルを作る ↓ 出現テーブルの中から最も出現頻度の低い２つの値を取り出し，その二つをまとめて一つの木にする． ↓ 二つの合計値を新たに対象データの出現テーブルに加える ↓ 出現テーブルのデータが全て取り出されるまで繰り返す

というようになっています．

例えばテキストデータを対象に A:8 B:2 C:7 というような出現テーブルが作れた場合，まず出現頻度の最も低いB,Cが取り出されて木になります．

f:id:attox:20180721163810p:plain

二つを合計したデータとして一時的にαという記号を使用しています．

これにより，テーブルは次のように更新されます． A:8 α:9

同じように取り出して木を作ると f:id:attox:20180721163736p:plain

このようになり，ハフマン木の完成です．

デコードは，rootからノードをたどっていくのですが，例えば，右のノードに１，左のノードに０を追加していくように設定すると(これはどちらでも良いがエンコードとデコードで合わせる必要がある)

f:id:attox:20180721163755p:plain

このように割り当てられて，各値は次のようにエンコードされたことがわかります．

A:1 B:00 C:01

三文字しかないデータで例を表してしまったため，いまいち効果を実感しにくいですが，一番多く出ている値Aに一番小さいビットが当てられています．

ハフマン符号の理論的な部分はこのように非常に簡単なものになっています．

実装

ハフマン符号はの実装方法には色々とあるのですが，今回は理論通りに実際に木構造を生成してエンコードする方法をやっていこうと思います．まずは，各値を表すノードの宣言を行います．pythonにおいて構造体を表すには，ディクショナリでよいみたいなことを聞いたのですが，色々都合がいいのでメソッドを持たないオブジェクトを作ることにします．

class Node:
    def __init__(self, code, count=0, left=None, right=None, parent=None):
        self.key = count
        self.code = code
        self.count = count
        self.left = left
        self.right = right
        self.parent = parent
        self.bitcode = ''

ハフマン木の生成は一つのオブジェクトにします．

class HuffTree:
    def __init__(self):
        self.histgram = {}
        self.leaf = {}
        self.root = None

    def makeHistgram(self, f):
        data = f.read()
        for c in data:
            if c not in self.histgram.keys():
                self.histgram[c] = 1
            else:
                self.histgram[c] += 1

    def makeTree(self):
        pq = nodepq.PriorityQueue()
        for k in self.histgram.keys():
            pq.push(Node(k, self.histgram[k]))

        while True:
            x = pq.pop()
            if x.left == None and x.right == None:
                self.leaf[x.code] = x

            if pq.empty():
                break

            y = pq.pop()
            if y.left == None and y.right == None:
                self.leaf[y.code] = y

            node = Node(None, x.count+y.count, x, y, None)
            x.parent = y.parent = node

            pq.push(node)

        self.root = x

    def encode(self, node, bitcode=''):
        if node.code != None:
            node.bitcode = bitcode
        else:
            self.encode(node=node.left, bitcode=bitcode+'0')
            self.encode(node=node.right, bitcode=bitcode+'1')

    def decode(self, node, bitcode):
        if bitcode == '' and node.code == None:
            return -1
        elif bitcode == '' and node.code != None:
            return node.code
        else:
            if bitcode[0] == '1':
                return self.decode(node.right, bitcode[1:])
            elif bitcode[0] == '0':
                return self.decode(node.left, bitcode[1:])

makeHistgramメソッドはファイルのデータを読み込んで，出現したデータがテーブルの中に存在していなかったら追加し，存在していたらデータの数を増やしていく処理をしています．

makeTreeメソッドが一番キモになっているメソッドで，ハフマン木を実際に構築しています．まずプライオリティーキューを用意します．これは具体的なアルゴリズムはここでは説明しませんが，キューに追加したデータから，一番小さいものを取り出すことができます．今回の場合，追加するデータは複数のデータを持つ構造体であるため，出現回数をキーとしてキューの中でソートするように少し改造しています．あとは単純で，取り出して枝を設定して，再度キューに追加する，ということをデータが最後の一つになるまで繰り返しています．

encode,decodeは再帰処理を行って，上記理論で説明したようなことをそのまま行っています．

tree = HuffTree()
    with open(<符号化の対象ファイル>, 'rb') as f:
        tree.makeHistgram(f)
    tree.makeTree()
    tree.encode(tree.root)

    print(tree.histgram)
    for k in tree.leaf:
        print('{} -> {}'.format(chr(k), tree.leaf[k].bitcode))

こんな感じでmainをかくと符号化されたコードが出てきます．対象ファイルデータ AAAAAAAAABBBBBBCCCCCCCCAAAAAAABCBC AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABCBABC