huffman_base.h

根据最常用的链表法进行huffman编码

#ifndef _HUFFMAN_BASE_HEADER_001_
#define _HUFFMAN_BASE_HEADER_001_

#include <cstring>
#include <string>
#include <vector>
#include <exception>
#include <stdexcept>
using namespace std;

class huffman_exception : public exception
{
public:
	huffman_exception(const char* message) throw()
		{ this->message = message; }
		~huffman_exception() throw() {}
	virtual const char *what( ) const throw()
		{ return message.c_str(); }
private:
	string message;
};

class huffman_base
{
public:	
	huffman_base() { need_sorted = false; }
	virtual ~huffman_base(void) {}

protected:
	// 调用generate_codes()前，算法是否要求weights已从小到大排序
	// 只有A. Moffat和J. Katajainen的内部建树算法需要预先排序
    bool need_sorted;

public:
	// 获得need_sorted的值
	bool if_need_sorted() { return need_sorted; }

	// 生成所有元素的Huffman编码，输入元素个数和每个元素的权值
	virtual void generate_codes(int num, const unsigned long* weights) = 0;

	// 获得某个元素的码长，index >= 0
	int get_code_len(int index);

	// 获得所有元素的码长
	vector<int> get_all_code_lens(void);

	// 获得某个元素的编码，index >= 0
	unsigned long get_code(int index);
	
	// 获得所有元素的编码
	vector<unsigned long> get_all_codes(void);

	// 获得某个元素的编码，字符串方式，index >= 0
	string get_code_str(int index);

	// 获得所有元素的编码，字符串方式
	vector<string> get_all_code_strs(void);
		
	// 根据编码查找元素序号，输入的编码为unsigned long方式
	// 返回-1表示没有找到
	int find(unsigned long code);

	// 根据编码查找元素序号，输入的编码为字符串方式，如"00101"
	// 返回-1表示没有找到
	int find(const string& code);

	// 检验已生成的Huffman树是否正确，这里只检验码长
	bool verify();

protected:
	// 每个元素的编码，未生成编码前，codes中元素个数为0
	// 编码以unsigned long方式存储，编码的最右一位与unsigned long的最低位对齐
	// 如，编码"00101"对应的unsigned long值为5
	// 在这种方式下，可表示的编码最大长度为sizeof(unsigned long) * 8个二进制位
	vector<unsigned long> codes;

	// 每个元素的码长，未计算码长前，code_lens中元素个数为0
	vector<int> code_lens;

protected:
	// 将字符串方式的编码转换为unsigned long方式的编码
	inline unsigned long string_to_long(const char* code);
	// 将unsigned long方式的编码转换为字符串方式的编码
	inline string long_to_string(unsigned long code, int code_len);

	// 检查weights是否已初始化，检查huffman是否已生成
	inline void check();

	// 已知所有元素得码长，生成Canonical Huffman编码
	void generate_canonical_codes();
};

#endif