huffman_c.cpp

高效的huffman编解码

#include "huffman_c.h"

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

	// 权值为0的元素不参与编码，nonzero_num实际参与编码的元素数量
	int nonzero_num = 0;

	unsigned long* tree = new unsigned long[2*num]; // 0号单元未用
	if (tree == NULL) throw new huffman_exception("内存不足");
	// 将所有元素的权值复制到tree[1..num]
	for(int i = 1; i <= num; i++)
	{
		tree[i] = weights[i - 1];
		if (weights[i - 1] != 0) 
			nonzero_num++;
	}

	// flags数组记录每个叶子结点或子树是否已连入了Huffman树
	bool* flags = new bool[2*num];
	if (flags == NULL) throw new huffman_exception("内存不足");
	memset(flags, 0, sizeof(bool) * 2*num);
	
	// 建Huffman树
	int s1, s2;
	for(int i = num + 1; i < num + nonzero_num; i++) 
	{
		select(tree, flags, i - 1, s1, s2);
		tree[i] = tree[s1] + tree[s2];
		tree[s1] = tree[s2] = i; 
		flags[s1] = flags[s2] = true;		
	}

	// 从根出发，求每个编码的码长	
	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[] flags;
}

void huffman_c::select(unsigned long* tree, bool* flags, int n, int& s1, int& s2)
{
	tree[0] = (unsigned long)(-1l); s1 = s2 = 0;
	for(int i = 1; i <= n; i++)
		if (tree[i] != 0 && !flags[i])
		{
			if (tree[i] < tree[s1] )
			{ s2 = s1; s1 = i;}
			else if (tree[i] < tree[s2])
			{ s2 = i; }
		}
}