「情報源符号化」で遊んでみた

I enjoyed "source coding".

　情報理論の授業で情報源符号化について扱ったので, プログラムを書いて遊んでみました.
主に優れた符号を扱います.

・情報源記号と符号

表1 情報源記号と符号

情報源記号	発生確率	符号C1	符号C2	符号C3
A	0.60	00	0	0
B	0.20	01	10	10
C	0.15	10	110	110
D	0.05	11	1110	111

　4つの情報源記号{A,B,C,D}の符号C1, C2, C3について, どの符号が優れているのかを検証します. もちろん, どの符号も一意復号可能です. また, C1は等長符号となっています. 符号の良さを表す指標に平均符号長というものがありますので, まずそちらでそれぞれの平均符号長を求めてみましょう. 平均符号長Lは以下で定義されます.

ここで, pは発生確率, lは符号語長を表します. Lは符号語長の期待値とも言えますね. それぞれの平均符号長を求めると,

となります.
　符号化する際できるだけ少ない情報(bit数)で表現できるほうが優れていることからLが小さければ小さいほど良い符号となります. よって, C3の符号が一番優れているということになります.

このことを踏まえ, 実際にC3が優れているのかを今度はプログラムで検証してみました.

・プログラムでの検証

A,B,C,Dを表1の確率で10000文字発生させ, それらを符号化. 長さをカウントするプログラムを作成しました. 結果は次のようになりました.

表2 符号化後のビット数

符号	0の数	1の数	符号語の合計
C1	15413	4587	20000
C2	10000	6619	16619
C3	9508	6619	16127

割合的には平均符号長のまんまとなりました. そりゃそうなるよな, という感じ. 結果としては, C3がもっとも優れた符号ということがわかりました.
　情報源記号については次のような割合となっております.

表3 生成された情報源記号の個数

情報源記号	個数
A	5905
B	2063
C	1540
D	492
合計	10000

rand()はいつも同じ乱数を返すんですね, 知りませんでした.
C++の練習がてら, 作成したわけですが, 数万文字のデータを生成・分析は少し面白いですね.

参考文献

[1] 林田行雄, 「情報理論入門」, ムイスリ出版(2008), pp.19-23.

添付資料

プログラムのソース

Download先(Github) - https://github.com/Yuta-ubiquitous/Codeword/archive/master.zip

#include<iostream>
#include<string>
#include<stdio.h>
#define SETTER 1 //ここでC1=1,C2=2,C3=3を選択

using namespace std;

char makechar();
char* Cnamemaker(int flag);
char* ABCDencorder(char Code, int flag);

int main()
{
int count;
int flag = SETTER;
int A, B, C, D;
int count0, count1;
char s;
errno_t err0, err1;
FILE *stream, *cfile;

count0 = 0;
count1 = 0;
A = 0;
B = 0;
C = 0;
D = 0;

err0 = fopen_s(&stream, "ABCD.txt", "w"); //To open file.
if (err0 == 0)
{
printf("The file was opend\n");
}
else
{
printf("The file was not opend\n");
}

err1 = fopen_s(&cfile, Cnamemaker(flag), "w"); //To open file.
if (err1 == 0)
{
printf("The file was opend\n");
}
else
{
printf("The file was not opend\n");
}

if (stream)
{
for (count = 1; count <= 10000; count++)
{
s = makechar();
fputc(s, stream);
fputs(ABCDencorder(s, flag), cfile);
switch (s)
{
case 'A':
A++;
if (flag == 1) count0 += 2;
if (flag == 2 || flag == 3) count0++;
break;
case 'B':
B++;
count0++;
count1++;
break;
case 'C':
C++;
if (flag == 1)
{
count0++; count1++;
}
if (flag == 2 || flag == 3)
{
count0++;
count1 += 2;
}
break;
case 'D':
D++;
if (flag == 1) count1 += 2;
if (flag == 2)
{
count0++;
count1 += 3;
}
if (flag == 3) count1 += 3;
break;
}
if (count % 50 == 0)
{
fputc('\n', stream);
fputc('\n', cfile);
}
}
fprintf(cfile, "\n0:%d 1:%d sum:%d\nA:%d B:%d C:%d D:%d sum:%d\n", count0, count1, count0 + count1, A, B, C, D, A + B + C + D);
if (stream) //To close file.
{
err0 = fclose(stream);
if (err0 == 0)
{
printf("The file 'stream' was closed\n");
}
else
{
printf("The file 'stream' was not closed\n");
}
}
printf("count=%d\n",count);
}
if (cfile) //To close file.
{
err1 = fclose(cfile);
if (err1 == 0)
{
printf("The file 'cfile' was closed\n");
}
else
{
printf("The file 'cfile' was not closed\n");
}
}
}

char makechar()
{
double sigh = rand()/32767.0;

cout << sigh << endl;

if (sigh < 0.60)
{
return 'A';
}
else if(sigh >= 0.60 && sigh < 0.80 )
{
return 'B';
}
else if (0.80 <= sigh && sigh < 0.95)
{
return 'C';
}
else
{
return 'D';
}
}

char* Cnamemaker(int flag)
{
switch (flag)
{
case 1:
return "C1.txt";
break;

case 2:
return "C2.txt";
break;

case 3:
return "C3.txt";
break;

}
}

char* ABCDencorder(char Code, int flag)
{
switch (Code)
{
case 'A':
if (flag == 1) return "00";
if (flag == 2) return "0";
if (flag == 3) return "0";
break;
case 'B':
if (flag == 1) return "01";
if (flag == 2) return "10";
if (flag == 3) return "10";
break;
case 'C':
if (flag == 1) return "10";
if (flag == 2) return "110";
if (flag == 3) return "110";
break;
case 'D':
if (flag == 1) return "11";
if (flag == 2) return "1110";
if (flag == 3) return "111";
break;

default:
return "\n";
break;
}
}