情報源符号化はデータ圧縮ともよばれ、一定の確率法則に従って生成される情報を少ない記号で表現する方法について考えます。
情報源符号化には送信者と受信者という二人の登場人物が登場します。電報のように送信者と受信者は異なる地点にいる異なる人間である場合もあれば、ファイル圧縮の場合は過去の自分と未来の自分という時間的に離れた同一人物が対応する場合もあります。
情報源は情報源記号とよばれる情報源記号 \(\mathcal{X}\) とその確率分布 \(p(x)\) により定義されます。情報源記号は電報であればアルファベットやカタカナに対応します。\(\mathcal{X}\) と \(p(x)\) は送信者と受信者はお互い知っているものとします。
まず、\(p(x)\) をもとに、各情報源記号に対応する符号を割り当てます。たとえば、「A」は「・－」、「B」は「－・・・」というような要領です。この符号化についての取り決めはあらかじめ送信者と受信者の間で共有されます。符号化の段階では、確率分布 \(p(x)\) は知っていますが実際に送信するメッセージは判明していないことに注意してください。「・」や「－」など符号に使われる記号を符号アルファベットといいます。情報理論では符号アルファベットには「0」「1」が使われることが多いです。
次に、送信者と受信者は地理的または時間的に分かれて簡単に情報のやりとりができないようにします。送信者はこの段階で \(p(x)\) にしたがって送信するべき情報、すなわち情報源記号の列 \(x_1, x_2, \cdots, x_n\) を観測します。送信者は取り決めた符号化方法に基づいてこの列を符号アルファベットの列 \(w_1, w_2, \cdots, w_l\) に変換し、受信者に送信します。受信者は \(w_1, w_2, \cdots, w_l\) のみを受信し、ここから元のメッセージを推測します。
このとき、受信者が正しくメッセージを復元できることと、送信する符号が短くすることが重要です。そのようにするにはどのように符号化の取り決めをすれば良いかを考えるのが情報源記号化の問題です。
繰り返しになりますが、符号化の取り決めの時点では具体的なメッセージは判明していないことに注意してください。メッセージは「SOS」であるとあらかじめ分かっているのであれば、「SOS」を一文字で符号化すれば非常に短い符号化が実現できますがこれは意味がありません。「FINE」や「WAIT」やその他さまざまなメッセージを送る可能性もあることを想定して符号化を決めなければなりません。\(p(x)\) に従って観測されるメッセージの符号の平均的な長さが短いほど良い符号化方法であるといえます。
これまでの説明でも何度も出てきましたが、モールス信号は情報源符号化の代表的な例です。
欧文モールス信号では、情報源記号は \(\mathcal{X} = \{A, B, C, \dots, Z\}\) で符号化アルファベットは「・」「－」「（空白）」の三種類です（情報源記号として数字やピリオド・カンマなどを含める場合もあります。）。空白記号は見落としがちですが、必要であることに注意してください。たとえば、「・ー」という列が「・」「ー」（ET）という二記号であるのか「・ー」(A) という一記号であるのかを区別する必要があります。
\(p(x)\) は通信中に現れるアルファベット記号の確率を表します。たとえば、英文では E, T, A の頻度が高く、X, Q の頻度が低いことが知られています。モールス信号ではこの事実を反映して、E: 「・」、T: 「－」、A: 「・ー」は短く、X: 「－・・－」、Q: 「－－・－」は長く符号化されています。これにより、平均的に符号長が短くなるようになっています。
ファイル圧縮も情報源符号化の代表的な例です。
圧縮前のファイルがオリジナルのメッセージ、圧縮後のファイルが符号語に対応します。圧縮前のファイル（オリジナルのメッセージ）が手元に無くても、圧縮後のファイル（符号語）さえあれば、解凍プログラムにより圧縮前のファイル（元のメッセージ）を復元ができます。
ファイル圧縮は多くの場合、情報源記号も符号化アルファベットも「0」「1」の二種類です。テキストファイルなどでは情報源記号が \(\mathcal{X} = \{A, B, C, \dots, Z\}\) やアスキー文字全体となる場合もあります。
符号化や復号化の方法はモールス信号のような単純な置き換え規則ではなく、圧縮プログラム・解凍プログラムで定義されます。
\(p(x)\) は圧縮プログラムに入力されるファイルの確率です。ファイルには膨大なパターンがあるので、この分布を厳密に求めることはできません。しかし、テキストファイルやプログラムファイルには E, T, A などの文字が多く登場することが期待でき、画像ファイルでもでたらめなパターンよりは同じ記号が連続して登場することが期待できます。このような確率のムラの構造を利用して、高い確率のパターンに短い符号語を与えることで、平均的に容量の小さいファイルに圧縮できます。このため、逆に言うと、いくら優秀な圧縮プログラムであっても事前に想定していないようなデタラメなファイルを入力すると全く圧縮されません。
試しに簡単な符号を設計してみましょう。
あなたは、南極の探検家で、これから南極に渡航して毎日の天気を本国に送信するとします。天気は晴れ・曇り・雨・雪の四種類とします。どのように天気の情報を送信すればよいでしょうか。符号アルファベットは「0」「1」とします。
この場合、情報源は南極の天気です。情報源記号は晴れ・曇り・雨・雪の四種類です。情報源の確率分布は南極での天気の分布です。南極では、晴れの日がほとんどで、次いで曇りの日があり、雪の日はあまりなく、雨の日はまずないとします。
符号化に使える記号が 2 種類で、情報源記号が 4 種類なので、各情報源記号を 2 文字でも符号化することが考えられます。
晴れ: 00
曇り: 01
雨: 10
雪: 11
晴れの日がほとんどだという事実を用いて、晴れには短い符号を割り当てることとします。
晴れ: 0
曇り: 10
雨: 110
雪: 111
実際に南極に行って観測すると、天気は晴れ、晴れ、晴れ、晴れ、曇り、晴れ、晴れ、晴れ、晴れ、晴れ、曇り、晴れ、晴れ、雪、晴れ、晴れ、だったとします。このとき、それぞれの符号化方法で送信する情報は以下のようになります。
ケース1: 00000000010000000000010000110000
ケース2: 00001000000100011100
ケース 1 では、メッセージの大半である晴れに 2 文字割いているので長くなってしまっています。一方、ケース 2 では、雪に 3 文字を割り当てていますが、登場することは滅多にないので、晴れに 1 文字しか割り当てていないという事実が効いてきて全体として短くなっています。この点、ケース 2 の方が優れた符号化方法であるといえます。
以降の章では、情報源記号は独立同分布 (i.i.d.) に従って生成されるとします。すなわち、生成される情報源記号 \(x_1, x_2, \cdots, x_n\) のうち \(x_i\) と \(x_j ~(j \neq i)\) は独立であり、周辺分布は同じであるということです。雨の日の次の日は雨となりやすかったり、「Q」の次には「U」が来やすかったりと、現実の情報源は独立でないことが多いですが、独立でない情報源を扱うにはさまざまな追加の議論が必要となってしまいます。基本的で重要な内容については、独立の場合の符号化に含まれているので、このシリーズでは基本的な内容に集中することとします。独立でない情報源については別の記事で扱う予定です。
また、以降は符号アルファベットは「0」と「1」の二種類とします。符号アルファベットを三種類以上にするのは難しくありません。ですが、表記が複雑になってしまうため、簡単のため二種類とします。
- 情報源符号化は一定の確率分布に従う記号列を短く表現することをめざす
- 圧縮した表現（符号）から元の情報が復元できることと、表現が平均的に短くなることが重要
- モールス信号やファイル圧縮が代表的な応用例
