3夜連続で自分の人生やり直し中です。
夢で自分の人生小学生からやり直してます。最近自分の見たい夢を高確率で見られるようになる謎の技術を身につけました。
昨日の人生が一番サクセスしてたな。あの時こうしときゃよかったとか、人生の選択を色々と変えられるのは楽しいです。
まぁ目が覚めれば現実に引き戻されますが。あぼーん。
そして前で展開されている半導体工学、授業もうちょっと何とかならんかね…
眠くてたまらん…
おっと、手が滑った…
#include <stdio.h>
#define SAMPLE_MAX 27
int len;
void init(char ch[SAMPLE_MAX], double probability[2 * SAMPLE_MAX - 1],
int parent[2 * SAMPLE_MAX - 1], int left[2 * SAMPLE_MAX - 1],
int right[2 * SAMPLE_MAX - 1]);
void encode(int huff, int size, int parent[2 * SAMPLE_MAX - 1]);
double ave(double probability[2 * SAMPLE_MAX - 1], int length[SAMPLE_MAX]);
int main(void)
{
int i, j, num1, num2, size;
double min;
char ch[SAMPLE_MAX];
double probability[2 * SAMPLE_MAX - 1];
int parent[2 * SAMPLE_MAX - 1], left[2 * SAMPLE_MAX - 1],
right[2 * SAMPLE_MAX - 1], length[SAMPLE_MAX];
/* 初期化 */
init(ch, probability, parent, left, right);
size = SAMPLE_MAX;
/* 最初にどのようなデータを使用するのか見せておく */
printf("ch:probability\n");
for (i = 0; i < size; i++)
printf(" %c: %7lfn", ch[i], probability[i]);
/* 確率の小さいもの2つをまとめ続ける */
while (1)
{
/* 解析の終わった符号には負数のフラグを予め立ててある */
/* 一番小さい数を探す */
for (i = 0; i < size; i++)
if (probability[i] >= 0) break;
/* ここにヒットしたら、解析が終了している(頻度リストが空) */
if (i == size) break;
/* 仮の最小値をセット */
num1 = i;
min = probability[num1];
while (i < size)
{
/* さらに小さい数があればそれをセット */
if (probability[i] < min && probability[i] >= 0)
{
min = probability[i];
num1 = i;
}
i++;
}
/* 二番目に小さい数を探す */
for (i = 0; i < size; i++)
if ((probability[i] >= 0) && (i != num1)) break;
/* 頻度リストが1つしかない */
if (i == size) break;
/* 仮の最小値をセット */
num2 = i;
min = probability[num2];
while (i < size)
{
/* さらに小さい数があればそれをセット */
if (probability[i] < min && probability[i] >= 0 && i != num1)
{
min = probability[i];
num2 = i;
}
i++;
}
/* ハフマン木に登録 */
/* left, rightは復号化しなければ必要ないかも */
left[size] = num1;
right[size] = num2;
parent[num1] = size;
parent[num2] = -size;
probability[size] = probability[num1] + probability[num2];
probability[num1] = probability[num2] = -1;
size++;
}
/* 結果出力 */
printf("----result----\n");
for (i = 0; i < SAMPLE_MAX; i++)
{
printf(" %c: ", ch[i]);
len = 0;
encode(i, size, parent);
length[i] = len;
for (j = 0; j < 15 - length[i]; j++)
printf(" ");
printf(": length = %d\n", length[i]);
}
printf("--------------\n");
printf("average code length: %lf\n", ave(probability, length));
}
/* 平均長を求める かなりやっつけ */
double ave(double probability[2 * SAMPLE_MAX - 1], int length[SAMPLE_MAX])
{
double ave_length = 0.0;
double pro_ori[SAMPLE_MAX];
int i;
pro_ori[0] = 0.0642;
pro_ori[1] = 0.0127;
pro_ori[2] = 0.0218;
pro_ori[3] = 0.0317;
pro_ori[4] = 0.1031;
pro_ori[5] = 0.0208;
pro_ori[6] = 0.0152;
pro_ori[7] = 0.0467;
pro_ori[8] = 0.0575;
pro_ori[9] = 0.0008;
pro_ori[10] = 0.0049;
pro_ori[11] = 0.0321;
pro_ori[12] = 0.0198;
pro_ori[13] = 0.0574;
pro_ori[14] = 0.0632;
pro_ori[15] = 0.0152;
pro_ori[16] = 0.0008;
pro_ori[17] = 0.0484;
pro_ori[18] = 0.0514;
pro_ori[19] = 0.0796;
pro_ori[20] = 0.0228;
pro_ori[21] = 0.0083;
pro_ori[22] = 0.0175;
pro_ori[23] = 0.0013;
pro_ori[24] = 0.0164;
pro_ori[25] = 0.0005;
pro_ori[26] = 0.1859;
for (i = 0; i < SAMPLE_MAX; i++)
ave_length += (double)(pro_ori[i] * length[i]);
return ave_length;
}
/* ハフマン符号化 */
void encode(int huff, int size, int parent[2 * SAMPLE_MAX - 1])
{
if (huff == size - 1) return ;
if (parent[huff] < 0)
{
encode(-parent[huff], size, parent);
printf("1");
len++;
}else{
encode(parent[huff], size, parent);
printf("0");
len++;
}
}
/* データの初期化 もっとスマートな方法ないかな? */
void init(char ch[SAMPLE_MAX], double probability[2 * SAMPLE_MAX - 1],
int parent[2 * SAMPLE_MAX - 1], int left[2 * SAMPLE_MAX - 1],
int right[2 * SAMPLE_MAX - 1])
{
int i;
for (i = 0; i < (SAMPLE_MAX - 1); i++)
ch[i] = 'A' + i;
ch[i] = ' ';
for (i = 0; i < (SAMPLE_MAX + 2); i++)
left[i] = right[i] = parent[i] = 0;
probability[0] = 0.0642;
probability[1] = 0.0127;
probability[2] = 0.0218;
probability[3] = 0.0317;
probability[4] = 0.1031;
probability[5] = 0.0208;
probability[6] = 0.0152;
probability[7] = 0.0467;
probability[8] = 0.0575;
probability[9] = 0.0008;
probability[10] = 0.0049;
probability[11] = 0.0321;
probability[12] = 0.0198;
probability[13] = 0.0574;
probability[14] = 0.0632;
probability[15] = 0.0152;
probability[16] = 0.0008;
probability[17] = 0.0484;
probability[18] = 0.0514;
probability[19] = 0.0796;
probability[20] = 0.0228;
probability[21] = 0.0083;
probability[22] = 0.0175;
probability[23] = 0.0013;
probability[24] = 0.0164;
probability[25] = 0.0005;
probability[26] = 0.1859;
}
おっと、実行結果も手が滑ったぁ!!
/Users/user/huffman% ./huffman
ch:probability
A: 0.064200
B: 0.012700
C: 0.021800
D: 0.031700
E: 0.103100
F: 0.020800
G: 0.015200
H: 0.046700
I: 0.057500
J: 0.000800
K: 0.004900
L: 0.032100
M: 0.019800
N: 0.057400
O: 0.063200
P: 0.015200
Q: 0.000800
R: 0.048400
S: 0.051400
T: 0.079600
U: 0.022800
V: 0.008300
W: 0.017500
X: 0.001300
Y: 0.016400
Z: 0.000500
: 0.185900
----result----
A: 1011 : length = 4
B: 100000 : length = 6
C: 00000 : length = 5
D: 10100 : length = 5
E: 010 : length = 3
F: 110011 : length = 6
G: 100001 : length = 6
H: 0001 : length = 4
I: 0111 : length = 4
J: 1100001001 : length = 10
K: 11000011 : length = 8
L: 10101 : length = 5
M: 110010 : length = 6
N: 0110 : length = 4
O: 1001 : length = 4
P: 100010 : length = 6
Q: 1100001010 : length = 10
R: 0010 : length = 4
S: 0011 : length = 4
T: 1101 : length = 4
U: 00001 : length = 5
V: 1100000 : length = 7
W: 110001 : length = 6
X: 1100001011 : length = 10
Y: 100011 : length = 6
Z: 1100001000 : length = 10
: 111 : length = 3
--------------
average code length: 4.119500