数据结构——哈夫曼(Huffman)树+哈夫曼编码

哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码（有时也称为霍夫曼编码）。
##哈夫曼的思考

想要找到一个成绩所处的等级，都需要从60开始判断，

成绩?比重: 在70~89分之间占?用了了70% 但是都是需要经过3次判断才能得到正 确的结果. 那么如果数量量集?非常?大时,这样的?比较就会出现效率问题.

思考:

1. 结点D 的路路径?长度是?
   2.树的路路径?长度?

定义:
给定n个权值作为n个叶子结点，构造一棵二叉树，若树的带权路径长度达到最小，则这棵树被称为哈夫曼树。
####(01) 路径和路径长度
?定义：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。 例子：100和80的路径长度是1，50和30的路径长度是2，20和10的路径长度是3。

####(02) 结点的权及带权路径长度
? 定义：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。 例子：节点20的路径长度是3，它的带权路径长度= 路径长度 * 权 = 3 * 20 = 60。

####(03) 树的带权路径长度
?定义：树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。

sum = 1+1+2+2+3+3+4+4 = 20 A =1
A’ = 1
B =2
B’ = 2 C =3 C’ = 3 D =4 E =4

但是上面我们根据概率统计发现CD连个区域的概率相对来说是大一点的,重新规划一下书的结构

sum = 1+2+3 +3 +2 +1 + 2 + 2 = 16 B’ = 1
A’ = 2
A =3sum < 80
B =3 C =2 C’ = 1 D =2 E =2

最后我们可以发现
?1的WPL = 1 * 5 + 2 * 15 + 3 *40 +4 * 30 + 4 * 10 = 315
?2的WPL = 5 * 3 + 15 * 3 + 40 * 2 + 30 * 2 +10 * 2 = 220
所以?2的WPL就比?1的WPL小很多
##如何创建一个哈夫曼树

1. 所有的权重进行排序
2. 去除最小的两个权重，按照左子树永远小于右子树，如果相等的情况下依然左子树的优先级高，合成一个新的结点
   3.如果遇见新的结点的权重大于剩余权重的最小者，那么新结点就变成了右子树，一次合并成为新的一个?
3. 如果新结点比剩余权重的两个以上都大，那么 剩余权重可以重新合成一个树，最后按照左子树小于等于右子树的规则合并成为一个?

####case 2
A 000 27
B 001 8
C 010 15
D 011 15
E 100 30
F 101 5

然后重新进行编码
BADCADFEED 编码
原编码?二进制: 001 000 011 010 000 011 101 100 100 011(共30个字符)
新编码?二进制: 1001 01 00 101 01 00 1001 11 11 00(共25个字符)

##哈夫曼树的结点的形式:

const int MaxValue = 10000;//初始设定的权值最大值
const int MaxBit = 4;//初始设定的最大编码位数
const int MaxN = 10;//初始设定的最大结点个数typedef struct HaffNode{int weight;int flag;int parent;int leftChild;int rightChild;
}HaffNode;

##根据权重值,构建哈夫曼树;

//
//{2,4,5,7}
//n = 4;
void Haffman(int weight[],int n,HaffNode *haffTree){int j,m1,m2,x1,x2;//1.哈夫曼树初始化//n个叶子结点. 2n-1for(int i = 0; i < 2*n-1;i++){if(i<n)haffTree[i].weight = weight[i];elsehaffTree[i].weight = 0;haffTree[i].parent = 0;haffTree[i].flag = 0;haffTree[i].leftChild = -1;haffTree[i].rightChild = -1;}//2.构造哈夫曼树haffTree的n-1个非叶结点for (int i = 0; i< n - 1; i++){m1 = m2 = MaxValue;x1 = x2 = 0;//2,4,5,7for (j = 0; j< n + i; j++)//循环找出所有权重中，最小的二个值--morgan{if (haffTree[j].weight < m1 && haffTree[j].flag == 0){m2 = m1;x2 = x1;m1 = haffTree[j].weight;x1 = j;} else if(haffTree[j].weight<m2 && haffTree[j].flag == 0){m2 = haffTree[j].weight;x2 = j;}}//3.将找出的两棵权值最小的子树合并为一棵子树haffTree[x1].parent = n + i;haffTree[x2].parent = n + i;//将2个结点的flag 标记为1,表示已经加入到哈夫曼树中haffTree[x1].flag = 1;haffTree[x2].flag = 1;//修改n+i结点的权值haffTree[n + i].weight = haffTree[x1].weight + haffTree[x2].weight;//修改n+i的左右孩子的值haffTree[n + i].leftChild = x1;haffTree[n + i].rightChild = x2;}}

##哈夫曼编码代码实现

typedef struct Code//存放哈夫曼编码的数据元素结构
{int bit[MaxBit];//数组int start;  //编码的起始下标int weight;//字符的权值
}Code;

##哈夫曼编码
哈夫曼树的实现思路路:

1. 获取根据权值构建的哈夫曼树
2. 循环遍历[0,n]个结点;
3. 创建临时结点cd ,从根结点开始对?齐进?行行编码,左孩?子为0,右孩?子为1; 4. 将编码后的结点存储haffCode[i]
4. 设置HaffCode[i]的开始位置以及权值;

/*9.2 哈夫曼编码由n个结点的哈夫曼树haffTree构造哈夫曼编码haffCode//{2,4,5,7}*/
void HaffmanCode(HaffNode haffTree[], int n, Code haffCode[])
{//1.创建一个结点cdCode *cd = (Code * )malloc(sizeof(Code));int child, parent;//2.求n个叶结点的哈夫曼编码for (int i = 0; i<n; i++){//从0开始计数cd->start = 0;//取得编码对应权值的字符cd->weight = haffTree[i].weight;//当叶子结点i 为孩子结点.child = i;//找到child 的双亲结点;parent = haffTree[child].parent;//由叶结点向上直到根结点while (parent != 0){if (haffTree[parent].leftChild == child)cd->bit[cd->start] = 0;//左孩子结点编码0elsecd->bit[cd->start] = 1;//右孩子结点编码1//编码自增cd->start++;//当前双亲结点成为孩子结点child = parent;//找到双亲结点parent = haffTree[child].parent;}int temp = 0;for (int j = cd->start - 1; j >= 0; j--){temp = cd->start-j-1;haffCode[i].bit[temp] = cd->bit[j];}//把cd中的数据赋值到haffCode[i]中.//保存好haffCode 的起始位以及权值;haffCode[i].start = cd->start;//保存编码对应的权值haffCode[i].weight = cd->weight;}
}

测试结果

    int i, j, n = 4, m = 0;//权值int weight[] = {2,4,5,7};//初始化哈夫曼树, 哈夫曼编码HaffNode *myHaffTree = malloc(sizeof(HaffNode)*2*n-1);Code *myHaffCode = malloc(sizeof(Code)*n);//当前n > MaxN,表示超界. 无法处理.if (n>MaxN){printf("定义的n越界，修改MaxN!");exit(0);}//1. 构建哈夫曼树Haffman(weight, n, myHaffTree);//2.根据哈夫曼树得到哈夫曼编码HaffmanCode(myHaffTree, n, myHaffCode);//3.for (i = 0; i<n; i++){printf("Weight = %d\n",myHaffCode[i].weight);for (j = 0; j<myHaffCode[i].start; j++)printf("%d",myHaffCode[i].bit[j]);m = m + myHaffCode[i].weight*myHaffCode[i].start;printf("\n");}printf("Huffman's WPS is:%d\n",m);