第 9 回 情報理論

本日の内容

• 9-1. アイスブレイク
• 9-2. レポート課題
• 9-3. 講義

このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。

9-1. アイスブレイク

本日の属性

手順

1. 全色が揃うように4人前後の班を作る
2. 班ごとに着席する。椅子を動かして机を囲むようにする。（使わない机を動かしても良い）
3. 順番を決める
4. 作成した4枚の用紙に決まった番号を記入する
5. 班員に用紙を名刺代わりに配る
6. 1番から色を付けた属性を含めた自己紹介を1分程度で行う

9-2. レポート課題

ハフマン符号

班で各自の名前を元に下記の通りハフマン符号を作成すること (Excel やプログラミング言語など各自使いやすいツールを使用して良い)

1. 班員の名前をそれぞれローマ字で表し、班員全員の名前のアルファベッ トの頻度を計算する。

   SAKAMOTO NAOSHIだけなら次のようになる

   S	A	K	M	O	T	N	H	I	Total
   2	3	1	1	3	1	1	1	1	14

2. 出現確率を計算します。

   文字	S	A	K	M	O	T	N	H	I	Total
   頻度	2	3	1	1	3	1	1	1	1	14
   確率	0.14	0.21	0.07	0.07	0.21	0.07	0.07	0.07	0.07	1(0.98)

3. 付箋紙に確率とアルファベットを上下に書く。

   0.14

   S

   0.21

   A

   0.07

   K

4. アルゴリズムに従って、小さいペアを選び、確率の合計値を新しい付箋紙 に書き、 すべてのアルファベットが葉になるような木構造を作る
5. 木構造の辺にそれぞれ 0,1 を割り当てていき、根から各アルファベット への道の0,1のラベルの列を、そのアルファベットの符号語とする。

考察課題

以下の事項について、班で取りまとめよ。

1. 自分の名前（ローマ字）を作成したハフマン符号でコード化すること
2. 前回の課題で作成した、モールス符号、ASCII符号、Shift-JIS, UTF-8 などと比べ、符号長が何％短くなったかを計算せよ
3. 世界中で使われる文字を 100万文字と考えることは妥当か？ また、Unicode が 32bit の符号長を持つことの妥当性について考えよ

締切、提出方法

11/20 火曜日の夕方までに <sakamoto@c.dendai.ac.jp>宛に ハフマン符号と、考察課題を取りまとめて一通のレポートを作成し、 メールすること。

9-3. 講義

情報理論

情報とはどのようなものでしょうか？ 知ると有用な情報とは、知らないうちは不確定な事柄です。 これは、確率論の事象に対応します。 つまり、例えば、サイコロを振ったときに出た目は、予めわからないため、 サイコロの出た目は情報になります。 これは、明日の天気、事故の状況など、予めわからないものすべてに当ては まります。

サイコロの目は6通りあります。 したがって、目の情報はまずは6個あります。 しかし、それ以外にも考えられます。 例えば、「偶数の目が出た」というのも、予めはわからないので、これも情 報になります。この情報を得ると、出た目が1,3,5 ではないことが分かるの で、知る前よりは知った後の方が不確定度が減っています。 知る前は6パターンのうちのどれかだったのが、2,4,6 の3パターンのどれか になっています。 つまり、情報を知れば知るほど、事象の各確率が上がることになります。 すべての情報を知るとは、その事象がおきている確率が1になることを意味 します。

サイコロの目に関して、「偶数の目」と「4以上」は共に有用で、それぞれ は事象が半分に絞れますが、合わせると4か6と2個の事象に絞れます。 これは情報量を考えるとき、それぞれの情報は合わせることができるが、純 粋に半分ずつと考えることはできません。 情報量は事象の確率の対数の符号を反転させたものと定義されます。 つまり、確率 $p$の事象$E$ の情報 量$I\left(E\right)$ は $-\log p$ で定義されます。 単位は log の底が 2 の時 bit で表します。

「サイコロの目が偶数」であるという情報量は 1bit です。 「サイコロの目が4以上」も情報量は 1bit です。 「サイコロの目が6」という情報量は次のように計算します。

例えば、256文字が等確率で出現する場合、各文字の情報量は以下のように 8bit になります。

得られる情報量の期待値をエントロピーや平均情報量と言いま す。 n 個の各事象 $E_i$ が起きうる確率分布$P$である時、エントロピー $H\left(P\right)$ は以 下のようになります。

例えば、A,B が試合をして、どちらが勝つかわからない場合、つまり勝率 0.5 の場合の勝敗の持つ情報量のエントロピーは以下の計算により 1bit に なります。

一方、A,B が試合をして、Aが 9割方勝つと分かっている場合、つまりAの勝率 0.9 の場合の勝敗の持つ情報量のエントロピーは以下の計算により 0.5bit を下回ります。 つまり、勝敗を知る価値が半減以下ということになります。

グラフ、木

要素間の接続関係のみに着目することがあります。 その時、要素のことを頂点(vertex)やノード(node)、 接続関係のことを辺(edge)などと呼び、 頂点と辺のみの関係を示すものをグラフと呼びます。

グラフは数学の対象になっており、小学校でも一筆書きや対角線の本数など で触れられています。 アルゴリズムを考えるときによく使われるので、プログラミングを覚える上で重要な数学の範囲になっています。

木の基本用語

しばしば、特定の形状のグラフに対する良いアルゴリズムが考えられます。 最も重要なグラフとして木構造があります。 これは、根という一つの頂点から複数の頂点へ枝分かれしていくのですが、合 流をしないものです。 その中でも特に、枝分かれが一回に高々2本までのを二分木といいます。 根の反対側の終点（枝分かれしない頂点）を葉と言います。 接続している頂点同士で根に近い方を親、遠い方を 子と言います。 頂点から頂点への辺の列を道(path)と言います。

ハフマン符号

文字列を符号化する時、すべての文字に対して同じ長さの符号を対応させるの ではなく、出現頻度の多い文字に短い符号を割り当て、出現頻度の少ない文字 に長い符号を割り当てると、平均符号長を短くできます。 特に、符号長を出現頻度の情報量とすると、平均符号長が文字のエントロピー とできるため、最適な符号になります。

デビッド・ハフマンが1952年に開発したハフマン符号は、エントロピーに対 して最適な符号が得られます。 これは次のアルゴリズムにより得られます。

1. 文字の出現頻度を予め求めておく
2. 各文字を一つの頂点（葉）からなる木とみなし、すべての文字を含む森 を考える。 各木の根には出現頻度の和を対応させ、それを木の出現頻度と考える。
3. 森の中から最小の出現頻度を持つ2つの木を選び、根の頂点を付け足し、 一つの二分木とする。 これを全体が一つの二分木になるまで繰り返す。
4. 完成した二分木の辺に 0 または 1 のラベルを割り当て、根から各文字 （葉）までの符号とする。

このアルゴリズムは JPEGなどの情報圧縮にも使用されます。