ハフマン符号化とは？②
参考リンク
さて、前回の①では
A…「00」
B…「01」
C…「10」
D…「11」
っていう、「0」「1」の割り当て規則の元で
「ABADAACB」は「00 01 00 11 00 00 10 01」という
16ビットに置き換えられることを書いた。
その上で、この文字列をもっと少ないビット数で
表せないかを考えたけど、それぞれのアルファベットに
下手な「0」「1」の割り当て規則を与えてしまうと、
一意に送信文字列を決められない問題があったよね。
さて、それじゃどういう「0」「1」の割り当て方が
全体で少ないビット数になり、文字列が一意に送信できるのだろうか？
ハフマン符号は、それに対する一つの有効な解決法なんだけど
この手法の着眼点は
- 出現確率の高いアルファベットには、短い「0」「1」を割り振り
- 出現確率の低いアルファベットには、長い「0」「1」を割り振る
事によって、全体のビット数を削減しようってことなんだな。
例えば以下の割り当て規則を考えてみよう。
A…「0」
B…「10」
C…「110」
D…「111」
この時「ABADAACB」は
「0 10 0 111 0 0 110 10」と、14ビットで表せて
最初の16ビットの例から、2ビットの圧縮が可能になる。
さらにこの割り当て規則であれば、
上記のビット列からきちんと一意に
「ABADAACB」に戻せるのが確認できるだろう。
それじゃ、どうやってこの「0」「1」の割り当て規則を
自動的に生成すればいいのか？
とりあえず、さっきも書いたけど
それぞれのアルファベットの「出現確率」に注目してみよう。
「ABADAACB」で各アルファベットの出現確率は以下のようになる。
A…4/8
B…2/8
C…1/8
D…1/8
さて、これらの確率の中で小さい物を二つ選んでみよう。
今の場合、CとDが該当するよね。
ここで、下のように該当する組を線で結んであげよう。
なお、それぞれの文字には出現確率が割り当てられていて、
結んでできたところに対しては、その出現確率を足していくことにする。
_⊥_
｜ ｜ ｜２｜
Ａ Ｂ Ｃ Ｄ
４ ２ １ １
さて、これで
Ａ→４、Ｂ→２、ＣＤ→２となったわけだが(分母は共通してるので省略)、
この「小さい物を二つ選ぶ」作業を繰り返す。
って事で次は、BとCDを選ぶ。
__⊥__
｜ ４ _⊥_
｜ ｜ ｜２｜
Ａ Ｂ Ｃ Ｄ
４ ２ １ １
そうすると今度は、Ａ→４、ＢＣＤ→４となった。
最後にこの二つを結ぶと
___⊥___
｜ ８ __⊥__
｜ ｜ ４ _⊥_
｜ ｜ ｜２｜
Ａ Ｂ Ｃ Ｄ
４ ２ １ １
これで、すべてのアルファベットがつながった。
この一番上から下に行く事を考えるんだけど
左に行くたびに「0」、右に行くたびに「1」を与えてあげると
A…「0」
B…「10」
C…「110」
D…「111」
となるのがわかるだろうか？
そう、たったこれだけなのだ。
こんな単純な作業(2つの小さい出現確率を結んであげる)だけで、
圧縮効果があって、かつ一意に元に戻せる
「0」「1」割り当て規則の生成が可能なのである。
もっとも今の例の場合、たかだか2ビットしか削減ビット数がないけれど
もっと長い文字列を扱う場合、かなりの圧縮効果が出てくるんだよね。
さて、実はこのハフマン符号化って
「通信」を考えると、非常に痛い弱点があるんだけど
それを次の③では説明しよう。
