数据压缩实验3-Huffman编码
一、实验原理
1.Huffman 编码
1) Huffman Coding (霍夫曼编码)是一种无失真编码的编码方式，Huffman 编码是可
变字长编码(VLC)的一种。
2) 2 Huffman 编码基于信源的概率统计模型，它的基本思路是，出现概率大的信源符
号编长码，出现概率小的信源符号编短码，从而使平均码长最小。
3) 3 在程序实现中常使用一种叫做树的数据结构实现 Huffman 编码，由它编出的码是
即时码。
2.Huffman 编码的方法
a) 统计符号的发生概率；
b) 把频率按从小到大的顺序排列
c) 每一次选出最小的两个值，作为二叉树的两个叶子节点，将和作为它们的根节点，
这两个叶子节点不再参与比较，新的根节点参与比较；
d) 重复上一步，直到最后得到和为 1 的根节点；
e) 将形成的二叉树的左节点标 0，右节点标 1，把从最上面的根节点到最下面的叶
子节点途中遇到的 0，1 序列串起来，就得到了各个符号的编码。
举例如下：
二、实验过程
1. 实验流程
2. Huffman编码的数据结构
2.1节点：
通过Huffman节点建立Huffman树。
typedef structhuffman_node_tag
{
unsigned char isLeaf; //是否为树叶
unsigned long count; //节点代表的符号加权和
struct huffman_node_tag *parent; //父节点指针
union
{
struct
{
struct huffman_node_tag *zero, *one;
//子节点指针,分别代表0,1子节点指针
};
unsigned char symbol; //节点代表的符号
};
} huffman_node;
2.2 Huffman码结构
typedef struct huffman_code_tag
{
unsigned longnumbits; //该码所用的比特数
unsigned char*bits; //指向该码比特串的指针
/*码字的第 1 位存于 bits[0]的第 1 位,
码字的第 2 位存于 bits[0]的第的第 2 位,
码字的第 8 位存于 bits[0]的第的第 8 位,
码字的第 9 位存于 bits[1]的第的第 1 位*/
} huffman_code;
三、实验代码分析
1从指定文件中读取数据，统计每个符号发生的概率，并建立相应的树叶节点
//设置符号概率统计结果输出
#define MAX_SYMBOLS 256
//256个信源符号的Huffman节点
typedef huffman_node*SymbolFrequencies[MAX_SYMBOLS];
//256个Huffman节点的编码符号，即码表
typedef huffman_code*SymbolEncoder[MAX_SYMBOLS];
//----------------以下结构体用于保存符号频率统计结果-----------------------//
typedef struct huffman_statistics_result
{
/*创建一个 256 个元素的指针数组，用以保存 256 个信源符号的频率*/
floatfreq[256];
/*创建一个 256 个元素的指针数组，用以保存 256 个信源符号的所用比特长度*/
unsignedlong numbits[256];
/*将每个信源符号与其使用比特数相对应起来*/
unsignedchar bits[256][100];
}huffman_stat;
// 在统计所有信源符号前将结果结构初始化，开辟空间
huffman_stat *init_huffstatistics()
{ huffman_stat*p;
int i;
p= (huffman_stat*)malloc(sizeof(huffman_stat));
p->freq= (float *)malloc(sizeof(float)*256 );
p->numbits= (unsigned long *) malloc(sizeof(unsigned long)*256);
for (i=0 ; i<256;i++)
p->bits[i]= (unsigned char *)malloc(sizeof(unsigned char)*100);
returnp;
}
//----------------------------------------------------------------------------------------------//
/*统计信源符号发生频次并记录的函数*/
static unsigned int
get_symbol_frequencies(SymbolFrequencies*pSF, FILE *in)
{
intc;
unsignedint total_count = 0;
/*初始化所有频率都为0. */
init_frequencies(pSF);
/*第一次扫描，从输入文件中统计每个信源符号发生概率 */
while((c= fgetc(in)) != EOF)
{
unsignedchar uc = c;
// 如果是一个新符号,则产生该字符的一个新叶节点
if(!(*pSF)[uc])
(*pSF)[uc]= new_leaf_node(uc);
++(*pSF)[uc]->count; //当前字符出现的频数+1
++total_count; //总信源符号数 +1
}
returntotal_count;
}
2 按频率从小到大的顺序排序并建立Huffman树
static SymbolEncoder*
calculate_huffman_codes(SymbolFrequencies *pSF)
{
unsignedint i = 0;
unsignedint n = 0;
huffman_node*m1 = NULL, *m2 = NULL;
SymbolEncoder*pSE = NULL;
#if 1
printf("BEFORESORT\n");
print_freqs(pSF);
#endif
/*按信源符号出现频率从小到大排序.*/
qsort((*pSF),MAX_SYMBOLS, sizeof((*pSF)[0]), SFComp);
#if 1
printf("AFTERSORT\n");
print_freqs(pSF);
#endif
/*得到所出现的信源符号的总数为n */
for(n= 0; n < MAX_SYMBOLS && (*pSF)[n]; ++n)
;
/* 建立 huffman 树，将节点合并 n-1 次，直至根节点，每次循环生成一个非树叶节点，循环过后指针数组中只剩下一个根节点元素*/
for(i= 0; i < n - 1; ++i)
{
/*将 m1、m2 置为当前频数最小的两个信源符号*/
m1= (*pSF)[0];
m2 = (*pSF)[1];
/*将 m1、m2 合并为一个 huffman 结点加入到数组中，并将此节点的
左右孩子分别置为 m1、m2 的地址，频数为 m1、m2 的频数之和*/
(*pSF)[0]= m1->parent = m2->parent =
new_nonleaf_node(m1->count+ m2->count, m1, m2);
(*pSF)[1]= NULL;
/*在合并m1，m2节点为一个节点后重新进行排序*/
qsort((*pSF),n, sizeof((*pSF)[0]), SFComp);
}
/*由建立的 huffman 树计算每个符号的码字.*/
pSE= (SymbolEncoder*)malloc(sizeof(SymbolEncoder));
memset(pSE,0, sizeof(SymbolEncoder));
build_symbol_encoder((*pSF)[0],pSE);
returnpSE;
}
3 递归遍历 Huffman 树，对存在的每个字符计算码字
//建立新的树叶节点
static huffman_node*
new_leaf_node(unsigned char symbol)
{
huffman_node*p = (huffman_node*)malloc(sizeof(huffman_node));
p->isLeaf= 1;
p->symbol= symbol;
p->count= 0;
p->parent= 0;
returnp;
}
//建立新的非树叶节点
static huffman_node*
new_nonleaf_node(unsigned long count,huffman_node *zero, huffman_node *one)
{
huffman_node*p = (huffman_node*)malloc(sizeof(huffman_node));
p->isLeaf= 0;
p->count= count;
p->zero= zero;
p->one= one;
p->parent= 0;
returnp;
}
//遍历Huffman树，得到每个已存在信源符号的码字，形成码表
static void
build_symbol_encoder(huffman_node *subtree,SymbolEncoder *pSF)
{
if(subtree== NULL)
return;//根节点则返回
if(subtree->isLeaf)
(*pSF)[subtree->symbol]= new_code(subtree); //若为树叶,则构造霍夫曼码结构
else
{ ////否则递归这个函数,直到达到树叶节点
build_symbol_encoder(subtree->zero,pSF);
build_symbol_encoder(subtree->one,pSF);
}
}
static huffman_code*
new_code(const huffman_node* leaf)
{
/*从树叶节点至根节点进行码符号查询并反向排列得到码字 */
unsignedlong numbits = 0;//码长
unsignedchar* bits = NULL;//码字首地址
huffman_code*p;
//找到树叶节点后，向上遍历，顺序写入码串
while(leaf&& leaf->parent)//节点及父节点是否存在
{
huffman_node*parent = leaf->parent;
// 所编位在当前 byte中的位置
unsignedchar cur_bit = (unsigned char)(numbits % 8);
unsignedlong cur_byte = numbits / 8; // 当前byte数
/* realloc与 malloc 不同，它在保持原有的数据不变的情况下重新分配新的空间，原有数据存在新空间中的前面部分*/
if(cur_bit== 0) // 开辟一个字节来存储码字
{
size_tnewSize = cur_byte + 1;
bits= (char*)realloc(bits, newSize);
bits[newSize- 1] = 0; /* Initialize the new byte. */
}
if(leaf== parent->one) //若为1节点,则将对应位置1
bits[cur_byte]|= 1 << cur_bit;
++numbits;//码位数加一
leaf= parent;//将其置为父节点
}
if(bits)
reverse_bits(bits, numbits);//实现码字逆序排列
p= (huffman_code*)malloc(sizeof(huffman_code));
p->numbits= numbits;
p->bits= bits;
returnp;
}
4.将 Huffman 码表写入文件
static int
write_code_table(FILE* out, SymbolEncoder*se, unsigned int symbol_count)
{
//……省略部分代码
/*将码表写入文件*/
for(i= 0; i < MAX_SYMBOLS; ++i)
{
huffman_code*p = (*se)[i];
if(p)
{
unsignedint numbytes;
/*Write the 1 byte symbol. */
fputc((unsignedchar)i, out);
/*Write the 1 byte code bit length. */
fputc(p->numbits,out);
/*Write the code bytes. */
numbytes= numbytes_from_numbits(p->numbits);
if(fwrite(p->bits,1, numbytes, out) != numbytes)
return1;
}
}
return0;
}
/*其他码表分析函数*/
//----------得到码字长度与所占权重--------//
int huffST_getSymFrequencies(SymbolFrequencies*SF, huffman_stat *st,int total_count)
{
inti,count =0;
for(i= 0; i < MAX_SYMBOLS; ++i)
{
if((*SF)[i])
{
st->freq[i]=(float)(*SF)[i]->count/total_count;
count+=(*SF)[i]->count;
}
else
{
st->freq[i]=0;
}
}
if(count==total_count)
return1;
else
return0;
}
//--------得到码字与码长-------//
int huffST_getcodeword(SymbolEncoder *se,huffman_stat *st)
{
unsignedlong i,j;
for(i= 0; i < MAX_SYMBOLS; ++i)
{
huffman_code*p = (*se)[i];
if(p)
{
unsignedint numbytes;
st->numbits[i] = p->numbits;
numbytes= numbytes_from_numbits(p->numbits);
for(j=0;j<numbytes;j++)
st->bits[i][j] = p->bits[j];
}
else
st->numbits[i]=0;
}
return0;
}
//-----------------以表格形式输出码表------------------//
void output_huffman_statistics(huffman_stat*st,FILE *out_Table)
{
inti,j;
unsignedchar c;
fprintf(out_Table,"symbol\t freq\t codelength\t code\n");
for(i= 0; i < MAX_SYMBOLS; ++i)
{
fprintf(out_Table,"%d\t ",i);
fprintf(out_Table,"%f\t ",st->freq[i]);
fprintf(out_Table,"%d\t ",st->numbits[i]);
if(st->numbits[i])
{
for(j= 0; j < st->numbits[i]; ++j)
{
c=get_bit(st->bits[i], j);
fprintf(out_Table,"%d",c);
}
}
fprintf(out_Table,"\n");
}
}
5. 编码
int
huffman_encode_file(FILE *in, FILE *out,FILE *out_Table) //可以表格形式输出结果
{
SymbolFrequenciessf;
SymbolEncoder*se;
huffman_node*root = NULL;
intrc;
unsignedint symbol_count;
/*得到每一个信源符号发生概率并以表格形式输出统计结果*/
huffman_staths;
symbol_count= get_symbol_frequencies(&sf, in);
huffST_getSymFrequencies(&sf,&hs,symbol_count);
/*Build an optimal table from the symbolCount. */
se= calculate_huffman_codes(&sf);
root= sf[0];
//获取码表并输出
huffST_getcodeword(se,&hs);
output_huffman_statistics(&hs,out_Table);
/*第二次扫描文件，从输入文件中遍历每一个输入符号
查询码表进行编码，并将码字写入文件，并以表格形式输出实验结果*/
rewind(in);
rc= write_code_table(out, se, symbol_count);
if(rc== 0)
rc= do_file_encode(in, out, se);
/*清空Huffman树. */
free_huffman_tree(root);
free_encoder(se);
returnrc;
}
主函数：
int
main(int argc, char** argv)
{
charmemory = 0;
charcompress = 1;
intopt;
constchar *file_in = NULL, *file_out = NULL;
//统计数据表格指针
constchar *file_out_table = NULL;
FILE*in = stdin;
FILE*out = stdout;
FILE* outTable = NULL;
/*获取命令行参数 */
while((opt= getopt(argc, argv, "i:o:cdhvmt:")) != -1)
{
switch(opt)
{
case'i':
file_in= optarg;
break;
case'o':
file_out= optarg;
break;
case'c':
compress= 1;
break;
case'd':
compress= 0;
break;
case'h':
usage(stdout);
return0;
case'v':
version(stdout);
return0;
case'm':
memory= 1;
break;
//生成数据统计表格
case't':
file_out_table= optarg;
break;
default:
usage(stderr);
return1;
}
}
//…..省略部分代码
}
四、实验结果及分析
将10种不同类型的文件直接进行Huffman编码，统计各个文件符号概率分布
统计各个文件平均码长以及压缩比：
由于各个文件符号概率都比较平均，Huffman编码并没有带来较高的压缩率，
Huffman编码对符号概率相差比较大的信源压缩效率更好。