huffman_d.cpp

高效的huffman编解码

#include "huffman_d.h"

#include <stdlib.h>
#include <search.h>

unsigned long* huffman_d::tree = NULL;

int huffman_d::index_compare(const void* a, const void* b)
{
	// qsort()使用的比较函数，因为是对索引数组排序，
	// 所以这里比较的对象实际是索引指向的tree中某结点的权值
	if (tree[*((int*)a)] > tree[*((int*)b)])
		return 1;
	else if (tree[*((int*)a)] < tree[*((int*)b)])
		return -1;
	else
		return 0;
}

void huffman_d::binsert(int* index, int n, int start)
{
	int end = n - 1, m;
	while(start <= end)
	{
		m = (start + end) / 2;
		if (tree[index[n]] < tree[index[m]])
			end = m - 1;
		else
			start = m + 1;
	}
	int tmp = index[n];
	for(int i = n; i > start; i--)
		index[i] = index[i - 1];
	index[start] = tmp;
}

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

	tree = new unsigned long[2*num]; // 0号单元未用
	if (tree == NULL) throw new huffman_exception("内存不足");
	memcpy(tree + 1, weights, sizeof(unsigned long)*num);

	// 标记结点权值顺序的索引数组
	int* index = new int[2*num]; // 0号单元未用
	if (index == NULL) throw new huffman_exception("内存不足");		

	// 初始化索引数组
	for(int i = 1; i < 2*num; i++)
		index[i] = i;

	// 权值从小到大排序，这里使用C运行库的qsort()函数
	qsort(index + 1, num, sizeof(index[0]), index_compare);

	// 计算权值不为0的元素个数，因为已排序，
	// 只要在索引数组开头数有几个0就行了
	int nonzero_num = num; index[0] = -1;
	while(tree[index[num - nonzero_num + 1]] == 0) 
		nonzero_num--;

	// 建Huffman树
	int s1, s2;
	for(int i = num + 1; i < num + nonzero_num; i++) 
	{
		// 直接挑出最前面也就是权值最小（除了权值为0的元素外）
		// 的两个元素
		s1 = (i - num) * 2 - 1 + (num - nonzero_num); 
		s2 = (i - num) * 2 + (num - nonzero_num);
		tree[i] = tree[index[s1]] + tree[index[s2]];
		tree[index[s1]] = tree[index[s2]] = i;
		// tree[i]存放合并后的结点权值，使用折半插入法，
		// 将i排到index有序表中的正确位置
		binsert(index, i, s2 + 1);
	}

	// 从根出发，求每个编码的码长	
	code_lens.clear();
	tree[0] = (unsigned long)(-1l); // 双亲结点为0的叶子，可由此算得码长0
	tree[num + nonzero_num - 1] = 0; // 根结点码长为0
	for (int i = num + nonzero_num - 2; i >= 1; i--) 		
		tree[i] = tree[tree[i]] + 1; // 结点码长等于双亲结点码长加1
	for (int i = 1; i <= num; i++)
		code_lens.push_back(tree[i]);

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

	delete[] tree;
	delete[] index;
}