哈夫曼树

· · 个人记录

哈夫曼编码有等长和不等长之分。

等长

---- ### 不等长 要求： - 频率越高，长度越短； - 一个字符编码不能是另一个字符编码前缀，即不能有二义性； - 编码只有$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 ```