14.6.2. 可変長符号化

平均情報量を議論したときのイベントを、bit 列で符号化することを考えます。 このときうまく符号化したときの、平均符号長の下限が平均情報量で与えられます。

符号化と平均符号長 #

イベントとして、出席、欠席、遅刻、早退を考え、これを符号化します。 4通りなので2bitで普通に符号化すると、たとえば以下のようになります。

この場合ははどのイベントも 2bit で表現されます。これを等長符号と呼びました。

2bitより短く符号化できるでしょうか? 確率が偏っている場合は可能になります。 たとえばそれぞれの確率が 1/2, 1/4, 1/8, 1/8 のときに以下の表で符号化したとします。

この符号化では、イベント毎に符号長が異なります。等長符号に対して可変長符号と呼びました。 可変長符号の符号長を測る指標として、確率で期待値をとった平均的な符号長 平均符号長 を考えます。 \( 1/2 \cdot 1 \text{bit} + 1/4\cdot 2 \text{bit} + 1/8 \cdot 3 \text{bit} + 1/8 \cdot 3 \text{bit} = 1.75 \text{bit} \)

\( 1.75 < 2\) と、等長符号より短くすることができました。

このような工夫で、平均符号長をどこまで短くできるでしょうか?

復号可能性と木の表現 #

短い符号化を検討するうえで、 前提を明確にします。まず復号できるものに限定します。

さらに一意に復号できる符号の中で 即時に復号できる符号化を考えます。これはどの符号も、より長い符号の冒頭に重なっていないという意味です。

上記で示した二つの符号化方法を、木で示します。 符号の復号は、黒丸で示した木の根から、0または1に対応して枝を選択し分岐し、到達した葉のイベントを得ることに相当します。符号化は、対応する葉に根から向かう枝のラベルを順に並べたものです。

stateDiagram-v2
    state "?" as s0
    state "?" as s1
    state "出席" as s00
    state "欠席" as s01
    state "遅刻" as s10
    state "早退" as s11
	[*] --> s0 : 0
	[*] --> s1 : 1
	s0 --> s00 : 0
	s0 --> s01 : 1
	s1 --> s10 : 0
	s1 --> s11 : 1

stateDiagram-v2
    state "出席" as s0
    state "?" as s1
    state "欠席" as s10
    state "?" as s11
    state "遅刻" as s110
    state "早退" as s111
	[*] --> s0 : 0
	[*] --> s1 : 1
	s1 --> s10 : 0
	s1 --> s11 : 1
	s11 --> s110 : 0
	s11 --> s111 : 1

情報源符号化定理 #

前節で学んだ情報理論の平均情報量は、平均符号長の下限を与えます。
どちらも平均がついて紛らわしいですが、平均情報量と平均符号長を意識して区別してください。前者は、確率から決まる理論的な量、後者は人が自由に決めた符号化方法の性質です。

出席簿の例では、もし出席、欠席、遅刻、早退、が全て等確率なら、
平均情報量は \(-4\cdot(1/4)\log_2(1/4) = －\log2_2(-2) = 2\) です。
つまり、それぞれを 2bit で符号化する単純な等長符号が、最善で改善の余地がありません。

確率が偏った 1/2, 1/4, 1/8, 1/8 の例では、平均情報量は減少し 1.75 となります。 \( H = \left( \left(-\frac{1}{2}\log_2\frac{1}{2}\right) + \left(-\frac{1}{4}\log_2\frac{1}{4}\right) + 2\cdot\left(－\frac{1}{8}\log_2\frac{1}{8}\right) \right) = 1.75 \)

一方で、上の例で上げた可変長符号化方法の平均符号長は 1.75 でした。 平均情報量と一致していることから、最善の符号化の一つとがわかります。

平均情報量が平均符号長の下限を与えることが証明できますが、平均符号長がぴったり平均情報量であるような符号化の方法が常に存在するとは限りません。 出席簿やサイコロを振ることのように同じ試行を多数回繰り返す場合は、平均情報量にいくらでも近い平均符号長での符号化が実現できます。この事実は Shannon によって示されました。

英字アルファベットの文字列の符号化を考えます。 素直な方法は、アルファベットの`a`, `b`, .., `z`のそれぞれが出席簿の「出席」などのイベントに相当するようにbit列を割り当てます。 別の方法として、通常のアルファベットを2文字並べた `aa`, `ab`, `ac`, .., `az`, `ba`, `bb`, ..., `zz` という仮想的な文字を想定して、文字列をこの2文字ずつの並びと解釈し、それぞれを符号化することもできます。 後者の方が面倒ですが、多くの場合は効率の良い符号化になります。人の使う文字は前後で関連があり、確率が偏るためです。

情報理論の概念については、正確な説明は教科書や参考書籍で確認してください。

Huffman 符号化 #

良い符号化方法を自動で計算する手順として、Huffman 符号化を紹介します。 アイデアは「出現頻度の高い文字には短い符号を、出現頻度の低い文字には長い符号を割り当てる」ことです。

手順は、符号を割り当てる対象の文字と頻度を得たうえで、

• 出現頻度の低い順に文字を2つ選び、「両者のどちらか」を意味する仮想的な文字で置き換える。この操作で対象の文字は、2文字減って1文字増えるので、差し引き文字数は1減る。
• 1文字になるまで、上記の手順を繰り返す。
• 2文字をまとめたペア毎に、仮想的な文字を親、それぞれを子として辺で結び、辺に0または1を割り当てる。 その結果、全体が木となる。

具体例で A, B, C, D, E という 5 つのアルファベットからなる文字列 AEEADACDEBCDAAE を符号化します

1. 各文字の出現頻度を数える。今の場合 A が 5 回、B が 1 回、C が 2 回、D が 3 回、E が 4 回であった。
2. 出現頻度が最も低い2文字 `B`, `C` に着目し、それらを子とする木を描き、辺に `0`, `1` を割り当てる。以後は`B`や`C`の代わりに `B`または`C` という意味の仮想的な文字を考え `BC` と表記する。その出現頻度は、それぞれの和である。

   stateDiagram-v2
       state "BC (2)" as bc
       state "B (1)" as b
       state "C (2)" as c
   	bc --> b : 0
   	bc --> c : 1
   

3. 残りの文字で出現頻度が最低の2文字 `BC`, `D` に着目し、それらを子とする木を描く。このとき仮想文字 `BC` は対応する木を持つので、木に木をつなげる。また以後は、`BCD` をひとまとめにした仮想的な文字を考える。

   stateDiagram-v2
       state "BCD (6)" as bcd
       state "D (3)" as d
       state "BC (2)" as bc
       state "B (1)" as b
       state "C (2)" as c
   	bcd --> d : 0
   	bcd --> bc : 1
   	bc --> b : 0
   	bc --> c : 1
   

4. 出現頻度が低い順に A, E を取り出し、A と E を子とする木を描く。以降、`AE` はひとまとめにして考える。

   stateDiagram-v2
       state "AE (2)" as ae
       state "A (5)" as a
       state "E (4)" as e
   	ae --> a : 0
   	ae --> e : 1
   

5. 出現頻度が低い順に `AE`, `BCD` を取り出し、これらを子とする木を描く。

   stateDiagram-v2
       state "AE (2)" as ae
       state "A (5)" as a
       state "E (4)" as e
   	ae --> a : 0
   	ae --> e : 1
       state "BCD (6)" as bcd
       state "D (3)" as d
       state "BC (2)" as bc
       state "B (1)" as b
       state "C (2)" as c
   	bcd --> d : 0
   	bcd --> bc : 1
   	bc --> b : 0
   	bc --> c : 1
   	[*] --> ae : 0
   	[*] --> bcd : 1
   

6. 根から葉までの辺のラベルの列が、その文字の符号。これを使うと、文字列が `AEEADACDEBCDAAE` なら `000101001000111100111011110000001` の33 ビットとなる。

   | A | B | C | D | E | |:--:|:---:|:---:|:--:|:--:| | 00 | 110 | 111 | 10 | 01 |

何を入力の文字と定めるかは任意なので、 Huffman 符号化をディジタルデータの圧縮に用いることもできます。 その場合は、符号化後の表現だけでなく、 符号化の方法も含める必要があります。