ハフマン符号化復号の応用(0.9 a版)

一.せっけい構想
1.明文の{文字+重み}セットを生成する
2.Huffmanツリーの構築(欲張り法+ボトムアップ)
3.ハフマンツリーを利用して、明文を符号化する
4.huffmanツリーを用いて、符号化を明文に復号する
二.明文の{文字+重み}セットを生成
1.文字テーブル:文字アイテムと重みアイテムが含まれます.

<span style="font-size:14px;">#define N 256

// 
struct charcode 
{
	char c; // 
	int w;  // 
};

struct charcode ctable[N];

// ， 
int num = 0;</span>

2.文字テーブルで文字を検索する

<span style="font-size:14px;">// ， ； -1
int find (char ch)
{
	int i;
	for(i = 0; ctable[i].c != 0; i++)
	{
		if(ctable[i].c == ch) // 
		{
			return i;
		}
	}

	return i;// 
}</span>

3.次に、文字の出現頻度(重み)を記録する

<span style="font-size:14px;">// ， ； 0
// （ )
void getweight()
{
	char ch;
	freopen("plaintext.txt", "r", stdin);
	while((ch=getchar())!=EOF)
	{
		int i = find(ch);// 
		if(!ctable[i].c)// 
		{
			ctable[i].c = ch;// 
			num++;	// 1
		}
		ctable[i].w++; // 1
	}
	fclose(stdin);
}</span>

二.ハフマンの木を作る
1.Huffmanツリー構造:文字、権、父の下付き、左の子の下付き、右の子の下付き

<span style="font-size:14px;">//Huffman ： ， ， ， ， 
struct treenode// 
{
	char c; //char
	int w;  //weight
	int f;  //father
	int l;  //left child index
	int r;  //right child index
};

//N ， 2N - 1
struct treenode htree[2 * N - 1];</span>

2.重み付けでソート

<span style="font-size:14px;">// 
void sort()
{
	int i,j;
	struct charcode t;

	for(i = 0; i < num; i++) // 
	{
		int m = i; //m 
		for(j = i + 1; j < num; j++)
		{
			if(ctable[j].w < ctable[m].w)
			{
				m = j;
			}
		}

		t = ctable[m];
		ctable[m] = ctable[i];
		ctable[i] = t;
	}
}</span>

三.Huffmanツリーの構築

<span style="font-size:14px;">// Huffman ， 
void huffman()
{
	int i, j, k, n;

	for(i = 0; i < num; i++)
	{
		// 
		htree[i].c = ctable[i].c;
		htree[i].w = ctable[i].w;
		htree[i].l = htree[i].f = htree[i].r = -1;

		//printf("[%d]%c: %d
",i, htree[i].c, htree[i].w);
	}

	j = 0;//j 
	k = num;//K 

	for(n = num; n < 2 * num -1; n++)
	{// 
		int r = 0, s = 0;
		htree[n].l = htree[n].f = htree[n].r = -1;

		while(r < 2)
		{
			if(htree[k].w == 0 || htree[k].w > htree[j].w && j < num)
			{
				s+=htree[j].w;// 
				if(r == 0)
				{
					htree[n].l = j;// 
				}
				else
				{
					htree[n].r = j;// 
				}

				htree[j].f = n;// 
				j++;
			}
			else
			{// 
				s+=htree[k].w;
				if(r == 0)
				{
					htree[n].l = k;
				}
				else
				{
					htree[n].r = k;
				}
				htree[k].f = n;
				k++;
			}
			r++;
		}

		htree[n].w = s;// 
	}
}</span>

四.ハフマン符号化

<span style="font-size:14px;">// plaintext.txt ， ， telgraph.txt 
void encode()
{
	char ch;
	freopen("plaintext.txt", "r", stdin);
	freopen("telegraph.txt", "w", stdout);

	char* str= (char*)malloc(sizeof(char) * N);

	while((ch=getchar()) != EOF)
	{
		int i = find(ch);
		memset(str,0,sizeof(char) * N);
		getcode(i, str);
		printf("%s", str);
	}
	fclose(stdout);
	fclose(stdin);
	//free(str);
}</span>

<span style="font-size:14px;">// ， 
// huffman 
void getcode(int i, char* str)
{
	int n, j, l = 0;
	for(n = i;htree[n].f != -1; n = htree[n].f)
	{// 
		int m = htree[n].f;
		if(n == htree[m].l)
		{
			str[l++] = '0';// 0
		}
		else
		{
			str[l++] = '1';// 1
		}
	}

	for(j = 0; j <= (l -1)/2;j++)
	{// 
		char t;
		t = str[j];
		str[j] = str[l - 1 -j];
		str[l - 1 - j] = t;
	}
	str[l] = '\0';//str huffman ， 
}</span>

五.ハフマンコーディング

<span style="font-size:14px;">// telgraph.txt ， 
// tanslation.txt
void decode()
{
	char ch;
	freopen("telegraph.txt", "r", stdin);
	freopen("tanslation.txt", "w", stdout);
	ch = getchar();

	// ， ， 
	while(ch != EOF)
	{
		int i;
		for(i = 2 * num - 2; htree[i].l != -1;)
		{
			if(ch == '0')
			{
				i = htree[i].l;
			}
			else
			{
				i = htree[i].r;
			}
			ch = getchar();
		}
		printf("%c", htree[i].c);
	}
	 fclose(stdout);
	 fclose(stdin);
}</span>

六.しゅかんすう

<span style="font-size:14px;">// ： 
int _tmain(int argc, _TCHAR* argv[])
{
	getweight();// （ ）
	sort();// 
	huffman();// Huffman 
	encode();// 
	decode();// 
	return 0;
}</span>

七.VC 2008 HumanTestケースhttp://download.csdn.net/detail/u013354805/8849497