huffman_arithmetic.c

自己用C编写的Huffman编码通信系统应用

#include "huffman.h"
//2006-11-04
/*利用哈夫曼树很容易求出给定字符集及其概率(或频度)分布的最佳不等长编码。哈夫曼编码正是一种应用广泛
  且非常有效的数据压缩技术。该技术一般可将数据文件压缩掉20％至90％，其压缩效率取决于被压缩文件
  的特征。
*/
/*由哈夫曼树求得编码为最优异字头码的原因：
①每个叶子字符ci的码长恰为从根到该叶子的路径长度li，平均码长(或文件总长)又是二叉树的带权路径长度WPL。而哈夫曼树是WPL最小的二叉树，因此编码的平均码长(或文件总长)亦最小。
②树中没有一片叶子是另一叶子的祖先，每片叶子对应的编码就不可能是其它叶子编码的前缀。即上述编码是二进制的异字头码。
*/

/*-------------------------------------------------------------------------------------*/
//在函数InputWeightData()中调用函数characters_analysis()从而求出了N和M的大小。
void CreateHuffmanTree(HuffmanTree T,const char* const FILENAME) //构造哈夫曼树;T[M-1]为其根结点
{
	int i;
	int p1;
	int p2;    

	InitHuffmanTree(T); //将T初始化,T有M个结点，即T是有M个元素的数组。
	InputWeightData(T,FILENAME);//输入N个叶子的权值及数据至T[0．．N-1]的weight域及data域
	for(i = N;i < M;++i){ //共进行N-1次合并，新结点依次存于T[i]中
		SelectMin(T,i - 1,&p1,&p2); //在T[0．．i-1]中选择两个权最小的根结点，其序号分别为p1和p2
        T[p1].parent = i; //数组下标；其值>=0。
		T[p2].parent = i;        
        T[i].lchild = p1; //最小权的根结点是新结点的左孩子
		T[i].rchild = p2; //次小权的根结点是新结点的右孩子
		T[i].weight = T[p1].weight + T[p2].weight;
	} 
}

/*-------------------------------------------------------------------------------------*/
//哈夫曼编码算法——由哈夫曼树T求得字符集的"哈夫曼编码表H"
void SetHuffmanEncodeTable(HuffmanTree T,HuffmanCodeTable H) //根据哈夫曼树T求哈夫曼编码表H
{
	int child;
	int parent; // c和p分别指示T中孩子和双亲的位置
	int i; 
    char code[N1 + 1]; //临时存放编码，数组大小为N1 + 1。
	int start; //指示编码在code中的起始位置

	code[N1] = '\0'; //编码结束符
	for(i = 0;i < N;++i){ //依次求N个叶子结点T[i]的编码
		H[i].ch = T[i].data;//读入叶子T[i]对应的字符
		start = N1; //编码起始位置的初值
		child = i; //从叶子T[i]开始上溯
		while((parent = T[child].parent) >= 0){//直至上溯到T[c]是树根为止,树根时parent为-1。
			code[--start] = (T[parent].lchild == child) ? '0' : '1';//用一个三目运算符表示
//若T[child]是T[parent]的左孩子，则生成代码0；否则生成代码1
            child = parent; //继续上溯
		}
		strcpy(H[i].bits,&code[start]); //复制编码位串,在此好好理解字符串拷贝
/*&code[start]表示是以字符串code的从start位置开始到结束的一个code的字符子串。因为start是字符串
  开始的有效位置，所以从此地方开始拷贝字符串。*/
	}
}

/*-------------------------------------------------------------------------------*/
//哈夫曼编码——对原始数据文件"DATAFILE"的编码：
//对数据文件中的1个字符进行编码
char HuffmanEncode(HuffmanCodeTable H,FILE* fp1,FILE* fp2)
{
	int i = 0;
	char ch;
	char code[N1 + 1]; //临时存放编码	

	ch = ReadACharFromFile(fp1); //从原始数据文件中读取一个字符
	if(ch == '\0') //当读到文件尾标记EOF时返回了标记'\0'
		return ch; //返回'\0'标记读到文件尾标记EOF

	FindChar(H,ch,&i); //在哈夫曼编码表H中找到字符ch的位置i
	if(ch == H[i].ch)
		strcpy(code,H[i].bits); //编码结果存在code中
	WriteStringsToFile(fp2,code);//把字符串code写入编码文件保存
	return '!'; //返回非'\0'
}

/*----------------------------------------------------------------------------------*/
//哈夫曼译码——对已编码文件"ENCODEFILE"的译码：
/*算法中可以使用T[i].lchild是否为-1来判定T[i]是否为叶子结点，是因为哈夫曼树是严格二叉树，树中
  没有度数为1的分支结点。*/
//哈夫曼树的根结点为T[M-1]。 
//对1个字符对应的编码序列进行译码
char HuffmanDecode(HuffmanTree T,HuffmanCodeTable H,FILE* fp1,FILE* fp2)
{
	int i;
	char ch;
	char ch1; //临时存储所译码的对应字符集中的字符。

	i = M -1; //指向树的根结点。此地方要用M,不能用M1,注意!!!因为Huffman树的结点总数是M。
	while(1){
		ch = ReadACharFromFile(fp1); //从编码文件中读取一个二进制码'0'或'1'字符
		if(ch == '\0')  //当读到文件尾标记EOF时返回了标记'\0'
			return ch; //返回'\0'标记读到文件尾标记EOF

		if(ch == '0')
			i = T[i].lchild; //转向左孩子
		else
			i = T[i].rchild; //转向右孩子
		if(T[i].lchild == -1){ //则已到叶子结点
			ch1 = H[i].ch;//对应哈夫曼码表中的字符
			WriteACharToFile(ch1,fp2); //把译码结果写入译码文件保存
			break; //结束此次译码
		}
	}
    return '!'; //返回非'\0'
}

/*--------------------------------------------------------------------------------------------*/
void InitHuffmanTree(HuffmanTree T) //将T初始化,T有M个结点，即T是有M个元素的数组。
{
	int i;

/*初始定义的数组大小为M1；其有效数据元素为M个。M是在程序中所求；M1是一个常量,以声明数组的
  大小(编译时就要确定数组的大小)。*/
	for(i = 0;i < M1;++i){ //这里M的值还没有求出来，故对整个初始数组进行初始化
		T[i].data = '\0';
		T[i].weight = 0.0;
		T[i].lchild = -1;
		T[i].rchild = -1;
		T[i].parent = -1;
	}
}	

/*--------------------------------------------------------------------------------------*/
//输入N个叶子的权值及数据至T[0．．N-1]的weight域及data域
//由分析原始数据文件后得到字符集F的字符个数N。在函数characters_analysis()中求出了N和M。
void InputWeightData(HuffmanTree T,const char* const FILENAME) 
{
	int i;
    StrSetFrequencyTable F; //字符集的频率(频度)表F(数组),有N个元素(对应N个字符)

    characters_analysis(F,FILENAME);//分析数据文本文件的字符构成及各字符的频率(频度)
//到此已求出了N和M的大小。
	for(i = 0;i < N;++i){ //这里要用N，表示N个叶子结点。不能用N1。注意!!!
		T[i].data = F[i].data;
		T[i].weight = F[i].weight;
	}
}

/*---------------------------------------------------------------------------------*/
void SelectMin(HuffmanTree T,int i,int* p1,int* p2)//在T[0．．i]中选择两个权最小的根结点，由p1,p2返回其位置
{
	int minimum1; //最小值位置标记
	int minimum2; //次小值位置标记
	int j;
	int flag1;
	int flag2;
	int FLAG;

	FLAG = 0;
	for(j = 0;j <= i;++j){//在当前的(i+1)个结点中选取两个权值最小的根结点
		while(T[j].parent != -1)//找一个树根；为-1时即为求解问题时森林中某孤立树的树根。
			++j; 		
		flag1 = j;
		if(FLAG == 0){//第一次要找两个孤立树的树根，以后每次只需找一个；以后不再执行此代码段。
			while(T[++j].parent != -1)//找下一个孤立树的树根；
				continue;
			flag2 = j;
			if(T[flag1].weight < T[flag2].weight){
				minimum1 = flag1;
				minimum2 = flag2;
				FLAG = 1;
				continue;//继续找下一个孤立树的树根;进行下一次for循环
			}
		}
		if(T[flag1].weight < T[minimum1].weight){
            minimum2 = minimum1; //修正次小值
			minimum1 = flag1; //修正最小值
		}			
		else if(T[flag1].weight < T[minimum2].weight)//只需修正次小值
			minimum2 = flag1; 			
	}
	*p1 = minimum1;
	*p2 = minimum2;
}

/*------------------------------------------------------------------------------*/
void FindChar(HuffmanCodeTable H,char ch,int* ptr_i)
{
	int j;

	for(j = 0;j < N;++j){
		if(H[j].ch == ch){
			*ptr_i = j;
			break;
		}
	}
}

/*-------------------------------------------------------------------------------*/
/*① 初始森林中的n棵二叉树，每棵树有一个孤立的结点，它们既是根，又是叶子
  ② n个叶子的哈夫曼树要经过n-1次合并，产生n-1个新结点。最终求得的哈夫曼树中共有2n-1个结点。
  ③ 哈夫曼树是严格的二叉树，没有度数为1的分支结点。

哈夫曼算法的简要描述:
    　在上述存储结构上实现的哈夫曼算法可大致描述为(设T的类型为HuffmanTree)：
(1)初始化
将T[0．．m-1]中2n-1个结点里的三个指针均置为空(即置为-1,因为数组下标从0开始)，权值置为0.0，
数据值置为'0'。
(2)输入
读人n个叶子的权值存于向量的前n个分量(即T[0．．n-1])中。它们是初始森林中n个孤立的根结点上的权值。
(3)合并
对森林中的树共进行n-1次合并，所产生的新结点依次放人向量T的第i个分量中(n≤i≤m-1)。每次合并分两步：
①在当前森林T[0．．i-1]的所有结点中，选取权最小和次小的两个根结点[p1]和T[p2]作为合并对象，
  这里0≤p1，p2≤i-1。
②将根为T[p1]和T[p2]的两棵树作为左右子树合并为一棵新的树，新树的根是新结点T[i]。具体操作：
　将T[p1]和T[p2]的parent置为i，
　将T[i]的lchild和rchild分别置为p1和p2
　新结点T[i]的权值置为T[p1]和T[p2]的权值之和。
注意：合并后T[pl]和T[p2]在当前森林中已不再是根，因为它们的双亲指针均已指向了T[i]，所以下一次合并
      时不会被选中为合并对象。
*/