第 4 回 情報理論

本日の内容

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

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

4-1. アイスブレイク

本日の属性

手順

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

4-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のラベルの列を、そのアルファベットの符号語とする。

文字符号（個人、宿題？）

自分の名前をディジタル符号化する。 以下のそれぞれのフォーマットで、自分の名前をディジタル符号にすること。 なお、それぞれの符号において、ローマ字表記などの英字、ひらがな、漢字 表記など、表記法を別々に選んで良い。 （モールス符号、ASCIIはローマ字、Shift_JIS, UTF-8 は漢字など）。 基本は0,1で表すこととするが、煩瑣な場合は16進法の記法も許す。

1. モールス符号（・ー空白で表す）
2. ASCII符号
3. 日本人はShift_JIS(MS漢字コード)、外国人はShift_JISあるいは母国語用 の文字符号方式がある場合は、その符号方式名(ISO-8859-1, BIG5, EUC-KRなど)を挙げ、その符号方式で符号化する
4. UTF-8

考察課題

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

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

締切、提出方法

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

4-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などの情報圧縮にも使用されます。

文字の符号化

日本語に使われている文字は一般には10万文字以上だと言われています。 しかも、中学校までで学校で習う範囲で考えても、日本独自の文化である漢文の返 り点など、今でも一般的なワープロで書くことが困難な表記がまだまだあり ます。

文字表記にも優先すべき文字とそうでない文字があり、 JIS規格では優先順位で第一水準、第二水準、第三水準、第四水準が定めら れています。 現在はコンピュータにおいて、第二水準までは必ず使用でき、第四水準まで も使用できます。 但し、第四水準まででも11,233文字までしか収録できてなく、地名や人名な どで収録できていない文字もあります。 例えば「わたなべ」という姓名には「渡辺」の他にも「渡邉」「渡邊」など もあり、第四水準でも複数ありますが、使われている表記すべてが収録され ているわけではありません。

通信に使う文字表記にはいくつかの規格があります。 歴史的に電気通信で広く使われたものとして「モールス符号」があります。 これは、文字を単音と長音の二種類の音の組み合わせで表現するものです。 Aは「・ー」Bは「・ー・ー」などと表します。 近年まで、無線技師の試験の必須項目でもありましたが、現在は試験項目か らも外されるようになってきて、廃れていく状況です。

コンピュータでは当初は数字だけが計算できればよかったのと、メモリーが 当初は高額だったので、10進数が扱えるように4bit(2⁴=16)や、 数字(10)、英字(26 or 26✕2)に必要な6bit(2⁶=64), 7bit(2⁷=128)の文字コードが使われました。 大昔は大文字しか使えないコンピュータもあった名残で、今のWindowsパソ コンでもファイル名で大文字と小文字を区別しないで使えるようになってい たりします。

7bit の文字コードで今でも最も重要なのは ASCII コードです。 これには、数字、英大文字、英小文字が含まれています。

コンピュータはアメリカで発展し、また、当初メモリーが高価だったことも あり、 20世紀では、主にコンピュータで使用できる文字は英字＋一言語でした。 コンピュータで使用する情報の単位として1Byteが 8bitになっていった過程で、文字コード表の前半の128個がASCII、残りの 128個に一言語を割り当てる文字コードが使われました。 ISO-8859 はその規格で、ISO-8859-1 は西ヨーロッパ言語の文字拡張がされ ていました。 JIS X 0201はカタカナを埋めていました。

ISO-2022 は7bitの可変長の文字コード体型で、しかも ASCII と共存できる ようになっていました。 ISO-2022-JP は複数バイト で漢字も表現できるようになっていました。 ただ、これを実現するために、文字コードの中に制御文字が必要なため、文 字列の途中から見たとき、特定のバイトが漢字コードなのか ASCIIコードな のかの判定ができませんでした。 ただ、電子メールは古くから7bitで運用されていたのと、ISO-2022 は広く世 界の言葉を含んでいたので、過去においては電子メール用の国際文字コード として使われていました。

マイクロソフトは、8bitコードの後半は2byteの文字コードとするMS漢字コー ドを考案し、JIS第二水準までの文字を表現できるようにしました。 これは、SJISなどという名前で広まり、1997年に正式にShift_JISとして規 格化されました。 Windowsや 組込系などの小さなシステムでの漢字表記などでは、今でも使用されていま す。

「英字＋一言語」という枠組みから抜けて、 国際的な枠組みですべての文字を包括するために、UNICODE が定められまし た。 これは、多バイト文字ですが、用途により表現法がいくつか定められました。

UTF-7

電子メールのために制定された7bit表記。セキュリティホールの原因に もなったため、現在使用が廃れている

UTF-8

ASCII文字と共存できる可変長他バイト文字表現。通信でよく使われる。

UTF-16

よく使う文字を16bitに収める可変長文字表現。Javaなどの内部表現で使 用される

UTF-32

すべてを32bitで表現する固定長の文字表現。メモリ効率が悪いので記憶 や通信では使用されないが、プログラム中では処理しやすいため使われる こともある。

現在では多くのOSでUNICODEが使用されている。