霍夫曼树以及哈夫曼编码

一、什么是哈夫曼树与哈夫曼编码

1. 编码是什么
   答:
   在ASCII 编码中
   ‘a’ = 97 = $(01100001{)}_2$
   ‘0’ = 48 = $(00110000{)}_2$
   注意：任何信息，在计算机中，都是二进制存储的

ASCII编码规则下的信息：“aa00” = 0110 0001、01100001、00110000、00110000
信息的价值在于流通，从一台计算机 传输到 另外一台计算机，传输上面信息，需要传输32个比特位
假设:计算机的网络带宽是32bit/s, 传上述信息，用时：1s

在特定场景中：假设需要传输的只有a,b,0,1四种字符需要传输
重新编排编码a:00, b:01, 0:10, 1:11
自定义规则下的信息“aa00” = 00 00 10 10
在带宽不变的情况下，当前只需要传输0.25s
在相同传输的数据量下，越好的编码方式，传输的效率越快 -> (各个直播平台相同网络下，流畅度的区别)

2. 定长与变长编码
   1. ASCII 编码和刚刚特定场景下的编码，都属于定长编码
   2. 对于每一种字符，编码长度相同，这就是定长编码
   3. UTF-8编码，是变长编码，UTF-16，是定长编码
   4. 对于每一个字符，编码长度不相同，这就是变长编码
   5. 将定长编码，看成时变长编码的特例
   6. 变长编码，一定不差于定长编码

变长编码应用场景
特定场景：

1. 只有四种字符：ab01
2. P(a) = 0.8, P(b) = 0.05, P© = 0.1, P(1) = 0.05
   平均编码长度：
   $l_i$:第i中字符，编码长度
   $p_i$:第i中字符，出现概率
   $avg(l)=\sum l_i\times p_i$

假设，平均编码长度：1.16，估算传输100个字符，需要传输116个比特位
上述编码的平均编码长度：$avg(l)=2\ast \sum p_i=2$
新建编码：出现概率大的编码长度短，出现概率小的编码长度长
新·编码 a : 1 b : 01 0：000 1：001 （问题1：为什么b的编码不能时‘10’）
平均编码长度： $1\ast 0.8+2\ast 0.05+3\ast 0.1+3\ast 0.05=1.35$
意味着，传输100个字符的期望值为135比特位
优秀的编码都是根据特定场景做的优化

问题1：为什么b的编码不能是10？
解码过程，遇到和字典中匹配的字符，立刻解析字符，则当b为10的时候，碰到110，会解析为aa0  b与a冲突

哈夫曼树的建立

每一次从集合中选出两个概率最低的节点，将他们合并成一棵子树，
并将新生成的节点，放回到原集合种

哈夫曼编码

	1. 首先，统计得到每一种字符的概率2. 将n个字符，建立成一棵哈夫曼树3. 每一个字符，都落在叶子节点上4. 按照左0，右1的形式，将编码取出来a : 0.8  b:0.05  0 : 0.1  1 : 0.05***因为所有字符都落在叶子节点上，所以没有任何一个字符时另一个字符的前缀***

得到新编码
a: 0
0: 10
b: 110
c : 111
哈夫曼编码，平均编码长度：$ 1 * 0.8 + 2 * 0.1 + 3 * 0.05 + 3 * 0.05 = 1.3$

结论：哈夫曼编码时最优的变长编码 （下述证明）

二、为什么哈夫曼编码是最优的变长编码（不想了解的可以直接下一步qwq）

设 P(a) : 0.25 ,P(b) : 0.25 ,P© : 0.25 ,P(d) : 0.25
则构成的哈夫曼树为：

当P(a) = P(b) = P© = P(d) 时，哈夫曼编码退化为变长编码
所以，定长编码做的好，哈夫曼编码一定做的好，甚至做的更好

证明

证明那个指标最优？ 平均编码长度最优， $\sum p_i\times l_i$最小
当所有字符在叶子节点上

若仅需4个编码，则需在当前的哈夫曼树中选4个节点

越往上的节点，覆盖节点越多，
越往下的节点，覆盖节点越少。
对于某个节点覆盖子节点的数量为$2^{H-l}$

手写推导

熵：$-\sum p_i\log p_i$ 在系统种，最小的平均信息，表示单元的长度（平均编码长度）
熵越大，系统越复杂

引出
交叉熵$-\sum p_i\log q_i$
$-\sum p_i\log q_i$ 越小，$p_i,q_i$越相似 ， $p_i=q_i$时，最小
$-\sum p_i\log q_i$ 越大，$p_i,q_i$相差的越多

对照推导中
概率越高($p_i$) $L_i$ 越大,
$l_i‘=-l_i=\log L_i$ $-l_i$ 越大 $l_i$越小 则，概率越大，路径长度越小

推到过程

1.首先表示平均每编码长度，秋节公式最优解
2.最终，和熵与交叉熵的关系

tips：
这个证明也不是很严谨的，因为哈夫曼编码是离散的，这个证明是连续的

三、霍夫曼树的代码演示

#include <stdio.h>
#include <stdlib.h>#define swap(a, b) {\__typeof(a) __c = a;\a = b,b = __c;\
}
typedef struct Node {char ch;//字符double p;//出现的概率struct Node *lchild, *rchild;
} Node ;Node *getNewNode(char ch, double per) {Node *p = (Node *)malloc(sizeof(Node));p->ch = ch;p->p = per;p->lchild = p->rchild = NULL;return p;
}Node *CombinNode (Node *a, Node *b) {//合并最小的两个节点Node *p = getNewNode(0, a->p + b->p);p->lchild = a;p->rchild = b;return p;
}void pick_min(Node **arr, int n) {for (int j = n - 1; j >= 0; --j) {if (arr[n]->p > arr[j]->p) {swap(arr[n], arr[j]);}}return ;
}Node *getHaffmanTree(Node **arr, int n) {for (int i = 1; i < n; i++) {//n个字符，需要合并n - 1次pick_min(arr, n - i);//最小的放在n - i处pick_min(arr, n - i - 1);//第2小的放在n - i - 1处arr[n - i - 1] = CombinNode(arr[n - i], arr[n - i - 1]);}//也可以用优先队列简化代码return arr[0];//最后剩下的头节点，就是haffman树的根节点
}void __output_encode(Node *root, char *str, int k) {//k为层数str[k] = 0;if (root->lchild == NULL && root->rchild == NULL) {//遇到根节点输出printf("%c %s\n", root->ch, str);return ;}str[k] = '0';//左子树为0__output_encode(root->lchild, str, k + 1);str[k] = '1';//右子树为1__output_encode(root->rchild, str, k + 1);return ;
}void output_encode(Node *root) {char str[100];__output_encode(root, str, 0);return ;
}void clear(Node *root) {if (root == NULL) return ;clear(root->lchild);clear(root->rchild);free(root);return ;
}int main() {int n;Node **arr;scanf("%d", &n);arr = (Node **)malloc(sizeof(Node *) * n);for (int i = 0; i < n; i++) {char ch[10];double p;scanf("%s%lf", ch, &p);arr[i] = getNewNode(ch[0], p);}Node *root = getHaffmanTree(arr, n);output_encode(root);clear(root);free(arr);return 0;
}

代码运行结果图