huffman_g.cpp

huffman编码的c++实现源码

#include "huffman_g.h"

/*
A. Moffat和J. Katajainen设计的使用最少内存空间计算最小冗余编码（Huffman编码）
的算法源代码。在元素权值已从小到大排序的前提下，此算法通过对数组进行3次
遍历，不使用额外数组空间，即可得到所有元素的Huffman码长（bit length）。
经此函数计算码长后，利用Canonical Huffman编码方法，可以得到所有元素的编码。
参数
	A	包含各元素的权值的数组，调用前，应将数组A中的权值按从小到大排序
	n	数组A中元素的个数
*/
void huffman_g::calculate_minimum_redundancy(unsigned long A[], int n) 
{
	int root; /* 在第1次遍历中是当前子树的根结点，在第3次遍历中是当前深度中的分支结点 */
	int leaf; /* 只用于第1次遍历，是下一个要考察的叶子结点 */
	int next; /* 在第1次遍历中，是下一个合并用的结点（子树），该位置将存储该子树
					的两个分支合并后的权值总和；
					在第2次遍历中，是简单循环变量；
					在第3次遍历中，是将要填入码长值的元素位置 */
	int avbl; /* 用于第3次遍历，是当前深度中可用结点数量。
					最初等于该层结点总数，由上一层分支结点总数乘2得来。
					然后逐一排除分支结点，剩下的就是该层叶子结点总数 */
	int used; /* 用于第3次遍历，是当前深度中分支结点总数 */
	int dpth; /* 用于第3次遍历，当前深度，如果当前层有叶子结点，即为该叶子结点的码长 */

	/* 边界条件检查	*/
	if (n==0) {	return;	}
	if (n==1) {	A[0] = 0; return; }

	/* 
		第1次遍历，从左至右。
		第1次遍历的结果是，A[0]..A[n-3]对应于所有分支结点（不包含根结点），其中的数值为该
		分支结点的双亲结点索引；A[n-2]对应于根结点，其中的数值是所有权值的总和。所有分支
		结点的排列顺序：从左到右是二叉树中从下向上的顺序（假定树根在上），深度相同的分支
		结点排列在一起。
		参考：在Huffman树中，所有分支结点都有左、右两个子树，这样的二叉树中，当叶子结点数
		量为n时，分支结点（含根结点）数量为n-1
	*/

	/*
		首先将最小的两个元素（叶子结点）合并为子树，其权值之和存入A[0]中。这时，当前子树
		根为数组中第0个元素，因此root=0，下一个要考察的叶子结点是第3个元素，因此leaf=2
	*/
	A[0] +=	A[1]; root = 0;	leaf = 2;

	/* 从1到n-1循环，生成所有分支结点，并将它们连成完整的二叉树	*/
	for	(next=1; next <	n-1; next++) {
		/* 在root所指的当前子树和leaf所指的叶子结点中选一个最小的，作为下一个子树的一个分支	*/
		if (leaf>=n	|| A[root]<A[leaf])	{
			/* 如果root所指的当前子树比leaf所指的叶子结点小
				则将root所指的当前子树作为下一个子树的第一个分支
				其值（当前子树的权值总和）存入next所指的下一子树的根结点中
				然后令root所指的当前子树的双亲结点等于next
				同时root加1，考察下一个子树 */
			/* 如果已考察完所有叶子结点，而next还小于n-1，则表明现有的子树还没有完全连入
				1棵完整的Huffman树（这相当于没有深度为n-1-next的叶子结点），这时也需要执
				行同样的操作，以便将现有子树连在一起	*/
			A[next]	= A[root]; A[root++] = next;
		} else
			/* 如果root所指的当前子树大于等于leaf所指的叶子结点
				则将leaf所指的叶子结点作为下一个子树的第一个分支
				其值（当前子树的权值总和）存入next所指的下一子树的根结点中
				leaf加1，继续考察下一个叶子结点 */
			A[next]	= A[leaf++];

		/* 在root所指的当前子树和leaf所指的叶子结点中选一个最小的，作为下一个子树的另一个分支 */
		if (leaf>=n	|| (root<next && A[root]<A[leaf])) {
			A[next]	+= A[root];	A[root++] =	next;
		} else
			A[next]	+= A[leaf++];
	}
	
	/* 
		第2次遍历，从右至左，设置所有分支结点的深度。
		第2次遍历的结果是，A[n-2]..A[0]顺序保存了从根结点到最底层的所有分支结点的深度信息。
	*/

	/* 将根结点的深度设置为0 */
	A[n-2] = 0;
	for	(next=n-3; next>=0;	next--)
		/* 将每个分支结点的深度设置为其双亲结点深度加1 */ 
		A[next]	= A[A[next]]+1;

	/* 
		第3次遍历，从右至左，设置所有叶子结点的深度（码长） 
		第3次遍历的结果是，A[0]..A[n-1]顺序保存了每个元素的码长（即元素在二叉树中的深度）
	*/
	/* 
		从根出发，因此root为n-2，当前深度dpth为0；
		used用于统计当前深度中分支结点数目，其初始值为0；
		avbl为根据上一层分支结点算出的当前层结点数目，因初始时是根结点，所有结点数目为1；
		next指向下一个要设置的元素位置，从最后一个元素开始；
		说明：从右向左看，传入此函数的元素权值最初是从大到小排列的，其深度值或码长必然是
		从小到大排列的，而第2次遍历后得到的分支结点深度是从0逐渐增大的，因此，只要从根开
		始，知道每一层叶子结点数目，在数组中填相应数目的当前深度值就可以了。
	*/
	avbl = 1; used = dpth =	0; root	= n-2; next	= n-1;

	while (avbl>0) {
		/* 对当前层的所有分支结点循环 */
		while (root>=0 && A[root]==(unsigned int)dpth) { 
			/* 分支结点计数used加1 */
			used++;	root--;
		}
		/* 这时，avbl和used的差值就是当前层的叶子结点数目 */
		/* 对当前层所有叶子结点循环 */ 
		while (avbl>used) { 
			/* 从右至左设置元素的深度值（码长） */
			A[next--] =	dpth; avbl--;
		}
		/* 下一层的结点总数等于当前层分支结点乘2；深度值加1；used清0 */
		avbl = 2*used; dpth++; used	= 0;
	}
}

void huffman_g::generate_codes(int num, const unsigned long* weights)
{
	if (num <= 1 || weights == NULL)
		throw new huffman_exception("参数非法");

	unsigned long* A = new unsigned long[num];	
	memcpy(A, weights, num * sizeof(unsigned long));

	// 只计算权值非0的元素（因为传入的数据已从小到大排序，只简单忽略前面的0即可）
	int i = 0;
	while (A[i] == 0) i++;
	calculate_minimum_redundancy(A + i, num - i);

	code_lens.clear();
	for (int i = 0; i < num; i++)
		code_lens.push_back(A[i]);
	generate_canonical_codes();
	
	delete[] A;
}