4.4--贪心--Huffman编码（哈夫曼编码）_贪心算法哈夫曼编码

Huffman编码的贪心算法体现在--总是合并最小频率的字符

哈夫曼编码简介

哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%～90%之间。

哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。 

给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长。

1、前缀码：对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其它字符代码的前缀。这种编码称为前缀码。编码的前缀性质可以使译码方法非常简单。表示最优前缀码的二叉树总是一棵完全二叉树，即树中任一结点都有2个儿子结点。树叶代表给定的字符，每一个字符的前缀码可以看做是从树根到代表该字符树叶的一条路，每一位0或者1分别作为指示的“路标”。

举个例子

 定长编码不是最优的，最优前缀码总是一颗满二叉树，给定编码字符集C中任意字符c以频率f(c)出现在数据文件中，d(c)是字符c的前缀码长，也就是说字符c在树T中的深度记为d(c)，那么这个编码方案的平均码长是 sum( f(c) * d(c) )其中c是属于字符集C的一个字符。

2、构造哈夫曼编码 ：哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。         

1）哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。         

2）算法以|C|个叶结点开始，执行|C|－1次的“合并”运算后产生最终所要求的树T。

3）假设编码字符集中每一字符c的频率是f(c)。以f为键值的优先队列Q用在贪心选择时有效地确定算法当前要合并的2棵具有最小频率的树。一旦2棵具有最小频率的树合并后，产生一棵新的树，其频率为合并的2棵树的频率之和，并将新树插入优先队列Q。经过n－1次的合并后，优先队列中只剩下一棵树，即所要求的树T。

构造过程如下图所示

算法描述

 Huffman算法首先用字符集C中每个字符c，频率为f(c)，初始化优先队列Q。

然后不断地从优先队列Q中取出具有最小频率的两棵树x和y，将它们合并为一棵树z，z=x+y

新树z，左儿子是x，右儿子是y。经过n-1次的合并后，优先队列中只剩下一棵树，就是要求的最优Huffman编码树

时间分析

贪心选择性质

证明可以对T作适当修改后得到一棵新的二叉树T”，在T”中x和y是最深叶子且为兄弟，同时T”表示的前缀码也是C的最优前缀码。

设b和c是二叉树T的最深叶子，且为兄弟。

设f(b)<=f(c)，f(x)<=f(y)。由于x和y是C中具有最小频率的两个字符，有f(x)<=f(b)，f(y)<=f(c)。

首先，在树T中交换叶子b和x的位置得到T'，然后再树T'中交换叶子c和y的位置，得到树T''。

 类似的，可以证明在T'中交换y与c的位置也不断增加平均码长，即B(T')-B(T'')也是非负。

由此可知，B(T'')<=B(T') <=B(T)

因此，T''表示的前缀码也是最优前缀码，且x,y具有相同的码长，同时，仅最优一位编码不同。

最优子结构性质

 代码：

main.cpp

//4d4 贪心算法 哈夫曼算法
//#include "stdafx.h"
#include "BinaryTree.h"
#include "MinHeap.h"
#include <iostream> 
using namespace std; 
 
const int N = 6;
 
template<class Type> class Huffman;
 
template<class Type> 
BinaryTree<int> HuffmanTree(Type f[],int n);
 
template<class Type> 
class Huffman
{
	friend BinaryTree<int> HuffmanTree(Type[],int n);
	public:
		operator Type() const 
		{
			return weight;
		}
	//private:
		BinaryTree<int> tree;
		Type weight;
};
 
int main()
{
	char c[] = {'0','a','b','c','d','e','f'};
	int f[] = {0,45,13,12,16,9,5};//下标从1开始
	BinaryTree<int> t = HuffmanTree(f,N);
 
	cout<<"各字符出现的对应频率分别为："<<endl;
	for(int i=1; i<=N; i++)
	{
		cout<<c[i]<<":"<<f[i]<<" ";
	}
	cout<<endl;
 
	cout<<"生成二叉树的前序遍历结果为："<<endl;
	t.Pre_Order();
	cout<<endl;
 
	cout<<"生成二叉树的中序遍历结果为："<<endl;
	t.In_Order();
	cout<<endl;
 
	t.DestroyTree();
	return 0;
}
 
template<class Type>
BinaryTree<int> HuffmanTree(Type f[],int n)
{
	//生成单节点树
	Huffman<Type> *w = new Huffman<Type>[n+1];
	BinaryTree<int> z,zero;
 
	for(int i=1; i<=n; i++)
	{
		z.MakeTree(i,zero,zero);
		w[i].weight = f[i];
		w[i].tree = z;
	}
 
	//建优先队列
	MinHeap<Huffman<Type>> Q(n);
	for(int i=1; i<=n; i++) Q.Insert(w[i]);
 
	//反复合并最小频率树
	Huffman<Type> x,y;
	for(int i=1; i<n; i++)
	{
		x = Q.RemoveMin();
		y = Q.RemoveMin();
		z.MakeTree(0,x.tree,y.tree);
		x.weight += y.weight;
		x.tree = z;
		Q.Insert(x);
	}
 
	x = Q.RemoveMin();
 
	delete[] w;
 
	return x.tree;
}

MinHeap.h 最小堆实现

#include<iostream>
using namespace std;
template<class T>
class MinHeap
{
	private:
		T *heap; //元素数组，0号位置也储存元素
		int CurrentSize; //目前元素个数
		int MaxSize; //可容纳的最多元素个数
 
		void FilterDown(const int start,const int end); //自上往下调整，使关键字小的节点在上
		void FilterUp(int start); //自下往上调整
 
	public:
		MinHeap(int n=1000);
		~MinHeap();
		bool Insert(const T &x); //插入元素
 
		T RemoveMin(); //删除最小元素
		T GetMin(); //取最小元素
 
		bool IsEmpty() const;
		bool IsFull() const;
		void Clear();
};
 
template<class T>
MinHeap<T>::MinHeap(int n)
{
	MaxSize=n;
	heap=new T[MaxSize];
	CurrentSize=0;
}
 
template<class T>
MinHeap<T>::~MinHeap()
{
	delete []heap;
}
 
template<class T>
void MinHeap<T>::FilterUp(int start) //自下往上调整
{
	int j=start,i=(j-1)/2; //i指向j的双亲节点
	T temp=heap[j];
 
	while(j>0)
	{
		if(heap[i]<=temp)
			break;
		else
		{
			heap[j]=heap[i];
			j=i;
			i=(i-1)/2;
		}
	}
	heap[j]=temp;
}
 
template<class T>
void MinHeap<T>::FilterDown(const int start,const int end) //自上往下调整，使关键字小的节点在上
{
	int i=start,j=2*i+1;
	T temp=heap[i];
	while(j<=end)
	{
		if( (j<end) && (heap[j]>heap[j+1]) )
			j++;
		if(temp<=heap[j])
			break;
		else
		{
			heap[i]=heap[j];
			i=j;
			j=2*j+1;
		}
	}
	heap[i]=temp;
}
 
template<class T>
bool MinHeap<T>::Insert(const T &x)
{
	if(CurrentSize==MaxSize)
		return false;
 
	heap[CurrentSize]=x;
	FilterUp(CurrentSize);
 
	CurrentSize++;
	return true;
}
 
template<class T>
T MinHeap<T>::RemoveMin( )
{
	T x=heap[0];
	heap[0]=heap[CurrentSize-1];
 
	CurrentSize--;
	FilterDown(0,CurrentSize-1); //调整新的根节点
 
	return x;
}
 
template<class T>
T MinHeap<T>::GetMin()
{
	return heap[0];
}
 
template<class T>
bool MinHeap<T>::IsEmpty() const
{
	return CurrentSize==0;
}
 
template<class T>
bool MinHeap<T>::IsFull() const
{
	return CurrentSize==MaxSize;
}
 
template<class T>
void MinHeap<T>::Clear()
{
	CurrentSize=0;
}

BinaryTree.h 二叉树实现

#include<iostream>
using namespace std;
 
template<class T>
struct BTNode
{
	T data;
	BTNode<T> *lChild,*rChild;
 
	BTNode()
	{
		lChild=rChild=NULL;
	}
 
	BTNode(const T &val,BTNode<T> *Childl=NULL,BTNode<T> *Childr=NULL)
	{
		data=val;
		lChild=Childl;
		rChild=Childr;
	}
 
	BTNode<T>* CopyTree()
	{
		BTNode<T> *nl,*nr,*nn;
 
		if(&data==NULL)
		return NULL;
 
		nl=lChild->CopyTree();
		nr=rChild->CopyTree();
 
		nn=new BTNode<T>(data,nl,nr);
		return nn;
	}
};
 
 
template<class T>
class BinaryTree
{
	public:
		BTNode<T> *root;
		BinaryTree();
		~BinaryTree();
 
		void Pre_Order();
		void In_Order();
		void Post_Order();
 
		int TreeHeight()const;
		int TreeNodeCount()const;
 
		void DestroyTree();
		void MakeTree(T pData,BinaryTree<T> leftTree,BinaryTree<T> rightTree);
		void Change(BTNode<T> *r);
 
	private:
		void Destroy(BTNode<T> *&r);
		void PreOrder(BTNode<T> *r);
		void InOrder(BTNode<T> *r);
		void PostOrder(BTNode<T> *r);
 
		int Height(const BTNode<T> *r)const;
		int NodeCount(const BTNode<T> *r)const;
};
 
template<class T>
BinaryTree<T>::BinaryTree()
{
	root=NULL;
}
 
template<class T>
BinaryTree<T>::~BinaryTree()
{
	
}
 
template<class T>
void BinaryTree<T>::Pre_Order()
{
	PreOrder(root);
}
 
template<class T>
void BinaryTree<T>::In_Order()
{
	InOrder(root);
}
 
template<class T>
void BinaryTree<T>::Post_Order()
{
	PostOrder(root);
}
 
template<class T>
int BinaryTree<T>::TreeHeight()const
{
	return Height(root);
}
 
template<class T>
int BinaryTree<T>::TreeNodeCount()const
{
	return NodeCount(root);
}
 
template<class T>
void BinaryTree<T>::DestroyTree()
{
	Destroy(root);
}
 
template<class T>
void BinaryTree<T>::PreOrder(BTNode<T> *r)
{
	if(r!=NULL)
	{
		cout<<r->data<<' ';
		PreOrder(r->lChild);
		PreOrder(r->rChild);
	}
}
 
template<class T>
void BinaryTree<T>::InOrder(BTNode<T> *r)
{
	if(r!=NULL)
	{
		InOrder(r->lChild);
		cout<<r->data<<' ';
		InOrder(r->rChild);
	}
}
 
template<class T>
void BinaryTree<T>::PostOrder(BTNode<T> *r)
{
	if(r!=NULL)
	{
		PostOrder(r->lChild);
		PostOrder(r->rChild);
		cout<<r->data<<' ';
	}
}
 
template<class T>
int BinaryTree<T>::NodeCount(const BTNode<T> *r)const
{
	if(r==NULL)
		return 0;
	else
		return 1+NodeCount(r->lChild)+NodeCount(r->rChild);
}
 
template<class T>
int BinaryTree<T>::Height(const BTNode<T> *r)const
{
	if(r==NULL)
		return 0;
	else
	{
		int lh,rh;
		lh=Height(r->lChild);
		rh=Height(r->rChild);
		return 1+(lh>rh?lh:rh);
	}
}
 
template<class T>
void BinaryTree<T>::Destroy(BTNode<T> *&r)
{
	if(r!=NULL)
	{
		Destroy(r->lChild);
		Destroy(r->rChild);
		delete r;
		r=NULL;
	}
}
 
template<class T>
void BinaryTree<T>::Change(BTNode<T> *r)//将二叉树bt所有结点的左右子树交换
{
	BTNode<T> *p;
	if(r){ 
		p=r->lChild;
		r->lChild=r->rChild;
		r->rChild=p; //左右子女交换
		Change(r->lChild);  //交换左子树上所有结点的左右子树
		Change(r->rChild);  //交换右子树上所有结点的左右子树
	}
}
 
template<class T>
void BinaryTree<T>::MakeTree(T pData,BinaryTree<T> leftTree,BinaryTree<T> rightTree)
{
	root = new BTNode<T>();
	root->data = pData;
	root->lChild = leftTree.root;
	root->rChild = rightTree.root;
}