精华内容
下载资源
问答
  • 实验目的:理解哈弗曼信源编码算法,并能应用于文件压缩中。 实验内容:写出程序,利用哈弗曼编码实现对文件的压缩,并能解压文件。 实验步骤: 1、压缩 (1) 统计原始文件中各字节出现的概率(次数); (2) 采用...
  • 基于哈夫曼编码的文本文件压缩与解压缩,使用c语言,实际只是编码解码,不应该称为解压缩,因为编码后文件会更大
  • 哈夫曼编码用于解压和压缩的示例代码,非常简单易懂,C风格C++写法。
  • 文件压缩与解压(哈夫曼编码

    热门讨论 2011-11-06 15:13:55
    利用哈夫曼编码原理对磁盘文件进行压缩与解压
  • 用面向对象的程序设计思想自己动手写压缩软件,采用了优先队列这一很好的数据结构实现的贪心算法构造Huffman树,能打印Huffman树,显示编码表,压缩文件和解压缩文件,采用UTF-8字符集,支持中文文件
  • 草稿版代码 内容超详细 可压缩任何文件类型 亲测可用 100%还原
  • 根据ASCII码文件中各ASCII字符出现的频率情况创建Haffman树,再将各字符对应的哈夫曼编码写入文件中,实现文件压缩
  • 本文采用哈夫曼编码的方式进行文件(文本文件)压缩和解压缩,首先介绍项目的整体思路:哈夫曼编码压缩文件实际就是统计出文件中各个字符出现的频率,然后为每个字符生成对应的编码,然后将每个字符用哈夫曼编码的...

             本文采用哈夫曼编码的方式进行文件(文本文件)压缩和解压缩,首先介绍项目的整体思路:哈夫曼编码压缩文件实际就是统计出文件中各个字符出现的频率,然后为每个字符生成对应的编码,然后将每个字符用哈夫曼编码的形式按字节保存在压缩文件中。而文件的解压缩实际上就是将压缩文件翻译过来保存到解压缩文件中,需要使用压缩过程中生成的配置文件配合完成。下面将具体介绍文件的压缩和解压缩步骤:

           文件的压缩的核心是产生哈夫曼编码,而哈夫曼编码的过程中需要找到一系列数据中的最小权重和次小权重,我们自然联想到用堆这种结构时间复发度小并且很方便找到最小值和次小值,我将堆的源代码放在Heap.h文件中(见下文)。现在我们进行文件压缩。

           1。统计文件中所有字符的出现次数。由于Ascall码字符一共255个,只有前128个字符可以显示,定义字符变量时一定要定义成无符号型变量unsigned char ch如下,这是ch读不到文件的结束标志,所以我们可以用函数feof来代替文件的结束标志EOF,最重要的是文件的打开方式一定要是二进制的形式打开否则读不到汉字字符,将出现乱码。关于存储方式我们采用哈希表的方式将每个字符映射为哈希表的下标,这样可以很方便的将每个字符和出现的次数对应起来。需要说明的是我们这个哈希表存的绝不是单纯的次数而是结点FileInfo,这个节点称为权重结点中保存出现次数和字符以及将来我们产生的哈夫曼编码,方便我门进行索引。

    bool Compress(const char *filename)//该函数起到统计的作用
    {
    FILE *fout = fopen(filename, "rb");//以二进制形式打开文件
    assert(fout);
    unsigned char ch = fgetc(fout);
    while (!feof(fout))
    {
    _Infos[ch]._count++;//统计各种字符在文件中的个数
    ch = fgetc(fout);
    COUNT++;//统计文件中总的字符个数
    }
    fclose(fout);
    return true;
    }

         2。现在我们创建一个最小堆,将统计到的结点压入堆中

         3。从堆中取数据在HuffMan.h头文件中建立哈夫曼树

         4。通过哈夫曼树产生哈夫曼编码存入节点中

         5。遍历待压缩文件将对应的哈夫曼编码按字节保存到压缩文件中

         6.将每个字符出现的个数保存到配置文件中。由步骤5产生的压缩文件,当我们遍历到文件的最后一个字符时,如果编码凑不成8      一个字节我们给剩下的位置补0,为了解决最后一个字符的解析问题,我们将待压缩文件中的总的字符个数统计出来存到配置文       件的第一行,以后每行一“X,n”的形式存放字符和对应的出现次数。这样我们的文件压缩过程就完成了。


         文件的解压缩思路简单,但是要尤其注意细节读配置文件就要花些心思,体现在换行符的统计上,下面进行文件的解压缩(源文件见Uncompress.h):

          1。读配置文件

          2。通过配置文件重构哈夫曼树

          3。开始文件的解压缩,按字符读入编码通过编码在哈夫曼树种寻找对应的字符,并将字符存入到解压缩文件中去,通过配置文件中读入的COUNT来控制最后一个字符正确编码的起止。这样文件的解压缩完成。

    总结:

    项目的特点和用到的技术有,仿函数,堆,哈夫曼编码技术,string类,哈希表

    项目注意事项,文件名字转换方法艺术,文件的二进制读入写入,读配置文件时换行符的处理,以及统计的字符数如何以10进制字符的形式存到文件中去。其他问题详见源代码重点注释的地方。

    Heap.h

    #include <vector>
    
    
    template<class T>
    struct Less
    {
    	bool operator() (const T& l, const T& r)
    	{
    		return l < r; // operator<
    	}
    };
    
    template<class T>
    struct Greater
    {
    	bool operator() (const T& l, const T& r)
    	{
    		return l > r; // operator>
    	}
    };
    
    
    template<class T, class Compare=Less<T>>//哈夫曼结点的仿函数
    class Heap
    {
    public:
    	Heap()
    	{}
    	Heap(const T* a, size_t size)
    	{
    		for (size_t i = 0; i < size; ++i)
    		{
    			_arrays.push_back(a[i]);//将所有数据插入堆
    		}
    
    		// 建堆
    		for (int i = (_arrays.size() - 2) / 2; i >= 0; --i)
    		{
    			AdjustDown(i);//对这个范围的每个节点都向下调整,建堆的过程实际就是向下调整堆的过程
    		}
    	}
    
    	void Push(const T& x)
    	{
    		_arrays.push_back(x);
    		AdjustUp(_arrays.size() - 1);//插入节点的过程实际就是向上调整堆的过程
    	}
    
    	void Pop()
    	{
    		assert(_arrays.size() > 0);
    		swap(_arrays[0], _arrays[_arrays.size() - 1]);
    		_arrays.pop_back();
    
    		AdjustDown(0);
    	}
    
    	T& Top()
    	{
    		assert(_arrays.size() > 0);
    		return _arrays[0];
    	}
    
    	bool Empty()
    	{
    		return _arrays.empty();
    	}
    
    	size_t Size()
    	{
    		return _arrays.size();
    	}
    
    	void AdjustDown(int root)
    	{
    		int child = root * 2 + 1;
    
    		Compare com;
    		while (child < _arrays.size())
    		{
    			// 比较出左右孩子中小的那个
    			if (child + 1<_arrays.size() &&
    				com(_arrays[child + 1], _arrays[child]))
    			{
    				++child;
    			}
    
    			if (com(_arrays[child], _arrays[root]))
    			{
    				swap(_arrays[child], _arrays[root]);
    				root = child;
    				child = 2 * root + 1;
    			}
    			else
    			{
    				break;
    			}
    		}
    	}
    
    	void AdjustUp(int child)
    	{
    		int parent = (child - 1) / 2;
    
    		while (child > 0)
    		{
    			if (Compare()(_arrays[child], _arrays[parent]))
    			{
    				swap(_arrays[parent], _arrays[child]);
    				child = parent;
    				parent = (child - 1) / 2;
    			}
    			else
    			{
    				break;
    			}
    		}
    	}
    
    	void Print()
    	{
    		for (size_t i = 0; i < _arrays.size(); ++i)
    		{
    			cout << _arrays[i] << " ";
    		}
    		cout << endl;
    	}
    
    public:
    	vector<T> _arrays;
    };
    
    //测试堆 
    //void Test1()
    //{
    //	int a[10] = { 10, 11, 13, 12, 16, 18, 15, 17, 14, 19 };
    //	Heap<int, Greater<int> > hp1(a, 10);
    //	hp1.Push(1);
    //	hp1.Print();
    //
    //	Heap<int> hp2(a, 10);
    //	hp2.Push(1);
    //	hp2.Print();
    //
    //
    //	Less<int> less;
    //	cout<<less(1, 2)<<endl;
    //
    //	Greater<int> greater;
    //	cout<<greater(1, 2)<<endl;
    //}
    
    HuffMan.h

    #pragma once
    
    #include "Heap.h"
    
    template<class T>
    struct HuffManNode
    {
    	HuffManNode<T> *_left;
    	HuffManNode<T> *_right;
    	HuffManNode<T> *_parent;
    	T _weight;
    	HuffManNode(const T&x)
    		: _left(NULL)
    		, _right(NULL)
    		, _parent(NULL)
    		, _weight(x)
    	{}
    };
    
    template<class T>
    class HuffMan
    {
    	typedef HuffManNode<T> Node;
    
    	template<class T>
    	struct NodeCompare
    	{
    		bool operator() ( const Node*l, const Node*r)//模板不能分离编译
    		//因此用到NodeCompare的地方都要放到一个文件
    		{
    			return l->_weight < r->_weight;
    		}
    	};
    
    protected:
    	Node* _root;
    
    public:
    	HuffMan()
    		:_root(NULL)
    	{}
    
    	~HuffMan()
    	{}
    
    public:
    	Node* GetRootNode()
    	{
    		return _root;
    	}
    
    	Node* CreatTree(T*a, size_t size,const T& invalid)
    	{
    		//取数转换成哈夫曼结点,放到最小堆中
    		assert(a);
    		Heap<Node*, NodeCompare<T>> minHeap;
    		for (size_t i = 0; i < size; ++i)
    		{
    			if (a[i] != invalid)
    			{
    				Node*node = new Node(a[i]);
    			    minHeap.Push(node);
    			}
    			
    		}
    		/*for (int i = 0; i<10; i++)
    		{
    			Node *temp = minHeap._arrays[i];//用于测试的代码
    			cout << temp->_weight << " ";
    		}*/
    		//从最小堆中取最小的和次小的结点,建立哈夫曼树
    		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);//将最小的和次小的之和放到堆中重新调整
    		}
    		_root = minHeap.Top();//堆中最后剩下的结点就是哈夫曼的根结点
    		return _root;
    	}
    	
    	HuffManNode<T>* GetRoot()
    	{
    		return _root;
    	}
    	void PrintHuff()
    	{
    		Node *root = _root;
    		_Print(root);
    	}
    protected:
    	void _Print(Node *root)
    	{
    		if (root == NULL)
    		{
    			return;
    		}
    		else
    		{
    			cout << root->_weight;
    		}
    		_Print(root->_left);
    		_Print(root->_right);
    	}
    
    };
    
    //void TestHuff()
    //{
    //	int a[] = { 1, 0, 2, 3, 4, 5, 6, 7, 8, 9 };
    //	HuffMan<int> t;
    //	t.CreatTree(a, sizeof(a) / sizeof(int), -1);
    //
    //}
    filecompress.h

    # include<iostream>
    # include<cassert>
    # include<string>
    # include<algorithm>
    # include"HuffMan.h"
    using namespace std;
    typedef unsigned long long LongType;
    struct FileInfo
    {
      unsigned	char _ch;
      LongType  _count;
      string  _code;
      FileInfo(unsigned char ch=0)
    	  :_ch(ch)
    	  , _count(0)
      {}
     FileInfo operator+(FileInfo filein)
      {
    	 FileInfo temp;
    	 temp._count=_count + filein._count;
    	 return temp;
      }
     bool operator<( const FileInfo filein)const               
     {
    	 return _count < filein._count;
     }
     bool operator!=(const FileInfo  Invalid)const
     {
    	 return _count != Invalid._count;
     }
    };
    class FileCompress
    {
    protected:
    	FileInfo _Infos[256];
    	LongType COUNT = 0;
    public:
    	FileCompress()
    	{
    		for (int i = 0; i < 256;i++)
    		{
    			_Infos[i]._ch = i;
    		}
    	}
    	bool Compress(const char *filename)//该函数起到统计的作用
    	{
    		FILE *fout = fopen(filename, "rb");//以二进制形式打开文件
    		assert(fout);
    		unsigned char ch = fgetc(fout);
    		while (!feof(fout))
    		{
    			_Infos[ch]._count++;//统计各种字符在文件中的个数
    			ch = fgetc(fout);
    			COUNT++;//统计文件中总的字符个数
    		}
    		fclose(fout);
    		return true;
    	}
    	void GenerateHuffManCode()
    	{
    		HuffMan<FileInfo> t;
    		FileInfo invalid;
    		t.CreatTree(_Infos, 256, invalid);
    		HuffManNode<FileInfo>*root = t.GetRoot();
    		_GenrateHuffManCode(root);
    	}
    	void _GenrateHuffManCode(HuffManNode<FileInfo>* root)
    	{
    		if (root == NULL)
    		{
    			return;
    		}
    		_GenrateHuffManCode(root->_left);
    		_GenrateHuffManCode(root->_right);
    
    		if ((root->_left == NULL) && (root->_right == NULL))
    		{
    			HuffManNode<FileInfo>*cur = root;
    			HuffManNode<FileInfo>*parent = cur->_parent;
    			string &code = _Infos[cur->_weight._ch]._code;
    			while (parent)//从叶子节点走到根结点
    			{
    				if (parent->_left == cur)
    			
    					code += '0';		
    				else		
    					code += '1';	
    				cur = parent;
    				parent = cur->_parent;
    			}
    			reverse(code.begin(), code.end());
    		}		
    	}
    
    	//下面进行文件压缩
    	void CompressFile(const char *filename)
    	{
    		Compress(filename);
    		string compressFile = filename;
    		compressFile += ".huffman";
    		FILE *FinCompress = fopen(compressFile.c_str(), "wb");
    		assert(FinCompress);//对压缩文件的命名处理
    		
    		GenerateHuffManCode();//产生编码
    		FILE *fout = fopen(filename, "rb");
    		assert(fout);
    
    		//进行文件压缩
    		 unsigned char inch = 0;
    		int index = 0;
    		char ch = fgetc(fout);
    		while (ch!=EOF)
    		{
    			string&code = _Infos[(unsigned char)ch]._code;
    			for (int i = 0; i < code.size(); ++i)
    			{
    				++index;
    				inch <<= 1;
    				if (code[i] == '1')
    				{
    					inch |= 1;
    				}
    				if (index == 8)
    				{
    					fputc(inch, FinCompress);
    					index = 0;
    					inch = 0;
    				}		
    			}
    			ch = fgetc(fout);
    		}
    		if (index != 0)
    		{
    			inch <<= (8 - index);
    			fputc(inch,FinCompress);
    		}
    		fclose(fout);
    		FileInfo invalid;
    		CreateConfig(filename,invalid);
    	}
    	void CreateConfig( const char* filename,FileInfo invalid)
    	{
    		string ConfigFile = filename;
    		ConfigFile += ".config";
    		FILE *FileConfig = fopen(ConfigFile.c_str(), "wb");
    		assert(FileConfig);
    
    		char ch[256];
    		string tempcount;
    		int i = 0;
    		tempcount=	_itoa(COUNT, ch, 10);
    		while (i < tempcount.size())
    		{
    			fputc(tempcount[i],FileConfig);
    			i++;
    		}//将总的字符数写入配置文件
    		fputc('\n', FileConfig);
    		for (size_t i = 0; i < 256; i++)
    		{
    			if (_Infos[i] != invalid)
    			{
    				string chInfo;
    				chInfo.clear();
    
    				if (_Infos[i]._count>0)
    				{
    					chInfo += _Infos[i]._ch;
    					chInfo += ',';
    					char ch[256]; //转换成的字符可能足够长
    					_itoa(_Infos[i]._count,ch, 10);
    					chInfo += ch;
    					for (int j = 0; j < chInfo.size(); j++)
    					{
    						fputc(chInfo[j], FileConfig);
    					}
    								
    						fputc('\n', FileConfig);					
    				}
    			}
    		}
    		fclose(FileConfig);
    	}
    
    };
    void TestFileCompress()
    {
    	FileCompress FC;
    	FC.CompressFile("fin.txt");
    	cout << "压缩成功" << endl;
    }
    
    Uncompress.h



    # include<iostream>
    using namespace std;
    # include"HuffMan.h"
    # include"filecompress.h"
    
    class Uncompress
    {
    private:
    	FileInfo _UNinfos[256];
    	LongType Count;
    public:
    	Uncompress()//哈希表的初始化
    	{
    		for (int i = 0; i < 256; i++)
    		{
    			_UNinfos[i]._ch = i;
    		}
    		Count = 0;
    	}
    	bool _Uncompress(const char *Ufilename)//读配置文件
    	{
    		string Configfile = Ufilename;
    		Configfile += ".config";
    		FILE *fpConfig = fopen(Configfile.c_str(), "rb");
    		assert(fpConfig);
    
    		string line;
    	    unsigned char ch = fgetc(fpConfig);
    		while (ch != '\n')
    		{   
    			line += ch;
    			ch =fgetc(fpConfig);		
    		}//读取第一个字符
    		Count = atoi(line.substr(0).c_str());//(总的字符个数)
    		ch = fgetc(fpConfig);//读入下一行字符
    		line.clear();
    		int j = 0;
    		while (!feof(fpConfig))
    		{
    			
    			j++;
    			while (ch != '\n')
    			{
    				line += ch;
    				ch = fgetc(fpConfig);
    
    			}
    			if (line.empty())
    			{
    				line += '\n';
    				ch = fgetc(fpConfig);
    				while (ch != '\n')
    				{
    					line += ch;
    					ch = fgetc(fpConfig);
    				}
    			}
    			ch = fgetc(fpConfig);
    			unsigned char tempch = line[0];//将第一个字符转换成无符号数和下标对应起来
    			                               //尤其要注意这里稍微不注意就全乱码了  
    			_UNinfos[tempch]._count = atoi(line.substr(2).c_str());//截取字符串并转换成整型数据
    			line.clear();
    		}
    		return true;
    	}
    	void GenrateHuffManCode(HuffManNode<FileInfo>* root)//重构哈夫曼树
    	{
    		if (root == NULL)
    		{
    			return;
    		}
    		GenrateHuffManCode(root->_left);
    		GenrateHuffManCode(root->_right);
    
    		if ((root->_left == NULL) && (root->_right == NULL))
    		{
    			HuffManNode<FileInfo>*cur = root;
    			HuffManNode<FileInfo>*parent = cur->_parent;
    			string &code = _UNinfos[cur->_weight._ch]._code;
    			while (parent)//从叶子节点走到根结点
    			{
    				if (parent->_left == cur)
    
    					code += '0';
    				else
    					code += '1';
    				cur = parent;
    				parent = cur->_parent;
    			}
    			reverse(code.begin(), code.end());
    		}
    	}
    
    	bool UncomPress(const char *UNfilename)//文件的解压缩过程
    	{
    		_Uncompress(UNfilename);
    		HuffMan<FileInfo> Re_huffTree;
    		FileInfo invalid;
    		HuffManNode<FileInfo>*root = Re_huffTree.CreatTree(_UNinfos, 256, invalid);//重构哈夫曼树
    		GenrateHuffManCode(root);
    
    		//打开文件
    		string UnComPressFile = UNfilename;
    		UnComPressFile += ".Unhuffman";
    		FILE *UCPfile = fopen(UnComPressFile.c_str(), "wb");
    		string ComPressFile = UNfilename;
    		ComPressFile += ".huffman";
    		FILE *CPfile = fopen(ComPressFile.c_str(), "rb");
    
    		//解压缩字符写入文件
    
    
    		HuffManNode<FileInfo>*tempRoot = root;//获得其根结点
    		while (!feof(CPfile))
    		{
    			unsigned char ch = fgetc(CPfile);
    			int bitCount = 7;
    			for (int i = bitCount; i >= 0; i--)
    			{
    				if (ch&(1 << i))
    				{
    					tempRoot = tempRoot->_right;
    				}
    				else
    				{
    					tempRoot = tempRoot->_left;
    				}
    				if (!tempRoot->_left&&!tempRoot->_right)//做到这里
    				{
    					fputc(tempRoot->_weight._ch, UCPfile);
    					Count--;
    					tempRoot = root;
    				}
    				if (Count <= 0)
    				{
    					break;
    				}
    			}
    			if (Count <= 0)
    			{
    				break;
    			}
    		}
    		return true;
    	}
    
    };
    void TestUNCP()
    {
    	Uncompress Uncp;
    	Uncp.UncomPress("fin.txt");
    }




    展开全文
  • 实验目的了解文件的概念掌握线性链表的插入、删除等算法掌握Huffman树的概念及构造方法掌握二叉树的存储结构及遍历算法利用Huffman树及Huffman编码,掌握实现文件压缩的一般原理 参考博文和源码下载地址:...

    实验目的

    了解文件的概念

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

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

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

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

    6607861-b6007b085c856754.png

    参考博文和源码下载地址:

    https://write-bug.com/article/1281.html

    展开全文
  • 文件压缩与解压缩哈夫曼编码

    千次阅读 2017-09-07 15:41:51
    本文采用哈夫曼编码的方式进行文件(文本文件)压缩和解压缩,首先介绍项目的整体思路:哈夫曼编码压缩文件实际就是统计出文件中各个字符出现的频率,然后为每个字符生成对应的编码,然后将每个字符用哈夫曼编码的...

    本文采用哈夫曼编码的方式进行文件(文本文件)压缩和解压缩,首先介绍项目的整体思路:哈夫曼编码压缩文件实际就是统计出文件中各个字符出现的频率,然后为每个字符生成对应的编码,然后将每个字符用哈夫曼编码的形式按字节保存在压缩文件中。而文件的解压缩实际上就是将压缩文件翻译过来保存到解压缩文件中,需要使用压缩过程中生成的配置文件配合完成。下面将具体介绍文件的压缩和解压缩步骤:

       文件的压缩的核心是产生哈夫曼编码,而哈夫曼编码的过程中需要找到一系列数据中的最小权重和次小权重,我们自然联想到用堆这种结构时间复发度小并且很方便找到最小值和次小值,我将堆的源代码放在Heap.h文件中(见下文)。现在我们进行文件压缩。
    

    1 . 统计文件中所有字符的出现次数。 由于Ascall码字符一共255个,只有前128个字符可以显示,定义字符变量时一定要定义成无符号型变量 unsigned char ch ,这是ch读不到文件的结束标志,所以我们可以用函数feof来代替文件的结束标志EOF,最重要的是文件的打开方式一定要是二进制的形式打开否则读不到汉字字符,将出现乱码。关于存储方式我们采用哈希表的方式将每个字符映射为哈希表的下标,这样可以很方便的将每个字符和出现的次数对应起来。需要说明的是我们这个哈希表存的绝不是单纯的次数而是结点FileInfo,这个节点称为权重结点中保存出现次数和字符以及将来我们产生的哈夫曼编码,方便我们进行索引。

    bool Compress(const char *filename)//该函数起到统计的作用
    {
    FILE *fout = fopen(filename, "rb");//以二进制形式打开文件
    assert(fout);
    unsigned char ch = fgetc(fout);
    while (!feof(fout))
    {
    _Infos[ch]._count++;//统计各种字符在文件中的个数
    ch = fgetc(fout);
    COUNT++;//统计文件中总的字符个数
    }
    fclose(fout);
    return true;
    }

    2 . 现在我们创建一个最小堆,将统计到的结点压入堆中;
    3 . 从堆中取数据在HuffMan.h头文件中建立哈夫曼树;
    4 . 通过哈夫曼树产生哈夫曼编码存入节点中;
    5 . 遍历待压缩文件将对应的哈夫曼编码按字节保存到压缩文件中;
    6 . 将每个字符出现的个数保存到配置文件中。由步骤5产生的压缩文件,当我们遍历到文件的最后一个字符时,如果编码凑不成8位一个字节我们给剩下的位置补0,为了解决最后一个字符的解析问题,我们将待压缩文件中的总的字符个数统计出来存到配置文 件的第一行,以后每行以“X,n”的形式存放字符和对应的出现次数。这样我们的文件压缩过程就完成了。

    文件的解压缩思路简单,但是要尤其注意细节读配置文件就要花些心思,体现在换行符的统计上,下面进行文件的解压缩(源文件见Uncompress.h):

    1 . 读配置文件;
    2 . 通过配置文件重构哈夫曼树;
    3 .文件的解压缩,按字符读入编码通过编码在哈夫曼树种寻找对应的字符,并将字符存入到解压缩文件中去,通过配置文件中读入的COUNT来控制最后一个字符正确编码的起止。这样文件的解压缩完成。

    Heap.h

    #include <vector>  
    
    template<class T>  
    struct Less  
    {  
        bool operator() (const T& l, const T& r)  
        {  
            return l < r; // operator<  
        }  
    };  
    
    template<class T>  
    struct Greater  
    {  
        bool operator() (const T& l, const T& r)  
        {  
            return l > r; // operator>  
        }  
    };  
    
    
    template<class T, class Compare=Less<T>>//哈夫曼结点的仿函数  
    class Heap  
    {  
    public:  
        Heap()  
        {}  
        Heap(const T* a, size_t size)  
        {  
            for (size_t i = 0; i < size; ++i)  
            {  
                _arrays.push_back(a[i]);//将所有数据插入堆  
            }  
    
            // 建堆  
            for (int i = (_arrays.size() - 2) / 2; i >= 0; --i)  
            {  
                AdjustDown(i);//对这个范围的每个节点都向下调整,建堆的过程实际就是向下调整堆的过程  
            }  
        }  
    
        void Push(const T& x)  
        {  
            _arrays.push_back(x);  
            AdjustUp(_arrays.size() - 1);//插入节点的过程实际就是向上调整堆的过程  
        }  
    
        void Pop()  
        {  
            assert(_arrays.size() > 0);  
            swap(_arrays[0], _arrays[_arrays.size() - 1]);  
            _arrays.pop_back();  
    
            AdjustDown(0);  
        }  
    
        T& Top()  
        {  
            assert(_arrays.size() > 0);  
            return _arrays[0];  
        }  
    
        bool Empty()  
        {  
            return _arrays.empty();  
        }  
    
        size_t Size()  
        {  
            return _arrays.size();  
        }  
    
        void AdjustDown(int root)  
        {  
            int child = root * 2 + 1;  
    
            Compare com;  
            while (child < _arrays.size())  
            {  
                // 比较出左右孩子中小的那个  
                if (child + 1<_arrays.size() &&  
                    com(_arrays[child + 1], _arrays[child]))  
                {  
                    ++child;  
                }  
    
                if (com(_arrays[child], _arrays[root]))  
                {  
                    swap(_arrays[child], _arrays[root]);  
                    root = child;  
                    child = 2 * root + 1;  
                }  
                else  
                {  
                    break;  
                }  
            }  
        }  
    
        void AdjustUp(int child)  
        {  
            int parent = (child - 1) / 2;  
    
            while (child > 0)  
            {  
                if (Compare()(_arrays[child], _arrays[parent]))  
                {  
                    swap(_arrays[parent], _arrays[child]);  
                    child = parent;  
                    parent = (child - 1) / 2;  
                }  
                else  
                {  
                    break;  
                }  
            }  
        }  
    
        void Print()  
        {  
            for (size_t i = 0; i < _arrays.size(); ++i)  
            {  
                cout << _arrays[i] << " ";  
            }  
            cout << endl;  
        }  
    
    public:  
        vector<T> _arrays;  
    };  
    
    //测试堆   
    //void Test1()  
    //{  
    //  int a[10] = { 10, 11, 13, 12, 16, 18, 15, 17, 14, 19 };  
    //  Heap<int, Greater<int> > hp1(a, 10);  
    //  hp1.Push(1);  
    //  hp1.Print();  
    //  
    //  Heap<int> hp2(a, 10);  
    //  hp2.Push(1);  
    //  hp2.Print();  
    //  
    //  
    //  Less<int> less;  
    //  cout<<less(1, 2)<<endl;  
    //  
    //  Greater<int> greater;  
    //  cout<<greater(1, 2)<<endl;  
    //}

    HuffMan.h

    #pragma once  
    
    #include "Heap.h"  
    
    template<class T>  
    struct HuffManNode  
    {  
        HuffManNode<T> *_left;  
        HuffManNode<T> *_right;  
        HuffManNode<T> *_parent;  
        T _weight;  
        HuffManNode(const T&x)  
            : _left(NULL)  
            , _right(NULL)  
            , _parent(NULL)  
            , _weight(x)  
        {}  
    };  
    
    template<class T>  
    class HuffMan  
    {  
        typedef HuffManNode<T> Node;  
    
        template<class T>  
        struct NodeCompare  
        {  
            bool operator() ( const Node*l, const Node*r)//模板不能分离编译  
            //因此用到NodeCompare的地方都要放到一个文件  
            {  
                return l->_weight < r->_weight;  
            }  
        };  
    
    protected:  
        Node* _root;  
    
    public:  
        HuffMan()  
            :_root(NULL)  
        {}  
    
        ~HuffMan()  
        {}  
    
    public:  
        Node* GetRootNode()  
        {  
            return _root;  
        }  
    
        Node* CreatTree(T*a, size_t size,const T& invalid)  
        {  
            //取数转换成哈夫曼结点,放到最小堆中  
            assert(a);  
            Heap<Node*, NodeCompare<T>> minHeap;  
            for (size_t i = 0; i < size; ++i)  
            {  
                if (a[i] != invalid)  
                {  
                    Node*node = new Node(a[i]);  
                    minHeap.Push(node);  
                }  
    
            }  
            /*for (int i = 0; i<10; i++) 
            { 
                Node *temp = minHeap._arrays[i];//用于测试的代码 
                cout << temp->_weight << " "; 
            }*/  
            //从最小堆中取最小的和次小的结点,建立哈夫曼树  
            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);//将最小的和次小的之和放到堆中重新调整  
            }  
            _root = minHeap.Top();//堆中最后剩下的结点就是哈夫曼的根结点  
            return _root;  
        }  
    
        HuffManNode<T>* GetRoot()  
        {  
            return _root;  
        }  
        void PrintHuff()  
        {  
            Node *root = _root;  
            _Print(root);  
        }  
    protected:  
        void _Print(Node *root)  
        {  
            if (root == NULL)  
            {  
                return;  
            }  
            else  
            {  
                cout << root->_weight;  
            }  
            _Print(root->_left);  
            _Print(root->_right);  
        }  
    
    };  
    
    //void TestHuff()  
    //{  
    //  int a[] = { 1, 0, 2, 3, 4, 5, 6, 7, 8, 9 };  
    //  HuffMan<int> t;  
    //  t.CreatTree(a, sizeof(a) / sizeof(int), -1);  
    //  
    //}

    filecompress.h

    # include<iostream>  
    # include<cassert>  
    # include<string>  
    # include<algorithm>  
    # include"HuffMan.h"  
    using namespace std;  
    typedef unsigned long long LongType;  
    struct FileInfo  
    {  
      unsigned  char _ch;  
      LongType  _count;  
      string  _code;  
      FileInfo(unsigned char ch=0)  
          :_ch(ch)  
          , _count(0)  
      {}  
     FileInfo operator+(FileInfo filein)  
      {  
         FileInfo temp;  
         temp._count=_count + filein._count;  
         return temp;  
      }  
     bool operator<( const FileInfo filein)const                 
     {  
         return _count < filein._count;  
     }  
     bool operator!=(const FileInfo  Invalid)const  
     {  
         return _count != Invalid._count;  
     }  
    };  
    class FileCompress  
    {  
    protected:  
        FileInfo _Infos[256];  
        LongType COUNT = 0;  
    public:  
        FileCompress()  
        {  
            for (int i = 0; i < 256;i++)  
            {  
                _Infos[i]._ch = i;  
            }  
        }  
        bool Compress(const char *filename)//该函数起到统计的作用  
        {  
            FILE *fout = fopen(filename, "rb");//以二进制形式打开文件  
            assert(fout);  
            unsigned char ch = fgetc(fout);  
            while (!feof(fout))  
            {  
                _Infos[ch]._count++;//统计各种字符在文件中的个数  
                ch = fgetc(fout);  
                COUNT++;//统计文件中总的字符个数  
            }  
            fclose(fout);  
            return true;  
        }  
        void GenerateHuffManCode()  
        {  
            HuffMan<FileInfo> t;  
            FileInfo invalid;  
            t.CreatTree(_Infos, 256, invalid);  
            HuffManNode<FileInfo>*root = t.GetRoot();  
            _GenrateHuffManCode(root);  
        }  
        void _GenrateHuffManCode(HuffManNode<FileInfo>* root)  
        {  
            if (root == NULL)  
            {  
                return;  
            }  
            _GenrateHuffManCode(root->_left);  
            _GenrateHuffManCode(root->_right);  
    
            if ((root->_left == NULL) && (root->_right == NULL))  
            {  
                HuffManNode<FileInfo>*cur = root;  
                HuffManNode<FileInfo>*parent = cur->_parent;  
                string &code = _Infos[cur->_weight._ch]._code;  
                while (parent)//从叶子节点走到根结点  
                {  
                    if (parent->_left == cur)  
    
                        code += '0';          
                    else          
                        code += '1';      
                    cur = parent;  
                    parent = cur->_parent;  
                }  
                reverse(code.begin(), code.end());  
            }         
        }  
    
        //下面进行文件压缩  
        void CompressFile(const char *filename)  
        {  
            Compress(filename);  
            string compressFile = filename;  
            compressFile += ".huffman";  
            FILE *FinCompress = fopen(compressFile.c_str(), "wb");  
            assert(FinCompress);//对压缩文件的命名处理  
    
            GenerateHuffManCode();//产生编码  
            FILE *fout = fopen(filename, "rb");  
            assert(fout);  
    
            //进行文件压缩  
             unsigned char inch = 0;  
            int index = 0;  
            char ch = fgetc(fout);  
            while (ch!=EOF)  
            {  
                string&code = _Infos[(unsigned char)ch]._code;  
                for (int i = 0; i < code.size(); ++i)  
                {  
                    ++index;  
                    inch <<= 1;  
                    if (code[i] == '1')  
                    {  
                        inch |= 1;  
                    }  
                    if (index == 8)  
                    {  
                        fputc(inch, FinCompress);  
                        index = 0;  
                        inch = 0;  
                    }         
                }  
                ch = fgetc(fout);  
            }  
            if (index != 0)  
            {  
                inch <<= (8 - index);  
                fputc(inch,FinCompress);  
            }  
            fclose(fout);  
            FileInfo invalid;  
            CreateConfig(filename,invalid);  
        }  
        void CreateConfig( const char* filename,FileInfo invalid)  
        {  
            string ConfigFile = filename;  
            ConfigFile += ".config";  
            FILE *FileConfig = fopen(ConfigFile.c_str(), "wb");  
            assert(FileConfig);  
    
            char ch[256];  
            string tempcount;  
            int i = 0;  
            tempcount=  _itoa(COUNT, ch, 10);  
            while (i < tempcount.size())  
            {  
                fputc(tempcount[i],FileConfig);  
                i++;  
            }//将总的字符数写入配置文件  
            fputc('\n', FileConfig);  
            for (size_t i = 0; i < 256; i++)  
            {  
                if (_Infos[i] != invalid)  
                {  
                    string chInfo;  
                    chInfo.clear();  
    
                    if (_Infos[i]._count>0)  
                    {  
                        chInfo += _Infos[i]._ch;  
                        chInfo += ',';  
                        char ch[256]; //转换成的字符可能足够长  
                        _itoa(_Infos[i]._count,ch, 10);  
                        chInfo += ch;  
                        for (int j = 0; j < chInfo.size(); j++)  
                        {  
                            fputc(chInfo[j], FileConfig);  
                        }  
    
                            fputc('\n', FileConfig);                      
                    }  
                }  
            }  
            fclose(FileConfig);  
        }  
    
    };  
    void TestFileCompress()  
    {  
        FileCompress FC;  
        FC.CompressFile("fin.txt");  
        cout << "压缩成功" << endl;  
    }

    Uncompress.h

    # include<iostream>  
    using namespace std;  
    # include"HuffMan.h"  
    # include"filecompress.h"  
    
    class Uncompress  
    {  
    private:  
        FileInfo _UNinfos[256];  
        LongType Count;  
    public:  
        Uncompress()//哈希表的初始化  
        {  
            for (int i = 0; i < 256; i++)  
            {  
                _UNinfos[i]._ch = i;  
            }  
            Count = 0;  
        }  
        bool _Uncompress(const char *Ufilename)//读配置文件  
        {  
            string Configfile = Ufilename;  
            Configfile += ".config";  
            FILE *fpConfig = fopen(Configfile.c_str(), "rb");  
            assert(fpConfig);  
    
            string line;  
            unsigned char ch = fgetc(fpConfig);  
            while (ch != '\n')  
            {     
                line += ch;  
                ch =fgetc(fpConfig);          
            }//读取第一个字符  
            Count = atoi(line.substr(0).c_str());//(总的字符个数)  
            ch = fgetc(fpConfig);//读入下一行字符  
            line.clear();  
            int j = 0;  
            while (!feof(fpConfig))  
            {  
    
                j++;  
                while (ch != '\n')  
                {  
                    line += ch;  
                    ch = fgetc(fpConfig);  
    
                }  
                if (line.empty())  
                {  
                    line += '\n';  
                    ch = fgetc(fpConfig);  
                    while (ch != '\n')  
                    {  
                        line += ch;  
                        ch = fgetc(fpConfig);  
                    }  
                }  
                ch = fgetc(fpConfig);  
                unsigned char tempch = line[0];//将第一个字符转换成无符号数和下标对应起来  
                                               //尤其要注意这里稍微不注意就全乱码了    
                _UNinfos[tempch]._count = atoi(line.substr(2).c_str());//截取字符串并转换成整型数据  
                line.clear();  
            }  
            return true;  
        }  
        void GenrateHuffManCode(HuffManNode<FileInfo>* root)//重构哈夫曼树  
        {  
            if (root == NULL)  
            {  
                return;  
            }  
            GenrateHuffManCode(root->_left);  
            GenrateHuffManCode(root->_right);  
    
            if ((root->_left == NULL) && (root->_right == NULL))  
            {  
                HuffManNode<FileInfo>*cur = root;  
                HuffManNode<FileInfo>*parent = cur->_parent;  
                string &code = _UNinfos[cur->_weight._ch]._code;  
                while (parent)//从叶子节点走到根结点  
                {  
                    if (parent->_left == cur)  
    
                        code += '0';  
                    else  
                        code += '1';  
                    cur = parent;  
                    parent = cur->_parent;  
                }  
                reverse(code.begin(), code.end());  
            }  
        }  
    
        bool UncomPress(const char *UNfilename)//文件的解压缩过程  
        {  
            _Uncompress(UNfilename);  
            HuffMan<FileInfo> Re_huffTree;  
            FileInfo invalid;  
            HuffManNode<FileInfo>*root = Re_huffTree.CreatTree(_UNinfos, 256, invalid);//重构哈夫曼树  
            GenrateHuffManCode(root);  
    
            //打开文件  
            string UnComPressFile = UNfilename;  
            UnComPressFile += ".Unhuffman";  
            FILE *UCPfile = fopen(UnComPressFile.c_str(), "wb");  
            string ComPressFile = UNfilename;  
            ComPressFile += ".huffman";  
            FILE *CPfile = fopen(ComPressFile.c_str(), "rb");  
    
            //解压缩字符写入文件  
    
    
            HuffManNode<FileInfo>*tempRoot = root;//获得其根结点  
            while (!feof(CPfile))  
            {  
                unsigned char ch = fgetc(CPfile);  
                int bitCount = 7;  
                for (int i = bitCount; i >= 0; i--)  
                {  
                    if (ch&(1 << i))  
                    {  
                        tempRoot = tempRoot->_right;  
                    }  
                    else  
                    {  
                        tempRoot = tempRoot->_left;  
                    }  
                    if (!tempRoot->_left&&!tempRoot->_right)//做到这里  
                    {  
                        fputc(tempRoot->_weight._ch, UCPfile);  
                        Count--;  
                        tempRoot = root;  
                    }  
                    if (Count <= 0)  
                    {  
                        break;  
                    }  
                }  
                if (Count <= 0)  
                {  
                    break;  
                }  
            }  
            return true;  
        }  
    
    };  
    void TestUNCP()  
    {  
        Uncompress Uncp;  
        Uncp.UncomPress("fin.txt");  
    }
    展开全文
  • 哈夫曼压缩与解压缩

    万次阅读 多人点赞 2018-08-13 12:52:01
    哈夫曼压缩与解压缩 目录 哈夫曼压缩与解压缩 一:引言 二:主要技术点 三:过程介绍 1、压缩: 2、解压缩 四:详细分析 一:准备过程 二:压缩 三:解压缩 五:结果演示 六:总结 七:源码地址 一:...

    哈夫曼压缩与解压缩

    目录

    哈夫曼压缩与解压缩

    一:引言

    二:主要技术点

    三:过程介绍

    1、压缩:

    2、解压缩

    四:详细分析

    一:准备过程

    二:压缩

    三:解压缩

    五:结果演示

    六:总结

    七:源码地址


    一:引言

    之前的两个贪吃蛇和巨大数的练习,总体来说难度不大,有好的算法和比较新颖的微译码补码。但是,哈夫曼压缩与解压缩可以说难度比前两个大得多,涉及的知识面更加广。做完这个,是对自己基本功的检测,更能提升自己的编程能力。 

    hffman编码的思想对文件进行压缩,主要原理是通过huffman编码来重新表示字符,使得出现频率高的字符编码短,出现少的字符编码长。整体下来的话,所需的总的bit位是减少的。但是要注意当大部分字符出现的频率都差不多时,huffman压缩的压缩效率会很低。

    编程环境:

    UE(或sublime),TDM-GCC。

    二:主要技术点

    1. 文件的各种操作
    2. 递归思想构造哈夫曼编码。
    3. 位运算思想进行压缩与解压缩。
    4. 自定义目标压缩文件头部元数据。
    5. 主函数带参,命令行参数。

    三:过程介绍

    1、压缩:

    1、统计字符种类及频度:ASCII码值当下标,字符频度当对应下标的值。

    2、构建哈夫曼树:在没有访问过的节点中,找最小字符频度下标来构建哈夫曼树。

    3、构建哈夫曼编码:递归思想构建。

    4、生成压缩文件(.ycyHuf后缀名):把字符的哈夫曼编码以二进制形式写入目标文件中。给压缩文件头部写入元数据,解压缩时需使用这些数据。

    注意事项:给目标文件写二进制数据时,最后一个字节如果不满八位,会产生垃圾数据,如果不进行处理,在解压后,就不能完整的还原。所以,需计算最后一个字节中的有效位数。

    2、解压缩

    1、根据压缩文件的头部元数据,得到字符种类和频度。

    2、构建哈夫曼树:在没有访问过的节点中,找最小字符频度下标来构建哈夫曼树。

    3、构建哈夫曼编码:递归思想构建。

    4、生成解压缩的文件(后缀名和源文件后缀名一样 )即可:一位一位的从压缩文件中读取信息,'1'向左子树走,'0'向右子树走。

    注意事项:压缩文件头部有元数据,所以,解压时需要把文件指针定位到真正的信息处。当碰到最后一字节的垃圾位时,应结束,否则解压出的信息和源文件会不匹配。

    四:详细分析

    一:准备过程

    三个关于位运算的宏

    1、取出index位,若取出的index位为0,则GET_BYTE值为假,否则为真

    #define GET_BYTE(vbyte, index) (((vbyte) & (1 << ((index) ^ 7))) != 0)

    2、把index位设置为‘1’

    #define SET_BYTE(vbyte, index) ((vbyte) |= (1 << ((index) ^ 7)))

    3、把index位设置为‘0’ 

    #define CLR_BYTE(vbyte, index) ((vbyte) &= (~(1 << ((index) ^ 7))))

    二:压缩

    1、统计字符种类和频度

    结构体定义:

    typedef struct ALPHA_FREQ {
    	unsigned char alpha;		//字符,考虑到文件中有汉字,所以定义成unsigned char
    	int freq;					//字符出现的频度
    } ALPHA_FREQ;

    代码分析:

    ALPHA_FREQ *getAlphaFreq(char *sourceFileName, int *alphaVariety) {
    	int freq[256] = {0};
    	int i;
    	int index;
    	ALPHA_FREQ *alphaFreq = NULL;
    	FILE *fpIn;
    	int ch;
    	
    	fpIn = fopen(sourceFileName, "rb");
    	
    	/*统计所有字符的频度*/
    	ch = fgetc(fpIn);
    	while(!feof(fpIn)) {
    		freq[ch]++;
    		ch = fgetc(fpIn);
    	}
    	fclose(fpIn);
    
    	/*统计所有字符的种类*/
    	for(i = 0; i < 256; i++) {
    		if(freq[i]) {
    			(*alphaVariety)++;
    		}
    	}
    
    	alphaFreq = (ALPHA_FREQ *) calloc(sizeof(ALPHA_FREQ), *alphaVariety);
    	for(i = index = 0; i < 256; i++) {
    		if(freq[i]) {
    			alphaFreq[index].alpha = i;
    			alphaFreq[index].freq = freq[i];
    			index++;
    		}
    	}
    
    	return alphaFreq;
    }

    统计字符及其频度,开始想到了一个笨办法。 如下:

    AlPHA_FREQ freq[256]
    count = 0;
    i = 0;
    
    while(str[i]) {
    	index = 0;
    	while(index < count) {
    		if(freq[index].alpha == str[i]) {
    			break;
    		}
    		index++
    	}
    	
    	if(index < count) {
    		freq[count].freq++;
    	} else {
    		freq[count].alpha = str[i];
    		freq[count].freq = 1;
    		count++;
    	}
    }

    但是,这样做有一个很大的缺点:随着字符串的增多,查找次数就会越来越多,极端情况下,没有重复的字符,那么就要执行n-1次,光一个统计字符的函数,其时间复杂度就达到了O(n^2);这显然是不合理的。因此,有一个更好的算法:构建一个大的数组,以字符的ASCII码值当下标,字符频度当对应下标的值,实现用空间,换时间的目的。例如'A'的频度,永远存放在下标为65的元素中。这样做,其时间复杂度达到了O(n)。

    2、初始化哈夫曼表

    结构体定义:

    typedef struct HUFFMAN_TAB {
    	ALPHA_FREQ alphaFreq;
    	int leftChild;
    	int rightChild;
    	boolean visited;
    	char *code;
    } HUFFMAN_TAB;
    HUFFMAN_TAB *initHuffmanTab(ALPHA_FREQ *alphaFreq, int alphaVariety, int *hufIndex) {
    	int i;
    	HUFFMAN_TAB *huffmanTab = NULL;
    
    	huffmanTab = (HUFFMAN_TAB *) calloc(sizeof(HUFFMAN_TAB), 2 * alphaVariety - 1);
    	//huffmanTab申请了 2 * alphaVariety - 1大小的空间,在这只用了 alphaVariety个,还剩alphaVariety - 1个
    	for(i = 0; i < alphaVariety; i++) {
    		hufIndex[alphaFreq[i].alpha] = i;	//把哈夫曼表中的字符和其对应的下标形成键值对,存到hufIndex中
    		huffmanTab[i].alphaFreq = alphaFreq[i];
    		huffmanTab[i].leftChild = huffmanTab[i].rightChild = -1;
    		huffmanTab[i].visited = FALSE;
    		huffmanTab[i].code = (char *) calloc(sizeof(char), alphaVariety);
    	}
    
    	return huffmanTab;
    }

    字符种类个数即为哈夫曼树的叶子结点个数,那么,根据完全二叉树的性质,这个哈夫曼树的总结点数为叶子节点数加度为2的节点数,所以,n总 = 2 * n0 - 1。先构建出哈夫曼表,为后面构建哈夫曼树做准备。注意,需设置一个visited成员来表示结点有没有被访问过。

    例如:字符串为“siytweusitweusitweusitwesitesitesitesieieieeeeee”,那么,统计出的结果为这样:

    根据这个哈夫曼表,可以画出哈夫曼树的结构了,如下:

    3、生成哈夫曼树

    生成哈夫曼树,我们需要把频度大的节点放在离根近的地方,频度小的节点放在离根远的地方。所以,需要进行最小字符频度的查找。

    int getMinFreq(HUFFMAN_TAB *huffmanTab, int count) {
    	int index;
    	int minIndex = NOT_INIT;
    
    	for(index = 0; index < count; index++) {
    		if(FALSE == huffmanTab[index].visited) {
    			if(NOT_INIT == minIndex || huffmanTab[index].alphaFreq.freq < huffmanTab[minIndex].alphaFreq.freq) {
    				minIndex = index;
    			}
    		}
    	}
    	huffmanTab[minIndex].visited = TRUE;
    
    	return minIndex;
    }
    void creatHuffmanTree(HUFFMAN_TAB *huffmanTab, int alphaVariety) {
    	int i;
    	int leftChild;
    	int rightChild;
    
    	//huffmanTab使用剩下的 alphaVariety - 1个空间
    	for(i = 0; i < alphaVariety - 1; i++) {
    		leftChild = getMinFreq(huffmanTab, alphaVariety + i);
    		rightChild = getMinFreq(huffmanTab, alphaVariety + i);
    		huffmanTab[alphaVariety + i].alphaFreq.alpha = '#';
    		huffmanTab[alphaVariety + i].alphaFreq.freq = huffmanTab[leftChild].alphaFreq.freq
    																									 + huffmanTab[rightChild].alphaFreq.freq;
    		huffmanTab[alphaVariety + i].leftChild = leftChild;
    		huffmanTab[alphaVariety + i].rightChild = rightChild;
    		huffmanTab[alphaVariety + i].visited = FALSE;
    	}
    }

    生成的哈夫曼树的表格形式如下

    4、生成哈夫曼编码

    哈夫曼树都已经生成,那么就需要生成哈夫曼编码了。

    思路:需要把哈夫曼树从根节点除法,进行遍历,向左子树为‘1’,右子树为‘0’;若碰到叶子结点,需要把编码存给对应的字符。若没有碰到叶子结点,则需要继续向下遍历。所以,这需要一个递归程序完成。

    void makeHuffmanCode(HUFFMAN_TAB *huffmanTab, int root, int index, char *code) {
    	if(huffmanTab[root].leftChild != -1 && huffmanTab[root].rightChild != -1) {
    		code[index] = '1';
    		makeHuffmanCode(huffmanTab, huffmanTab[root].leftChild, index + 1, code);
    		code[index] = '0';
    		makeHuffmanCode(huffmanTab, huffmanTab[root].rightChild, index + 1, code);
    	} else {
    		code[index] = 0;
    		strcpy(huffmanTab[root].code, code);
    	}
    }

    5、把哈夫曼编码以二进制位形式写入目标文件中

    此时,我们需要考虑一个问题。如果,光把“siytweusitweusitweusitwesitesitesitesieieieeeeee”这个字符串的哈夫曼编码以二进制形式写入目标文件,形成的目标文件中全是0101这种二进制代码,那如何解密呢?没有人能看懂这种二进制代码,所以,我们需要给目标文件的头部写入元数据(解释数据的数据),这些元数据主要包括源文件字符种类,字符频度。有了元数据,那么,就可以在解压缩程序中再构造一个完全相同的哈夫曼树,完成解压缩。

    所以,我们也可以构造我们的文件头部元数据,定义一个结构体如下:

    typedef struct HUF_FILE_HEAD {
    	unsigned char flag[3];				//压缩二进制文件头部标志 ycy
    	unsigned char alphaVariety;		//字符种类
    	unsigned char lastValidBit;		//最后一个字节的有效位数
    	unsigned char unused[11];			//待用空间
    } HUF_FILE_HEAD;								//这个结构体总共占用16个字节的空间

    依次给文件头部写入头部标志“ycy”, 字符种类alphaVariety, 最后一字节的有效位数lastValidBit。

    HUF_FILE_HEAD fileHead = {'y', 'c', 'y'};
    fileHead.alphaVariety = (unsigned char) alphaVariety;
    fileHead.lastValidBit = getlastValidBit(huffmanTab, alphaVariety);
    
    fwrite(&fileHead, sizeof(HUF_FILE_HEAD), 1, fpOut);
    fwrite(alphaFreq, sizeof(ALPHA_FREQ), alphaVariety, fpOut);

    lastValidBit计算过程:

    //取最后一个字节的有效位数
    int getlastValidBit(HUFFMAN_TAB *huffmanTab, int alphaVariety) {
    	int sum = 0;
    	int i;
    	
    	for(i = 0; i < alphaVariety; i++) {
    		sum += strlen(huffmanTab[i].code) * huffmanTab[i].alphaFreq.freq;
    		//如果不执行这一步,当数据长度超过int的表示范围,就会出错
    		sum &= 0xFF; //0xFF化为二进制位1111 1111,这样做sum始终是最后一个字节,8位
    	}
    	//举例:若最后生成7位二进制,划分为一个字节,那么,这一个字节只有7位为有效位,其余都是垃圾位。
    	//我们只需要取出这个字节的那7个有效位,所以sum和8取余即可
    	//sum = sum % 8 <=> sum = sum & 0x7
    	//返回最后一个字节的有效位数
    	sum &= 0x7;
    		
    	return sum == 0 ? 8 : sum;
    }

    完后,我们的.ycyHuf文件头部就写好了:

    头部元数据写好后,就需要写入真正的压缩信息了。但是,如何根据字符,迅速找到其哈夫曼编码呢?有一种笨办法,就是每次都根据当前字符,在哈夫曼表中查找,如果字符匹配,就找到了哈夫曼编码。

    for(i = 0; i < alphaVariety; i++) {
    	if(str[index] == huffmanTab[i]) {
    	hufCode = huffmanTab[i].code;
        }
    }

     但是,这样每次查找进行的比较次数平均为n / 2,若字符串长度为len,则时间复杂度为O(len * n / 2)。所以,这样做不是很好,有一种方法,可以不进行“查找”,就能“查找到”,时间复杂度为O(1); 这样,需要构造出一个“字符”:“下标”的键值对关系,字符可以直接定位,就完成了这个“迅速查找”的任务。所以,我在初始化哈夫曼表initHuffmanTab()函数中,构造了这个键值对关系。

    //构造键值对
    hufIndex[alphaFreq[i].alpha] = i;	//把哈夫曼表中的字符和其对应的下标形成键值对,存到hufIndex中
    //查找
    hufCode = huffmanTab[hufIndex[ch]].code;

    下来,就可以正式的给目标压缩文件中写数据了。

    ch = fgetc(fpIn);
    	while(!feof(fpIn)) {
    		hufCode = huffmanTab[hufIndex[ch]].code;
    		//把每个字符的哈夫曼编码一个一个过。
    		//如果是字符'0',就转换为二进制的0
    		//如果是字符'1',就转换为二进制的1
    		for(i = 0; hufCode[i]; i++) {
    			if('0' == hufCode[i]) {
    				//value为一个字节
    				//从第1位依次赋值,若大于八位(一个字节)了,就写入文件中
    				CLR_BYTE(value, bitIndex);
    			} else {
    				SET_BYTE(value, bitIndex);
    			}
    			bitIndex++;
    			if(bitIndex >= 8) {
    				bitIndex = 0;
    				fwrite(&value, sizeof(unsigned char), 1, fpOut);
    			}
    		}
    		ch = fgetc(fpIn);
    	}
    	//如果最后一次不满一个字节,依然需要写到文件中,注意:写入的最后一个字节可能会存在垃圾位
    	if(bitIndex) {
    		fwrite(&value, sizeof(unsigned char), 1, fpOut);
    	}

     如果遇到了字符‘0’,就利用位运算转换为二进制0,否则,为二进制1。 如果最后一次不满一个字节,依然需要写到文件中,注意:写入的最后一个字节可能会存在垃圾位。

    三:解压缩

    1、统计字符种类和频度

    直接从压缩的文件中的头部读取。先匹配是不是自定义的格式:

    fileHead = readFileHead(sourceFileName);
    if(!(fileHead.flag[0] == 'y' && fileHead.flag[1] == 'c' && fileHead.flag[2] == 'y')) {
    	printf("不可识别的文件格式\n");
    }

     如果是“ycy”,那么再统计字符种类和频度:

    ALPHA_FREQ *getAlphaFreq(char *sourceFileName, int *alphaVariety, HUF_FILE_HEAD fileHead) {
    	int freq[256] = {0};
    	int i;
    	int index;
    	ALPHA_FREQ *alphaFreq = NULL;
    	FILE *fpIn;
    	int ch;
    
    	*alphaVariety = fileHead.alphaVariety;
    	alphaFreq = (ALPHA_FREQ *) calloc(sizeof(ALPHA_FREQ), *alphaVariety);
    	fpIn = fopen(sourceFileName, "rb");
    	//略过前16个字节的元数据
    	fseek(fpIn, 16, SEEK_SET);
    	fread(alphaFreq, sizeof(ALPHA_FREQ), *alphaVariety, fpIn);
    	fclose(fpIn);
    
    	return alphaFreq;
    }

     2、初始化哈夫曼表

    和压缩过程一样。

    3、生成哈夫曼树

    和压缩过程一样。

    4、生成哈夫曼编码

    和压缩过程一样。

    5、从压缩文件中读取二进制信息,还原文件

     应该先利用fseek()函数把文件指针跳过前面的元数据和字符种类及频度,定位到真正需要还原的地方。一位一位的进行判断,'1'向左子树走,'0'向右子树走;若到达叶子结点,向文件中写入叶子结点下标对应的字符。再回到根结点继续;若超过一个字节,8位,则需要读取下一个字节。

    void huffmanDecoding(HUFFMAN_TAB *huffmanTab, char *sourceFileName, char *targetFileName, int alphaVariety, HUF_FILE_HEAD fileHead) {
    	int root = 2 * alphaVariety - 2;
    	FILE *fpIn;
    	FILE *fpOut;
    	boolean finished = FALSE;
    	unsigned char value;
    	unsigned char outValue;
    	int index = 0;
    	long fileSize;
    	long curLocation;
    
    	fpIn = fopen(sourceFileName, "rb");
    	fpOut = fopen(targetFileName, "wb");
    	fseek(fpIn, 0L, SEEK_END);
    	fileSize = ftell(fpIn);	//文件总长度fileSize
    	fseek(fpIn, 16 + 5 * fileHead.alphaVariety, SEEK_SET);	//略过前面16个字节的元数据,5字节的字符种类和频度
    	curLocation = ftell(fpIn);
    	
    	//从根出发,'1'向左子树走,'0'向右子树走,若到达叶子结点,输出叶子结点下标对应的字符。再回到根结点继续。
    	fread(&value, sizeof(unsigned char), 1, fpIn);
    	while(!finished) {
    		if(huffmanTab[root].leftChild == -1 && huffmanTab[root].rightChild == -1) {
    			outValue = huffmanTab[root].alphaFreq.alpha;
    			fwrite(&outValue, sizeof(unsigned char), 1, fpOut);
    			if(curLocation >= fileSize && index >= fileHead.lastValidBit) {
    				break;
    			} 
    			root = 2 * alphaVariety - 2;
    		}
    		
    		//取出的一个字节从第一位开始看,'1'向左子树走,'0'向右子树走
    		//若超过一个字节,8位,则需要读取下一个字节
    		if(GET_BYTE(value, index)) {
    			root = huffmanTab[root].leftChild;
    		} else {
    			root = huffmanTab[root].rightChild;
    		}
    		if(++index >= 8) {
    			index = 0;
    			fread(&value, sizeof(unsigned char), 1, fpIn);
    			curLocation = ftell(fpIn);
    		}
    	}
    
    	fclose(fpIn);
    	fclose(fpOut);
    }

    五:结果演示

    六:总结

    哈夫曼压缩与解压缩的项目完成了(以后还会继续完善,优化)。这个项目涉及了C语言里更加高级的操作(文件,位运算,主函数带参······)。哈夫曼压缩与解压缩涉及的知识是我目前以来接触的项目里最多,最广的,收获很多。经过这个练习,还是觉得写程序前,一定一定要认真,仔细的进行手工过程的分析,一定要分析的很到位,否则,程序的逻辑就会出错,酿成大错。最后,不要忘记free申请的空间,以免造成内存泄漏。

    七:源码地址

    https://github.com/yangchaoy259189888/Huffman-compress/

    纠错:
    感谢下面这位前辈指出的这两个问题,经过测试,确实,当初测试了一个bmp文件,成功压缩和解压缩之后,以为大功告成。其实,还有很多极端情况没有考虑到。比如:一个全是a的txt文件就会失败。

    本人能力有限,毕竟这个代码不是我一个人从头到尾完成的,其中的很多思想都来自教主。

    还请看到的大神和我沟通,争取把这个错误解决······

    展开全文
  • 哈夫曼编码--压缩与解压

    千次阅读 多人点赞 2016-12-20 01:27:43
    使用哈夫曼编码的方法对文件进行压缩和解压缩。该编码方式根据不同字符出现的概率来进行构建最佳二叉树,所有的字符都位于叶子节点,规定从根节点开始,往左走为0,往右走为1,通过这种方式,可以对所有的字符进行...
  • 利用无失真信源编码方法中的哈夫曼编码进行程序设计实践,实现对文件的压缩与解压操作。
  • 哈夫曼压缩与解压缩(c语言版)

    千次阅读 多人点赞 2019-09-29 19:18:13
    哈夫曼压缩与解压缩(c语言版) 一:引言 二:主要原理 三:主要技术点 四:实现过程 1.压缩: 2.解压缩: 五:详细分析,及代码实现 哈夫曼压缩与解压缩(c语言版) 一:引言 学过数据结构的同学,应该都...
  • 利用二叉树哈夫曼编码实现对文件压缩以及解压缩
  • 使用哈夫曼编码统计字符的频率作为权值来实现压缩技术 ,包括哈夫曼树的创建,构造哈夫曼编码,使用哈夫曼编码压缩文件,和解压文件
  • 利用哈夫曼编码压缩文本

    千次阅读 多人点赞 2020-04-12 16:27:21
    文章目录使用哈夫曼编码进行压缩文本文本内容读取文件内容至内存中遍历文本内容,获取每个字符对应出现概率值建立哈夫曼树获取哈夫曼编码将转换后的编码写入新文件检测压缩率利用编码文件进行还原文本完整code ...
  • 哈夫曼编码使用哈夫曼树的数据结构,哈夫曼树图解如下,即构造一个带权路径最小的数; 2、哈夫曼编码 使用哈夫曼树生成哈夫曼编码,已实现减少传输中数据的冗余;截取网络课程中的几张图来说明; 3、...
  • 根绝哈夫曼编码写的数据压缩解压软件
  • 最近学习韩顺平老师主讲的“图解java 数据结构算法”的哈夫曼编码这一章节时,在编码实现上遇到了些许问题,本文主要记述一下问题及自己的解决方案,如有更优解还请指点
  • 哈夫曼编码实现压缩解压缩java

    热门讨论 2012-06-04 19:26:01
    使用哈夫曼编码实现对文本文件的压缩和解压缩
  • 哈夫曼编码有一个很重要的特性:每个字符编码不会成为另一个编码的前缀。这个特性保证了即使我们把不同长度的编码存在一起,仍然也可以把它们分离开,不会出现认错人的冲突。 那么我们就可以把所有
  • 哈夫曼编码压缩.rar

    2019-12-13 10:34:30
    哈夫曼编码实训,通过构建哈夫曼树及哈夫曼编码,实现无损压缩解压缩,内含完整注释,代码简便容易理解(100%运行成功+代码+简单窗口美化)~~~仅供学习交流,请勿他用!!
  • java实现哈夫曼压缩与解压缩

    千次阅读 2019-09-30 10:30:03
    哈夫曼压缩与解压缩(java版) 一哈夫曼树以及文件压缩原理: 1.哈夫曼树 : 2.如何利用haffman编码实现文件压缩: 二主要技术点: 三实现过程: 四运行展示: 哈夫曼压缩与解压缩(java版) 一哈夫曼树以及...
  • 哈夫曼编码实现文件压缩 二、实验目的 了解文件的概念 掌握线性链表的插入、删除等算法 掌握Huffman树的概念及构造方法 掌握二叉树的存储结构及遍历算法 利用Huffman树及Huffman编码,掌握实现文件...
  • 哈夫曼编码压缩和解压文件的Java实现 上一次已经介绍了如何用Huffman树实现文件的压缩及其原理,那么今天我们试着真正运用它实现文件的压缩与解压 前戏 我们先来整理一下思路 首先我们拿到一个文件,看起来是一串串...
  • 压缩过程就是编码过程,解压缩过程就是解码过程。压缩技术分为无损压缩和有损压缩两大类,前者在解码时可以精确地恢复原图像,没有任何损失;后者在解码时只能近似原图像,不能无失真地恢复原图像。
  • 数据结构,哈夫曼编码,文件压缩和解压缩一个完整的程序,大神们最好能带点注释,简单点的就行。重点:哈夫曼编码,文件压缩和解压缩
  • 哈夫曼实现文件压缩解压缩(c语言)

    万次阅读 多人点赞 2019-01-23 17:04:47
    在计算机数据处理中,霍夫曼编码使用变长编码表对源符号(如文件中的一个字母)进行编码,其中变长编码表是通过一种评估来源符号出现机率的方法得到的,出现机率高的字母使用较短的编码,反之出现机率低的则使用较长...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,583
精华内容 1,033
关键字:

哈夫曼编码的压缩与解压缩