精华内容
下载资源
问答
  • 这是我做的一个基于哈夫曼树思想的压缩算法程序源码,希望大家指正
  • 哈夫曼树以及文件压缩的实现

    万次阅读 多人点赞 2016-12-22 22:20:46
    哈夫曼树到哈夫曼编码再到文件压缩,一步步讲解,一步步实现

    一、HuffmanTree

    哈夫曼树也称为最优二叉树,是加权路径长度最短的二叉树。在讲述哈夫曼树之前先给出几个概念:

    路径:从一个结点到一个结点之间的分支构成这两个结点之间的路径

    路径长度:路径上分支的数目称为路径长度

    树的路径长度:从根节点到每一个结点的路径长度之和

    结点的带权路径长度:从该节点到树根之间的路径长度与节点上权值的乘积

    树的带权路径长度(WPL):树中所有叶子节点的带权路径长度之和

    以下这是两棵叶子节点带有权值的二叉树:


    分析上图中的两棵树:

    (a)树的路径长度 = 1+1+2+2+3+3+4+4 = 20

        WPL = 5*1 + 15*2 + 40*3 + 30*4 + 10*4 = 315

    (b)树的路径长度 = 1+1+2+2+2+2+3+3 = 16

        WPL = 5*3 + 15*3 + 40*2 + 30*2 + 10*2 = 220

    通过比较我们发现,二叉树a的路径长度和WPL值都大于二叉树b,而且上边也给出了哈夫曼树概念,因此在这里二叉树b其实就是一棵哈夫曼树。那么我们如何才能构造这样一棵树呢?!

    二、哈夫曼树的构造

    其实哈夫曼最早给出了构建树的算法,称为哈夫曼算法,这个算法大家在网上搜搜也就出来了,因此我在这里就不再写了。但是,我相信很多人看了这个都会很蒙圈,所以我就利用图+文字的形式来构建一棵哈夫曼树。

    我们在构建这棵哈夫曼树时可利用"贪心算法"的思想来构建,也就是说,每次只考虑局部最优解

    (1)先将所有的权值按照从小到大的顺序进行排序,例如为n1,n2,n3,n4,n5,......

    (2)每次选出头两个最小权值的结点n1,n2来构建n1和n2的父亲节点N1,其做法是:n1与n2的权值相加作为N1的权值,并且n1和n2中权值较小的作为左孩子

    (3)用得到的N1替换n1与n2,可得到N1,n3,n4,n5,.....,每次都要保持从小到大的顺序

    (4)重复步骤(2)(3),当所有结点都在树中时,这棵树也就构建好了

    需要说的一点是,当在进行步骤(2)(3)时,若遇到两个数的和正好是下一步的两个最小数的其中一个时,则这棵树就继续向上生长;若是两个数的和比较大不是下一步的两个最小数中的一个,就并列生长。

    例如:我们利用{0,1,2,3,4,5,6,7,8,9}这组数来构建哈夫曼树


    三、哈夫曼编码

    哈夫曼研究这种最优二叉树的更大目的是为了解决当年远距离通信的数据传输的最优化问题,其实哈夫曼树最经典的一种应用就是哈夫曼编码,现在我们可以利用哈夫曼编码来进行文件压缩。

    哈夫曼编码:假若我们规定给每个结点的左路标记'0',右路标记'1',那么我们就可以用0、1来表示每个字母。以第一幅图中的二叉树b为例


    四、文件压缩

    文件压缩的主要思想是利用哈夫曼编码来实现的,但是得到编码之前我们需要构建这棵树。那么利用什么来构建树呢?!这里,我们需要统计每个字符出现的次数,用次数来构建HuffmanTree。假设我们现在有一个.txt的小文件,内容是"aaaabbbccd"。字符存在计算机中时以字节为单位的,因此我们需要将这些字符压缩成0、1表示的编码,0和1表示字节中的“位”,这样能大大降低文件的大小。


    上图中的文字就是文件压缩的4个步骤。

    对第4步的结果进行对比可以看出,源文件需要的大小是10个字节,压缩后的文件是使用了19个比特位的空间,其实也就是3个字节的大小,剩下不够的5个比特位用0来补。这样其实也就时文件压缩后的效果!

    五、文件解压

    文件解压时就需要从根节点向叶子节点走了,读取压缩文件的编码,遇到'0'就向树的左边走,遇到'1'就向树的右边走。由于这些字符肯定都是存在与叶子结点上的,因此当遇到叶子节点以后就说明已经还原出一个字符,这时将还原的一个字符写入解压文件中;解压完一个字符后再次开始从根节点向下遍历。

    解压文件时会遇到的问题:

    上边说过,压缩以后的文件如果不够一个字节大小,会用0来代替空缺的比特位,这样带来的问题就是可能会多解压出字符。以上述的"aaaabbbccd"为例,压缩以后的编码为19比特位:00001111  11110110  100,计算机存储的最小单位为字节,因此这些编码会被存储为00001111  11110110  10000000,后边的五个0对我们来说就是多余的,如果不处理,就会多还原出5个a

    解决:

    给出一个charCount来统计所有字符串的个数,其实也就是根节点的值,每次还原出一个字符后,charCount就-1,直到charCount为0时说明所有字符都已经解压完成。


    PS:以上所有代码我都上传至github,可以点这个链接查看源代码:

    https://github.com/lybb/FileCompress


    六、测试用例

    我分别测试了.txt文件、.mp3文件、.jpg文件,还有一个自己定义的.BIG的文件


    以Input.BIG文件压缩为例,其进行压缩与解压后的结果如下:


    我们不能仅用解压文件与源文件的大小来判断是否解压成功,可以借助BeyondCompared软件来比对,对比结果如下(页面中没有显示红色的字体就表示文件一样):



    展开全文
  • 北京邮电大学信息与通信工程学院 第 PAGE 1页 北京邮电大学电信工程学院 第 PAGE 1页 2008级数据结构实验报告 实验名称 实验三实现哈夫曼树 学生姓名 * 班 级 * 班内序号 * 学 号 * 日 期 200 1实验要求 利用二叉树...
  • 哈夫曼树实现文件压缩与解压缩

    万次阅读 多人点赞 2016-06-06 21:23:14
    见识了360压缩的神奇后,想要实现自己的文件压缩程序,然后花了近一个星期的时间去完成文件压缩与解压缩,期间有很多坑,花了很长时间去调试它,最后把坑给填了(真心的感受到了程序员写代码时的小小粗心会把自己给...

           见识了360压缩的神奇后,想要实现自己的文件压缩程序,然后花了近一个星期的时间去完成文件压缩与解压缩,期间有很多坑,花了很长时间去调试它,最后把坑给填了(真心的感受到了程序员写代码时的小小粗心会把自己给坑惨)。以下是些程序时的一些坑:

    1. 在windows下回车的字符是‘\r’'\n',编译器在读取字符时读取到'\r'后再读取到'\n'就会转换为回车。。。
    2. 在解压缩小文件时不会出现的问题在解压缩大文件时会出现。最常见的时没有解压缩完文件就退出了,因为会出现一些控制字符导致程序提前退出。
    3. 压缩汉字的时候 要使用unsigned char!!!

        正如标题所说,实现文件压缩我是使用哈夫曼树产生哈夫曼编码,使用哈夫曼编码来压缩文件。

        构造哈夫曼树的key值是文件中每个字符出现的次数。将出现的字符插入一个最小堆中,每次从堆中取出出现次数最少的字符构造哈夫曼树。


    为此,我们先实现一个最小堆:
    #pragma once
    #define _CRT_SECURE_NO_WARNINGS 1
    #include<iostream>
    #include<vector>
    #include<assert.h>
    //#include"HaffmanTree.h"
    using namespace std;
    
    template<class T>
    struct Less
    {
    	bool operator()(const T& l, const T& r)
    	{
    		return l < r;
    	}
    };
    
    
    template<class T>
    struct Greater
    {
    	bool operator()(const T& l, const T& r)
    	{
    		return l > r;
    	}
    };
    
    template<class T>
    struct Less<T*>
    {
    	bool operator()(const T*Nodel, const T*Noder)
    	{
    		return Nodel->_wight < Noder->_wight;
    	}
    };
    
    template<class T,class Continer = Less<T>>//默认为小堆
    class Heap
    {
    public:
    	Heap(){};
    	Heap(const T* a, size_t size,const T& invalid);
    	Heap(vector<T> a);
    	Heap(const vector<T>& v);
    	void Push(const T& x);
    	void Pop();
    	T& GetTop();
    	bool Empty();
    	size_t Size();
    	void HeapSort(T* a, size_t size);
    protected:
    	void _AdjustDown(size_t parent);
    	void _AdjustUp(int child);
    protected:
    	vector<T> _a;
    };
    
    template<class T, class Continer = Less<T>>
    Heap<T, Continer>::Heap(const T* a, size_t size,const T& invalid)
    {
    	_a.reserve(size);
    
    	for (size_t i = 0; i < size; ++i)
    	{
    		if (a[i] != invalid)
    		{
    			_a.push_back(a[i]);
    		}
    	}
    
    	//建堆
    	for (int i = (_a.size() - 2) / 2; i >= 0; i--)
    		//从第一个非叶子结点开始下调,叶子结点可以看作是一个大堆或小堆
    	{
    
    		_AdjustDown(i);
    	}
    }
    template<class T, class Continer = Less<T>>
    Heap<T, Continer>::Heap(vector<T> a)
    {
    	_a.swap(a);
    
    	// 建堆
    	for (int i = (_a.size() - 2) / 2; i >= 0; --i)
    	{
    		_AdjustDown(i);
    	}
    }
    template<class T, class Continer = Less<T>>
    Heap<T, Continer>::Heap(const vector<T>& v)
    	:_a(v)
    {
    	//_a.resize(v.size());
    }
    template<class T, class Continer = Less<T>>
    void Heap<T, Continer>::Push(const T& x)
    {
    	_a.push_back(x);
    	_AdjustUp(_a.size() - 1);
    }
    template<class T, class Continer = Less<T>>
    void Heap<T, Continer>::Pop()
    {
    	assert(!_a.empty());
    	size_t size = _a.size();
    	swap(_a[0], _a[size - 1]);
    	_a.pop_back();
    	_AdjustDown(0);
    }
    template<class T, class Continer = Less<T>>
    T& Heap<T, Continer>::GetTop()
    {
    	return _a[0];
    }
    template<class T, class Continer = Less<T>>
    bool Heap<T, Continer>::Empty()
    {
    	return _a.empty();
    }
    template<class T, class Continer = Less<T>>
    size_t Heap<T, Continer>::Size()
    {
    	return _a.size();
    }
    
    template<class T, class Continer = Less<T>>
    void Heap<T, Continer>::_AdjustDown(size_t parent)
    {
    	Continer _con;
    	size_t child = parent * 2 + 1;
    	size_t size = _a.size();
    	while (child < size)
    	{
    		if (child + 1 < size&&_con(_a[child + 1], _a[child]))
    			//注意这必须是child+1更大或更小,所以把child+1放在前面
    			++child;
    		if (/*_a[parent] < _a[child]*/_con(_a[child], _a[parent]))
    		{
    			swap(_a[parent], _a[child]);
    			parent = child;
    			child = parent * 2 + 1;
    		}
    		else
    			break;
    	}
    }
    template<class T, class Continer = Less<T>>
    void Heap<T, Continer>::_AdjustUp(int child)
    {
    	Continer _con;
    	int parent = (child - 1) / 2;
    	while (child > 0)
    	{
    		if (_con(_a[child], _a[parent]))
    		{
    			swap(_a[child], _a[parent]);
    			child = parent;
    			parent = (child - 1) / 2;
    		}
    		else
    			break;
    	}
    <p>}</p>

        使用类模板实现的小顶堆,方便我们传入哈夫曼结点的结构体,并且实现了比较两个结构体的大小的仿函数。实质是比较_wight值


    实现了堆以后实现哈夫曼树:

    #pragma once
    #include<iostream>
    #include"Heap.h"
    #include"FileComparess.h"
    
    using namespace std;
    
    
    template<class T>
    struct HaffmanNode
    {
    	HaffmanNode<T>* _left;
    	HaffmanNode<T>* _right;
    	T _wight;
    	HaffmanNode(const T& wight)
    		:_left(NULL)
    		, _right(NULL)
    		, _wight(wight)
    	{}
    };
    
    
    template<class T>
    class HaffmanTree
    {
    public:
    	typedef HaffmanNode<T> Node;
    	HaffmanTree(const T* a, size_t size, const T& invalid)
    	{
    		_root = _CreatHaffmanTree(a, size, invalid);
    	}
    	Node* GetRoot()
    	{
    		return _root;
    	}
    protected:
    	Node* _CreatHaffmanTree(const T* a,size_t size, const T& invalid)
    	{
    		Heap<Node*, Less<Node*>> minHeap;
    		for (size_t i = 0; i < size; ++i)
    		{
    			if (a[i] != invalid)
    			{
    				Node* tmp = new Node(a[i]);
    				minHeap.Push(tmp);
    			}
    		}
    		while (!minHeap.Empty())
    		{
    			Node* left = minHeap.GetTop();
    			minHeap.Pop();
    			Node* right = NULL;
    			if (!minHeap.Empty())
    			{
    				right = minHeap.GetTop();
    				minHeap.Pop();
    			}
    			Node* parent = NULL;
    			if (right)
    			{
    				parent = new Node(left->_wight + right->_wight);
    			}
    			else
    			{
    				parent = new Node(left->_wight);
    			}
    			parent->_left = left;
    			parent->_right = right;
    			if (minHeap.Empty())
    			{
    				return parent;
    			}
    			minHeap.Push(parent);
    		}
    		return NULL;
    	}
    protected:
    	Node* _root;
    };
    
         可以看到树节点的_wight成员,建立哈夫曼树时就是依据_wight大小来建立的,也就是文件中各个字符出现的次数。

         构造哈夫曼树时每次从小顶堆中取出堆顶元素插入到哈夫曼树中,当堆中的元素为空时,构造哈夫曼树完成。


    哈夫曼树构造完成开始文件压缩

    #pragma once
    #define _CRT_SECURE_NO_WARNINGS 1
    #include<iostream>
    #include"HaffmanTree.h"
    using namespace std;
    typedef long LongType;
    
    struct CharInfo
    {
    	unsigned char _ch;
    	LongType _count;
    	string _code;
    	CharInfo(const LongType count = 0 )
    		:_count(count)
    	{}
    	CharInfo(const char ch)
    		:_ch(ch)
    	{}
    	bool operator!=(const CharInfo& c)const
    	{
    		return _count != c._count;
    	}
    	CharInfo operator+(const CharInfo& c)const
    	{
    		return CharInfo(_count + c._count);
    	}
    	bool operator<(const CharInfo& c)const
    	{
    		return _count < c._count;
    	}
    };
    
    class FileComparess
    {
    public:
    	//文件压缩
    	void Comparess(const char* filename)
    	{
    		FILE* fread = fopen(filename, "rb");
    		if (fread == NULL)
    		{
    			cout << "打开待压缩文件失败" << endl;
    			return;
    		}
    		for (int i = 0; i < 256; i++)
    		{
    			_info[i]._ch = i;
    		}
    		unsigned char ch = fgetc(fread); //不能使用char,压缩汉字时的字符出现范围是0~255
    		while (!feof(fread)) //统计各字符出现的次数
    		{
    			//在windows下回车是'\r\n'的组合,遇到‘\r\n’时屏幕上打印换行
    			if (ch == '\r')
    			{
    				ch = fgetc(fread); //跳过‘\r’
    				if (ch != '\n')
    				{
    					fseek(fread, -1, SEEK_CUR);
    				}
    			}
    			_info[ch]._count++;
    			ch = fgetc(fread);
    		}
    		HaffmanTree<CharInfo> h(_info, 256, CharInfo());
    		HaffmanNode<CharInfo>* root = h.GetRoot();
    		string str;
    		GenerateHaffmanCode(root, str);
    		//重新打开待压缩文件读
    		fseek(fread, 0, SEEK_SET);
    		ch = fgetc(fread);
    		unsigned char data = 0;   //要写入压缩文件的数据
    		int bitcount = 7;  //标记移位信息
    		//打开文件写压缩后的编码
    		string write(filename);
    		write = write + ".comparess";
    		FILE* fwrite = fopen(write.c_str(), "wb");
    		while (!feof(fread))
    		{
    			if (ch == '\r')
    			{
    				ch = fgetc(fread);
    				if (ch != '\n')
    				{
    					fseek(fread, -1, SEEK_CUR);
    				}
    			}
    			const char* cur = _info[ch]._code.c_str();
    			while (*cur)
    			{
    				if (bitcount >= 0)
    				{
    					data = data | ((*cur - '0') << bitcount);
    					bitcount--;
    				}
    				if (bitcount < 0)
    				{
    					fputc(data, fwrite);
    					bitcount = 7;
    					data = 0;
    				}
    				cur++;
    			}
    			ch = fgetc(fread);
    		}
    		fputc(data, fwrite);//最后一个字节没写满8位也要把data写入文件(困扰好久)
    		//写配置文件
    		WriteConfig(filename);
    		fclose(fread);
    		fclose(fwrite);
    	}
    
    
    	//文件解压缩
    	void UnComparess(const char* filename)
    	{
    		CharInfo HNarry[256];
    		//读配置文件
    		ReadConfig(filename, HNarry);
    		//重建Haffman树
    		HaffmanTree<CharInfo> h(HNarry, 256, CharInfo());
    		//遍历树,找叶子结点,写输出文件
    		HaffmanNode<CharInfo>* root = h.GetRoot();
    		HaffmanNode<CharInfo>* cur = root;
    		//打开压缩文件读
    		string comf(filename);
    		comf = comf + ".comparess";
    		FILE* fread = fopen(comf.c_str(), "rb");
    		unsigned char ch = fgetc(fread);
    		FILE* fwrite = fopen("output", "wb");
    		int readcount = root->_wight._count;//根节点的_count值就是整棵树字符出现的次数
    		while (readcount)
    		{
    			unsigned int tmp = 1;
    			int bit = 7;   //移动的位数
    			while (bit>=0)
    			{
    				if (ch & (tmp << bit))
    				{
    					cur = cur->_right;
    					bit--;
    				}
    				else
    				{
    					cur = cur->_left;
    					bit--;
    				}
    				//找到叶子结点
    				if (cur->_left == NULL&&cur->_right == NULL)
    				{
    					fputc(cur->_wight._ch, fwrite);
    					cur = root;
    					readcount--;
    					//最后一个字符的编码在最后两个字节当中的情况
    					if (!readcount)
    					{
    						break;
    					}
    				}
    				
    			}
    			ch = fgetc(fread);
    		}
    		fclose(fread);
    		fclose(fwrite);
    	}
    protected:
    	//得到Haffman编码(后序遍历HaffmanTree)
    	void GenerateHaffmanCode(HaffmanNode<CharInfo>* root, string& code)
    	{
    		if (root == NULL)
    			return;
    		GenerateHaffmanCode(root->_left, code + '0');
    		GenerateHaffmanCode(root->_right, code + '1');
    		root->_wight._code = code;
    		if (root->_left == NULL&&root->_right == NULL)
    		{
    			_info[root->_wight._ch]._code = code;
    		}
    
    	}
    	void WriteConfig(const char* filename)
    	{
    		string conf(filename);
    		conf = conf + "config";
    		FILE* fcon = fopen(conf.c_str(), "wb");
    		for (int i = 0; i < 256; ++i)
    		{
    
    			if (_info[i]._count)
    			{
    				fputc(_info[i]._ch, fcon);
    				fputc(',', fcon);
    				char count[100];
    				_itoa(_info[i]._count, count, 10);
    				fputs(count, fcon);
    				fputc(',', fcon);
    				fputs(_info[i]._code.c_str(), fcon);
    				fputc('\n', fcon);
    			}
    		}
    		fclose(fcon);
    	}
    	void ReadConfig(const char* filename, CharInfo* HNarry)
    	{
    		string conf(filename);
    		conf = conf + "config";
    		FILE* fread = fopen(conf.c_str(), "rb");
    		if (fread == NULL)
    		{
    			cout << "打开待压缩文件失败" << endl;
    			return;
    		}
    		char str[100];
    		while (fgets(str, 100, fread))
    		{
    			char* ptr = str;
    			unsigned char index = (unsigned char)*ptr;
    			if (index == '\n') //换行符
    			{
    				HNarry[index]._ch = index;
    				fgets(str, 100, fread);
    				char* ptr = str;
    				ptr++;
    				LongType count = 0;//字符的权值,出现的次数
    				while (*ptr != ',' && *ptr)
    				{
    					count *= 10;
    					count += (*ptr - '0');
    					ptr++;
    				}
    				HNarry[index]._count = count;
    				ptr++;
    				string code(ptr);
    				HNarry[index]._code = code;
    			}
    			else
    			{
    				HNarry[index]._ch = index;
    				ptr += 2;
    				LongType count = 0;//字符的权值,出现的次数
    				while (*ptr != ',' && *ptr)
    				{
    					count *= 10;
    					count += (*ptr - '0');
    					ptr++;
    				}
    				HNarry[index]._count = count;
    				ptr++;
    				string code(ptr);
    				HNarry[index]._code = code;
    			}
    		}
    	}
    protected:
    	CharInfo _info[256];
    };
        文件压缩的思路已在代码中表明。

    注意:

    1. 在文件压缩时最好写配置文件,使用配置文件可以简化压缩程序代码。
    2. 在写配置文件和读配置文件的时候要采用一样的规则,不然会出错。在这个程序中,我是以“  字符,出现次数,哈夫曼编码          ”的格式来写和读的。
    3. 压缩文件时要考虑到所有会出现的情况,比如在压缩完最后一个字符时往压缩文件中写的那个字节不满8位,我们也要把这个字节写进压缩文件.compress。
    4. 在读压缩文件时这里有一个小技巧。重建哈夫曼树后哈夫曼树的root所携带的_count值就是所有字符出现次数的总和。利用这个值可以控制读压缩文件.compress时什么时候结束。有时候最后一个字节(8位)的后几位并不是我们需要的,如果读了会出现许错误。


    以下是此程序压缩与解压缩花费的时间截图:

    debug下:


    release下:



    展开全文
  • 输入一串字符,根据给定的字符串中字符出现的频率建立相应的哈夫曼树,构造哈夫曼编码表,在此基础上可以对压缩文件进行压缩(即编码),同时可以对压缩后的二进制编码文件进行解压(即译码)。 输入要求 多组数据,每组数据1...

    写在前边:这是一个菜鸡的19年秋季学期数据结构实验课,趁寒假整理一下,欢迎各位大佬指正)
    【实验目的】

    1. 掌握哈夫曼树的构造算法。
    2. 掌握哈夫曼编码的构造算法。
      【实验内容】
      问题描述
      输入一串字符,根据给定的字符串中字符出现的频率建立相应的哈夫曼树,构造哈夫曼编码表,在此基础上可以对压缩文件进行压缩(即编码),同时可以对压缩后的二进制编码文件进行解压(即译码)。
      输入要求
      多组数据,每组数据1行,为一个字符串(只考虑26个小写字母即可)。当输入字符串为"0”时,输入结束。
      输出要求
      每组数据输出2n+3行(n为输入串中字符类别的个数)。第1行为统计出来的字符出现频率(只输出存在的字符,格式为字符:频度),每两组字符之间用一个空格分隔,字符按照ASCII码从小到大的顺序排列。第2行至第2n行为哈夫曼树的存储结构的终态(参照实验提示表5.2,一行当中的数据用空格分隔)。第2n+1行为每个字符的哈夫曼编码(只输出存在的字符,格式为字符:编码),每两组字符之间用一个空格分隔,字符按照ASCII码从小到大的顺序排列。第2n+2行为编码后的字符串,第2n+3行为解码后的字符串(与输入的字符串相同)。
      输入样例
      aaaaaaabbbbbccdddd
      aaccb
      0
      输出样例
      a:7 b:5 c2 d:4
      1 7 7 0 0
      2 5 6 0 0
      3 2 5 0 0
      4 4 5 0 0
      5 6 6 3 4
      6 1 1 7 2 5
      7 1 8 0 1 6
      a:0 b:10 c:110 d:111
      00000001010101011011011111
      aaaaaaabbbbbccdddd
      a:2 b:1 c:3
      1 2 4 0 0
      2 1 4 0 0
      3 3 5 0 0
      4 3 5 2 1
      5 6 0 3 4
      a:11 b:10 c:0
      111110000
      aabccc
      【实验提示】
      首先,读入一行字符串,统计每个字符出现的频率;然后,根据字符出现的频率利用提示算法1建立相应的哈夫曼树;最后,根据得到的哈夫曼树利用算法2求出每个字符的哈夫曼编码。
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<string>
    #define MAX 100
    using namespace std;
    
    int coun[26]; //频率 
    char saveletter[26];//存字母 
    char temp[MAX];//暂存被译码串 
    
    typedef struct htnode
    {
        int weight;
        int lchild, rchild, parent;
        char data;
        int frequency;//出现频率 
    }*huftree;
    
    typedef char **hufcode;
    
    void select(huftree &hf, int x, int &s1, int &s2)//在叶子结点里找最小的两个 
    {
        
    int min = 999, cmin = 999;//最小值和次小值 
        int i = 1;
        while (i <= x)
        {
            if (hf[i].parent == 0)
            {
                if (hf[i].weight < min)//寻找权值最小 
                {
                    min = hf[i].weight;
                    s1 = i;
                }
                i++;
            }
            else
                i++;
        }
        int flag = s1;
        i = 1;
        while (i <= x)
        {
            if (hf[i].parent == 0)
            {
                if ((hf[i].weight > min && hf[i].weight < cmin) || (hf[i].weight == min && flag != i))//找次小值 
                {
                    cmin = hf[i].weight;
                    s2 = i;
                }
                i++;
            }
            else
                i++;
        }
    
       
    }
    
    void Create(huftree &hf, int n)//叶子为n的哈树有2n-1个结点 
    {
        int m = 2 * n - 1, s1 = 0, s2 = 0;
    
        if (n <= 1) return;
    
        hf = new htnode[m + 1];//0号单元不用
    
        for (int i = 1; i <= m; i++)//都初始化为0 
        {
            hf[i].parent = 0;
            hf[i].rchild = 0;
            hf[i].lchild = 0;
            hf[i].data = saveletter[i - 1];//字母
        }
    
        for (int i = 1; i <= n; i++)
            hf[i].weight = coun[i - 1];//输入权值 
    
        for (int i = n + 1; i <= m; i++)//前n个为叶子,后面需要构建 
        {
            select(hf, i - 1, s1, s2);//选择最小的两个节点,返回序号 
            hf[s1].parent = i;
            hf[s2].parent = i;//结点双亲变为i
            hf[i].lchild = s1;
            hf[i].rchild = s2;//i的左右孩子
            hf[i].weight = hf[s1].weight + hf[s2].weight;
            //i权值更改 
        }
    
    }
    
    
    void Show(huftree &hf, int x)
    {
        for (int i = 1; i <= 2 * x - 1; i++)
        {
            cout << i << " ";
            cout << hf[i].weight << " " << hf[i].parent << " " << hf[i].lchild << " " << hf[i].rchild << endl;
        }
    }
    
    void count(char str[], huftree &hf, int &n)//出现频率 ,字母个数 
    
    {
        int num[26];
        char ch;
        int i = 0, j = 0;
        memset(num, 0, sizeof(num));
        while (str[i] != '\0')
        {
            j = str[i] - 97;
            num[j]++;
            i++;
        }
        j = 0;
        for (i = 0; i < 26; i++)
        {
            if (num[i] != 0)
            {
                saveletter[j] = char(i + 97);
                coun[j] = num[i];
                j++;
            }
        }
        n = j;
        for (int i = 0; i < n; i++)
        {
            if (i == n - 1)
                cout << saveletter[i] << ":" << coun[i];
            else
                cout << saveletter[i] << ":" << coun[i] << " ";
        }
        cout << endl;
    }
    
    void hfcode(huftree &hf, hufcode &hc, int n)
    {
        char *cd;
        int start = 0, c, f;
        hc = new char*[n + 1];//编码表 
        cd = new char[n];//每个字符的编码一定小于n 
        cd[n - 1] = '\0';
        for (int i = 1; i <= n; i++)
        {
            start = n - 1;
            c = i;
            f = hf[i].parent;
    
            while (f != 0)//不是根节点
            {
                start--;
    
                if (hf[f].lchild == c)
                    cd[start] = '0';
                else
                    cd[start] = '1';
    
                c = f;//向上回溯 
                f = hf[f].parent;
            }
            hc[i] = new char[n - start];
            strcpy(hc[i], &cd[start]);//把临时空间的编码复制到编码表中 
        }
        delete cd;
    
        int i, j, z = 0;
        for (j = 1; j <= n; j++)//输出字母编码 
        {
            if (j == n)
                cout << saveletter[j - 1] << ":" << hc[j];
            else
                cout << saveletter[j - 1] << ":" << hc[j] << " ";
        }
        cout << endl;
    }
    void transtonum(huftree &hf, hufcode &hc, int n, char str[])
    {
        for (int i = 0; str[i] != '\0'; i++)
            for (int j = 1; j <= n; j++)
                if (str[i] == saveletter[j - 1])
                {
                    cout << hc[j];
                    strcat(temp, hc[j]);
                }
    
        cout << endl;
    }
    void transtoletter(huftree &hf, hufcode &hc, int n)
    {
        int i = 2 * n - 1;
        int j = 0;
    
        while (temp[j] != '\0')
        {
            if (temp[j] == '0')
                i = hf[i].lchild;   //左孩子
            else if (temp[j] == '1')
                i = hf[i].rchild;    //右孩子
            if (hf[i].lchild == 0)
            {
                cout << hf[i].data;
                i = 2 * n - 1;
            }
            j++;   //无论是否找到叶子节点都读取下一个编码串字符
        }
        cout << endl;
    }
    
    int main()
    {
    
        while (1)
        {
            huftree hf;
            hufcode hc;
            int n;
            char str[MAX];
            scanf("%s", &str);
            if (str[0] == '0')
                break;
            count(str, hf, n);
            Create(hf, n);
            Show(hf, n);
            hfcode(hf, hc, n);
            transtonum(hf, hc, n, str);
            transtoletter(hf, hc, n);
            memset(coun, 0, sizeof(coun));
            memset(saveletter, '\0', sizeof(saveletter));
            memset(temp, '\0', sizeof(temp));
            delete hf;
            delete hc;
        }
        return 0;
    }
    
    展开全文
  • 一,Huffman的简介 1,定义 给定n个带权值的节点,将这n个节点作为叶子节点构建一棵二叉树,若该的带权路径最小,则称该为最优二叉树,也叫Huffman。 2,生成方法 <1>,在节点中取权值最小的两个节点...

    一,Huffman树的简介

    1,定义
    给定n个带权值的节点,将这n个节点作为叶子节点构建一棵二叉树,若该树的带权路径最小,则称该树为最优二叉树,也叫Huffman树。
    2,生成方法
    <1>,在节点中取权值最小的两个节点为叶节点,生成一棵二叉树,该二叉树的父节点权值为两个叶节点的权值之和。
    <2>,将取出的两个节点删除,加入新生成的父节点,重新回到步骤1,直到只剩下1个节点不能再生成树为止。
    举个例子,现在我们有一下几个节点,它们的权值分别如下所示:

    带权路径长度WPL(weighted path length)的计算公式:
    在这里插入图片描述
    公式中,n为叶子节点树,Wk为第k个叶子结点的权值,Lk为该结点的路径长度。
    生成的Huffman树为:
    在这里插入图片描述
    这里我们规定了权值小的节点为左子节点,实际上最后生成的Huffman树结构不一定只有一种,但他们的带权路径长是相同的。
    3,Huffman树的特点
    <1>一开始给出需要处理的节点都是Huffman树的叶节点。
    <2>Huffman树的带权路径长度是最小的。

    现在我们以这些节点为叶节点随便构建一棵二叉树:

    该树的带权路径长度为:
    在这里插入图片描述

    同样利用这些节点生成Huffman树的带权路径长为:
    在这里插入图片描述

    这里我们可以看到:
    在这里插入图片描述
    这是因为在生成Huffman树的时候,我们让权值大的节点的路径尽可能最短。
    4,编码规则
    生成Huffman树之后,我们可以对每个叶子节点编码,我们规定,左边路径编码为0,右编路径编码为1,则上述Huffman树编码为:
    在这里插入图片描述
    节点e可以用01表示,节点b可以用011表示。
    5,应用
    Huffman树可以用来压缩数据,以上面节点为例,一共有5种不同的节点,采用不同的编码规则传输。
    <1>如果我们用等长编码分别表示这五个节点:
    000 ——> a
    001 ——> b
    010 ——> d
    011 ——> f
    100 ——> e
    那么我们要传送下面这串字符串的话传输的编码为:

    一共传输48位,解码时3位一读就可以还原。
    <2>不等长编码
    在传输电位时为了使传输的位数尽可能小,可以令出现频次多的字符编码长度短,出现频次少的字符编码长度长,如:
    0 ——> d
    1 ——> a
    00 ——> e
    10 ——> b
    111 ——> f
    则传输的编码为:

    传输长度为23位。
    但当我们解码时以前5位11111为例,我们不知道到底时5个a还是1个f和2个a,这是因为有编码字符是另一个编码字符的前缀,导致译码不唯一,因此这种编码方式不可取。
    <3>Huffman编码
    为了使传输的位数尽可能少并且使任何一个编码字符都不是另一个编码字符的前缀,设计出了Huffman编码。
    当我们采用Huffman编码时
    在这里插入图片描述
    传输的编码为:

    一共传输33位,码表如下:
    10 ——> a
    011 ——> b
    11 ——> d
    010 ——> f
    00 ——> e
    所有字母都处在叶子节点上,每个叶子节点都不会经过其他叶子节点,这样不会出现一个字母的编码是另一个字母编码左起子串的情况。

    二,Huffman树的构建

    1,先创建节点类,该类中包含了每一个节点所需要的属性,以及不同情况创建节点时使用的构造方法。

    package com.yzd0425.Huffman;
    
    //节点类
    public class HNode {
    	public String code;//节点的Huffman编码
    	public char data;//节点数据
    	public int count;//节点频次;
    	public HNode left;//节点的左子节点
    	public HNode right;//节点的右子节点
    	
       //构造方法  构建叶节点时使用的方法
    	public HNode(char data,int count) {
    		this.data=data;
    		this.count=count;
    	}
    	
    	//构造方法  构建父节点时使用的方法
    	public HNode(int count,HNode left,HNode right) {
    		this.count=count;
    		this.left=left;
    		this.right=right;
    	}
    
    }
    
    

    2,创建字符数据类,我们使用链表LinkedList来存储字符相关信息,这样方便读取。LinkedList中存储的是统计了频次的字符信息,每一个元素代表了每个字符的信息:字符数据+字符频次。

    public LinkedList<CharData> charList;//用来存放去重字符的队列
    
    package com.yzd0425.Huffman;
    
    //每个独一无二字符的信息:字符c+出现次数num
    public class CharData {
    	public char c;
    	public int num = 1;//初始化为1   只要创建了则最少出现一次
    	
    	//构造方法
    	public CharData(char c) {
    		this.c=c;
    	}
    
    }
    

    3,统计字符串中每个字符出现的频次。依次从传入的字符串str中取出每个字符,如果和字符链表charList中某个字符相同,该字符的频次num+1,没有的话创建一个新的CharData加入到charList中。

    	//统计出现的字符及其频率
    	public LinkedList<CharData> getCharNum(String str,LinkedList<CharData> charList) {
    		for(int i=0;i<str.length();i++) {
    			char c = str.charAt(i);//得到字符串中指定位置的字符
    			flag = false;//默认不重复
    			//取出的字符和存放去重的字符队列中的每一个元素比较   如果都不相同  则时一个新字符   添加进字符队列中
    			for(int j=0;j<charList.size();j++) {
    				CharData cd = charList.get(j);
    				if(c==cd.c) {
    					cd.num++;
    					flag = true;
    					break;
    				}
    			}
    			if(!flag) {//遍历完CharList都没找到 则创建一个新的CharData
    				charList.add(new CharData(c));    //该函数中已对全局参数charList进行了具体赋值   之后的charList可以使用形参
    			}
    		}
    		return charList;
    	}
    

    4,创建节点。将统计完的charList中的元素创建为一个个节点,同样也使用一个链表nodeList来存储创建好的节点,这样在创建Huffman树的时候就可以从nodeList中取出节点创建了。

    public LinkedList<HNode> nodeList;//用来存放节点的队列(已去重)
    
    	//将出现的不重复字符创建为单个节点   因为生成Huffman树是用节点生成
    	public LinkedList<HNode> createNode(LinkedList<CharData> charList,LinkedList<HNode> nodeList) {
    		for(int i=0;i<charList.size();i++) {
    			char data = charList.get(i).c;
    			int count = charList.get(i).num;
    			HNode node = new HNode(data,count);
    			nodeList.add(node);//该函数中已对全局参数nodeList进行了具体赋值   之后的nodeList可以使用形参
    		}
    		return nodeList;
    	}
    

    5,对创建好的节点按频次升序排序。

    	//对去重的nodeList中的节点数据升序排序
    	public LinkedList<HNode> order(LinkedList<HNode> nodeList) {
    		for(int i=0;i<nodeList.size()-1;i++) {
    			for(int j=i+1;j<nodeList.size();j++) {
    				if(nodeList.get(i).count>nodeList.get(j).count) {
    					HNode temNode = nodeList.get(i);
    					nodeList.set(i, nodeList.get(j));
    					nodeList.set(j, temNode);
    				}
    			}
    			
    		}
    		return nodeList;
    	}
    

    6,取出升序排序后的nodeList中的前两个节点,将这两个节点作为左、右两个子节点创建一棵二叉树,父节点的频次为左、右节点频次之和,将取出的两个节点从nodeList中删除,父节点加入nodeList中,重新升序排序,不断重复这一步骤,直到nodeList中只剩下一个节点无法再生成树为止。
    我们在生成二叉树的时候也进行编码操作,设置当前生成的左节点的编码为0,右节点的编码为1,同时从当前左、右节点一直递归到叶节点不断更新其余子树节点的编码值(该更新操作每加入两个节点都要重新执行)。

    	//设置节点的Huffman编码   从当前传入的节点一致递归编码至叶节点
    	//根节点并没有编码     每次子树编码更新是在传入的节点的编码上+0/1   并不是在子树原来的编码上+0/1   这样能保证父节点编码是子节点编码的前子串
    	public void setCode(HNode node) {
    		if(node.left!=null) {
    			node.left.code=node.code+"0";
    			setCode(node.left);
    		}
    		if(node.right!=null) {
    			node.right.code=node.code+"1";
    			setCode(node.right);
    		}
    	}
    	
    	//生成Huffman树
    	public void createTree(LinkedList<HNode> nodeList) {
    		while(nodeList.size()>=2) {//当队列中节点数目>=2时,就仍能构成一棵树
    			//1,取出并删除节点队列中的前两个节点(权值最小)
    			HNode left = nodeList.poll();
    			HNode right = nodeList.poll();
    			//2,设置当前子树的Huffman编码
    			left.code="0";
    			right.code="1";
    			setCode(left);//从当前子树一直递归到叶节点设置编码     不断更新   并不是将Huffman树完全构建后再从根节点开始设置编码
    			setCode(right);
    			//3,生成父节点并加入节点队列中
    			int count  = left.count+right.count;
    			HNode parent  = new HNode(count,left,right);//此时已构成父子连接关系
    			nodeList.add(parent);
    			//4,重新将nodeList中的节点升序排序   这样保证每次处理的1、2、3步骤处理nodeList都是排序好的
    			order(nodeList);//不断递归
    		}
    	}
    

    7,调用以上函数生成一棵Huffman树,使用中序遍历方法仅打印出叶节点的值验证。

    	//生成Huffman树   函数在该函数中调用
    	public void createHuffman(String str) {
    		//this.str=str;
    		charList = new LinkedList<CharData>();
    		nodeList = new LinkedList<HNode>();
    		//1,统计需要处理的字符串中字符出现的个数
    		charList = getCharNum(str,charList);
    		//2,创建节点
    		nodeList = createNode(charList,nodeList);
    		//3,对节点权值升序排序
    		nodeList = order(nodeList);//保证第一次处理的nodeList是有序的
    		//4,生成Huffman树
    		createTree(nodeList);//内部已不断重新排序
    		//5,最后一个生成的父节点赋给根节点 方便找到此树   队列中该节点不能和其他节点和起来再生成树   但有一个相同的节点已经被生成作为树的根节点
    		root = nodeList.get(0);
    	}
    
    	//遍历节点  中序遍历   递归调用   只输出打印叶节点的数据:     字符+频次+Huffman编码
    	public void printNode(HNode node) {
    		if(node.left==null&&node.right==null) {
    			System.out.println("该节点数据为:"+node.data+"  "+"频次为:"+node.count+"  "+"Huffman编码为:"+node.code);
    		}
    		if(node.left!=null) {
    			printNode(node.left);
    		}
    		if(node.right!=null) {
    			printNode(node.right);
    		}
    	}
    
    	//主函数   程序入口
    	public static void main(String[] args) {
    		HuffmanTree huff = new HuffmanTree();
    		String data = "aaabbdddddfeeea";
    		huff.createHuffman(data);//创建树
    		huff.printNode(root);//打印已去重的节点
    
    	}
    

    输出结果如下:
    在这里插入图片描述
    和我们在上文中生成的Huffman树是一致的。

    三,Huffman编码

    利用上述生成的Huffman树,我们对字符串"aaabbdddddfeeea"进行编码。
    1,从字符串str的第一个字符开始,每个字符c都从根节点开始搜索,搜索Huffman树的所有叶子节点。
    2,当找到某个叶子节点的值data和字符c一致时,便使用该节点的code作为该字符的Huffman码。
    3,每个字符的Huffman码都添加到之前已完成搜索的HcodeStr之后,这样就能得到整个字符串str的Huffman编码了。

        public static String HcodeStr="";//字符串编码后的Huffman编码
    	/***********************以下是编码的实现*************************/
    	//得到字符串Huffman编码  每次调用都在上一个Huffman编码的基础上累加
    	public void search(HNode node,char c) {
    		//找到叶节点
    		if(node.left==null&&node.right==null) {
    			if(node.data==c) {
    				HcodeStr += node.code;
    				//System.out.println("找到了");
    			}
    		}
    		if(node.left!=null) {
    			search(node.left,c);
    		}
    
    		if(node.right!=null) {
    			search(node.right,c);
    		}
    	}
    	
    	//得到Huffman编码    每个字符搜索一次     每次Huffman编码累加     得到字符串完整的Huffman编码
    	public String getHcode(String str) {
    		for(int i=0;i<str.length();i++) {
    			char c = str.charAt(i);
    			search(root,c);
    		}
    		return HcodeStr;
    	}
    	
    	//将得到的Huffman编码打印出来
    	public void printHcode(String Hcodestr) {
    		System.out.println("该字符串的Huffman编码为:"+Hcodestr);
    	}
    
    	HcodeStr = huff.getHcode(data);//编码
    	huff.printHcode(HcodeStr);
    

    输出如下:
    在这里插入图片描述

    四,Huffman解码

    我们对上述得到的Huffman码HcodeStr"101010011011111111111101000000010"进行解码。
    1,因为每个字符的Huffman编码长度不一,每个字符对应的Huffman编码是整个HcodeStr的子串,所以我们定义每次查找的子串起始位start和终止位end,使用函数HcodeStr.substring()得到得到codeString的 start : end-1 位子编码串。
    2,用result保存解码后的字符串,设置一个标识符target判断是否找到匹配字符,每次查找前默认为没找到false。
    3,从HcodeStr的第一位开始查找,得到一个子编码串str,从Huffman树的根节点开始遍历所有叶子节点,这里有两种情况:
    (a)如果有叶节点字符的Huffman编码与str一致,则认为找到了,将target置为true,该节点的字符data存入result中,设置下一次查找的起始位start为该次查找的end位,同时end位向后移一位end++。
    (b)如果没有叶节点的Huffman编码与str一致,该次查找未找到,target保持默认值false,将查找的子编码串添加一位end++,起始位star仍然不变,继续查找,直到满足情况(a)。
    4,重复(a)(b)两步,不断将每次查找到的data加在result后,直到遍历完codeString的所有字符。

    	public static String result="";//Huffman解码后的字符串
    	public boolean target;//判断某字符串是否解码成功的标志    成功为true   不成功为false
    
    	/***********************以下是解码的实现*************************/
    	//匹配Huffman编码   找到编码对应的字符   递归调用   遍历所有叶子节点
    	public void matchCode(HNode node,String code) {
    		if(node.left==null&&node.right==null) {//在叶节点中寻找
    			if(code.equals(node.code)) {//编码对应的字符找到
    				target = true;
    				result+=node.data;
    				return;//一找到即返回退出函数    不在找其他叶节点
    			}
    		}
    		if(node.left!=null) {
    			matchCode(node.left,code);
    		}
    		if(node.right!=null) {
    			matchCode(node.right,code);
    		}		
    	}
    	
    	//解码函数   
    	public String code2string(String HcodeStr) {
    		int start = 0;//从Huffman编码的第一个数字开始查找
    		int end = 1;
    		while(end<=HcodeStr.length()) {//查找到Huffman编码的最后一位
    			target = false;//每次查找前默认为没找到对应字符
    			String str = HcodeStr.substring(start,end);//得到codeString的   start : end-1    位子字符串
    			matchCode(root,str);//每次都从根节点开始查询  可以遍历所有叶子节点    查找该编码是否有对应的字符  遍历完结果可能有也可能没有			
    			if(target) {
    				start = end;//如果找到了就从找到Huffman编码的下一位开始重新查找  如果没找到start保持原位
    			}
    			end++;//无论找没找到 每重新执行一次查找时  都将查找编码的最后一位向后移一位
    		}
    		return result;
    	}
    	
    	//打印Huffman解码后的字符串
    	public void printString(String result) {
    		System.out.println("Huffman解码后的字符串为:"+result);
    	}
    
    	result = huff.code2string(HcodeStr);//解码
    	huff.printString(result);
    

    输出如下:
    在这里插入图片描述
    Huffman树构建、编码、解码完整代码:
    百度网盘提取码:polp

    展开全文
  • (3) 依次读取原始文件的每个字节,查找其对应的哈弗曼编码,将这些位写入到压缩文件中(注意:要凑够8位二进制才写入到文件中)。 (4) 将原始文件中各字节及出现的次数也写入到压缩文件中。 2、解压 (1) 从...
  • 文件压缩哈夫曼树

    千次阅读 2018-08-02 22:11:07
    哈夫曼树又称为最优二叉树,是加权路径长度最短的二叉树。 构建规则:每次在给定数据中挑选出两个权值最小的数,分别作为左右孩子节点,构建一个父节点将两个孩子节点链接起来,父节点权值等于左右孩子权值之和,...
  • C语言利用哈夫曼树压缩文本文件

    千次阅读 2020-04-13 17:12:04
    利用最优二叉树(也称哈夫曼树)可以对文本进行编码, 从而实现压缩
  • 一、哈夫曼树 具有n个权值的n个叶子结点,构造出一个二叉树,使得该树的带权路径长度(WPL)最小,则称此二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。 注意:哈夫曼树是带权路径长度最短的树,且权值越...
  • 功能要求 1. 针对一幅BMP格式的图片文件,统计...2. 利用上述哈夫曼树产生的哈夫曼编码对图片文件进行压缩。 3. 压缩后的文件与原图片文件同名,加上后缀.huf(保留原后缀),如pic.bmp 压缩后pic.bmp.huf 4. 解压缩
  • 哈夫曼树
  • 利用已建好的哈夫曼树(如不在内存,则从文件hfmTree中读入),对文件ToBeTran中的正文进行编码,然后将结果存入文件CodeFile中。 (3) D:译码(Decoding)。利用已建好的哈夫曼树文件CodeFile中的代码进行译码,...
  • 利用哈夫曼树实现文件压缩

    千次阅读 多人点赞 2017-02-27 10:51:49
    2.根据字符出现的次数构建哈夫曼树(得出字符的哈夫曼编码)。 3.根据字符的哈夫曼编码进行转换、压缩,然后创建压缩文件。 4.读取压缩文件,读出哈夫曼编码和字符的对照表。解压缩。 数据结构的设计: 1.保存字符...
  • 实现文件压缩与解压并计算压缩率 A.描述压缩基本符号的选择方法 B.运行时压缩文件的规模应不小于5K C.提供恢复文件与原文件相同性对比功能
  • 输入一串字符串,根据给定的字符串中字符出现的频率建立相应哈夫曼树,构造哈夫曼编码表,在此基础上可以对待压缩文件进行压缩(即编码),同时可以对压缩后的二进制编码文件进行解压(即译码)。 输入 多组数据,每...
  • C++数据结构之文件压缩(哈夫曼树)实例详解概要:项目简介:利用哈夫曼编码的方式对文件进行压缩,并且对压缩文件可以解压开发环境:windows vs2013项目概述:1.压缩a.读取文件,将每个字符,该字符出现的次数和权值...
  • 构造自适应霍夫曼实现文件压缩与解压缩。-Adaptive Huffman tree structure for file compression and decompression. 文件列表(点击判断是否您需要的文件,如果是垃圾请在下面评价投诉): Encoder\Huffman.h...
  • Java小程序之哈夫曼树与文件压缩和解压缩(二)文件解压篇 一、解压原理: 了解了压缩原理之后,要解压文件就是压缩文件的逆过程;拿昨天的例子来说,如果我们收到这样一串二进制1 1 01 1 1 01 00(昨天漏掉了...
  • 草稿版代码 内容超详细 可压缩任何文件类型 亲测可用 100%还原
  • 利用哈夫曼树进行文件压缩

    千次阅读 2016-07-25 00:43:07
    项目简介:利用哈夫曼编码的方式对文件进行压缩,并且对压缩文件可以解压 开发环境:windows vs2013 项目概述:  1.压缩  a.读取文件,将每个字符,该字符出现的次数和权值构成哈夫曼树  b.哈夫曼树是利用小堆...
  • 哈夫曼树是带权路径最短的树,权值加大的节点离根节点较近. 示例代码如下: public class HuffmanTreeCode { public static void main(String[] args) { HuffmanTreeDemo huffmanTree = new HuffmanTreeDemo(); // ...
  • 1.哈夫曼树 哈夫曼树又称最优树(二叉树),是一类带权路径最短的树。构造这种树的算法最早是由哈夫曼(Huffman)1952年提出,这种树在信息检索中很有用。 结点之间的路径长度:从一个结点到另一个结点之间的分支...
  • 哈夫曼树应用——文件压缩

    千次阅读 2017-04-16 22:57:39
    1.哈夫曼树的简介: 哈夫曼树(Huffman tree),又名最优树,指给定n个权值作为n的叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman tree)。哈夫曼树是带权...
  • 哈夫曼树、哈弗曼编码:压缩,解压文本文件 由文本文件生成哈夫曼编码,即:压缩 *思路、步骤 性能分析 代码 *需注意的的问题 *不足与优化 译码,即:解压 *思路步骤 *代码 *需注意的问题 由文本文件生成...
  • 通过调用库中的优先级队列实现哈夫曼树,基于哈夫曼树最终实现文件压缩。 ## 实现哈夫曼树(利用优先级队列) ## #define _CRT_SECURE_NO_WARNINGS 1 #pragma once #include&amp;amp;lt;iostream&amp;amp...
  • 哈夫曼树压缩和解压缩

    千次阅读 2019-01-17 20:53:12
    不知不觉放寒假了,时间很快,我大概是从去年的九月多开始学了java,到现在也差不多有四个月了,java基础呢也就写了几个小的管理系统,总感觉缺少点什么,当时是报着玩的心态,...今天的主题是哈夫曼树的编码,译码...

空空如也

空空如也

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

哈夫曼树压缩文件算法

友情链接: Fastn-Queens.rar