训练2+用Huffman编码实现文本文件的无损压缩

用Huffman编码对文件进行压缩的C语言实现
路炜;门玉梅;李建俊
【期刊名称】《福建电脑》
【年(卷),期】2012(028)001
【摘要】本文介绍了采用Huffman编码对ASCII码文件进行压缩的基本原理，并用C语言程序实现了这个压缩过程。

文中给出了比较完整的C语言程序代码，可以直接用于调试实验。

【总页数】2页(P48-49)
【作者】路炜;门玉梅;李建俊
【作者单位】河北师范大学附属民族学院,河北石家庄050091;河北师范大学附属民族学院,河北石家庄050091;河北师范大学附属民族学院,河北石家庄050091【正文语种】中文
【中图分类】TP391.41
【相关文献】
1.Huffman编码和解码的C语言实现 [J], 张文质;郝鹏翼
2.用Huffman编码进行文件压缩的方法 [J], 潘玮华
3.基于Huffman编码的XML文件压缩存储算法研究与实现 [J], 周伟
4.运用Huffman编码进行数据压缩的新算法 [J], 何昭青
5.基于Huffman编码的XML文件压缩存储算法研究与实现 [J], 周伟
因版权原因，仅展示原文概要，查看原文内容请购买。

哈夫曼编码无损数据压缩的原理和实现无损数据压缩技术是计算机领域中的一项重要技术，而哈夫曼编码作为其中一种经典的压缩算法，被广泛应用于数据传输和存储中。

本文将介绍哈夫曼编码的原理和实现方法。

一、原理哈夫曼编码是一种变长编码（Variable Length Code）技术，它利用出现频率较高的字符使用较短的编码，而出现频率较低的字符使用较长的编码，从而达到数据压缩的目的。

其原理如下：1. 统计字符频率：首先，需要统计待编码的数据中每个字符出现的频率。

这可以通过扫描整个数据流来实现。

统计结果可以用于构建哈夫曼树。

2. 构建哈夫曼树：根据字符频率构建哈夫曼树，其中频率越高的字符位于树的顶部，频率越低的字符位于树的底部。

构建哈夫曼树的过程中，使用最小堆来选择两个最小频率的节点，将它们合并为一个新的节点，并更新频率。

3. 分配编码：通过沿着哈夫曼树的路径，从根节点到达叶子节点，将0或1分配给每个字符。

注意，由于哈夫曼树的性质，没有一个字符的编码是另一个字符编码的前缀，因此哈夫曼编码是一种无前缀编码（Prefix-Free Code）。

4. 压缩数据：根据哈夫曼编码表，将原始数据中的每个字符替换为对应的编码，从而得到压缩后的数据。

二、实现哈夫曼编码的实现通常包括以下几个步骤：1. 统计字符频率：读取待编码的数据流，统计每个字符的频率，并构建字符频率表。

2. 构建哈夫曼树：根据字符频率表构建哈夫曼树。

可以使用最小堆来选择两个最小频率的节点进行合并，直至构建出完整的哈夫曼树。

3. 生成哈夫曼编码表：通过遍历哈夫曼树的路径，生成每个字符对应的哈夫曼编码。

可以使用递归算法或迭代算法来实现。

4. 压缩数据：根据生成的哈夫曼编码表，将原始数据中的每个字符替换为对应的编码。

同时，需要记录编码后数据的长度和哈夫曼编码表，以便解码时使用。

5. 解压缩数据：根据哈夫曼编码表，将编码后的数据解码为原始数据。

在实际应用中，哈夫曼编码通常用于对文本文件、图像、音频等数据进行压缩。

Huffman的应用之文件压缩与解压缩最近这段时间一直在学习树的这种数据结构,也接触到了Huffman树以及了解了什仫是Huffman编码,而我们常用的zip压缩也是利用的Huffman编码的特性，那仫是不是可以自己实现一个文件压缩呢？当然可以了.在文件压缩中我实现了Huffman树和建堆Heap的代码，zip压缩的介绍>下面开始介绍自己实现的文件压缩的思路和问题...1).统计>读取一个文件统计这个文件中字符出现的次数.2).建树>以字符出现的次数作为权值使用贪心算法构建Huffman树(根据Huffman树的特性>字符出现次数多的一定靠近根结点，出现次数少的一定远离根结点).3).生成Huffman编码>规则左0右1.4).压缩>再次读取文件,根据生成的Huffman编码压缩文件.5).生成配置文件>将字符以及字符出现的次数写进配置文件中.6).解压缩>利用配置文件还原出Huffman树,根据压缩文件还原出原文件.7).测试>判断解压是否正确需要判断原文件和解压缩之后的文件是否相同,利用Beyond Compare软件进行对比.下面是我举的一个简单的范例，模拟压缩和解压缩的过程，希望有读者有帮助利用Beyond Compare软件进行对比>在实现中出现了很多的问题,下面我提出几个容易犯的问题,仅供参考1).在使用贪心算法构建Huffman树的时候,如果我们以unsigned char一个字节来存储它总共有2^8=256个字符,如果将所有的字符都构建Huffman树,这不仅降低了效率还将分配极大的内存.所以我设立了非法值这个概念,只有当字符出现的次数不为0的时候才将该字符构建到Huffman树中.2).在写压缩文件的时候我们是将字符对应的Huffman编码转化为对应的位,每当填满一个字节(8位)后再写入压缩文件中.如果最后一个字节没有填满我们就将已经填的位移位空出后几个位置,将未满的位置补0补满一个字节再写入压缩文件中.3).如果我们将源文件压缩之后再去解压,因为你的Huffman树和Huffman编码都是在压缩函数中得到的,此时再去解压那仫你的Huffman编码以及不存在了该如何去还原文件呢？这就是为什仫要生成配置文件的原因了,在配置文件中写入了字符以及字符出现的次数.在解压缩中根据配置文件构建新的Huffman树.4).由压缩文件还原文件的时候如何知道压了多少个字符呢？也就是说因为我们在压缩的时候最后一个字节是补了0的在解压缩的时候可能会把这个补的位当成字符的编码来处理.一种想法是在统计字符出现的次数的时候设置一个变量,每读取一个字符该变量就加1,最后将该变量写进配置文件中.另外一种想法就是根据根结点的权值,通过上述简单的实例观察可知根结点权值中的_count就是字符出现的次数.解决了以上几个问题,我的程序已经可以压缩那256个字符并正确的还原了,那仫如果是大文件或者是汉字，图片以及音频视频呢？1).因为有些特殊的字符编码，所以我们统计字符出现的次数的时候应该用的是unsigned char,刚开始我用的文件结束标志是EOF在ASII中它的编码是-1此时已经不可以用EOF来判断是否文件结束了，所以我用了feof这个函数来判断文件是否结束.2).统计字符出现次数应该用的类型是long long,这就解决了大文件的压缩和解压缩的问题了.3).因为汉字，图片，视频这些在内存中是以二进制的形式存在的,所以我们将以文本形式打开读或者写的修改为以二进制的形式读或者写.为了验证大文件的压缩我找了一个8.09M的文件压缩之后是6.50M,并且可以正确还原.1).测试效率>2).利用Beyond Compare软件进行对比，如果一样说明压缩成功>[cpp] view plain copy print?在CODE上查看代码片派生到我的代码片#define _CRT_SECURE_NO_W ARNINGS 1#pragma once#include "Heap.h"template<class T>struct HuffmanTreeNode{T _weight;HuffmanTreeNode<T> *_left;HuffmanTreeNode<T> *_right;HuffmanTreeNode<T> *_parent;HuffmanTreeNode(const T& w=T()):_weight(w),_left(NULL),_right(NULL),_parent(NULL){}};template<class T>class HuffmanTree{typedef HuffmanTreeNode<T> Node;public:HuffmanTree():_root(NULL){}HuffmanTree(const T* a,size_t size):_root(NULL){_root=_CreatHuffmanTree(a,size);}//将未出现的字符过滤出来，不构造堆HuffmanTree(const T* a,size_t size,const T& invalid){_root=_CreatHuffmanTree(a,size,invalid);}Node* GetRoot(){return _root;}~HuffmanTree(){_Destroy(_root);}protected:Node *_CreatHuffmanTree(const T* a,size_t size){struct NodeLess{bool operator()(Node *l,Node *r)const{return l->_weight < r->_weight;}};Heap<Node *,NodeLess> minHeap;//建立结点并放入vector中for (size_t i=0;i<size;++i){Node *tmp=new Node(a[i]);minHeap.Push(tmp);}//取出较小的两个结点作为左右孩子并构建父结点while (minHeap.Size() > 1){Node *left=minHeap.Top();minHeap.Pop();Node *right=minHeap.Top();minHeap.Pop();Node *parent=new Node(left->_weight + right->_weight);parent->_left=left;parent->_right=right;left->_parent=parent;right->_parent=parent;minHeap.Push(parent);}return minHeap.Top();}//思路类似不带过滤功能的Node *_CreatHuffmanTree(const T* a,size_t size,const T& invalid) {struct NodeLess{bool operator()(Node *l,Node *r)const{return l->_weight < r->_weight;}};Heap<Node *,NodeLess> minHeap;//建立结点并放入vector中for (size_t i=0;i<size;++i){if(a[i] != invalid){Node *tmp=new Node(a[i]);minHeap.Push(tmp);}}//取出较小的两个结点作为左右孩子并构建父结点while (minHeap.Size() > 1){Node *left=minHeap.Top();minHeap.Pop();Node *right=minHeap.Top();minHeap.Pop();Node *parent=new Node(left->_weight + right->_weight);parent->_left=left;parent->_right=right;left->_parent=parent;right->_parent=parent;minHeap.Push(parent);}return minHeap.Top();}void _Destroy(Node *&root)if(root == NULL)return ;Node *cur=root;if(cur){_Destroy(cur->_left);_Destroy(cur->_right);delete cur;cur=NULL;return ;}}protected:Node *_root;};void testHuffmanTree(){int a[]={0,1,2,3,4,5,6,7,8,9};int size=sizeof(a)/sizeof(a[0]);HuffmanTree<int> ht(a,size);}[cpp] view plain copy print?在CODE上查看代码片派生到我的代码片#define _CRT_SECURE_NO_W ARNINGS 1#pragma once//利用仿函数的特性实现代码的复用性template<class T>struct Small{bool operator()(const T& l,const T& r){return l < r;}};template<class T>struct Large{bool operator()(const T& l,const T& r)return l > r;}};template<class T,class Compare=Large<T>> //缺省是建小堆class Heap{public:Heap(){}Heap(const T *a,int size){assert(a);_a.reserve(size);for (int i=0;i<size;++i){_a.push_back(a[i]);}//建堆的时候从倒数第一个非叶子结点开始.for (int j=(size-2)/2;j>=0;--j){_AdjustDown(j);}}void Push(const T& x){_a.push_back(x);_AdjustUp(_a.size()-1);}void Pop(){assert(!_a.empty());swap(_a[0],_a[_a.size()-1]);_a.pop_back();_AdjustDown(0);}size_t Size(){return _a.size();}bool Empty(){return _a.empty();const T& Top()const{assert(!_a.empty());return _a[0];}void Display(){for (size_t i=0;i<_a.size();++i){cout<<_a[i]<<" ";}cout<<endl;}protected:void _AdjustDown(int root){int parent=root;size_t child=2*root+1;while (child < _a.size()){Compare com;//child指向左右孩子中较大的那个数//if (child+1 < _a.size()// && _a[child+1] > _a[child])if(child+1 < _a.size()&& com(_a[child+1],_a[child])){child++;}//if (_a[child] > _a[parent])if(com(_a[child],_a[parent])){swap(_a[child],_a[parent]);parent=child;//初始的child默认指向左孩子child=2*parent+1;}elsebreak;}}void _AdjustUp(int child){while (child > 0){int parent=(child-1)/2;Compare com;//if (_a[child] > _a[parent])if(com(_a[child],_a[parent])){swap(_a[child],_a[parent]);child=parent;}else//插入的数据比父节点的数据域小break;}}protected:vector<T> _a;};//利用堆解决优先级队列的问题template<class T,class Compare=Large<T>>class PriorityQueue{public:PriorityQueue(int *a,int size):_pq(a,size){}void Push(const T& x){_pq.Push(x);}void Pop(){_pq.Pop();}const T& Top()const{return _pq.Top();}void Display(){_pq.Display();}protected:Heap<T,Compare> _pq;};[cpp] view plain copy print?在CODE上查看代码片派生到我的代码片#define _CRT_SECURE_NO_W ARNINGS 1#pragma once#include "HuffmanTree.h"typedef long long Type;struct CharInfo{unsigned char _ch; //出现的字符Type _count; //统计次数string _code; //Huffman编码CharInfo(Type count=0):_ch(0),_count(count),_code(""){}//重载对应的操作符CharInfo operator + (const CharInfo& fc)const{return CharInfo(_count + fc._count);}bool operator != (const CharInfo fc)const{return _count != fc._count;}bool operator < (const CharInfo& fc)const{return _count < fc._count;}};class FileCompress{public://默认的构造函数FileCompress(){for(size_t i=0;i<256;++i){_infos[i]._ch=i;}}string Compress(const char *filename){assert(filename);FILE *pf=fopen(filename,"rb");assert(pf);unsigned char ch=fgetc(pf);//统计字符出现的次数while (!feof(pf)){_infos[ch]._count++;ch=fgetc(pf);}//以该字符出现的次数构建一颗HuffmanTree.CharInfo invalid; //非法值HuffmanTree<CharInfo> ht(_infos,256,invalid);//生成Huffman编码string code;_CreatHuffmanCode(ht.GetRoot(),code);//_CreatHuffmanCode(ht.GetRoot());//压缩文件fseek(pf,0,SEEK_SET); //回到文件头string compressfile=filename;compressfile += ".compress"; //压缩后的文件名FILE *fin=fopen(compressfile.c_str(),"wb");assert(fin);size_t pos=0; //记录位数unsigned char value=0;ch=fgetc(pf);while (!feof(pf)){string &code=_infos[ch]._code;for (size_t i=0;i<code.size();++i){value <<= 1;if(code[i] == '1')value |= 1;elsevalue |= 0; //do-nothing++pos;if(pos == 8) //满一个字节{fputc(value,fin);value=0;pos=0;}}ch=fgetc(pf);}if(pos) //解决不足8位的情况.{value <<= (8-pos);fputc(value,fin);}//配置文件--便于重建Huffman树string ename=filename;configfilename += ".config";FILE *finconfig=fopen(configfilename.c_str(),"wb");assert(finconfig);string line;char buff[128];for (size_t i=0;i<256;++i){//一行一行的读if (_infos[i]._count){line += _infos[i]._ch;line += ",";line += _itoa(_infos[i]._count,buff,10);line += "\n";//fputs(line.c_str(),finconfig);fwrite(line.c_str(),1,line.size(),finconfig);line.clear();}}fclose(pf);fclose(fin);fclose(finconfig);return compressfile;}string UnCompress(const char *filename){assert(filename);string configfilename=filename;size_t index=configfilename.rfind(".");configfilename=configfilename.substr(0,index); configfilename += ".config";FILE *foutconfig=fopen(configfilename.c_str(),"rb"); assert(foutconfig);string line;//读取配置文件--获取字符出现的次数unsigned char ch=0;while (ReadLine(foutconfig,line)){if(line.empty()){line += '\n';continue;}//读到空行ch=line[0];_infos[ch]._count = atoi(line.substr(2).c_str());line.clear();}//构建Huffman树CharInfo invalid;HuffmanTree<CharInfo> hft(_infos,256,invalid);//根结点的权值也就是字符出现的次数总和HuffmanTreeNode<CharInfo> *root=hft.GetRoot(); Type charcount=root->_weight._count;//解压缩string uncompressfilename=filename;index=uncompressfilename.rfind("."); uncompressfilename=uncompressfilename.substr(0,index); uncompressfilename += ".uncompress";FILE *fin=fopen(uncompressfilename.c_str(),"wb"); assert(fin);//由压缩文件还原文件string compressfilename=filename;FILE *fout=fopen(compressfilename.c_str(),"rb");assert(fout);HuffmanTreeNode<CharInfo> *cur=root;int pos=7;ch=fgetc(fout);while (charcount > 0){while (cur){if(cur->_left == NULL && cur->_right == NULL){//叶子结点fputc(cur->_weight._ch,fin);cur=root;--charcount;if (charcount == 0) //所有的字符都处理完成break;}if (ch & (1 << pos)) //检查字符的每个位cur=cur->_right; //1向右走elsecur=cur->_left; //0向左走--pos;if(pos < 0) //一个字节解压完成{ch=fgetc(fout);pos=7;}}}fclose(foutconfig);fclose(fin);fclose(fout);return uncompressfilename;}//读取一行字符并放在line中bool ReadLine(FILE *fout,string& line){int ch=fgetc(fout);if(ch == EOF)return false;while (ch != EOF && ch != '\n'){line += ch;ch=fgetc(fout);}return true;}protected://递归的方法求HuffmanTreeCodevoid _CreatHuffmanCode(HuffmanTreeNode<CharInfo> *root,string &code) {if(root == NULL)return ;_CreatHuffmanCode(root->_left,code+'0');_CreatHuffmanCode(root->_right,code+'1');if(root->_left == NULL && root->_right == NULL) //叶子结点{_infos[root->_weight._ch]._code=code;}}//非递归求HuffmanTreeCodevoid _CreatHuffmanCode(HuffmanTreeNode<CharInfo> *root){if(root == NULL)return ;_CreatHuffmanCode(root->_left);_CreatHuffmanCode(root->_right);if(root->_left == NULL && root->_right == NULL) //叶子结点{string& code=_infos[root->_weight._ch]._code;HuffmanTreeNode<CharInfo> *cur=root;HuffmanTreeNode<CharInfo> *parent=root->_parent;while (parent){if(parent->_left == cur)code.push_back('0'); //左0elsecode.push_back('1'); //右1cur=parent;parent=cur->_parent;}//编码是从根到叶子结点的，需要逆置reverse(code.begin(),code.end());}}protected:CharInfo _infos[256];};void testFileCompress(){FileCompress fc;cout<<"开始压缩"<<endl;cout<<"压缩用时:";int start=GetTickCount();press("2.png"); //input input.BIG 3.mp3int end=GetTickCount();cout<<end-start<<endl;cout<<"开始解压"<<endl;cout<<"解缩用时:";start=GetTickCount();fc.UnCompress("press"); //press press 3.mp3end=GetTickCount();cout<<end-start<<endl;}void testFileUncompress(){FileCompress fc;cout<<"开始解压"<<endl;cout<<"解缩用时:";int start=GetTickCount();fc.UnCompress("2.png");int end=GetTickCount();cout<<end-start<<endl;}经过测试这个小项目已经可以压缩并还原一些文件了，目前还没有发现什仫大的Bug,如果有童鞋发现请第一时间告诉我哦...。

数据结构课程设计题目名称：huffman编码与解码实现文件的压缩与解压专业年级：组长：小组成员：指导教师：二〇一二年十二月二十六日目录一、目标任务与问题分析 (2)1.1目标任务 (2)1.2问题分析 (2)二、算法分析 (2)2.1构造huffman树 (2)2.1.1 字符的统计 (2)2.1.2 huffman树节点的设计 (2)2.2构造huffman编码 (3)2.2.1 huffman编码的设计 (3)2.3 压缩文件与解压文件的实现 (3)三、执行效果 (4)3.1界面 (4)3.2每个字符的编码 (4)3.3操作部分 (5)3.4文件效果 (6)四、源程序 (7)五、参考文献 (16)huffman编码与解码实现文件的压缩与解压一、目标任务与问题分析1.1目标任务采用huffman编码思想实现文件的压缩和解压功能，可以将任意文件压缩，压缩后也可以解压出来。

这样即节约了存储空间，也不会破坏文件的完整性。

1.2问题分析本问题首先应该是利用哈夫曼思想，对需要压缩的文件中的个字符进行频率统计，为了能对任意的文件进行处理，应该所有的文件以二进制的方式进行处理，即对文件（不管包含的是字母还是汉字）采取一个个的字节处理，然后根据统计的频率结果构造哈夫曼树，然后对每个字符进行哈夫曼编码，然后逐一对被压缩的文件的每个字符构建的新的哈夫曼编码存入新的文件中即得到的压缩文件。

解压过程则利用相应的哈夫曼树及压缩文件中的二进制码将编码序列译码，对文件进行解压，得到解压文件。

二、算法分析2.1构造huffman树要利用哈夫曼编码对文本文件进行压缩，首先必须知道期字符相应的哈夫曼编码。

为了得到文件中字符的频率，一般的做法是扫描整个文本进行统计，编写程序统计文件中各个字符出现的频率。

由于一个字符的范围在[0-255]之间，即共256个状态，所以可以直接用256个哈夫曼树节点即数组（后面有节点的定义）空间来存储整个文件的信息，节点中包括对应字符信息，其中包括频率。

数据结构课程设计报告Huffman编码与解码实现文件压缩与解压学号：06080711姓名：李爱武指导教师：陈波二○一零年九月三日目录目录 (2)目标任务和问题分析 (3)算法及思想描述 (3)---------建立哈夫曼树、压缩、解压缩程序结构及测试流程 (5)测试结果分析 (12)收获与体会 (12)参考文献 (13)Huffman编码与解码实现文件压缩与解压一、目标任务与问题分析1.1目标任务采用哈夫曼编码思想实现文件的压缩和解压缩功能，可以将任意文件压缩成任意的压缩文件类型，并且能将压缩后的文件解压成相应的源文件。

1.2问题分析本问题首先应该是利用哈夫曼思想，对需要压缩的文件中的个字符进行频率统计，为了能对任意的文件进行处理，应该所有的文件以二进制的方式进行处理，即对文件（不管包含的是字母还是汉字）采取一个个的字节（unsigned char）处理，然后根据统计的频率结果构造哈夫曼树，然后对每个字符进行哈夫曼编码，然后逐一对被压缩的文件的每个字符构建的新的哈夫曼编码存入新的文件中即得到的压缩文件。

解压过程则利用相应的哈夫曼树及压缩文件中的二进制码将编码序列译码，对文件进行解压，得到解压文件。

二、算法思想描述2.1 构造哈夫曼树要利用哈夫曼编码对文本文件进行压缩，首先必须知道期字符相应的哈夫曼编码。

为了得到文件中字符的频率，一般的做法是扫描整个文本进行统计，编写程序统计文件中各个字符出现的频率。

由于一个字符的范围在[0-255]之间，即共256个状态，所以可以直接用256个哈夫曼树节点即数组（后面有节点的定义）空间来存储整个文件的信息，节点中包括对应字符信息，其中包括频率。

2.1.1 哈夫曼树节点的设计用结构体NODE来存储节点的信息，其中有成员频率weight、父节点parent、左枝节点lchild、右枝节点rchild、对应的编码code。

2.1.2文件字符频率处理由于所有的文件都采用字节存取，字符的最多个数就只能是256个，即ASCII码在0-255之间，而我们用的是数组来存储文件的信息，我们用NODE[256]来统计文件的所有信息。

Huffman编码在数据压缩中的实际应用案例Huffman编码是一种常用的数据压缩算法，它通过利用字符出现频率的统计信息，将出现频率较高的字符用较短的编码表示，从而实现数据的高效压缩。

本文将介绍Huffman编码在实际应用中的各种案例。

1. 文本文件压缩文本文件是最常见的需要进行压缩的数据类型之一。

Huffman编码可以通过分析文本中出现的字符及其频率，为每个字符生成唯一的编码。

根据字符出现的频率不同，生成的编码长度也不同，使得出现频率较高的字符可以用更短的编码表示，从而实现对文本文件的有效压缩。

例如，一个包含大量英文字符的文本文件，使用Huffman编码可以将每个字符表示为一个较短的二进制序列，从而极大地减少文件大小。

2. 图像压缩图像是另一个常见的需要进行压缩的数据类型。

Huffman编码在图像压缩中的应用主要体现在色彩编码上。

对于彩色图像，Huffman编码可以将不同的颜色值映射为不同的二进制序列，使得出现频率较高的颜色可以用较短的编码表示。

通过使用Huffman编码，可以将图像文件压缩为更小的文件大小，而且在解压缩时能够恢复高质量的图像。

3. 音频压缩音频文件的压缩通常是有损压缩，即通过减少音频数据的冗余和不重要的部分来实现压缩。

Huffman编码可以用于对音频信号进行压缩编码，特别是在语音文件压缩中应用广泛。

通过对语音中的音频信号进行采样和量化，并使用Huffman编码对采样后的数据进行压缩，可以显著减少语音文件的大小。

这在电信领域中被广泛应用于语音通信和存储。

4. 视频压缩类似于音频压缩，视频压缩也是有损压缩的一种形式。

在视频压缩中，Huffman编码常常与其他压缩算法（如离散余弦变换或小波变换）结合使用，以进一步减小文件大小。

Huffman编码可以用于对视频中的图像帧进行编码，从而减少文件大小并提高传输和储存效率。

例如，在MPEG标准中，Huffman编码被用于对DCT变换后的视频图像进行熵编码，以实现高效的视频压缩。

使用哈夫曼树对英文文本进行压缩的简单代码例子## 一、简介哈夫曼树（Huffman Tree）是一种常用的字符编码方法，可以用来对英文文本进行压缩。

它根据字符出现的频率逐渐建立一颗二叉树，使得字符出现频率高的，用较短的编码表示，反之字符出现频率低的，用较长的编码表示。

下面给出一个简单的使用哈夫曼树对英文文本进行压缩的代码实例。

## 二、代码实例```python#!/usr/bin/env python# -*- coding: utf-8 -*-# 使用哈夫曼树对英文文本进行压缩# 统计每个字符出现的频率def get_frequency(input_str):frequency_dic = {}for c in input_str:if c in frequency_dic:frequency_dic[c] += 1else:frequency_dic[c] = 1return frequency_dic# 生成哈夫曼树def build_huffman_tree(frequency_dic):while len(frequency_dic) > 1:# 每次从频率字典中取出最小的两个字符，拼接成新字符c1, count1 = sorted(frequency_dic.items(), key=lambda x: x[1])[0]c2, count2 = sorted(frequency_dic.items(), key=lambda x: x[1])[1]new_c = c1 + c2# 构建新字符的频率字典，比如字符'ab'，频率是'a'和'b'的频率之和new_count = count1 + count2# 将新字符加入到频率字典中去frequency_dic[new_c] = new_count# 将取出的最小的两个字符从频率字典中删除del frequency_dic[c1]del frequency_dic[c2]# 频率字典中剩下最后一个字符就是根节点，返回该节点return list(frequency_dic.keys())[0]# 将哈夫曼树转换成编码表def build_huffman_code(huffman_tree):# 以字典的形式返回code_dic = {}# 从根节点开始，依次深度遍历哈夫曼树 def dfs(node, code):if len(node) == 1:# 叶子节点直接根据编码表添加进字典中 code_dic[node] = codeelse:# 非叶子节点，分别从左右子节点继续遍历 dfs(node[0], code + '0')dfs(node[1], code + '1')dfs(huffman_tree, '')return code_dic# 哈夫曼编码压缩def huffman_zip(input_str, code_dic): output_str = ''for c in input_str:output_str += code_dic[c]return output_str# 主函数def main():# 需要压缩的英文文本input_str = 'this is an english text'# 统计每个字符出现的频率frequency_dic = get_frequency(input_str)print('字符出现频率：', frequency_dic)# 根据字符出现的频率，生成哈夫曼树huffman_tree = build_huffman_tree(frequency_dic) print('哈夫曼树：', huffman_tree)# 将哈夫曼树转换成编码表code_dic = build_huffman_code(huffman_tree)print('编码表：', code_dic)# 哈夫曼编码压缩output_str = huffman_zip(input_str, code_dic)print('压缩后的字符串：', output_str)if __name__ == '__main__':main()```## 三、总结上述代码中，先通过统计每个字符出现的频率构建频率字典，再根据频率字典构建哈夫曼树，然后将哈夫曼树转换成编码表，最后对英文文本使用编码表进行压缩。

哈夫曼编码算法详解在计算机科学中，哈夫曼编码是一种压缩算法，也叫做霍夫曼编码，是由霍夫曼(Huffman)在1952年首创的。

霍夫曼编码是一种无损压缩算法，可以对文本文件、音频文件、图像文件等各种类型的文件进行压缩。

1. 哈夫曼编码的原理哈夫曼编码是基于频率统计的思想，通过统计每个字符在文件中出现的频率，选择出现频率最高的字符，将其映射为一组比特位，出现频率较低的字符则映射为比高的比特位，从而实现对文件的压缩。

通过哈夫曼编码，可以将文件压缩到原始大小的一半甚至更小。

2. 哈夫曼编码的实现哈夫曼编码的实现需要进行几个步骤：2.1 统计字符的出现频率从文件中读取字符，统计每个字符在文件中出现的次数，可以使用一个数组或字典来保存每个字符的出现次数。

对于英文文本来说，出现频率最高的字符是空格，其次是字母“e”。

2.2 构建哈夫曼树将所有的字符按照出现频率从小到大排序，选出出现频率最小的两个字符作为左右子节点，其父节点的出现频率为左右子节点出现频率之和。

重复这个过程，直到节点数为1，这样就得到了一棵哈夫曼树。

2.3 生成哈夫曼编码从哈夫曼树的根节点开始，遍历所有的节点，将左子节点标记为0，将右子节点标记为1，将所有的叶子节点的字符和对应的哈夫曼编码保存到一个字典中。

最终得到了每个字符对应的哈夫曼编码。

2.4 进行压缩将文件中每个字符替换为对应的哈夫曼编码，然后将所有的哈夫曼编码拼接成一个二进制数，在最后不足8位的位置补零，将其存储到文件中。

这样就完成了文件的压缩。

3. 哈夫曼编码的优点哈夫曼编码具有以下优点：3.1 压缩率高由于哈夫曼编码是根据不同字符的出现频率来进行编码的，出现频率高的字符用较短的编码表示，出现频率低的字符用较长的编码表示，能够最大限度地减少文件的大小，从而达到高的压缩率。

3.2 唯一解哈夫曼编码是通过构建哈夫曼树来得到每个字符对应的编码，哈夫曼树的构建是唯一的，因此哈夫曼编码也是唯一的。

《数据结构》实验报告利用Huffman编码对文件进行压缩解压学生:XXX学号:XXXXXXXX联系:XXXXXX@(一)基本信息1.实验题目利用Huffman编码对文件进行压缩解压2.完成人（姓名、学号）姓名：XXX 学号：XXXXXXXX3.报告日期2007年12月12日星期二(二)实习内容简要描述1.实习目标学会对树的基本操作学会对文件进行操作利用Huffman编码对文件压缩解压2.实习要求实现最小堆模板类利用最小堆构建Huffman树实现Huffman编码和解码根据用户从键盘输入的报文文本,输出各字符的Huffman编码以及报文的编码根据用户从键盘输入一串报文文本，输出各字符的Huffman编码输出报文的Huffman编码及长度根据输入的Huffman编码，解码输出利用Huffman编码和解码对二进制文件的压缩和解压(三)报告主要内容1.设计思路开发环境：Microsoft Visual C++ 2005设计思路：1.设计Pack类储存字符的权值2.设计MinHeap模板类构建最小堆3.设计ExtBinTree模板类为带权二叉树4.设计Compress模板类以实现文件的压缩解压2.主要数据结构1.MinHeap.h: 头文件,包含MinHeap模板类的类界面以及定义;2.HuffmanTree.h:头文件,包含ExtBinTree模板类以及Compress模板类的类的的类界面以及定义3.main.cpp:调用上述头文件实现相关操作3.主要代码结构主要代码结构为见附件中各文件的代码注释4.主要代码段分析主要代码段分析，见附件中的代码注释(四)实习结果1.基本数据源程序代码行数：约800行完成该实习投入的时间：二十四小时(不包括写实验报告的时间)与其他同学讨论交流情况:感谢刘畅同学对程序的测试2.测试数据设计1.对屏幕输入字符进行Huffman编码2.根据Huffman树非唯一性,虽然和课件上有些许不同,但是还是正确的3.输入字符串:CASTCASTSATATATASA4.输出编码:A:0 C:110 S:111 T:105.输入霍夫曼编码:01110101101106.输出译码:ASATCC7.8.对”实验05.PPT”的压缩操作9.使用0秒(不足一秒按0秒计算),压缩率为56.1755%10.对”实验05.ppt.hfm”(即刚才生成的压缩文件)的解压操作11.使用0秒(不足一秒按0秒计算),解压后文件无异常12.对一个18M的EXE安装包前后进行压缩和解压操作,分别用时10秒和9秒3.测试结果分析A)程序运行的系统资源配置操作系统：Microsoft Windows XP Professional SP2CPU: AMD Athlon 3600+ 2.0GRAM: 1024M DDRII开发环境：Microsoft Visual C++ 2005B)对TXT文档进行压缩和解压后,通过WinMerge检验和原文件无差异C)对MP3和EXE文件压缩和解压后仍能正常使用D)对于中文名字和带有空格的路径均能正确无误识别E)文件名只能小于16个字符(包括后缀名),否则解压会出错(只预留了16个字节用于储存文件名)F)相对于不用文件块读写的程序,效率提高了三倍以上G)具有动态进度条,可以显示当前压缩和解压的进度百分比(当然消耗了一些系统资源)H)出错处理不够充分,特别是cin部分,如果误输入可能会造成死循环(五)实习体会1.实习过程中遇到问题及解决过程A)一开始时候的程序运行很慢,,压缩一个4M左右的文件需要七八秒,后来改用文件块缓存字节来读写后,压缩一个4M的文件只需要两秒左右的时间.本来是只想写一个进度条而已的,后来发现如果只读一个字节就判断一次进度条的话会很消耗系统资源,后来干脆麻烦点用文件块来缓存.不过至于一次缓存多少字节才能达到最好的效果还未知,现在设置的是一次缓存40KB 的数据B)本来一个一个字节读的时候对最后一个字节的操作基本没费什么劲,但是在文件块读写的时候就不是那么清晰明了了,后来经过仔细Debug,才找到错误的所在.许多问题都是这样C)对于中文名和带空格路径,用C++的fstream就不支持,但是C中的FILE*就支持,不知道为什么.还有C++中的fstream的成员函数read返回值很奇怪,不知道如何获取成功读入的项数.改用C中的FILE*文件指针后就解决掉了D)由于这次实验的各个步骤是一环套一环的,在哪里出错很难找得出来,所以这次实验调试消耗的时间特别多.最郁闷的一次错误是发现在取得字符C的第N位函数中,居然把0x40写成了0x30.有时候文件解压出来不对,但是又不清楚是压缩时候错了,还是解压时候错了,然后就要两个函数都要检查一遍.2. 实习体会和收获这次实验最大的特点在于难找错,很锻炼自己的Debug能力(六)自评成绩分数：90 //功能做得较齐全,程序的效率也不错(七)参考文献MSDN还有某网站上树的遍历算法(八)源程序见同一文件夹内.。

使⽤huffman编码压缩与解压缩（python）⼀、huffman 编码1.1 huffman 编码介绍哈夫曼编码(Huffman Coding)，⼜称霍夫曼编码，是⼀种编码⽅式，哈夫曼编码是可变字长编码(VLC)的⼀种。

Huffman于1952年提出⼀种编码⽅法，该⽅法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，⼀般就叫做Huffman编码（有时也称为霍夫曼编码）huffman 编码是最优码，也是即时码（证明较为复杂，在此不给出证明）1.2 huffman 编码此处介绍⼆元 huffman 编码给定⼀个字符集合 S={s0,s1,⋯,s q}，每个字符的概率为 P={p0,p1,⋯,p q}将字符集合按概率由⼤到⼩重新排列，即使得p i≥p i+1将最末尾的两个字符s q−1和s q合并，记为s′，s′的概率为p′=p q−1+p q如果剩余的字符数不为 1，则回到第 1 步huffman 编码的过程⼤致就上述三步当编码完毕后，会构建出⼀棵码树，每个码字的编码可以从码树中获得举个简单的例⼦，对于字符集合 S={A,B,C}，概率为 P=0.5,0.3,0.2将B,C合并，记为BC，p(BC)=p(B)+p(C)=0.3+0.2=0.5然后将A,BC合并，记为ABC，p(ABC)=p(A)+p(BC)=0.5+0.5=1记根节点 ABC 码字为空，从根节点向下遍历，往左⾛码字末尾添0，往右⾛添1，那么 A, B, C 的码字分别为 0, 10, 11，编码表就是 {A:0,B:10,C:11}1.3 huffman 编程实现见后⽂的代码实现1.4 测试⾸先在代码⽬录下新建⼀个newfile.txt，⾥边写⼊ABCDEFG下⾯的代码实现了读取newfile.txt并对其压缩，将结果输出⾄output.enc然后对output.enc进⾏解压缩，将解压缩结果输出⾄output.dec# 读⼊⽂件with open('newfile.txt', 'rb') as fp_in:str_bytes = fp_in.read()# 构建huffman编码fre_dic = bytes_fre(str_bytes)huffman_dic = build(fre_dic)# 对⽂本进⾏编码str_enc, padding = encode(str_bytes, huffman_dic, False)# 输出⾄⽂件 output.encwith open('output.enc', 'wb') as fp_out:fp_out.write(str_enc)# 对编码后的⽂本进⾏解码str_dec = decode(str_enc, huffman_dic, padding, False)# 输出⾄⽂件 output.decwith open('output.dec', 'wb') as fp_out:fp_out.write(str_dec)# 打印huffman字典和填充位print('huffman_dic:', huffman_dic)print('padding:', padding)观察压缩前和压缩后的⽂件，发现经过我们的程序压缩之后，⽂件⼩了很多使⽤ winhex 打开 newfile.txt, output.enc, output.dec 查看对应的⼗六进制数值观察 newfile.txt 和 output.dec 的⼗六进制数值，发现⼀模⼀样，说明我们的压缩和解压并没有问题，程序正确接下来来分析 output.enc ⽂件的内容output.enc 中的数值为 C1 4E 50，转化成⼆进制为 11000001 01001110 01010000Loading [MathJax]/jax/output/HTML-CSS/jax.js我们将中间构造出的编码表打印出来，可以得到编码表字符A B C D E F G编码11000001010011100101以及填充位 padding 的值为 4我们对 newfile.txt 中的字符 ABCDEFG 进⾏编码，结果为 11 000 001 010 011 100 101。

#include<iostream>using namespace std;#include<iomanip>#include<fstream>#include<cstdlib>typedef struct Point{int parent;int weight;int left;int right;}POINT;class HUFFMAN{private:char Filech[258];POINT point[512]; //point[0]留作判断是否已经到文件的末尾了int root;char code[258][16];public:HUFFMANInit(char filename[]) //对huffman树进行一些初始化的操作{char ch;int i;for(i=0;i<512;i++){if(i<258)Filech[i]='\0';point[i].parent=point[i].weight=point[i].left=point[i].right=0;}Filech[0]=0;root=0;fstream FILE;FILE.open(filename,ios::in);if(!FILE){cout<<"打开文件失败"<<endl;exit(0);}while(!FILE.eof()){FILE.get(ch);if(FILE.fail())break;for(i=0;i<=strlen(Filech+1);i++){if(Filech[i]==ch){point[i].weight++;break;}}if(i==strlen(Filech+1)+1){Filech[i]=ch;point[i].weight++;}}buildhuffman();char s[2]="\0";gaincode(root,s);fstream FILEOUT; //将每个字符对应的二进制输出到文件中去FILEOUT.open("code.txt",ios::out);for(i=0;i<=strlen(Filech+1);i++){FILEOUT<<Filech[i]<<" "<<code[i]<<endl;}/* cout<<"各个字符在重新编码以后的码制："<<endl; //输出各个字符在重新编码后的码制for(i=0;i<=strlen(Filech+1);i++)cout<<Filech[i]<<" "<<code[i]<<endl;for(i=1;i<=strlen(Filech+1);i++) //输出各个字符在统计之后的所占的比重cout<<i<<": "<<Filech[i]<<" "<<point[i].weight<<endl;*/}void buildhuffman() //构建huffman树{int compare[2][2];int i,j;int length;length=strlen(Filech+1);for(i=0;i<strlen(Filech+1);i++){compare[0][1]=compare[0][0]=0;compare[1][0]=compare[1][1]=0x7fffffff;for(j=0;j<=length;j++){if(!point[j].parent&&point[j].weight<compare[1][1]){if(point[j].weight<compare[1][0]){compare[0][1]=compare[0][0];compare[1][1]=compare[1][0];compare[0][0]=j;compare[1][0]=point[j].weight;}else{compare[0][1]=j;compare[1][1]=point[j].weight;}}}length++;point[compare[0][0]].parent=length;point[compare[0][1]].parent=length;point[length].left=compare[0][0];point[length].right=compare[0][1];point[length].weight=compare[1][0]+compare[1][1];}root=length;/* cout<<" 序号：父节点：左孩子：右孩子：比重："<<endl;for(i=0;i<=root;i++)cout<<setw(4)<<i<<setw(8)<<point[i].parent<<setw(8)<<point[i].left<<setw(9)<<point[i].righ t<<setw(10)<<point[i].weight<<endl;*/}void gaincode(int address,char ch[]){if(point[address].left||point[address].right){int i=strlen(ch);char temp1[16];char temp2[16];strcpy(temp1,ch);strcpy(temp2,ch);temp1[i+1]='\0';temp1[i]='0';temp2[i+1]='\0';temp2[i]='1';gaincode(point[address].left,temp1);gaincode(point[address].right,temp2);}elsestrcpy(code[address],ch);}void jiami(char filename[],char fileoutname[]) //对文件进行编码后输出{fstream FileIn;fstream FileOut;FileIn.open(filename,ios::in);if(!FileIn){cout<<"打开文件失败"<<endl;exit(0);}FileOut.open(fileoutname,ios::out|ios::binary);if(!FileOut){cout<<"打开文件失败"<<endl;exit(0);}char ch;int num=0;int i=0,j,k;while(!FileIn.eof()){FileIn.get(ch);if(FileIn.fail())break;for(k=1;k<=strlen(Filech+1);k++)if(Filech[k]==ch)break;for(j=0;j<strlen(code[k]);j++){num<<=1;i++;if(code[k][j]=='1')num|=1;if(i==32){FileOut.write((char *)&num,sizeof(num));i=0;num=0;}}}for(j=0;j<strlen(code[0]);j++){num<<=1;i++;if(code[0][j]=='1')num|=1;if(i==32){FileOut.write((char *)&num,sizeof(num));i=0;num=0;}}if(i){num<<=32-i;FileOut.write((char *)&num,sizeof(num));}FileIn.close();FileOut.close();}void readFile(char filename[],char fileoutnmae[]) //将加密后的文件解密{fstream dataFileIn,dataFileOut;int i,j;int judge;int num;dataFileIn.open(filename,ios::in|ios::binary);if(!dataFileIn){cout<<"打开文件失败"<<endl;exit(0);}dataFileOut.open(fileoutnmae,ios::out);if(!dataFileOut){cout<<"打开文件失败"<<endl;exit(0);}j=root;while(!dataFileIn.eof()){dataFileIn.read((char *)&num,sizeof(num));if(dataFileIn.fail())break;for(i=31;i>=0;i--){if(point[j].left||point[j].right){judge=(num>>i)&1;if(judge)j=point[j].right;elsej=point[j].left;}else{i++;if(j==0)break;else{//cout<<Filech[j];dataFileOut.put(Filech[j]);j=root;}}}}}};。

《信息论与编码》实验报告班级：学号：姓名：完成时间：2011年6月2日实验2 Huffman编码对英文文本的压缩和解压缩一、实验内容根据信源压缩编码——Huffman编码的原理，制作对英文文本进行压缩和解压缩的软件。

要求软件有简单的用户界面，软件能够对运行的状态生成报告，分别是：字符频率统计报告、编码报告、压缩程度信息报告、码表存储空间报告。

二、实验环境1.计算机2.Windows 2000 或以上3.Microsoft Office 2000 或以上4.VC++ 6.05.MSDN6.0三、实验目的1.掌握Huffman编码的原理2.掌握VC开发环境的使用（尤其是程序调试技巧）3.掌握C语言编程（尤其是位运算和文件的操作）4.掌握数据结构的内容：链表、顺序表、堆栈、最优二叉树5.掌握结构化程序分析和开发的软件工程原理四、实验要求1.提前预习实验，认真阅读实验原理。

2.认真高效的完成实验，实验过程中服从实验室管理人员以及实验指导老师的管理。

3.认真填写实验报告。

要求有实验问题、实验原理、Matlab的源程序以及实验结果（实验内容中）。

4.每个同学必须独立完成实验（不能抄袭，否则两人均为零分），实验成绩是该门课程成绩的主要依据。

五、实验原理1.压缩/解压缩流程压缩流程：解压缩流程：2.Huffman编码算法（略）3.文件操作和位运算（略）六、Huffman 算法的8种不同实现方式1. huffman_a 使用链表结构生成Huffman树的算法，这是最基本的实现方法，效率最低。

2. huffman_b 使用《数据结构》（严蔚敏，吴伟民，1997，C语言版）中给出的算法，将二叉树存放在连续空间里（静态链表），空间的每个结点内仍有左子树、右子树、双亲等指针。

3. huffman_c 使用Canonical Huffman编码，同时对huffman_b的存储结构进行改造，将二叉树存放在连续空间tree里，空间的每个结点类型都和结点权值的数据类型相同，空间大小为2*num，tree[0]未用，tree[1..num]是每个元素的权值，生成Huffman后，tree[1..2*num-1]中是双亲结点索引。

二进制哈夫曼编码进行压缩摘要：1.二进制哈夫曼编码的概述2.二进制哈夫曼编码的原理3.二进制哈夫曼编码的实现过程4.二进制哈夫曼编码的优缺点5.二进制哈夫曼编码的应用实例正文：一、二进制哈夫曼编码的概述二进制哈夫曼编码，是一种基于哈夫曼编码的压缩算法。

哈夫曼编码是一种无损数据压缩编码方法，它可以将原始数据转换为对应的编码，从而达到压缩的效果。

二进制哈夫曼编码是哈夫曼编码的一种改进，它在原有的哈夫曼编码基础上，将编码的位数限制为二进制，从而提高了压缩效率。

二、二进制哈夫曼编码的原理二进制哈夫曼编码的原理是，根据输入数据（0，1）的出现频率，构造一棵哈夫曼树，然后将原始数据转换为对应的哈夫曼编码。

具体过程如下：1.根据输入数据（0，1）的出现频率，构造一棵哈夫曼树。

构造哈夫曼树的过程是，将输入数据中出现频率最低的两个节点合并为一个新节点，新节点的权值为这两个节点的权值之和。

然后，将新节点放入原节点的父节点中，并更新父节点的权值。

重复上述过程，直到只剩下一个节点，这个节点就是哈夫曼树的根节点。

2.通过哈夫曼树，得到对应的哈夫曼编码。

从哈夫曼树的根节点到每个叶子节点的路径，就是对应的哈夫曼编码。

从根节点到每个叶子节点的路径上的节点，按照先左后右的顺序访问，得到的二进制编码就是对应的哈夫曼编码。

三、二进制哈夫曼编码的实现过程二进制哈夫曼编码的实现过程，主要包括以下两个步骤：1.构造哈夫曼树。

这一步主要是根据输入数据（0，1）的出现频率，按照哈夫曼树的构造方法，构造一棵哈夫曼树。

2.得到哈夫曼编码。

这一步主要是通过哈夫曼树，得到对应的哈夫曼编码。

从哈夫曼树的根节点到每个叶子节点的路径，就是对应的哈夫曼编码。

四、二进制哈夫曼编码的优缺点二进制哈夫曼编码的优点是，压缩效率高。

由于哈夫曼编码是基于数据出现频率的，因此，出现频率高的数据会被压缩成较短的编码，而出现频率低的数据会被压缩成较长的编码。

这样，整体上来看，二进制哈夫曼编码的压缩效果较好。

文件的压缩与解压──huffman算法功能实现摘要：压缩的实质是数字变换，在多媒体信息中包含大量冗余的信息，把这些余冗的信息去掉，就是实现了压缩；解压是由于计算机处理的信息是以二进制数的形式表示的，因此压缩软件就是把二进制信息中相同的字符串以特殊字符标记来达到压缩的目的。

关键词：压缩；解压缩；需求分析；概要设计；详细设计；测试Abstract：Compression is the essence of digital transformation, contains a large amount of redundant information in the multimedia information, the residual redundancy information, is to implement the compression; Decompression is due to the computer processing of information in the form of a binary number, so the compression software is binary information in the same string tag as special characters to achieve the purpose of compression.Key words：Compression; The decompression; Demand analysis; The profile design; The detailed design; Test;1 需求分析解决整个项目系统的“做什么”的问题。

在这里，对于开发技术并没有涉及，而主要是通过建立模型的方式来描述用户的需求，为客户、用户、开发方等不同参与方提供一个交流的渠道。

随着科学技术的进步，信息技术越来越广泛地应用到社会的各个行业和领域，互联网深刻地改变着人们的生活方式，推动着人类文明的进步。

#include <iostream>#include <sys/stat.h>#ifndef _UNISTD_H#define _UNISTD_H#include <io.h>#include <process.h>#endif /* _UNISTD_H */#include <stdio.h>#include<stdlib.h>#include <windows.h>#include <fstream>#include <vector>#include <algorithm>#include <cstring>using namespace std;typedef struct{int weight;int parent,lchild,rchild;}HTNode,*HuffmanTree;typedef struct{char* data;int* num;int length;}TNode;typedef struct{char *data;char** HM;}Code;typedef char** HuffmanCode;bool IfEncode(){int choose;system("color 70");cout<<"\t 1.加密压缩 2.无密压缩"<<endl;cout<<"请输入选择：";cin>>choose;if(choose==1)return true;elsereturn false;}void Encode(vector<char>& v){char ch[30];v.push_back('@');system("color 70");cout<<"请输入压缩密码"<<endl;cin>>ch;for(int i=0;ch[i]!='\0';i++)v.push_back(ch[i]);v.push_back('\0');v.push_back('@');cout<<"开始压缩！"<<endl;}void ReadTxt(vector<char>& v){char ch;ifstream infile("test.txt",ios::in);if(!infile){cerr<<"open error"<<endl;exit(1);}if(IfEncode())Encode(v);while(infile.peek()!=EOF){infile.get(ch);v.push_back(ch);}infile.close();}void InitList(TNode& T){T.data=new char[256];T.num=new int[256];if(!T.data||!T.num)exit(1);T.length=0;}bool Find(TNode T,char ch){int i;for(i=0;i<T.length;i++)if(ch==T.data[i])return true;return false;}void TCount(vector<char> v1,TNode &T){int i,j=0;char ch;int m=v1.size();for(i=0;i<m;i++){ch=v1[i];if(!Find(T,ch)){T.data[j]=ch;T.num[j]=count(v1.begin(),v1.end(),ch);j++;T.length++;}}}void Select(HuffmanTree &HT,int m,int& s1,int& s2) {int k,j,n,min=32767;for(k=1;k<=m;k++){if(HT[k].parent==0)if(HT[k].weight<=min){j=k;min=HT[k].weight;}}s1=j;HT[j].parent=1;min=32767;for(k=1;k<=m;k++){if(HT[k].parent==0)if(HT[k].weight<=min){n=k;min=HT[k].weight;}}s2=n;}void CreateHuffmanTree (HuffmanTree &HT,TNode T,int length) {int m,i,s1,s2;if(length<=1)return;m=2*length-1;HT=new HTNode[m+1];for(i=1;i<=m;++i){HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;}for(i=1;i<=length;++i)HT[i].weight=T.num[i-1];for(i=length+1;i<=m;i++){Select(HT,i-1,s1,s2);HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;}}void CreatHuffmanCode (HuffmanTree HT,HuffmanCode &HC,int n) {int i,f,c,start;HC=new char*[n+1];char* cd=new char[n];cd[n-1]='\0';for(i=1;i<=n;i++){start=n-1;c=i;f=HT[i].parent;while(f!=0){--start;if(HT[f].lchild==c)cd[start]='0';elsecd[start]='1';c=f;f=HT[f].parent;}HC[i]=new char[n-start];strcpy(HC[i],&cd[start]);}delete cd;}int getFileSizeSystemCall(char * strFileName){struct stat temp;stat(strFileName, &temp);return temp.st_size;}void Zip(HuffmanCode HC,vector<char> v,TNode T){int i=0,j=0,k=0;ofstream outfile("zip.txt",ios::out);if(!outfile){cerr<<"open error"<<endl;exit(1);}cout<<"输出哈夫曼编码"<<endl;for(i=0;i<v.size();i++){for(j=0;j<T.length;j++)if(T.data[j]==v[i])break;for(k=0;HC[j+1][k]!='\0';k++){ cout<<HC[j+1][k]<<" ";}for(k=0;HC[j+1][k]!='\0';k++)outfile<<HC[j+1][k];}cout<<endl;outfile.close();cout<<"正在压缩。

求哈夫曼编码例题【原创版】目录1.哈夫曼编码的定义和原理2.哈夫曼编码的实现过程3.哈夫曼编码的应用实例4.哈夫曼编码的优点和局限性正文1.哈夫曼编码的定义和原理哈夫曼编码是一种无损数据压缩编码方法，它可以将原始数据转换为更短的二进制表示，同时保证数据可以被精确地还原。

哈夫曼编码的原理是按照数据中字符出现的频率构建一棵哈夫曼树，然后将每个字符映射到该树的一个叶子节点，从而得到对应的编码。

2.哈夫曼编码的实现过程哈夫曼编码的实现过程分为以下几个步骤：(1) 根据输入数据（字符）的出现频率构建哈夫曼树。

具体做法是，将输入数据中的每个字符作为叶子节点，并将出现频率作为权值。

然后通过权值最小的节点合并，得到一个新的父节点，将父节点的权值设置为两个子节点权值之和。

重复这个过程，直到只剩下一个节点，这个节点就是哈夫曼树的根节点。

(2) 通过哈夫曼树得到编码表。

从根节点到每个叶子节点的路径代表一个字符的编码，其中左子节点的边表示 0，右子节点的边表示 1。

(3) 根据编码表，将原始数据转换为对应的哈夫曼编码。

3.哈夫曼编码的应用实例哈夫曼编码广泛应用于数据压缩、图像压缩、语音压缩等领域。

以文本数据压缩为例，假设有如下一段英文文本：“This is an example of Huffman coding.”，通过对这段文本进行哈夫曼编码，可以得到压缩后的二进制表示，从而实现文本的压缩。

4.哈夫曼编码的优点和局限性哈夫曼编码的优点有：(1) 无损压缩：哈夫曼编码可以保证数据在压缩和解压缩过程中的精确还原。

(2) 压缩效率高：哈夫曼编码能够将数据压缩为相对较短的二进制表示，尤其适用于数据中存在大量重复字符的情况。

然而，哈夫曼编码也存在局限性：(1) 编码长度不确定：哈夫曼编码的长度取决于数据中字符的出现频率，因此对于不同数据，编码长度可能有较大差异。

《用哈夫曼编码实现文件压缩》实验报告课程名称数据结构B实验学期2012 至2013 学年第一学期学生所在系部计算机学院年级2011 专业班级信管B111学生姓名学号任课教师兰芸实验成绩用哈夫曼编码实现文件压缩1、了解文件的概念。

2、掌握线性链表的插入、删除等算法。

3、掌握Huffman树的概念及构造方法。

4、掌握二叉树的存储结构及遍历算法。

5、利用Huffman树及Huffman编码，掌握实现文件压缩的一般原理。

微型计算机、Windows 系列操作系统、Visual C++6.0软件根据ascii码文件中各ascii字符出现的频率情况创建Haffman树，再将各字符对应的哈夫曼编码写入文件中，实现文件压缩。

（1）构造Hufffman树的方法—Hufffman算法构造Huffman树步骤：I.根据给定的n个权值{w1,w2,……wn}，构造n棵只有根结点的二叉树，令起权值为wj。

II.在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和。

III.在森林中删除这两棵树，同时将新得到的二叉树加入森林中。

IV.重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树。

（2）Huffman编码：数据通信用的二进制编码思想：根据字符出现频率编码，使电文总长最短编码：根据字符出现频率构造Huffman树，然后将树中结点引向其左孩子的分支标“0”，引向其右孩子的分支标“1”；每个字符的编码即为从根到每个叶子的路径上得到的0、1序列。

(3) 解压根据存放在文件中的编码表和文件压缩后的编码，进行一对一的翻译过程。

压缩的代码#include <stdio.h>#include <string.h>#include <stdlib.h>#include <conio.h>struct head{unsigned char b; /*the charactor*/long count; /*the frequency*/long parent,lch,rch; /*make a tree*/char bits[256]; /*the haffuman code*/}header[512],tmp;void yasuo() /*压缩*/{char filename[255],outputfile[255],buf[512];unsigned char c; char wenjianming[255];long i,j,m,n,f;long min1,pt1,flength;FILE *ifp,*ofp;printf("输入文件地址及文件名:");gets(filename);ifp=fopen(filename,"rb"); /*打开源文件*/while(ifp==NULL){ printf("打开文件出错\n");printf("重新输入文件地址及文件名");gets(filename);ifp=fopen(filename,"rb");}printf("输入压缩后的文件地址和文件名及后缀:");gets(wenjianming);ofp=fopen(wenjianming,"wb"); /*创建并打开目的文件*/ while(ofp==NULL){printf("重新输入压缩后的文件地址和文件名及后缀:");ofp=fopen(wenjianming,"wb");}flength=0;while(!feof(ifp)) /*读取ifp文件*/{fread(&c,1,1,ifp); /*按位读取*/header[c].count++;flength++;}flength-1;header[c].count-1; /*读取文件结束*/for(i=0;i<512;i++) /*构造哈弗曼树*/{if(header[i].count!=0)header[i].b=(unsigned char)i;elseheader[i].b=0;header[i].parent=-1;header[i].lch=header[i].rch=-1;}for(i=0;i<256;i++){for(j=i+1;j<256;j++){if(header[i].count<header[j].count){tmp=header[i];header[i]=header[j];header[j]=tmp;}}}for(i=0;i<256;i++)if(header[i].count==0)break;n=i;m=2*n-1;for(i=n;i<m;i++){min1=999999999;for(j=0;j<i;j++){if(header[j].parent!=-1)continue;if(min1>header[j].count){pt1=j;min1=header[j].count;continue;}}header[i].count=header[pt1].count;header[pt1].parent=i;header[i].lch=pt1;min1=999999999;for(j=0;j<i;j++){if(header[j].parent!=-1)continue;if(min1>header[j].count){pt1=j;min1=header[j].count;continue;}}header[i].count+=header[pt1].count;header[i].rch=pt1;header[pt1].parent=i;}for(i=0;i<n;i++){f=i;header[i].bits[0]=0;while(header[f].parent!=-1){j=f;f=header[f].parent;if(header[f].lch==j){j=strlen(header[i].bits);memmove(header[i].bits+1,header[i].bits,j+1);header[i].bits[0]='0';}else{j=strlen(header[i].bits);memmove(header[i].bits+1,header[i].bits,j+1);header[i].bits[0]='1';}}} /*哈弗曼构造结束*/fseek(ifp,0,SEEK_SET); /*把文件指针指向文件的开头*/ fwrite(&flength,sizeof(int),1,ofp); //把哈弗曼代码写入ofp文件fseek(ofp,8,SEEK_SET);buf[0]=0;f=0;pt1=8;while(!feof(ifp)){c=fgetc(ifp); //从流中读取一个字符，并增加文件指针的位置f++;for(i=0;i<n;i++){if(c==header[i].b) break;}strcat(buf,header[i].bits); //把header[i].bits所指字符串添加到buf结尾处j=strlen(buf); //计算字符串buf的长度c=0;while(j>=8){for(i=0;i<8;i++){if(buf[i]=='1') c=(c<<1)|1;else c=c<<1;}fwrite(&c,1,1,ofp);pt1++;strcpy(buf,buf+8);j=strlen(buf);}if(f==flength)break;}if(j>0){strcat(buf,"00000000");for(i=0;i<8;i++){if(buf[i]=='1') c=(c<<1)|1;else c=c<<1;}fwrite(&c,1,1,ofp);pt1++;}fseek(ofp,4,SEEK_SET); /*fseek 用于二进制方式打开的文件,移动文件读写指针位置.第一个是文件流,第3个是指针零点位置,第2个是把指针移动到的地点. */ fwrite(&pt1,sizeof(long),1,ofp); /*是要输出数据的地址,每次写入的位数,数据项的个数，目标文件地址*/fseek(ofp,pt1,SEEK_SET);fwrite(&n,sizeof(long),1,ofp);for(i=0;i<n;i++){fwrite(&(header[i].b),1,1,ofp);c=strlen(header[i].bits);fwrite(&c,1,1,ofp);j=strlen(header[i].bits);if(j%8!=0) /*按八位读取*/{for(f=j%8;f<8;f++)strcat(header[i].bits,"0");}while(header[i].bits[0]!=0){c=0;for(j=0;j<8;j++){if(header[i].bits[j]=='1') c=(c<<1)|1;else c=c<<1;}strcpy(header[i].bits,header[i].bits+8); /*把从header[i].bits+8地址开始且含有NULL结束符的字符串赋值到以header[i].bits开始的地址空间*/fwrite(&c,1,1,ofp);}}fclose(ifp);fclose(ofp);printf("压缩成功\n");}void main() /*主函数*/{printf("输入a开始压缩\n");printf("输入b结束压缩\n");while(1){char c;c=getch();if(c=='a')yasuo();else{ if(c=='b')return;}}}压缩的图解解压的代码#include <stdio.h>#include <string.h>#include <stdlib.h>#include <conio.h>struct head{unsigned char b; /*the charactor*/long count; /*the frequency*/long parent,lch,rch; /*make a tree*/char bits[256]; /*the haffuman code*/}header[512],tmp;void jieya() /*解压*/ {char filename[255],outputfile[255],buf[255],bx[255];unsigned char c; char wenjianming[255];long i,j,m,n,f,p,l;long flength;FILE *ifp,*ofp;printf("要解压的文件：");gets(filename);ifp=fopen(filename,"rb"); /*打开源文件*/while(ifp==NULL){ printf("打开文件出错\n");printf("重新输入文件地址及文件名");gets(filename);ifp=fopen(filename,"rb");}printf("输入解压后的文件地址和文件名及后缀:");gets(wenjianming);ofp=fopen(wenjianming,"wb"); /*创建并打开目的文件*/ while(ofp==NULL){ofp=fopen("d:\\123\\解压的文件.txt","wb");}fread(&flength,sizeof(long),1,ifp);fread(&f,sizeof(long),1,ifp);fseek(ifp,f,SEEK_SET);fread(&n,sizeof(long),1,ifp);for(i=0;i<n;i++){fread(&header[i].b,1,1,ifp);fread(&c,1,1,ifp);p=(long)c;header[i].count=p;header[i].bits[0]=0;if(p%8>0) m=p/8+1;else m=p/8;for(j=0;j<m;j++){fread(&c,1,1,ifp);f=c;itoa(f,buf,2);f=strlen(buf);for(l=8;l>f;l--){strcat(header[i].bits,"0");}strcat(header[i].bits,buf);}header[i].bits[p]=0;}for(i=0;i<n;i++){for(j=i+1;j<n;j++){if(strlen(header[i].bits)>strlen(header[j].bits)){tmp=header[i];header[i]=header[j];header[j]=tmp;}}}p=strlen(header[n-1].bits);fseek(ifp,8,SEEK_SET);m=0;bx[0]=0;while(1){while(strlen(bx)<(unsigned int)p){fread(&c,1,1,ifp);f=c;itoa(f,buf,2);f=strlen(buf);for(l=8;l>f;l--){strcat(bx,"0");}strcat(bx,buf);}for(i=0;i<n;i++){if(memcmp(header[i].bits,bx,header[i].count)==0) break;}strcpy(bx,bx+header[i].count);c=header[i].b;fwrite(&c,1,1,ofp);m++;if(m==flength) break;}fclose(ifp);fclose(ofp);printf("解压成功\n");return;}void main() /*主函数*/{printf("输入a开始解压\n");printf("输入b结束解压\n");while(1){char c;c=getch();if(c=='a')jieya();else{ if(c=='b')return;}}}七、测试结果及分析：压缩前的文件夹中的内容压缩后的文件夹中的内容解压后文件夹中的内容八、教师评语：---精心整理，希望对您有所帮助。