哈夫曼编码演示.ppt

哈夫曼编码与文件压缩 ——1236003 6120610319 杜嘉诚 总体介绍 1 程序介绍 2 关键问题 3 内容 结束感想 4 总体介绍 哈夫曼编码是一种编码方式，经常用于数据压缩。在计算机信息处理中，哈夫曼编码是一种一致性编码法(又称“熵编码法”)，用于数据的无损耗压缩。 它的基本原理是建立一张编码表将原字符(例如某文件的一个符号)进行重新编码。它是根据每一个源字符出现的概率而建立起来的，这些字符(如字母)出现的次数越多，其编码的位数就越少。这时的编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的)。 这种方法是由David.A.Huffman发展起来的，故称为哈夫曼编码。 1 总体介绍 1 可以把哈夫曼编码比作道路优化，原本每个字符占一个char型，也就是8bit，所以所占空间为 V= 8 * 字符数 （bit） 而编码后，频率高的字符可以用少于8bit表示，而频率低的字符则用多余8bit表示，这样所占空间为 V= v1*n1+v2*n2+v3*n3+··· 其中vi代表每个字符所占bit，ni代表字符出现个数，可以证明这样所产生的编码所占空间是最小的 可以证明这样所得的编码所占空间是最小的。 直观的理解上，就好比城市规划。投入更多的资金来改善车流量大的道路，而对车流量小的道路减小投入，这样可使道路资源更充分利用。 在bit的利用上也是如此。 程序介绍 2 压缩程序 思路： 1.读入文件，统计频率，为出现的每一个字符建立节点,并排成一列 2.将节点转化成哈夫曼树 3.利用哈夫曼树产生编码表文件 4.利用编码将源文件转换成二进制编码表示的文本文件 5.将转码后的文本文件压缩成bin文件 a b c 0.1 0.2 0.7 0 0 1 1 产生代码 a: 00 b: 01 c: 1 程序介绍 2 压缩程序 函数： struct tnode* talloc(int symbol, float freq) ——为字符创建节点 void pq_insert(struct tnode* p) ——将节点插入升序排列的队列 struct tnode* pq_pop() ——将队列中第一个（最小频率）节点删除 void generate_code(struct tnode* root, int depth) ——产生编码表 void dump_code(FILE* fp) ——输出编码表 void encode(FILE* fout) ——压缩文件 void getfreq(float freq[]) ——统计字符频率 疑难备注： pq_insert()与pq_pop()两个函数搭配使用，前者用于构建节点队列，方便遍历节点从而找到最小节点。 后者用于建立哈夫曼树，也就是在建立父节点后在队列中删除那两个最小的子节点，以免每次找到同样的两个最小节点。 a b c int main(){ //初始化 struct tnode* p = NULL,* lc, *rc; float freq[255]= {0}; int NCHAR = 255,i = 0; memset(code, 0, sizeof (code)); //统计频率 getfreq(freq); //建立节点队列 for (i = 0; i NCHAR; i++) if(freq[i]0) pq_insert(talloc(i, freq[i])); //建立哈夫曼树（删除子节点创建父节点） while(qhead-next!=NULL) { lc = pq_pop(); rc = pq_pop(); p = talloc(0, lc-freq + rc-freq); lc-parent = rc-parent = p; //建立父子关系 p-right = rc; p-left = lc; p-isleaf = 0; pq_insert(p); } root = pq_pop(); //创建并输出编码表