哈夫曼树及哈夫曼编码
一、哈夫曼树
哈夫曼树，又称最优二叉树，是一类带权路径长度最短的树。
叶子结点的权值：对叶子结点赋予一个有意义的数量值。
二叉树的带权路径长度：设二叉树有n个带权值的叶子结点，从根结点到各个叶子结点的路径长度与相应叶子结点权值的乘积之和。
哈夫曼树：给定一组具有确定权值的叶子结点，带权路径长度最小的二叉树。
例如，给定4个叶子结点，其权值分别是2,3,4,7，可以构造出形状不同的多个二叉树：
如图所示，第一棵二叉树WPL=22+32+42+72=32；第二棵二叉树WPL=21+32+43+73=41；第三棵二叉树WPL=71+42+23+33=30。
由此可知哈夫曼树的特点：
（1）权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。
（2）只有度为0和度为2的结点，不存在度为1的结点。
哈夫曼算法的基本思想：
（1）初始化：由给定的n个权值w1,w2,w3...wn构造n棵只有一个根结点的二叉树，从而得到一个二叉树集合F={T1,T2,T3...Tn}；
（2）选取与合并：在F中选取根结点的权值最小的两棵二叉树分别作为左右子树构造一棵新的二叉树，这棵新二叉树的根结点的权值为其左右子树根结点的权值之和；
（3）删除与加入：在F中删除作为左右子树的两棵二叉树，并将新建立的二叉树加入到F中；
（4）重复（2）、（3）两步，当集合F中只剩下一棵二叉树时，这棵二叉树便是哈夫曼树。
由上述基本思想可知，具有n个叶子结点的哈夫曼树共有2n-1个结点，其中n-1个是非叶子结点。
二、哈夫曼树的存储结构
考虑到哈夫曼树有2n-1个结点，并且进行n-1次合并操作，为了便于选取根结点权值最小的二叉树以及合并操作，设置一个向量容器hufftree保存哈夫曼树中各结点的信息。向量中各元素的结点结构为：
其中，weight为结点的权值，lchild为结点的左孩子结点在向量中的位置，rchild为结点的右孩子结点在向量中的位置，parent为结点的双亲在向量的位置。用C++结构体定义上述结点：
struct element{
char data;
int weight;
int lchild, rchild, parent;
};为了判定一个结点是否已经加入到哈夫曼树中，可以通过parent的值来确定。初始化时parent的值为-1，当某个结点加入到树中时，该结点的parent的值为其双亲结点在向量中的位置。
哈夫曼算法：
1.向量hufftree初始化，向量中各元素的双亲、左右孩子都置为-1；
2.向量hufftree的前n个元素的权值置为给定叶子结点权值；
3.进行n-1次合并：
3.1.在二叉树集合中任取两个权值最小的根结点，其下标分别为i1,i2；
3.2.将二叉树i1,i2合并为一棵新的二叉树。
HuffmanTree::HuffmanTree(vector<element>& leafs){
length = leafs.size() * 2 - 1;
hufftree.resize(length);//向量hufftree大小即哈夫曼树结点个数重置
size_t i;
size_t k;
size_t i1, i2;
for (i=0; i != length; i++){//哈夫曼树初始化
hufftree[i].parent = -1;
hufftree[i].lchild = -1;
hufftree[i].rchild = -1;
}
for (i = 0; i != leafs.size(); i++){
hufftree[i].weight = leafs[i].weight;
hufftree[i].data = leafs[i].data;
}
for (k = leafs.size(); k != length; k++){
select(k,i1, i2); //选取两个权值最小的根结点
hufftree[i1].parent = k;
hufftree[i2].parent = k;
hufftree[k].weight = hufftree[i1].weight + hufftree[i2].weight;
hufftree[k].lchild = i1;
hufftree[k].rchild = i2;
}
}那么如何在二叉树集合中选取两个权值最小的根结点呢？
算法分析：
1.将前两个根结点（parent==-1的结点）进行比较，较小者放到min中，较大者放到nmin中，同时记下它们在向量中的位置；
2.从第三个根结点开始直到最后一个根结点，依次执行下列操作：
2.1.如果该结点比min小，则该结点为min，原来的min为nmin；
2.2.否则，如果该结点只比nmin小，则该结点为nmin，最小值min不变；
2.3.同时记下它们各自在向量中的位置。
void HuffmanTree::select(size_t count,size_t& i1, size_t& i2){
//最小值与次最小值
int min, nmin;
size_t i = 0;
while (hufftree[i].parent != -1){
i++;
}
size_t k = i+1;
while (hufftree[k].parent != -1){
k++;
}
if (hufftree[i].weight < hufftree[k].weight){
i1 = i;
i2 = k;
min = hufftree[i1].weight;
nmin = hufftree[i2].weight;
}
else{
i1 = k;
i2 = i;
min = hufftree[i1].weight;
nmin = hufftree[i2].weight;
}
for (size_t j =k+1; j != count; j++){
if (hufftree[j].parent == -1){
if (hufftree[j].weight < min){
i2 = i1;
i1 = j;
nmin = min;
min = hufftree[j].weight;
}
else if (hufftree[j].weight < nmin){
i2 = j;
nmin = hufftree[j].weight;
}
}
}
}三、哈夫曼编码
编码：给每一个对象标记一个二进制位串来表示一组对象。例如：ASCII，指令系统。
等长编码：表示一组对象的二进制位串的长度相等。
不等长编码：表示一组对象的二进制位串的长度不相等。
如果每个字符的使用频率相等，则等长编码是空间效率最高的方法；如果字符出现的频率不同，则可以让频率高的字符采用尽可能短的编码，频率低的字符采用稍长的编码，来构造一种不等长编码，则会获得更好的空间效率。
对于不等长编码，如果设计的不合理，将给解码带来困难。设计不等长编码时要考虑解码的唯一性。这里引入前缀编码：如果一组编码中任一编码都不是其他任何一个编码得的前缀，我们称这组编码为前缀编码，如{00,01,10,11}就是一组前缀编码，而{0,1,00,11}不是一组前缀编码。
哈夫曼树可用于构造最短的不等长编码方案，具体做法：设需要编码的字符集为{d1,d2,d3...dn}，它们在字符串中出现的频率为{w1,w2,w3...wn}，以d1,d2,d3...dn为叶子结点，w1,w2,w3...wn作为叶子结点的权值，构造一棵哈夫曼编码树，规定哈夫曼编码树的左分支代表0，右分支代表1，则从根结点到每个叶子结点所经过的路径组成的0-1序列便是该叶子结点对应字符的编码，称为哈夫曼编码。
vector<size_t> HuffmanTree::getCode(size_t i){
//第i个符号的编码向量
vector<size_t> code;
//parent是第i个结点的父结点下标
size_t parent = hufftree[i].parent;
while (parent != -1){
//只有根结点的parent是-1
if (hufftree[parent].lchild == i){
code.insert(code.begin(), 0);
}
else{
code.insert(code.begin(), 1);
}
i = parent;
parent = hufftree[parent].parent;
}
return code;
}对字符串编码的解码则是将编码串从左到右逐位判别，直到确定一个字符。这可以用生成哈夫曼树的逆过程实现。从根结点开始，根据每一位的值是0还是1确定选择左分支还是右分支——直到到达一个叶子结点，然后再从根结点出发，开始下一个字符的翻译。
string HuffmanTree::deCode(vector<size_t>& source){
//译码结果
string target = "";
//根结点下标
size_t root = length - 1;
size_t p = root;
for (size_t i = 0; i != source.size(); i++){
if (source[i] == 0){
p = hufftree[p].lchild;
}
else{
//逢1向右孩子下行
p = hufftree[p].rchild;
}
if (hufftree[p].lchild == -1 && hufftree[p].rchild == -1){
//若hufftree[p]是叶子结点
target += hufftree[p].data;
p = root;
}
}
return target;
}
string HuffmanTree::deCode(string& source){
string target = "";
size_t root = length - 1;
size_t p = root;
for (size_t i = 0; i != source.size(); i++){
if (source[i] =='0'){
p = hufftree[p].lchild;
}
else{
p = hufftree[p].rchild;
}
if (hufftree[p].lchild == -1 && hufftree[p].rchild == -1){
target += hufftree[p].data;
p = root;
}
}
return target;
}下面是全部源码，如有不足之处请多多指教~~
#include <iostream>
#include <vector>
#include <string>
using namespace std;
struct element{
char data;
int weight;
int lchild, rchild, parent;
};
class HuffmanTree{
private:
vector<element> hufftree;
size_t length;
public:
HuffmanTree(vector<element>& leafs);
vector<size_t> getCode(size_t i);
string deCode(vector<size_t>& source);
string deCode(string& source);
void select(size_t count,size_t& i1, size_t& i2);
};
HuffmanTree::HuffmanTree(vector<element>& leafs){
length = leafs.size() * 2 - 1;
hufftree.resize(length);
size_t i;
size_t k;
size_t i1, i2;
for (i=0; i != length; i++){
hufftree[i].parent = -1;
hufftree[i].lchild = -1;
hufftree[i].rchild = -1;
}
for (i = 0; i != leafs.size(); i++){
hufftree[i].weight = leafs[i].weight;
hufftree[i].data = leafs[i].data;
}
for (k = leafs.size(); k != length; k++){
select(k,i1, i2);
hufftree[i1].parent = k;
hufftree[i2].parent = k;
hufftree[k].weight = hufftree[i1].weight + hufftree[i2].weight;
hufftree[k].lchild = i1;
hufftree[k].rchild = i2;
}
}
vector<size_t> HuffmanTree::getCode(size_t i){
//第i个符号的编码向量
vector<size_t> code;
//parent是第i个结点的父结点下标
size_t parent = hufftree[i].parent;
while (parent != -1){
//只有根结点的parent是-1
if (hufftree[parent].lchild == i){
code.insert(code.begin(), 0);
}
else{
code.insert(code.begin(), 1);
}
i = parent;
parent = hufftree[parent].parent;
}
return code;
}
string HuffmanTree::deCode(vector<size_t>& source){
//译码结果
string target = "";
//根结点下标
size_t root = length - 1;
size_t p = root;
for (size_t i = 0; i != source.size(); i++){
if (source[i] == 0){
p = hufftree[p].lchild;
}
else{
//逢1向右孩子下行
p = hufftree[p].rchild;
}
if (hufftree[p].lchild == -1 && hufftree[p].rchild == -1){
//若hufftree[p]是叶子结点
target += hufftree[p].data;
p = root;
}
}
return target;
}
string HuffmanTree::deCode(string& source){
string target = "";
size_t root = length - 1;
size_t p = root;
for (size_t i = 0; i != source.size(); i++){
if (source[i] =='0'){
p = hufftree[p].lchild;
}
else{
p = hufftree[p].rchild;
}
if (hufftree[p].lchild == -1 && hufftree[p].rchild == -1){
target += hufftree[p].data;
p = root;
}
}
return target;
}
void HuffmanTree::select(size_t count,size_t& i1, size_t& i2){
//最小值与次最小值
int min, nmin;
size_t i = 0;
while (hufftree[i].parent != -1){
i++;
}
size_t k = i+1;
while (hufftree[k].parent != -1){
k++;
}
if (hufftree[i].weight < hufftree[k].weight){
i1 = i;
i2 = k;
min = hufftree[i1].weight;
nmin = hufftree[i2].weight;
}
else{
i1 = k;
i2 = i;
min = hufftree[i1].weight;
nmin = hufftree[i2].weight;
}
for (size_t j =k+1; j != count; j++){
if (hufftree[j].parent == -1){
if (hufftree[j].weight < min){
i2 = i1;
i1 = j;
nmin = min;
min = hufftree[j].weight;
}
else if (hufftree[j].weight < nmin){
i2 = j;
nmin = hufftree[j].weight;
}
}
}
}
void getFrequency(const string& sentence,vector<int>& frequency){
for (size_t j = 0; j != sentence.size(); j++){
if (sentence[j]>='a'&& sentence[j]<='z'){
frequency[sentence[j] - 'a']++;
}
}
}
void getLeaf(const vector<int>& frequency, vector<element>& leafs){
size_t i = 0;
size_t k = 0;
size_t count = 0;
for (i = 0; i != frequency.size(); i++){
if (frequency[i])
count++;
}
leafs.resize(count);
for (i=0; i != frequency.size(); i++){
if (frequency[i] != 0){
leafs[k].data = i + 'a';
leafs[k].weight = frequency[i];
k++;
}
}
}
ostream& operator<<(ostream& os, vector<size_t>& code){
for (size_t i = 0; i != code.size(); i++){
os << code[i];
}
os << endl;
return os;
}
int main(){
string input;
cout << "请输入：";
getline(cin, input);
vector<int> frequency(26,0);
vector<element> leafs;
getFrequency(input, frequency);
getLeaf(frequency, leafs);
HuffmanTree huff(leafs);
//输出各个字符的编码
for (size_t i = 0; i != leafs.size(); i++){
cout <<leafs[i].data<<":"<< huff.getCode(i);
}
cout << "请输入要译码的序列：";
getline(cin, input);
cout << huff.deCode(input) << endl;
return 0;
}测试结果：
