huffman_h.cpp

huffman编码的c++实现源码

#include "huffman_h.h"

#include <math.h>

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

	int heap_num, i, nonzero_count;

	// 分配生成Huffman树时使用的堆结构,其大小是元素数目的2倍
	unsigned long* heap = new unsigned long[2*num];
	if (heap == NULL) throw new huffman_exception("内存不足");
	
	// 将所有元素权值值(叶子结点)复制到堆的后半部分,堆的前半部分置0
	memcpy(heap + num, weights, sizeof(unsigned long)*num);
	memset((char *)heap, 0, num * sizeof (*heap));

	// 将堆的前半部分视作指针,按顺序指向后半部分的叶子结点
	// 同时统计权值非0的叶子结点数目
	for (nonzero_count = i = 0; i < num; i++)
		if (heap[num + i])
			heap[nonzero_count++] = num + i;

	if (pow(2.0, (double)max_code_len) < (double)nonzero_count)
		throw new huffman_exception("元素个数超出了预设的最大码长限制");

	/* 将堆的前半部分视作指针,按照指针所指的权值大小,把堆的前半部分组织成为
	   堆排序(Heap Sort)算法中定义的"堆",即:堆对应一棵完全二叉树，且所有非叶
	   结点的值均不大于其子女的值，根结点的值是最小的.在这里,根结点是heap[0]
	   参见数据结构或算法书籍中的堆排序(Heap Sort)算法介绍 */
	heap_num = nonzero_count;
	for (i = heap_num / 2; i > 0; i--)
	{
		register int curr, child;
		curr = i;
		child = curr * 2;
		while (child <= heap_num)
		{
			if (child < heap_num && heap[heap[child]] < heap[heap[child - 1]])
				child++;
			if (heap[heap[curr - 1]] > heap[heap[child - 1]])
			{
				register unsigned long temp;
				temp = heap[child - 1];
				heap[child - 1] = heap[curr - 1];
				heap[curr - 1] = temp;
				curr = child;
				child = 2 * curr;
			}
			else
				break;
		}
	}	

	/* 创建Huffman树
	   这里,创建Huffman树的过程利用了堆排序(Heap Sort)算法的基本原理,即根结点是
	   最小的元素,树中最后一个元素是最大的元素.选出根结点后,把最后的元素调到根
	   结点,从树根到树叶,让最后的元素移动到合适的位置,重新建成堆.这样,总是可以
	   找出2个最小的子树,将这两个子树合并后,再作为新元素放到堆中.所有子树都合并
	   后,Huffman树就建成了.(参见数据结构或算法书籍中的堆排序算法介绍) 
	   这一段代码的运行结果是整个heap数组成了一棵Huffman树,heap[0]未用,树根是
	   heap[1],其中保存所有权值值的总和, heap[2]..heap[num-1]对应于所有根以外
	   的分支结点,其中保存的是双亲结点的索引值, heap[num]..heap[num*2-1]对应于所
	   有叶子结点(即所有要编码的元素),其中保存的是双亲结点的索引值 */

	// 为了建树之后，对二叉树进行限制码长的调整，有必要在建树过程中，每选出一个
	// 叶子结点，就用数组index按顺序记录下元素位置
	int* index = new int[num]; int index_i = 0;
	if (index == NULL) throw new huffman_exception("内存不足");

	/* 当用于堆排序的二叉树中还有结点时循环 */
	while (heap_num > 1)
	{
		int pos[2];
		/* 循环2次,找出2个最小的子树,存入pos中 */
		for (i = 0; i < 2; i++)
		{
			register int curr, child;
			/* 根结点就是最小的结点 */
			pos[i] = heap[0];
			if (pos[i] >= num) // 如果是叶子结点，就记录
				index[index_i++] = pos[i];
			/* 将最后的结点移动到根结点处,总结点数目减1 */
			heap[0] = heap[--heap_num];
			/* 以下是重建堆的过程 */
			curr = 1;
			child = 2;
			while (child <= heap_num)
			{
				if (child < heap_num &&
					heap[heap[child]] < heap[heap[child - 1]])
					child++;
				if (heap[heap[curr - 1]] > heap[heap[child - 1]])
				{
					register int temp;
					temp = heap[child - 1];
					heap[child - 1] = heap[curr - 1];
					heap[curr - 1] = temp;
					curr = child;
					child = 2 * curr;
				}
				else
					break;
			}
		}

		/* 合并子树,其结果作为新的结点放入堆中(但不在堆排序的二叉树内,实际
		   上,新加入的结点是和堆的后半段一起构成了Huffman树) */
		heap[heap_num + 1] = heap[pos[0]] + heap[pos[1]];
		/* 子树的左,右分支都指向子树的根结点 */
		heap[pos[0]] = heap[pos[1]] = heap_num + 1;

		/* 把子树根结点作为叶子结点，放到堆排序中的二叉树内 */
		heap[heap_num] = heap_num + 1;
		{
			/* 在堆中,让新加入的叶子结点上升到合适的位置,不破坏堆的秩序 */
			register int parent, curr;
			heap_num++;
			curr = heap_num;
			parent = curr >> 1;
			while (parent && heap[heap[parent -	1]]	> heap[heap[curr - 1]])
			{
				register int temp;
				temp = heap[parent - 1];
				heap[parent	- 1] = heap[curr - 1];
				heap[curr -	1] = temp;
				curr = parent;
				parent = curr >> 1;
			}
		}
	}
		
	// 从根出发，求每个编码的码长
	int overflow = 0; // 记录有多少个编码超长	
	const int tmp = sizeof(unsigned long)*8 + 1;
	int len_count[tmp];
	memset(len_count, 0, sizeof(int)*tmp);
	heap[0] = (unsigned long)(-1l); // 双亲结点为0的叶子，可由此算得码长0
	heap[1] = 0; // 根结点码长为0
	for (i = 2; i < 2*num; i++)
	{		
		heap[i] = heap[heap[i]] + 1; // 结点码长等于双亲结点码长加1
		if (i >= num)
		{
			if (heap[i] <= (unsigned long)max_code_len)
				len_count[heap[i]]++;
			else // 统计超长叶子结点数量
			{			
				heap[i] = max_code_len;
				overflow++;
			}
		}
	}

	// 如果有编码被限制了码长，就意味着码长为max_code_len的编码
	// 数量已经超过了二叉树的容量，必须做二叉树的重整	
	if (overflow > 0)
	{
		// 假设把超长叶子结点都去掉，计算码长max_code_len处还可腾出几个位置
		// 计算方法是，从根开始，每层的分支结点数目等于上层分支结点数乘2减
		// 本层叶子结点数；最后一层的分支结点数，就是可腾出的空位数量
		int nonleaf = 1, bits; 
		for(i = 1; i <= max_code_len; i++)
			nonleaf = nonleaf * 2 - len_count[i]; 

		// 先把nonleaf个超长结点放到max_code_len这一层
		overflow -= nonleaf;
		len_count[max_code_len] += nonleaf;

		// 调整剩下的超长结点，这个循环只调整码长的计数数组len_count
		while(overflow > 0)
		{
			bits = max_code_len - 1;
			while(len_count[bits] == 0) bits--; // 向上找到一个有叶子的层次
			len_count[bits]--; // 把叶子移下一层
			len_count[bits+1] += 2; // 把移下来的叶子和超长的一个结点合并为一个子树
			overflow --;
		};

		// 下面这个循环真正对码长进行调整
		// 从码长最长的结点开始，在堆中倒着数，如果发现实际数目
		// 和len_count中记录的不一致，就调整码长，使之和len_count一致
		int m, n; index_i = 0;
		for(bits = max_code_len; bits != 0; bits--)
		{
			n = len_count[bits];
			while(n != 0)
			{
				m = index[index_i++];
				if (heap[m] != (unsigned long)bits)
					heap[m] = bits;
				n--;
			}			
		}
	}

	code_lens.clear();
	for (i = num; i < 2*num; i++)
		code_lens.push_back(heap[i]);

	// 由码长得到canonical huffman编码
	generate_canonical_codes();

	delete[] heap;
	delete[] index;
}