huffman编码实例（原创）
时间：2010-09-12 来源：止觞
因为自己算法方面一直比较薄弱，最近开始重新看数据结构，在看到树的这一节时，自己花了三天写了一个huffman编码的实例，c语言写成。想来惭愧，自己当初学习数据结构时，花了半个多月都没搞定，没想到现在从构思到编写，三天一个完整的实例就出来了，突然感觉原来自己真的变强了很多。在这里，请高手们莫笑我，一个小小的huffman还要花三天。确实是，代码总共也就500行，还用了三天，确实惭愧阿，惭愧～～～
最近一直在忙着保研，也没有太多时间写这个，很高兴，三天就写完，没花掉我太多宝贵的时间，当然这中间也没耽误了玩，自己一向比较好玩，希望以后别影响到我的工作还好。只是程序仍然存在一个小小的bug，huffman编码中，每个字符的编码长度是不一定的，因此最后一个编码的字节有可能凑不够八个bit，那么就存在了垃圾信息，本来自己想在文件开头留一个字节的位置，存一个1～7的小整数来记录垃圾信息的位数，理论上确实也是可以的。但是不知道为什么，自己在把所有编码都写到输出文件中之后，将文件指针重置到文件开头，却无法覆盖当时自己写的占位字符，百思不得其解。因为这个bug，在文件解码出来之后，有时候可能会存在一两个不应该出现的字符，只有文件结尾会出错，其他位置是不会出错的。
欢迎大家交流，若能帮助我改正这个错误，不胜感激。这个bug应该不是太复杂的问题，不需要改动太多代码，只是我仍然无法理解问题所在。如果大家对文件尾部有时候会出现的讨厌的多余字符不计较，这段程序还是比较好用的，呵呵～～～至于运行效率，时间什么的，自己也没太计较，上代码了～～～
代码：
huffman.c
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#define BUFFSIZE 2048
typedef struct statisElem{
unsigned char data; /*文件中的字符*/
unsigned int count; /*字符在文件中出现的次数*/
}SElem;
/*树的组织结构采用顺序结构，存在数组中，按索引查找*/
typedef struct treeNode{
SElem cData; /*字符数据*/
int leftChild; /*左儿子在数组中的索引*/
int rightChild; /*右儿子在数组中的索引*/
int parent; /*双亲索引*/
int maskLen; /*掩码位数，以位为单位，如“100101”,maskLen为6*/
unsigned char mask[32]; /*保存掩码，经计算，掩码数最大只可能为254，因此32个字节足够*/
}TreeNode;
/**
*因为最终需要将树结构存储在文件中，此部分空间为额外增加
*必须尽量减小树结构所占空间，下面结构即为精简版的树节点结构
*只保留了必要的解码需要的信息，如下
*/
typedef struct treeNodeSave
{
unsigned char data; /*字符*/
short leftChild; /*左儿子*/
short rightChild; /*右儿子*/
}TreeNodeSave;
int count = 0; /*已经发现的字符种类*/
SElem statis[256] = { {data:'\0', count:0} }; /*一个字符最多8 bits，因此最多有可能有256种组合，包括‘\0’在内*/
int treeCount;
TreeNode *huffTree = NULL; /*生成的huffman树，malloc分配，共treeCount个元素*/
TreeNodeSave *huffTreeSave = NULL; /*即将保存在文件中的树结构*/
/*
此函数仅仅在本文件内使用
主要是用在qsort函数中，用来为字符统计statis数组排序
数组内数据按照字符出现次数从大到小排序，后面编码时将大大减少搜索时间
*/
static int
Compare(const void *e1, const void *e2)
{
SElem data1 = *(SElem*)e1;
SElem data2 = *(SElem*)e2;
return data2.count-data1.count;
}
/**
*第一遍遍历整个输入文件
*/
void
FirstScan(FILE *input)
{
int i, j; /*循环索引*/
char buffer[BUFFSIZE] = {0}; /*存储文件数据的缓冲区*/
int readCount = 0; /*每一次实际读取的数据*/
int writeCount = 0; /*每一次实际写到文件中的数据*/
while((readCount = fread(buffer, sizeof(char), BUFFSIZE-1, input)) > 0)
{
buffer[readCount] = '\0';
/*
循环遍历整个buffer，统计字符出现次数
*/
for(i=0; i<readCount; i++)
{
unsigned char c = buffer[i];
/*
对此已经存储的字符统计信息，
若发现已经存入此字符，则将此字符的count加1
*/
for(j=0; j<count; j++)
{
if(c == statis[j].data)
{
statis[j].count++;
break;
}
}
/*
如果此字符是第一次出现，则将此字符存入一个新位置
*/
if(j >= count)
{
statis[count].data = c;
statis[count].count = 1;
++count;
}
}/*end for loop*/
}/*end while loop*/
/*为statis按照count值从大到小排个序，编码时可以提高查找的效率*/
qsort(statis, count, sizeof(SElem), Compare);
/************************************************************************************/
/*测试，打印统计信息*/
/*
for(i=0; i<count; i++)
{
printf("statis[%d]:{%c, %d}\n", i, statis[i].data, statis[i].count);
}*/
/***************************************************************************************/
}
/**
*在huffTree中寻找频率最小的两个节点
*/
static void
FindSmall(int *sIndex1, int *sIndex2)
{
int i;
int num;
int count1, count2;
if(count < 2)
{
perror("The file has too few chars, no need to huffman.Programme will exit!");
exit(0);
}
count1 = count2 = 0x7fffffff;
*sIndex2 = *sIndex1 = -1;
for(i=0; i<treeCount; i++)
{
num = huffTree[i].cData.count;
if(num > 0 && -1 == huffTree[i].parent)
{
if(num < count1)
{
count2 = count1;
count1 = num;
*sIndex2 = *sIndex1;
*sIndex1 = i;
}else if(num < count2)
{
count2 = num;
*sIndex2 = i;
}
}
}
}
/**
*前序遍历huffTree
*@ index: 起始下标
*@ mask: 要增加的一位编码
*/
static PreOrderCoding(int index, int mask)
{
int i, maskIndex, shiftMask, parent;
int masklen;
if(index != -1){
parent = huffTree[index].parent; //父下标
if(-1 == parent)
{
huffTree[index].maskLen = 0;
huffTree[index].mask[0] = 0;
}else{
masklen = huffTree[parent].maskLen;
/*将掩码全部清空*/
memset(huffTree[index].mask, 0, 32);
maskIndex = masklen/8;
/*
将父掩码复制给孩子
*/
for(i=0; i<=maskIndex; i++)
{
huffTree[index].mask[i] |= huffTree[parent].mask[i];
}
/*
在尾部追加一位掩码
*/
shiftMask = masklen%8;
huffTree[index].mask[maskIndex] |= mask << (7-shiftMask);
huffTree[index].maskLen = huffTree[parent].maskLen+1;
}
/*
左儿子追加掩码0，右儿子追加掩码1
*/
PreOrderCoding(huffTree[index].leftChild, 0);
PreOrderCoding(huffTree[index].rightChild, 1);
}
}
/*
建造huffman树
*/
void
BuildTree()
{
int i, j; /*循环索引*/
int maskIndex, shiftMask;
int smallIndex1, smallIndex2;
/*叶子节点数为字符，共count个，所以树节点共count*2-1*/
treeCount = count*2-1;
huffTree = (TreeNode*)malloc(sizeof(TreeNode)*treeCount);
huffTreeSave = (TreeNodeSave*)malloc(sizeof(TreeNodeSave)*treeCount);
memset(huffTree, 0, sizeof(TreeNode)*treeCount);
/*将统计数值复制到此处,并将父子全部设成-1*/
for(i=0; i<count; i++)
{
huffTree[i].cData = statis[i];
huffTree[i].leftChild = huffTree[i].rightChild = -1;
huffTree[i].parent = -1;
}
for(i=count; i<treeCount; i++)
{
huffTree[i].leftChild = huffTree[i].rightChild = -1;
huffTree[i].parent = -1;
}
/*开始建立huffman树*/
for(i=count; i<treeCount; i++)
{
FindSmall(&smallIndex1, &smallIndex2); /*寻找最小的两个索引值*/
huffTree[i].cData.data = '\0';
huffTree[i].cData.count = huffTree[smallIndex1].cData.count+huffTree[smallIndex2].cData.count;
huffTree[i].leftChild = smallIndex1;
huffTree[i].rightChild = smallIndex2;
huffTree[smallIndex1].parent = huffTree[smallIndex2].parent = i;
}
/*
前序遍历，给所有节点编码
*/
PreOrderCoding(treeCount-1, 0);
/*测试*/
/*******************************************************************************************************/
/*for(i=0; i<count; i++)
{
char c = huffTree[i].cData.data;
if(c == '\0')
printf("Char:#; count:%d; Masklen:%d;\t", huffTree[i].cData.count, huffTree[i].maskLen);
else
printf("Char:%c; count:%d;MaskLen:%d;\t", c, huffTree[i].cData.count, huffTree[i].maskLen);
for(j=0; j<huffTree[i].maskLen; j++)
{
maskIndex = j/8;
shiftMask = j%8;
printf("%d", huffTree[i].mask[maskIndex]&(1<<(7-shiftMask))?1:0);
}
printf("\n");
}*/
/**********************************************************************************************************/
/*将树结构精简，存入文件中，只保留必要的解码信息*/
for(i=0; i<treeCount; i++)
{
huffTreeSave[i].data = huffTree[i].cData.data;
huffTreeSave[i].leftChild = huffTree[i].leftChild;
huffTreeSave[i].rightChild = huffTree[i].rightChild;
}
}
void
HuffmanCode(FILE* input, FILE* output)
{
int i, j; /*循环索引*/
int m, n; /*循环索引*/
char c; /*文件中取到的字符*/
/*garbageBit:垃圾位。因为在写到最后一个字节时，有可能8位写不满，要剩余几位
必须在文件中保存位数，解码时去掉*/
char garbageBit;
int maskLen; /*掩码长度*/
int bitMask;
int writeUsed = 0; /*记录writeBuffer的使用情况,单位为bit*/
int writeIndex, writeShift;
unsigned char *mask; /*掩码，也是字符的huffman编码*/
int found = 0; /*是否找到字符对应的huffman编码，正常情况下总能找到*/
int readCount = 0, writeCount = 0;
unsigned char readBuffer[BUFFSIZE], writeBuffer[BUFFSIZE];
memset(readBuffer, 0, BUFFSIZE);
memset(writeBuffer, 0, BUFFSIZE);
printf("Huffman code in progress...\n");
/*第一遍扫描，生成字符的统计信息*/
FirstScan(input);
/*利用第一遍生成的统计信息生成huffman树*/
BuildTree();
/*开始第二编扫描，将字符编码放入输出文件中*/
fseek(input, 0L, SEEK_SET); /*将输入流重置到开始位置*/
fseek(output, 0L, SEEK_SET); /*将输出流重置到开始位置*/
/*
在输出文件中保存解码必要的信息t，reeCount为树节点数目
因为最后的一个字节可能含有垃圾信息(<8 bits),第二个字符保存垃圾信息
*/
fprintf(output, "%d%c",treeCount, 0);
fwrite(huffTreeSave, sizeof(TreeNodeSave), treeCount, output); /*写入树节点信息*/
while(0 < (readCount = fread(readBuffer, sizeof(char), BUFFSIZE, input)))
{
/*循环整个缓冲区，为每一个字符编码*/
for(i=0; i<readCount; i++)
{
found=0;
c = readBuffer[i]; /*取一个字符*/
/*查找字符编码*/
for(j=0; j<count; j++)
{
if(c == huffTree[j].cData.data)
{
found = 1;
maskLen = huffTree[j].maskLen;
mask = huffTree[j].mask;
break;
}
}/*end for*/
/*如果找到对应的字符编码，则编码，并输出到writeBuffer中*/
if(found){
writeIndex = writeUsed/8;
writeShift = writeUsed%8;
/*如果继续增加会超出writeBuffer容量*/
if(writeUsed+maskLen > 8*(BUFFSIZE-1))
{
char tmp = writeBuffer[writeIndex];
fwrite(writeBuffer, sizeof(char), writeIndex, output);
memset(writeBuffer, 0, BUFFSIZE);
writeBuffer[0] = tmp;
writeUsed = writeShift;
writeIndex = 0;
}//end if
for(m=0; m<maskLen; m++)
{
bitMask = mask[m/8]&(1<<(7-m%8))?1:0;
if(writeShift+m < 8)
{
writeBuffer[writeIndex] |= (unsigned)bitMask << (7-m) >> writeShift;
}else{
writeBuffer[writeIndex+(writeShift+m)/8] |= bitMask << (7-(m+writeShift)%8);
}
}//end for
writeUsed += maskLen;
}// end if
}/*end for*/
}/*end while,文件读取结束*/
/*
将writeBuff中剩余的字节写入文件，这里不知道为什么，垃圾位信息写不到文件中去，
文件为什么无法覆写？百思不得其解，暂时保留此bug，希望后续能解决
*/
if(writeUsed > 0)
{
int writeLen;
garbageBit = writeUsed%8;
if(0 == writeUsed%8)
{
writeLen = writeUsed/8;
}else{
writeLen = writeUsed/8+1;
}
fwrite(writeBuffer, sizeof(char), writeLen, output);
/*将垃圾位信息写入文件开头*/
fseek(output, sizeof(int), SEEK_SET);
int pos = ftell(output);
printf("garbageBit:%x; pos:%d\n", garbageBit, pos);
fwrite(&garbageBit, sizeof(char), 1, output);
//fprintf(output, "%c", garbageBit);
fflush(output);
}
/*************************************************************************/
/*测试编码是否正确*/
/*
unsigned char testBuff[BUFFSIZE];
int testTreeNum;
char cc;
fseek(output, 0L, SEEK_SET);
fscanf(output,"%d%c", &testTreeNum, &cc);
printf("%d %x\n", testTreeNum, cc);
fread(huffTreeSave, sizeof(TreeNodeSave), treeCount, output);
while(0 < (readCount=fread(readBuffer, sizeof(char), BUFFSIZE, output)))
{
int nn;
for(nn=0; nn<readCount; nn++)
{
printf("%x\t", readBuffer[nn]);
}
}
printf("\n");
*/
/***********************************************************************/
free(huffTree);
free(huffTreeSave);
printf("Huffman code compress end.\n");
}
void
HuffmanDecode(FILE *input, FILE *output)
{
int i, j; /*循环索引*/
int bit; /*0或1*/
int treeNodeNum; /*树节点数目*/
char garbageBit; /*垃圾位数目*/
int readCount=0, writeCount=0;
unsigned char readBuff[BUFFSIZE], writeBuff[BUFFSIZE];
TreeNodeSave *tree; /*保存的huffman数信息*/
TreeNodeSave *search; /*搜索用的节点指针*/
printf("Huffman decode in progress...\n");
memset(readBuff, 0L, BUFFSIZE);
fscanf(input, "%d%c", &treeNodeNum, &garbageBit);
printf("TreeNum:%d; garbageBit:%x\n", treeNodeNum, garbageBit);
if(treeNodeNum <= 0)
{
fprintf(stderr, "Bad tree node information!\n");
exit(-1);
}
tree = (TreeNodeSave*)malloc(sizeof(TreeNodeSave)*treeNodeNum);
fread(tree, sizeof(TreeNodeSave), treeNodeNum, input);
search = &tree[treeNodeNum-1]; /*将搜索指针置于最后一个元素上*/
/*循环读取文件*/
while(0 < (readCount=fread(readBuff, sizeof(char), BUFFSIZE, input)))
{
/*循环处理readBuffer中读取的字符*/
for(i=0; i<readCount; i++)
{
for(j=0; j<8; j++)
{
if(-1==search->leftChild && -1==search->rightChild )
{
if(search->data != '\0')
{
fprintf(output, "%c", search->data);
}
search = &tree[treeNodeNum-1];
}/*end if*/
bit = (readBuff[i]&(1<<(7-j)))? 1: 0;
search = bit? &tree[search->rightChild]: &tree[search->leftChild];
}/*end for*/
}/*end for*/
}/*end while*/
free(tree);
printf("Huffman decode end.\n");
}
main.c
#include <stdio.h>
#include <stdlib.h>
extern void HuffmanCode(FILE *input, FILE *output);
extern void HuffmanDecode(FILE *input, FILE *output);
int
main(int argc, char **argv)
{
FILE *input=NULL, *output=NULL;
if(argc != 4)
{
perror("wrong command format!");
printf("Correct:%s [-c/-d] inputFile outputFile\n", argv[0]);
exit(-1);
}
if(!(input = fopen(argv[2], "r")))
{
perror("Can not open the input file!");
exit(-1);
}
if(!(output = fopen(argv[3], "w+")))
{
perror("Can not open the output file!");
exit(-1);
}
if(0 == strcmp(argv[1], "-d"))
{
HuffmanDecode(input, output);
}else{
HuffmanCode(input, output);
}
return 0;
}
相关阅读 更多 +
