ハフマン符号化の問題を解くプログラム

質問

ハフマンの符号化の問題を解くプログラムをC言語（コンソールアプリケーション）で作りたいのですが
ファイルの圧縮とかをするプログラムはいろいろなサイトにあったのですが、
簡単な情報源を与えられたものを符号化するプログラムで参考にできるようなサイトは見つかりませんでした。
誰かプログラムの例を教えていただけないでしょうか？
入力する例はつぎのようなものです
S=（a1, a2, a3, a4, a5, a6／0.35, 0.15, 0.15, 0.20, 0.10, 0.05）

回答No.1

JaritenCat · ベストアンサー

木の作り方によって得られる符号は微妙に違いますのでこれは参考です。
シンボルと頻度テーブルから木を作って符号一覧を表示します。
符号化だけならleftとrightは不要です(復号化のとき使う)

#include <stdio.h>
#define N 6 /* N>=2 */
char *s[N]={"a1","a2","a3","a4","a5","a6"};
float f[2*N-1]={0.35,0.15,0.15,0.20,0.10,0.05};
int size=N, parent[2*N-1], left[2*N-1], right[2*N-1];
/* ハフマン木の作成 */
void huff(void) {
　int i,j,dat1,dat2;
　float min;
　/* 初期化 */
　for (i=0;i<2+N;i++) left[i]=right[i]=parent[i]=0;
　/* 最小頻度2個をまとめ続ける */
　while(1) {
　　/* 一番小さい数を探す */
　　for (i=0;i <size;i++) if (f[i]>=0) break;
　　if (i==size) break; /* 頻度リストが空？ */
　　dat1=i; min=f[dat1];
　　for (;i<size;i++) if (f[i]<min && f[i]>=0) {min=f[i]; dat1=i;}
　　/* 二番目に小さい数を探す */
　　for (i=0; i<size; i++) if ((f[i]>=0)&&(i!=dat1)) break;
　　if (i==size) break; /* 頻度リストが1個しかない */
　　dat2=i; min=f[dat2];
　　for (;i<size;i++) if (f[i]<min && f[i]>=0 && i!=dat1) { min=f[i]; dat2=i; }
　　/* 木に登録 */
　　left[size]=dat1; right[size]=dat2;
　　parent[dat1]=size; parent[dat2]= -size;
　　f[size]=f[dat1]+f[dat2]; f[dat1]= -1; f[dat2]= -1;
　　size ++;
　}
}
/* ハフマン符号の出力 */
void outenc(int huf) {
　if (huf== size-1) return;
　if (parent[huf]<0) {
　　outenc(-parent[huf]); printf("1");
　} else {
　　outenc(parent[huf]);　printf("0");
　}
}
/* メインルーチン */
int main(void) {
　int i;
　huff();
　for (i=0; i<N; i++) { printf("%s ",s[i]); outenc(i); printf("\n"); }
　return 0;
}

お礼

詳しい説明ありがとうございます。
コメントが多いのでとてもわかりやすかったです。
これを参考にいろいろ変えて試してみます。
本当にありがとうございました。