用哈夫曼编码压缩文件

这是我自己学习huffman编码时编写的一个小程序。可以对文件进行压缩和解压缩，支持2种压缩算法，文件名称和压缩模式在命令行参数设置。内有编译好的执行文件，测试结果，数据文件，比较详细的使用说明和注释。程序使用c语言编写，未使用任何第三方库。在某些情况下(比如super-pi的计算结果),用我的这个程序压缩后的文件甚至比winRAR最优压缩模式更小。

#include 
#include 
#include 
#include 

/* 
Author: Baocheng Liang
E-mail: liangbch@263.net   All rights reserved. May 2012.
Homepage: http://blog.csdn.net/liangbch
*/

/*
 该程序用来对文件进行huffman编码和解码
 包括打印各个字符的huffman编码

 编码用的huffman树的每个节点的数据结构
1. weight: UINT32 权重值该字符在文件中出现的次数
2. huffman_code: char* 该字符对应的huffman编码 
3. parent:  UINT16  父节点指针，0xffff表示空指针
4. l_child: UINT16:  左子节点指针，0xffff表示空指针
5. r_child: UINT16:  右子节点指针，0xffff表示空指针


采用huffman编码后的文件格式
文件包括4个部分，文件头单字节和双字节的转化表，huffman解码树原始文件的huffman编码。
1.文件头：共24个字节
1.1. 偏移0: 标记：4个字节，他们是BCHM
1.2. 偏移4 UINT32：4个字节，huffman 解码树的非叶子节点数若原始文件包含n个互不相同的字符，则huffman数共有n个叶子节点，n-1个非叶子节点
1.3. 偏移8 UINT32: 4个字节，原始文件的字节数记为bc
1.4. 偏移12UINT32: 4个字节，the huffman 编码包含的总bit数
1.5. 偏移16：UINT32: 4个字节，单字节和双字节的转化表长度，转化表长度最多为256，当使用普通方法压缩是，转化表长度为0
1.6. 偏移20：保留字符：BYTE: 1个字节
1.7  编译21-23： 不使用：

2.单双字节转化表，仅仅用于与高级算法
每个节点共2个字节，
  tab[i*2]:表示ASCII为i的字符表示对应的双字节的第1个字节。
  tab[i*2+1]:表示ASCII为i的字符表示对应的双字节的第2个字节。
  
3.huffman解码树的非叶子节
每个节点包含3个域，flagleftright共3个字节，其数据结构如下
3.1. flag: UINT8实际上只使用2个比特 
      00b：左右子节点均为非叶子节点
      01b：左子节点为叶子节点，此时，left字段存储右子节点的ASCII码
      10b：右子节点为叶子节点，此时，right字段存储左子节点的ASCII码
	  11b：左右子节点均为叶子节点，此时left和right字段存储左/右子节点的ASCII码 
3.2. left: UINT8 左子节点的指针或左子节点的ASCII码，需要查表，将编码换成单字节或者双字节编码
3.3. right:UINT8 右子节点的指针或右子节点的ASCII码，需要查表，将编码换成单字节或者双字节编码

4. 原始文件的huffman编码，采用从高位到低为的顺序存储，如一个字符的huffman编码是101001则再文件中存储是，第一个字节的bit0-bit5依次是
  101001
*/

#define NIL_PT		0xffff
#define LEFT_IDX	0
#define RIGHT_IDX   1
#define LEFT_MASK	（1<#define RIGHT_MASK	（1<#define SLICE_ARRAY_SIZE（slice_arr）  （slice_arr.tail-slice_arr.head+1）
#define GET_VALUE（ch1ch2）		 （（（UINT16）ch1<<8） + （UINT16）ch2）
#define FREE_CODE_LOW_LIMIT		128

#define CH_TYPE_CTR    0	//control char the ASCII<32
#define CH_TYPE_SYM	   1	//space “““+““（“ “:“ and so on
#define CH_TYPE_NUM    2	//‘0‘ to ‘9‘
#define CH_TYPE_LET	   3	//letter of the alphabet

typedef unsigned long  UINT32;
typedef unsigned short UINT16;
typedef unsigned char  BYTE;

typedef struct{
	UINT32 weight;
	char*  huffman_code;
	BYTE   bytes[2];
	UINT16 parent;
	UINT16 l_child;
	UINT16 r_child;
}HM_ENCODE_NODE;

typedef struct{
	UINT32 weight;
	BYTE   bytes[2];
	BYTE   no;
}DOUBLE_BYTES_CODE;	


typedef struct{
	DOUBLE_BYTES_CODE *data;
	int len;
}SEARCH_ARRAY;	//double bytes to single byte convert table


typedef struct{
	SEARCH_ARRAY arr;	
	int  coding_space;		//2 byte encoding space
	int  encode_mode;		//1:普通方式编码，2：对双字节组合使用单字节编码
	BYTE reserve_char;		//保留字符
}MAP_2BYTES_1BYTE;


typedef struct{
	BYTE flag;
				//: UINT8only use 2 bits
				// 00b：Both left child node and right child node are non-leaf node
				// 01b：Left child node is leaf node in this case the left field means ASCII of left child node
				// 10b：Right child node is leaf node in this case the Right field means ASCII of Right child node
		

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件      24061  2012-05-09 14:40  huffmanCoding\huffmanCoding\huffmanCoding.c

     文件       8192  2012-05-08 07:35  huffmanCoding\huffmanCoding\huffmanCoding.suo

     文件       4091  2012-05-09 13:56  huffmanCoding\huffmanCoding\huffmanCoding.vcproj

     文件        910  2012-05-08 07:35  huffmanCoding\huffmanCoding.sln

    ..A..H.      9728  2012-05-09 14:59  huffmanCoding\huffmanCoding.suo

     文件      13312  2012-05-09 14:59  huffmanCoding\huffzip.exe

     文件    1322392  2012-05-09 14:26  huffmanCoding\pi.txt

     文件    1176511  2012-05-08 07:35  huffmanCoding\pi_data.txt

     文件        950  2012-05-09 14:56  huffmanCoding\ReadMe.txt

     文件      36352  2012-05-09 15:38  huffmanCoding\test_result.doc

     目录          0  2012-05-09 15:03  huffmanCoding\huffmanCoding

     目录          0  2012-05-09 15:38  huffmanCoding

----------- ---------  ---------- -----  ----

              2596499                    12