c言語によるハフマン符号化の実現

ハフマン符号化(Huffman Coding)は符号化方式であり、ハフマン符号化は可変ワード長符号化(VLC)の一種である.ハフマンは1952年に、文字出現確率に完全に基づいて異字ヘッドの平均長が最も短い符号語を構築し、最適符号化と呼ばれる場合があり、一般的にハフマン符号化と呼ばれる符号化方法を提案した.
1951年、ハフマンとMIT情報論の同級生は学期報告を完成するか期末試験を完成するかを選択しなければならない.指導者のRobert M.Fanoが彼らに与えた学期報告のテーマは、最も有効なバイナリコードを探すことです.どの既存符号化が最も有効であるかを証明できないため,ハフマンは既存符号化の研究を放棄し,新しい探索に転向し,最終的に秩序化周波数に基づくツリー符号化の考え方を発見し,この方法が最も有効であることをすぐに証明した.
このアルゴリズムのため、学生はついに青より出て、彼のかつて情報論の創立者シャノンと共同で類似のコードを研究した指導者を上回った.ハフマンはボトムアップ法を用いて二叉木を構築し,最適アルゴリズムShannon‐Fano符号化の最大の弊害であるトップダウン構築木を回避した.
ハフマンツリー、すなわち最適なツリー、重み付きパス長が最小のツリーで、データ圧縮によく適用されます.コンピュータ情報処理において、「ハフマン符号化」は、データの無損失圧縮に用いる一貫性符号化法(エントロピー符号化法とも呼ばれる)である.
/*
説明したいのですが、次のコードは私が書いたものではありません.コードは清華大学の朱先生の作品から出ています.私は貼り出して勉強して、自分のコレクションの資料を整理します.
*/

#include 
#include 
#define M 8
typedef struct node *link;
struct node { int f; link l, r; };
link NODE(int f, link l, link r)
{
	link t = malloc(sizeof *t);
	t->f = f; t->l = l; t->r = r;
	return t;
}
link hh[M], *h = hh-1;
int N;
void swap(int i, int j)
{
	link tmp = h[i]; h[i] = h[j]; h[j] = tmp;
}
void sift_down(int k, int n)
{
	int j;
	while (2*k<=n) {
		j = 2*k;
		if (j+1<=n && h[j+1]->f < h[j]->f) j++;
		if (h[k]->f < h[j]->f) break;
		swap(k, j); k = j;
	}
}
void sift_up(int k)
{
	int j;
	while (k>1) {
		j = k/2;
		if (h[j]->f < h[k]->f) break;
		swap(k, j); k = j;
	}
}
link delMin()
{
	swap(1, N--);
	sift_down(1, N);
	return h[N+1];
}
void insert(link t)
{
	h[++N] = t;
	sift_up(N);
}
void build_heap()
{
	int i;
	N = M;
	for (i=N/2; i>=1; i--) sift_down(i, N);
}
link create_huffman_tree(int a[])
{
	int i;
	for (i=1; i<=M; i++) h[i] = NODE(a[i-1], NULL, NULL);
	build_heap();
	while (N>1) {
		link t1 = delMin();
		link t2 = delMin();
		insert(NODE(t1->f + t2->f, t1, t2));
	}
	return delMin();
}
void pprint(link t)
{
	if (t) {
		printf("(");
		printf("%d", t->f);
		pprint(t->l);
		pprint(t->r);
		printf(")");
	} else printf("()");
}
int main()
{
	int a[] = { 5, 29, 7, 8, 14, 23, 3, 11 };
	link root = create_huffman_tree(a);
	printf("\\tree"); pprint(root); printf("
");
	return 0;
}