1.哈夫曼编码的主要思想

• 在进行数据压缩时，为了使压缩后的数据文件尽可能短，可采用不定长编码。
• 其基本思想是：为出现次数较多的字符编以较短的编码。
• 为确保对数据文件进行有效的压缩和对压缩文件进行正确的解码，可以利用哈夫曼树来设计二进制编码。
• 哈夫曼树中，约定左分支标记为0，右分支标记为1，则根结点到每个叶子结点路径上的0、1序列即为相应字符的编码。

2.哈夫曼编码有关概念

• 前缀编码：如果在一个编码方案中，任一个编码都不是其他任何编码的前缀(最左子串)则称编码是前缀编码。例如编码0,10, 110,111是前缀编码，而编码0,01,010,111就不是前缀编码。前缀编码可以保证对压缩文件进行解码时不产生二义性，确保正确解码。
• 哈夫曼编码：对一棵具有n个叶子的哈夫曼树，若对树中的每个左分支赋予0，右分支赋予1，则从根到每个叶子的路径上，各分支的赋值分别构成一个二进制串，该二进制串就称为哈夫曼编码。

3.哈夫曼编码性质

• 性质1：哈夫曼编码是前缀编码。
  • 证明：哈夫曼编码是根到叶子路径上的编码序列，由树的特点知，若路径A是另一条路经B的最左部分，则B经过了A，则A的终点一定不是叶子。而哈夫曼编码对应路径的终点一定为叶子，因此，任一哈夫曼码都不会与任意其他哈夫曼编码的前缀部分完全重叠，因此哈夫曼编码是前缀编码。
• 性质2：哈夫曼编码是最优前缀编码。
  • 对于包括n个字符的数据文件，分别以它们的出现次数为权值构造哈夫曼树，则利用该树对应的哈夫曼编码对文件进行编码，能使该文件压缩后对应的二进制文件的长度最短。

4.哈夫曼编码的算法实现

• 在构造哈夫曼树之后，求哈夫曼编码的主要思想是：依次以叶子为出发点,向上回溯至根结点为止。回溯时走左分支则生成代码0，走右分支则生成代码1。
• 由于每个哈夫曼编码是变长编码，因此使用一个指针数组来存放每个字符编码串的首地址。
• 哈夫曼编码表的存储表示：typedef char **Huffmancode;   //动态分配数组存储哈夫曼编码表
• 各字符的哈夫曼编码存储在由Huffman Code定义的动态分配的数组HC中，为了实现方便，数组的0号单元不使用，从1号单元开始使用，所以数组HC的大小为n+1，即编码表HC包括n+1行。但因为每个字符编码的长度事先不能确定，所以不能预先为每个字符分配大小合适的存储空间。为不浪费存储空间，动态分配一个长度为n(字符编码长度一定小于n)的一维数组cd，用来临时存放当前正在求解的第i(1≤i≤n)个字符的编码，当第i个字符的编码求解完毕后，根据数组cd的字符串长度分配HC[i]的空间，然后将数组cd中的编码复制到HC[i]中。
• 因为求解编码时是从哈夫曼树的叶子出发，向上回溯至根结点。所以对于每个字符，得到的编码顺序是从右向左的，故将编码向数组cd存放的顺序也是从后向前的，即每个字符的第1个编存放在cd[n-2]中(cdn-1]存放字符串结束标志”0)，第2个编码存放在cdn-3]中，依此类推，直到全部编码存放完毕。
• 算法步骤
  • ①分配存储n个字符编码的编码表空间HC，长度为n+1；分配临时存储每个字符编码的动态数组空间cd，cdn-1]置为”0°。
  • ②逐个求解n个字符的编码，循环n次,执行以下操作：
    • 设置变量start用于记录编码在cd中存放的位置，start初始时指向最后，即编码结束符位置n-1;
    • 设置变量c用于记录从叶子结点向上回溯至根结点所经过的结点下标，c初始时为当前待编码字符的下标i，f用于记录i的双亲结点的下标；
    • 从叶子结点向上回溯至根结点，求得字符i的编码,当f没有到达根结点时,循环执行以下操作:
      • 回溯一次start向前指一个位置，即- - start;
      • 若结点c是f的左孩子，则生成代码0，否则生成代码1，生成的代码0或1保存在 cd[start]中；
      • 继续向上回溯，改变c和f的值。
    • 根据数组cd的字符串长度为第i个字符编码分配空间HC[i]，然后将数组cd中的编码复制到HC[i]中
  • ③释放临时空间cd。
• 算法描述

void CreatHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n)
{
	//从叶子到根逆向求每个字符的赫夫曼编码，存储在编码表HC中
	int i, start, c, f;
	HC = new char*[n + 1];  // 分配n个字符编码的头指针矢量
	char *cd = new char[n];	// 分配临时存放编码的动态数组空间
	cd[n - 1] = '\0';         // 编码结束符
	
	for (i = 1; i <= n; ++i)
	{                         // 逐个字符求赫夫曼编码
		start = n - 1;       // start开始时指向最后，即编码结束符位置
		c = i;
		f = HT[i].parent;     // f指向结点c的双亲结点
		while (f != 0)
		{                       // 从叶子结点开始向上回溯，直到根结点
			--start;             // 回溯一次start向前指一个位置
			if (HT[f].lchild == c)
				cd[start] = '0';    // 结点c是f的左孩子，则生成代码0
			else
				cd[start] = '1';     // 结点c是f的右孩子，则生成代码1
			c = f;
			f = HT[f].parent;          // 继续向上回溯
		}      
		// 求出第i个字符的编码      
		HC[i] = new char[n - start];  // 为第i 个字符编码分配空间
		strcpy(HC[i], &cd[start]);     // 将求得的编码从临时空间cd复制到HC的当前行中
	}

	delete cd; // 释放临时空间                           			
}

5.代码实现

• main.cpp

#include <iostream>
#include <cstdlib>
#include <string>

using namespace std;

typedef struct
{
	int weight;
	int parent, lchild, rchild;
}HTNode, *HuffmanTree;

typedef char **HuffmanCode;

void Select(HuffmanTree HT, int len, int &s1, int &s2)
{
	int i, min1 = 0x3f3f3f3f, min2 = 0x3f3f3f3f;  // 先赋予最大值
	for (i = 1; i <= len; i++)
	{
		if (HT[i].weight < min1 && HT[i].parent == 0)
		{
			min1 = HT[i].weight;
			s1 = i;
		}
	}
	int temp = HT[s1].weight; // 将原值存放起来，然后先赋予最大值，防止s1被重复选择
	HT[s1].weight = 0x3f3f3f3f;
	for (i = 1; i <= len; i++)
	{
		if (HT[i].weight < min2 && HT[i].parent == 0)
		{
			min2 = HT[i].weight;
			s2 = i;
		}
	}

	HT[s1].weight = temp;// 恢复原来的值
}

void CreatHuffmanTree(HuffmanTree &HT, int n)
{
	//构造赫夫曼树HT
	int m, s1, s2, i;
	if (n <= 1)
		return;
	m = 2 * n - 1;
	HT = new HTNode[m + 1];  // 0号单元未用，所以需要动态分配m+1个单元，HT[m]表示根结点   
	for (i = 1; i <= m; ++i)  // 将1~m号单元中的双亲、左孩子，右孩子的下标都初始化为0   
	{
		HT[i].parent = 0;  HT[i].lchild = 0;  HT[i].rchild = 0;
	}
	cout << "请输入叶子结点的权值：\n";
	for (i = 1; i <= n; ++i)   // 输入前n个单元中叶子结点的权值  
		cin >> HT[i].weight;

	/*――――――――――初始化工作结束，下面开始创建赫夫曼树――――――――――*/
	// 通过n-1次的选择、删除、合并来创建赫夫曼树
	for (i = n + 1; i <= m; ++i)
	{
		Select(HT, i - 1, s1, s2); // 在HT[k](1≤k≤i-1)中选择两个其双亲域为0且权值最小的结点,并返回它们在HT中的序号s1和s2
		HT[s1].parent = i;
		HT[s2].parent = i;
		// 得到新结点i，从森林中删除s1，s2，将s1和s2的双亲域由0改为i
		HT[i].lchild = s1;
		HT[i].rchild = s2; // s1,s2分别作为i的左右孩子
		HT[i].weight = HT[s1].weight + HT[s2].weight; //i 的权值为左右孩子权值之和
	}
}

void CreatHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n)
{
	//从叶子到根逆向求每个字符的赫夫曼编码，存储在编码表HC中
	int i, start, c, f;
	HC = new char*[n + 1];  // 分配n个字符编码的头指针矢量
	char *cd = new char[n];	// 分配临时存放编码的动态数组空间
	cd[n - 1] = '\0';         // 编码结束符
	
	for (i = 1; i <= n; ++i)
	{                         // 逐个字符求赫夫曼编码
		start = n - 1;       // start开始时指向最后，即编码结束符位置
		c = i;
		f = HT[i].parent;     // f指向结点c的双亲结点
		while (f != 0)
		{                       // 从叶子结点开始向上回溯，直到根结点
			--start;             // 回溯一次start向前指一个位置
			if (HT[f].lchild == c)
				cd[start] = '0';    // 结点c是f的左孩子，则生成代码0
			else
				cd[start] = '1';     // 结点c是f的右孩子，则生成代码1
			c = f;
			f = HT[f].parent;          // 继续向上回溯
		}      
		// 求出第i个字符的编码      
		HC[i] = new char[n - start];  // 为第i 个字符编码分配空间
		strcpy(HC[i], &cd[start]);     // 将求得的编码从临时空间cd复制到HC的当前行中
	}

	delete cd; // 释放临时空间                           			
}

void show(HuffmanTree HT, HuffmanCode HC)
{
	for (int i = 1; i <= sizeof(HC) + 1; i++)
		cout << HT[i].weight << "编码为" << HC[i] << endl;
}

int main()
{
	HuffmanTree HT;
	HuffmanCode HC;
	int n;
	cout << "请输入叶子结点的个数：\n";
	cin >> n;											//输入赫夫曼树的叶子结点个数
	CreatHuffmanTree(HT, n);
	CreatHuffmanCode(HT, HC, n);
	show(HT, HC);

	system("pause");

	return 0;
}