ハフマン符号

ハフマン符号とは、符号化する情報の出現頻度に基づいて作成した2分木を使って符号化したエントロピー符号のことです。

また、ハフマン符号は、接頭符号です。

ハフマン符号の手順

例えば、以下の情報をハフマン符号にしてみます。

情報	出現確率
a	0.3
b	0.25
c	0.2
d	0.1
e	0.07
f	0.05
g	0.03

手順1：2分木の作成

まず、最も出現確率が低いg（0.03）とその次に低いf（0.05）を子ノードに持つ新しいノード（0.03+0.05=0.08）を作り、2分木を作ります。

次に残りのa~eとルートノードの中で最も出現確率が低いe（0.07）と次に低いルートノード（0.08）を子ノードに持つ新しいノード（0.07+0.08=0.15）を作り、2分木を作ります。

次に残りのa~dとルートノードの中で最も出現確率が低いd（0.1）と次に低いルートノード（0.15）を子ノードに持つ新しいノード（0.1+0.15=0.25）を作り、2分木を作ります。

次に残りのa~cとルートノードの中で最も出現確率が低いc（0.2）と次に低いb（0.25）かルートノード（0.25）を子ノードに持つ新しいノード（0.2+0.25=0.45）を作り、2分木を作ります。ここでは、bを子ノードにします。

次に残りのaとルートノードの中で最も出現確率が低いルートノード（0.25）と次に低いa（0.3）を子ノードに持つ新しいノード（0.25+0.3=0.55）を作り、2分木を作ります。

最後に、2個のルートノードを子ノードに持つ新しいノード（0.55+0.45=1）を作り、2分木を作ります。このようにして作った.木.をハフマン木と呼びます。

手順2：符号の割り当て

以下のように、ハフマン木のエッジに0と1を割り振ります。例えば、上のエッジを0、下のエッジを1とします。

ルートノードからそれぞれのアルファベットまでたどり、経路上の0と1を拾って以下の表の符号列のように並べます。

情報	出現確率	符号
a	0.3	01
b	0.25	11
c	0.2	10
d	0.1	001
e	0.07	0001
f	0.05	00001
g	0.03	00000

なお、上記の例では、出現確率を使って2分木を作りましたが、出現頻度を使っても大小関係は変わらないため、同じ結果になります。