www.pudn.com > Huffman.rar > huffman_f.cpp

#include "huffman_f.h"

void huffman_f::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;

	/* 将堆的前半部分视作指针,按照指针所指的权值大小,把堆的前半部分组织成为
	   堆排序(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]对应于所
	   有叶子结点(即所有要编码的元素),其中保存的是双亲结点的索引值 */

	/* 当用于堆排序的二叉树中还有结点时循环 */
	while (heap_num > 1)
	{
		int pos[2];
		/* 循环2次,找出2个最小的子树,存入pos中 */
		for (i = 0; i < 2; i++)
		{
			register int curr, child;
			/* 根结点就是最小的结点 */
			pos[i] = heap[0];
			/* 将最后的结点移动到根结点处,总结点数目减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;
			}
		}
	}
		
	// 从根出发，求每个编码的码长	
	code_lens.clear();
	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
	for (i = num; i < 2*num; i++)
		code_lens.push_back(heap[i]);

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

	delete[] heap;
}