Huffman树
关于Huffman编码
Huffman编码是一种数据压缩技术中的无损压缩方法，同时也是一种变长的编码方案，编码的长短与使用频率有关，使用频率高的数据编码较短，反之较长，使用频率通过在全部数据中统计重复数据的出现次数来获得。
- 数据压缩&解压缩过程
假设存在字符串“AABBCAABDDBBAAA”，采用ASCII码存储，一共有15个字节，共15*8=120位。
统计上述字符串使用字符频率
A：7
B：5
C：1
D：2
即编码方案为：A->0,B->11,C->100,D->101
原串压缩为：00111110000111011011111000
共26位，压缩比为 120:26≈4.6:1
任何一个字符的编码都不是另一个字符编码的前缀，这样才能保证译码的唯一性（ps：译码指编码恢复成原数据的过程）。
关于Huffman树
Huffman树是带权外路径长度最小的二叉树，也称最优二叉树。
为了使所构造二叉树带权外路径长度最小，应该尽量使权值较大结点的外路径长度较小。
权值最小二叉树作为左右子树合并，反复采取合并二叉树的策略，新根结点权值为两者之和。每个字符结点都是叶子结点，故叶子结点不可能在根到其他叶子结点的路径上——任何一个字符的Huffman编码也不可能是另一个字符的Huffman编码的前缀。
由二叉树性质知，具有n个叶子结点的Huffman树共有n个2n-1个结点。已知结点总数且没有插入删除操作的情况下，可采用静态链表存储Huffman树。需要使用从父母结点到孩子结点的双向关系，因此采用静态三叉链表。
//采用三叉链表表示huffman树实现文件压缩
class TriElement//二叉树的静态三叉链表元素结构
{
public:
int data, parent, left, right;//数据域，父母结点和左右孩子结点下标
TriElement(int data = 0, int parent = -1, int left = -1, int right = -1)
{
this->data = data;
this->parent = parent;
this->left = left;
this->right = right;
}
friend ostream& operator<<(ostream& out, TriElement& e)
{
out << "(" << e.data << "," << e.parent << "," << e.left << "," << "e.right" << ")";
return out;
}
bool isLeaf()//判断是否是叶子结点
{
return this->left == -1 && this->right == -1;
}
bool operator==(TriElement& e)//重载==运算符，比较是否相等
{
return this->data == e.data;
}
};
静态三叉链表存储的Huffman树采用TriElement结点数组存储所有结点，一个TriElement元素储存一个结点，结点data域存储权值。
其中Huffman编码由变长的二进制序列组成，获得所有叶子结点表示字符Huffman编码的算法描述，从叶子结点开始向上寻找一条到根节点的路径，该路径上0和1组成的序列构建该字符的Huffman编码
//HuffmanTree类声明，实现构造Huffman树，并实行Huffman编码和译码
#include"SeqList.h"
#include "TriElement.h"
#include"MyString.h"
class HuffmanTree
{
private:
MyString charset;//字符集
SeqList<TriElement>huftree;//结点顺序表
MyString encode(int i);//返回charest[i]字符的编码字符串
public:
HuffmanTree(int weight[], int n);//指定权值集合构造huffman树
void printCode();//输出所有字符的编码
MyString encode(MyString& text);//编码，数据压缩
MyString decode(MyString& codestr);//译码，数据解压缩
};
//构造Huffman树，weight[]指定权值集合，n指定数组长度（叶子节点数）
HuffmanTree::HuffmanTree(int weight[], int n)
:huftree(2 * n - 1)//声明执行SeqList<T>(int length),n个叶子的Huffman树共有n-1个结点
{ //此处先执行MyString(char*s,int length),再执行SeqList<T>(int length)
for (int i = 0; i < n; i++)//初始化
{
this->charset.insert(i, 'A' + i);//默认字符集从'A'开始的n个字符
this->huftree.insert(TriElement(weight[i], -1, -1, -1));//初始有n个叶子结点
}
for (int i = 0; i < n-1; i++)//构造n-1个2度结点，每次循环构造1个2度结点
{
int min1 = 0x7fffffff, min2 = min1, x1 = 0, x2 = 0;//最小和次最小权值及其下标
for (int j = 0; j < n + i; j++)//查找两个无父母的最小权值结点
if (huftree[j].parent == -1 && huftree[j].data < min1)
{
min2 = min1;
x2 = x1;
min1 = huftree[j].data;//min1记最小权值结点
x1 = j;//x1记最小权值结点下标
}
else if (huftree[j].parent == -1 && huftree[j].data < min2)
{
min2 = huftree[j].data;//min2记次最小权值
x2 = j;//x2记次最小权值结点下标
}
huftree[x1].parent = n + i;//将找出的两棵权值最小的子树合并
huftree[x2].parent = n + i;
huftree.insert(TriElement(huftree[x1].data + huftree[x2].data, -1, x1, x2));//添加第n+i个结点
}
cout << "Huffman树的结点顺序表：" << this->huftree;
}
MyString HuffmanTree::encode(int i)//返回charset[i]字符的编码字符串
{
MyString str;//以MyString字符串保存Huffman编码
int child = i, parent = huftree[child].parent;
while (parent != -1)//由叶结点向上直到根节点循环
{
str += (huftree[parent].left == child) ? '0' : '1';//左右孩子结点编码为0,1.+=连接串
child = parent;
parent = huftree[child].parent;
}
str.reverse();//将str串逆转，得到编码字符串
return str;
}
void HuffmanTree::printCode()//输出所有字符编码
{
cout << "Huffman 编码， ";
for (int i = 0; i < this->charset.count(); i++)//输出所有叶子结点的Huffman编码
cout << this->charset[i] << ":" << encode(i) << ",";
cout << endl;
}
MyString HuffmanTree::encode(MyString& text)//返回将text中所有字符压缩的编码字符串
{
MyString codestr;
for (int i = 0; i < text.count(); i++)
codestr += encode(text[i] - 'A');//默认字符集是从A开始的n个字符串
return codestr;
}
MyString HuffmanTree::decode(MyString& codestr)//返回将编码串str解压后的译码字符串
{
MyString text;
int node = this->huftree.count() - 1;//node搜索一条从根到达叶子的路径
for (int i = 0; i < codestr.count(); i++)
{
if (codestr[i] == '0')
node = huftree[node].left;
else node = huftree[node].right;
if (huftree[node].isLeaf())//到达叶子结点
{
text += this->charset[node];//获得一个字符
node = this->huftree.count() - 1;//node再从根节点开始
}
}
return text;
}