哈夫曼树
inoichi_lim
2020-04-05 14:44:30
哈夫曼编码有等长和不等长之分。
### 等长
$n$个编码最多可以放$2^n$个字符。
----
### 不等长
要求:
- 频率越高,长度越短;
- 一个字符编码不能是另一个字符编码前缀,即不能有二义性;
- 编码只有$0$和$1$.
---
### 哈夫曼树
假如说现在有一个字符串`aaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbcdddfee`
则里面的`a`有$3$个,`b`有$30$个,`c`有$1$个,`d`$3$个,`e`$2$个,`f`$1$个。
则我们编码规则左$0$右$1$。
那么我们先去两个最小的字符`c`,`f`,构成节点如下所示:
`c1 f1`,合并得
```
[]2
/ \
c1 f1
```
再选一个最小的:
```
[]4
/ \
[]2 e2
/ \
c1 f1
```
递归即可。
成果:
```
[]40
/ \
[]10 a30
/ \
[]7 d3
/ \
[]4 a3
/ \
[]2 e2
/ \
c1 f1
```