哈夫曼树与哈夫曼编码

发表于 | 分类于

一、概念

哈夫曼树（Huffman tree），又名最优树，指给定n个权值作为n的叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。

二、想法

2.1、节点结构

哈夫曼树的节点中应该存在数据，权重，双亲以及左右孩子，
所以节点构造如下：

1
2
3
4
5
6
7
8
9
template <class T> 
struct HuffmanNode
{
	T data;					//数据 
	double weight;			//符号出现的频率
	int parent;				//双亲结点的坐标
	int lchild;				//左孩子的坐标
	int rchild;				//右孩子的坐标
};

2.2、哈夫曼树结构及树的构造方法

我们先说，如何去构造一个哈夫曼树，应该是根据权值的不同，每次找到两个小值，把他们两个拼凑起来，其中，权值应该是通过统计得到的，后面会提到方法，这边暂且假设已经得到。

1
2
3
4
5
6
7
8
template<class T>
class HuffmanTree  
{
    ……………………
private:
	vector<HuffmanNode<T> > huffmantree;	//huffmantree所有节点的存储空间
	int n;			//叶子结点数
};

哈夫曼树，接受一个存有所有叶子节点的向量，根据这些向量，来构造一棵树，我们知道，n个叶子节点，最后会生成2n-1个节点，所以需要先resize树向量。然后把huffmantree里面初值赋完，接下来，我们要找两个权值最小和次小的节点，并用这两个节点信息生成新的节点，填入。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
template<class T>
HuffmanTree<T>::HuffmanTree(vector<HuffmanNode<T> > &leafs)
{
	n = leafs.size();   //叶子节点个数赋值给n;
	huffmantree.resize(2*n-1);  //为为分支结点预留向量空间
	for (int i=0;i<n;i++)
	{
		huffmantree[i].data=leafs[i].data;
		huffmantree[i].weight=leafs[i].weight;
		huffmantree[i].parent=huffmantree[i].lchild=huffmantree[i].rchild=-1;
	}
	
	int least, less;  //最小数 次小数的下标
	for( i=n; i<2*n-1; i++)
	{
		SelectSmall(least, less, i); //找到最小值 次小值的结点下标
		//由之前的两个最小值生成新结点，
		huffmantree[least].parent = huffmantree[less].parent = i;//原2个节点的父节点置值
		huffmantree[i].data = i;//并没什么作用。。后面输出也会被过滤
		huffmantree[i].parent = -1;
		huffmantree[i].lchild = least;
		huffmantree[i].rchild = less;
		huffmantree[i].weight = huffmantree[least].weight + huffmantree[less].weight;
	}
}

2.3、找最小值以及次小值

下面介绍一下，如何找到最小值和次小值：
首先，只有没有被用过的节点才有比较的资格，也就是父节点为-1的才能参与比较，每轮比较，我们从头开始循环.循环判断过程如下

  • 父节点是否为-1
    • 当当前值比最小值小
      • 那么先把原先的最小值抛给最小值，并保存次小值序号，
  • 更新最小值及序号。
  • 当前值大于等于最小值，且小于次小值
    • 更新次小值及其序号 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
template<class T>
void HuffmanTree<T>::SelectSmall(int &least,int &less,int i)
{
	least = less = 0;
	int min1 = INT_MAX;
	int min2 = INT_MAX;
	for(int j=0; j<i; j++)
	{
		if(huffmantree[j].parent == -1)		//当没有父节点才有资格比较
		{//筛选没有父结点的最小值和次小值
			if(huffmantree[j].weight<min1)
			{//如果比最小值小
				min2 = min1;	//把原来的最小值先抛给次小
				less = least;	//保存次小值的序号
				min1 = huffmantree[j].weight;//保存最小值
				least = j;	//能保存最小值序号
			}
			else if((huffmantree[j].weight>=min1)&&(huffmantree[j].weight<min2))
			{//如果大于等于最小值，且小于次小值
				min2 = huffmantree[j].weight;
				less = j;
			}
		}
	}
}

2.4、频率统计

上面的构造函数，是根据所给的含有频率信息的HuffmanNode数组构造数，下面，我来介绍一下，对于ASCII码的字符（非汉字）如何统计。
思路如下，因为ASCII码值，不超过256个，所以，可以建立一个大小为256的int数组，初值置为0，遍历字符串，遇到一个，对应值加1，可以达到简单的统计效果，键值就是0~256，内容就是出现的次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int frequency[256];//用于记录每个ASCII出现的次数
memset(frequency,0,sizeof(frequency));
for (int i = 0; i < rst.length(); i++)
	frequency[rst[i]]++;	//每出现一次，次数加1
for ( i = 0; i < 256; i++)
{
	if (frequency[i] != 0)
	{
		weight.push_back(frequency[i]*1.0/rst.length()*100);		//当频率不为0的时候，压入权重向量//这个做了个规约处理
		s.push_back(i);											//同时把字符对应的ASCII值存到S向量
	}
}
for ( i = 0; i < s.size(); i++)									//把组织好的值压入向量中，供构造树。
{
	HuffmanNode<char> tmp={ s[i], weight[i], -1, -1, -1 };
	huffnode.push_back(tmp);
}

HuffmanNode<char> *hn=new HuffmanNode<char> [s.size()];
for (i=0;i<s.size();i++)
{
	hn[i]=huffnode[i];
}

这个统计字频的思路很简单，但是对于中文是完全无效的，算是缺陷。这边在频率统计完了之后，顺便构造了Node数组，便于后面构造树。

2.5、生成编码字符串

首先，我们要对这棵哈夫曼树的叶子节点编码，得到每个叶子节点的码值，然后在读取源码，生成对应的01编码。
编码的原理，就是从当前节点向前回溯，如是其父节点的左孩子插入1，相反插0；知道根节点停止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template<class T>
vector<int> HuffmanTree<T>::GetCode(int i)
{
	vector<int> code;
	int parent;
	parent = huffmantree[i].parent;   //先获得父节点的下标找到父节点
	while(parent != -1)  //parent == -1 时，表明已经到了根节点了
	{
		if(i == huffmantree[parent].lchild)
			code.insert(code.begin(), 0);
		else
			code.insert(code.begin(), 1);
		i = parent;  //把父节点换成当前的子节点
		parent = huffmantree[i].parent;  //沿父指针上溯
	}
	return code;
}

编码函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//编码,并把结果存在codes向量里面，并用hash表存储，便于读取
int hash[256];  
memset(hash,-1,sizeof(hash));
vector<string> codes;
vector<int> code;
cout<<endl<<"字符编码如下："<<endl;
for( i=0; i<HT.GetN(); i++)
{
	char c=HT.GetData(i);		cout<<c<<":   ";
	hash[c]=i;
	code = HT.GetCode(i);
	string tmp;
	for(int j=0; j<code.size(); j++)
		tmp+=(char)(code[j]+48);
	codes.push_back(tmp);
	cout<<tmp<<endl;
}

下面是生成编码字符串

1
2
3
4
5
6
7
8
9
10
11
string res;
for ( i=0;i<rst.length();i++)
{
	char c=rst.at(i);
	res+=codes[hash[c]];
}
ofstream out;
out.open("code.txt");
out<<res;
out.close();
cout<<endl<<"编译码已经写入code.txt!"<<endl;

2.6、解码

根据01编码进行解码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template<class T>	 
void HuffmanTree<T>::DeCode(string source)
{
	int root = huffmantree.size()-1;   //获得根节点下标
	int p = root;   //p为当前结点的下标
	for(int i=0; i<source.size(); i++)
	{
		if(source.at(i) == '0')
			p = huffmantree[p].lchild;
		else
			p = huffmantree[p].rchild;
		if( (huffmantree[p].lchild == -1) && (huffmantree[p].rchild == -1) )  //如果到了叶子节点 
		{
			cout<<huffmantree[p].data;
			p = root;   //当前结点再次是根结点
		}
	}
}

1
2
3
4
//下面是译码
cout<<endl<<"译码结果："<<endl;
HT.DeCode(res);
cout<<endl;

2.7、打印

为了方便查看哈夫曼树的结构，设计了这个方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
template<class T>
void HuffmanTree<T>::Print()
{
	cout<<"编号"<<"\t"<<"符号"<<"\t"<<"频率"<<"\t"<<"父结点"<<"\t"<<"左孩子"<<"\t"<<"右孩子"<<endl;
	for(int i=0; i<2*n-1; i++)
	{
		cout<<i<<"\t";
		if (i<n)
		{	
			cout<<huffmantree[i].data<<"\t";
		}
		else
		{
			cout<<"\t";
		}
		cout<<setprecision(4)<<huffmantree[i].weight<<"%"<<"\t";
		cout<<huffmantree[i].parent<<"\t";
		cout<<huffmantree[i].lchild<<"\t";
		cout<<huffmantree[i].rchild<<"\t";
		cout<<endl;
	}
}

2.8、保存哈夫曼树

为了讲编码翻译成源码，需要有哈夫曼树的存在，本来可以用对象的序列化存为二进制文件更加安全的，这边还是用文件的写保存。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
template<class T>
void HuffmanTree<T>::Save(char *fname)
{
	ofstream out;
	out.open(fname);
	out<<n<<endl;
	for(int i=0; i<2*n-1; i++)
	{
		if (i<n)
		{	
			out<<huffmantree[i].data<<"\t";
		}
		else
		{
			out<<0<<"\t";
		}
		out<<setprecision(4)<<huffmantree[i].weight<<"\t";
		out<<huffmantree[i].parent<<"\t";
		out<<huffmantree[i].lchild<<"\t";
		out<<huffmantree[i].rchild<<"\t";
		out<<endl;
	}
	out.close();
	cout<<endl<<"该树已经写入"<<fname<<endl;
}

2.9、还原哈夫曼树

也就是按照文件读入来构造哈夫曼树，实质上是构造函数，可能对于后于需要的其他功能提供方便。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
template<class T>
HuffmanTree<T>::HuffmanTree(char *fname)
{
	ifstream in;
	in.open(fname);
	in>>n;   //叶子节点个数赋值给n;
	huffmantree.resize(2*n-1);  //为为分支结点预留向量空间

	for(int i=0; i<2*n-1; i++)
	{
		char c;
		in>>c;
		if (c!='0')
		{
			huffmantree[i].data = c;
		}
		in>>huffmantree[i].weight;
		in>>huffmantree[i].parent;
		in>>huffmantree[i].lchild;
		in>>huffmantree[i].rchild;
	}
}

三、测试函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
int main()
{
	//统计字频
	vector<char> s;		//字符集
	vector<double> weight;//每个字符个数
	vector<HuffmanNode<char> > huffnode;//存每个结点
	string rst;
	ifstream in;
	cout<<"字符串内容来源于data.txt!"<<endl;
	in.open("data.txt");
	string tmp;
	while(getline(in,tmp))
	{
		rst+=tmp;
	}
	in.close();
	//cout << "请输入一个字符串：";
	//cin >> rst;
	//对rst做频率统计
	int frequency[256];//用于记录每个ASCII出现的次数
	memset(frequency,0,sizeof(frequency));
	for (int i = 0; i < rst.length(); i++)
		frequency[rst[i]]++;	//每出现一次，次数加1
	for ( i = 0; i < 255; i++)
	{
		if (frequency[i] != 0)
		{
			weight.push_back(frequency[i]*1.0/rst.length()*100);		//当频率不为0的时候，压入权重向量//这个做了个规约处理
			s.push_back(i);											//同时把字符对应的ASCII值存到S向量
		}
	}
	for ( i = 0; i < s.size(); i++)									//把组织好的值压入向量中，供构造树。
	{
		HuffmanNode<char> tmp={ s[i], weight[i], -1, -1, -1 };
		huffnode.push_back(tmp);
	}

	HuffmanNode<char> *hn=new HuffmanNode<char> [s.size()];
	for (i=0;i<s.size();i++)
	{
		hn[i]=huffnode[i];
	}
					
	//建树
	vector< HuffmanNode<char> > leafs(hn,hn+s.size());
	HuffmanTree<char> HT(leafs);
	cout<<"此哈夫曼树存储结构如下："<<endl;
	HT.Print();
	
	//编码,并把结果存在codes向量里面，并用hash表存储，便于读取
	int hash[256];	//存的是字符对应在codes的位置。
	memset(hash,-1,sizeof(hash));
	vector<string> codes;//存的是字符对应的码值
	vector<int> code;
	cout<<endl<<"字符编码如下："<<endl;
	for( i=0; i<HT.GetN(); i++)
	{
		char c=HT.GetData(i);		cout<<c<<":   ";
		hash[c]=i;
		code = HT.GetCode(i);
		string tmp;
		for(int j=0; j<code.size(); j++)
			tmp+=(char)(code[j]+48);
		codes.push_back(tmp);
		cout<<tmp<<endl;
	}
	
	//下面是生成编码字符串
	string res;
	for ( i=0;i<rst.length();i++)
	{
		char c=rst.at(i);
		res+=codes[hash[c]];
	}
	ofstream out;
	out.open("code.txt");
	out<<res;
	out.close();
	cout<<endl<<"编译码已经写入code.txt!"<<endl;


	//下面是译码
	cout<<endl<<"译码结果："<<endl;
	HT.DeCode(res);
	cout<<endl;
	
	delete hn;
	return 0;
}

测试一：提供源码文件，统计频率，输出编码，并译码。
此处输入图片的描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
HuffmanTree<char> ht("MyTree.txt");
ht.Print();
cout<<endl;
string code;
ifstream in;
in.open("code.txt");
string tmp;
while(getline(in,tmp))
{
	code+=tmp;
}
in.close();
ht.DeCode(code);
cout<<endl;

测试二：提供哈夫曼树，提供编码，译码（有误？）
此处输入图片的描述
这边空格被误识别，原因未知。