huffman_e.cpp

huffman编码的c++实现源码

#include "huffman_e.h"

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

unsigned long* huffman_e::tree = NULL;

int huffman_e::index_compare(const void* a, const void* b)
{
	// 这里是从大到小排序，和huffman_d中正好相反
	if (tree[*((unsigned long*)a)] > tree[*((unsigned long*)b)])
		return -1;
	else if (tree[*((unsigned long*)a)] < tree[*((unsigned long*)b)])
		return 1;
	else
		return 0;
}

void huffman_e::binsert(unsigned long* tree, int n, int start)
{
	// 这里是从大到小排序，和huffman_d中正好相反
	int end = n - 1, m;
	while(start <= end)
	{
		m = (start + end) / 2;
		if (tree[tree[n]] > tree[tree[m]])
			end = m - 1;
		else
			start = m + 1;
	}
	int tmp = tree[n];
	for(int i = n; i > start; i--)
		tree[i] = tree[i - 1];
	tree[start] = tmp;
}

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

	tree = new unsigned long[2*num];
	if (tree == NULL) throw new huffman_exception("内存不足");
	// 将所有元素的权值复制到tree[num..2*num-1]
	memcpy(tree + num, weights, sizeof(unsigned long)*num);
	// tree[0..num-1]作为索引数组，指向每个元素
	for(int i = 0; i < num; i++)
		tree[i] = i + num;

	// 权值从大到小排序
	qsort(tree, num, sizeof(tree[0]), index_compare);

	// 计算权值不为0的元素个数
	int nonzero_num = num;
	while(nonzero_num > 0 && tree[tree[nonzero_num - 1]] == 0) 
		nonzero_num--;

	// 建Huffman树
	int s1, s2; unsigned long sum;
	for(int i = nonzero_num - 1; i > 0; i--) 
	{		
		s1 = i; s2 = i - 1;
		sum = tree[tree[s1]] + tree[tree[s2]];
		tree[tree[s1]] = tree[tree[s2]] = i + num - nonzero_num;
		tree[i + num - nonzero_num] = sum;
		tree[i-1] = i + num - nonzero_num;
		binsert(tree, i - 1, 0); // 把tree[i-1]排入有序表tree[0..i-2]
	}

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

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

	delete[] tree;
}