Huffman编码对英文文本的压缩和解压缩

合肥学院计算机科学与技术系一、问题分析和任务定义1、题目采用哈夫曼编码思想实现英文文本的压缩与解压缩，并提供压缩前后的占用空间比。

要求 1）压缩原文件规模不小于5K2) 提供解压缩文件后文件与原文件的相同性比较功能2、问题分析压缩过程 news.txt →news1.txt1、以读的形式打开需要压缩的一个英文本文件，把其中出现的所有字符按其在文本中出现的频率利用哈夫曼树进行编码。

2、以写的形式打开一个新的文本文件，把它作为英文文本压缩后的文本文件，扫描需要压缩的英英文本文件（ new.txt ）中所有字符，把其对应的编码通过转换后存入新的文本文件( new1.txt )中。

3、把需要压缩的英文文本（ new.txt ）中所出现的字符及其编码等原始文件的信息保存在新的文本文件中。

解压缩过程news1.txt →news2.txt1、以读的形式打开一个压缩文件 news1.txt，按其中保存的原始文件的信息还原哈夫曼树及字符编码。

2、以写的形式打开一个新的文本文件，作为解压后的英文文本 news2.txt ，逐个扫描压缩文件 news1.txt中的所有字符，把其中所有转换后的编码再转换回来并与哈夫曼树中存储的字符编码比较，把其对应的字符写入news2.txt 中。

一个字符在文本文件中存储时占一个字节，而其二进制编码若直接存入文本文件其所占的空间不会少于一个字节。

例如：假设字符E的编码为001，若把001直接存入文件只能用字符串的形式，其所占用的空间为三个字节。

达不到文件压缩的目的，所以必须对编码的存储空间进行转换。

3 编码转换在文本文件中字符之间是连续的，所以在文本文件中存储编码也是连续的。

可以把连续的不同字符的编码存入同一个字节，再把这一个字节的二进制码转换成一个字符，把转换后的字符存储在文本文件中。

二、数据结构的选择和概要设计：1 此程序采用的数据结构为顺序表。

哈夫曼树是二叉树的一种，二叉树的顺序存储结构中可以把结点间的关系放在其存储位置中，无需附加任何信息就能在这种结构中找到每个结点的双亲结点和孩子结点，这正是哈夫曼编码所需要的。

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编码实现文件压缩算法设计训练(2)2011-3-21基本要求•目标–独立完成一个中等规模的项目–在程序设计中使用中等复杂度的数据结构•基本要求–自行建立一个测试文件a.txt•测试文件可以仅包含字母和数字，但不能仅有数字•测试文件中不能是单一的字符、空文件等(即不可对测试文件进行投机)–编写程序对测试文件进行压缩，并将压缩结果保存为一个新文件–编写程序对压缩后的新文件进行解压–要求“无损压缩”，即(源文件Æ压缩Æ解压)==(源文件)–要求用一个程序实现压缩和解压，以main 函数参数的形式提供压缩和解压的选项2011-3-21具体实现•基本要求的具体实现要求–扫描文件产生每个字符的使用频率–对每个字符根据使用频率建立最小堆–由最小堆建立Huffman 树–自行建立一个测试文件a.txt–用Huffman 树对测试文件进行压缩，并将压缩文件保存为a.hfm –将Huffman 树存储在a.hfm 的头部–以main 函数参数的形式提供解压的选项，以a.hfm 恢复出a.txt2011-3-21扩展要求•扩展要求–实现Holy Bible, Authorized (King James) Version (圣经,詹姆斯.金版见附件：kjv.rar)的压缩和解压缩–计算由Huffman 树给的压缩算法的压缩比•(压缩比=压缩后的文件大小/压缩前的文件大小)–尝试以下3种压缩方式• a. 扫描整个文件，以每个字符实际出线的频率计算Huffman 数• b. 不扫描整个文件，以英文字符的平均出线频率计算huffman 树• c. 扫描整个文件，以英文单词做为编码对象–提示•由于原文中是区分大小写的，并且要处理标点符号、数字等因此需要对0～255的ASCII 字符重新进行Huffman 编码•不同的Huffman 编码策略可以由main 函数的参数给出(参考字符界面的RAR)2011-3-21完整的作业要求•格式要求：•1.要求提交实验报告和源代码。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

数据结构课程设计题目名称：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个哈夫曼树节点即数组（后面有节点的定义）空间来存储整个文件的信息，节点中包括对应字符信息，其中包括频率。

哈夫曼编码的压缩与解压缩1.引言1.1 概述哈夫曼编码是一种常用的数据压缩算法，它采用了一种变长编码方式，将出现频率高的字符用较短的编码表示，出现频率低的字符用较长的编码表示，以达到压缩数据的目的。

该编码方法由美国数学家大卫·哈夫曼于1952年提出，被广泛应用于各种数据压缩和传输领域。

在传统的固定长度编码中，每个字符都使用相同的位数来表示，因此在表示不同概率出现的字符时，可能会浪费大量的位数。

而哈夫曼编码则是根据字符在文本中出现的频率来确定其对应的编码，使得高频出现的字符用更短的编码表示，低频出现的字符用较长的编码表示。

哈夫曼编码的核心思想是构建一棵哈夫曼树，将出现频率作为权值，频率越高的字符离根节点越近。

通过从叶子节点到根节点的路径确定每个字符的编码，即将左子树标记为0，右子树标记为1。

在对文本进行压缩时，将文本中的字符转换为其对应的哈夫曼编码，即可将原始数据压缩为较短的二进制串。

相比于传统固定长度编码，哈夫曼编码具有显著的优势。

首先，它可以根据文本中字符出现的实际情况进行编码，使得频率高的字符用较短的编码表示，从而大幅度减少了编码后的数据长度。

其次，哈夫曼编码是一种前缀编码，即任何一个字符的编码都不是其他字符编码的前缀，这样在解码时可以直接根据编码找到对应的字符，无需回溯查表，提高了解码效率。

哈夫曼编码的应用广泛，它被用于无损图像压缩、音频压缩、文本压缩等领域。

随着互联网和大数据时代的到来，数据的传输和存储成为重要的问题，如何高效地压缩和解压缩数据成为一个热门的研究方向。

哈夫曼编码作为一种简单而有效的压缩算法，具有广阔的应用前景。

然而，哈夫曼编码也存在一些问题，如编码时需要构建哈夫曼树，需要额外的空间和时间开销，对于小规模数据可能会影响压缩效率。

因此，在实际应用中，需要综合考虑数据规模和应用场景，选择合适的压缩算法。

1.2 文章结构本文主要介绍了哈夫曼编码的压缩与解压缩。

文章分为引言、正文和结论三个部分。

常见的文本压缩算法1. Huffman 编码：Huffman 编码是一种基于概率分布的编码方法，通过统计文本中字符出现的频率，然后构建一个 Huffman 树，按照编码规则对每个字符进行编码。

频率较高的字符使用较短的编码，频率较低的字符使用较长的编码，这样可以实现对文本的压缩。

2. Lempel-Ziv-Welch (LZW) 编码：LZW 编码是一种基于字典的编码方法。

它使用滑动窗口技术来寻找文本中的重复子串，并将其替换为短的编码。

在编码过程中，不断更新和扩展字典，以便能够更好地压缩文本。

3. Burrows-Wheeler Transform (BWT)：BWT 是一种重排文本字符的方法。

它通过将字符重新排序，使得文本中相邻的字符具有更高的相似性，从而方便后续的压缩工作。

BWT 常常与 Move-To-Front (MTF) 编码结合使用，MTF 编码根据字符上一次出现的位置来对字符进行编码。

4. Arithmetic Coding：算术编码是一种根据字符的概率分布来进行编码的方法。

它将整个文本视为一个连续的区间，根据字符的概率来更新区间的范围，并将最终的区间编码为一个二进制数。

算术编码可以实现非常高效的压缩，但也需要较大的计算量。

5. Run-Length Encoding (RLE)：RLE 是一种简单的压缩算法，它将连续重复的字符序列替换为一个字符和重复次数的组合。

例如，字符串"AAAAABBBBCCCC" 可以被压缩为 "A5B4C4"。

6. Huffman-RLE：Huffman-RLE 是 Huffman 编码和 RLE 的结合。

它首先使用 RLE 对文本进行预处理，将连续重复的字符序列替换为一个字符和重复次数的组合，然后再使用 Huffman 编码对处理后的文本进行压缩。

这些算法都有各自的优缺点，适用于不同的压缩场景。

在实际应用中，常常会将它们结合起来使用，以提高压缩效率。

使⽤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。