哈夫曼编码.cpp

算法分析中的贪心算法的实现

/*
前缀码
我们对每个字符规定一个0，1串作为其代码，并要求任一字符的代码都不是其它
字符代码的前缀。我们称这样的编码具有前缀性质。
*/
/*
一般情况下，若C是编码字符集，则表示其最优前缀的二叉树中恰有|C|个叶子。每个叶子
对应于字符集中一个字符，且该二叉树恰有|C|-1个内部结点。
给定编码字符集C及其频率分布f,即C中任一字符c以频率f(c)在数据文件中出现。
C的一个前缀编码方案对应于一棵二叉树T。字符c在树T中的深度记为dT(c)。dT(c)也是
字符c的前缀码长。
该编码方案的平均码长定义为：
B(T) = f(c)dT(c)总和{c属于C}
*/

/*
构造哈夫曼编码：
哈夫曼编码提出了一种构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼算法。
哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。算法以|C|个叶结点开始，执行
|C|-1次的“合并”运算后产生最终所要求的树T。
下面所给出的算法HuffmanTree中，编码字符集中每一个字符c的频率f(c)。
以f为键值的优先队列Q用以在作贪心选择时有效地确定算法当前
要合并的两棵具有最小频率的树。一旦两棵具有最小频率的树合并后，产生一棵新的树，
其频率为合并的两棵树的频率之和，并将新树插入到优先队列中。
*/
/*
算法用到的类Huffman定义如下：
*/
template< class Type >
class Huffman
{
	friend BinaryTree<int> HuffmanTree( Type[], int );
	public:
		operator Type() const
		{
			return weight;
		}
	private:
		BinaryTree<int> tree;
		Type weight;
};

/*
算法HuffmanTree描述如下：
*/
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 )
	{
		x.MakeTree( i, zero, zero );
		w[i].weight = f[i];
		w[i].tree = z;
	}

	//建优先队列
	MinHeap< Huffman< Type > > Q(1);
	Q.Initialize( w, n, n );
	//反复合并最小频率树
	Huffman< Type > x, y;
	for( int i = 1; i < n; ++i )
	{
		Q.DeleteMin( x );
		Q.DeleteMin( y );
		z.MakeTree( 0, x.tree, y.tree );
		x.weight += y.weight;
		x.tree = z;
		Q.Insert( x );
	}

	Q.DeleteMin( x );
	Q.Deactivate();
	delete []w;
	return x.tree;
}
/*
算法HuffmanTree用最小堆来实现优先队列Q。初始化优先队列需要O(n)计算时间，
由于DeleteMin和Insert只需要O(nlogn)时间，n-1次总时间需要O(nlogn)计算时间。
因此，关于n个字符的哈夫曼算法的计算时间为O(nlogn)。
*/

/*
哈夫曼算法的正确性：
*/

（1）贪心选择性质
设C是编码字符集，C中字符c的频率为f(c)。又设x和y是C中具有最小频率的两个字符，
则存在C的一个最优前缀编码使x和y具有相同码长且仅最后一位编码不同。
证明：