Huffman-encoding

刚学还热乎的算法

• 哈夫曼（Huffman）编码

Prefix Codes (前缀码)

考虑使用不同长度的 bit string 来编码不同的字符串，其中一种保证没有一个 bit string 对应两个及以上的字符串的编码叫做 prefix codes（前缀码）。
prefix code 可以通过二叉树来表示，每一个树中的叶节点的标签即为对应的字符串，而一条连接 left child 的边的标签被指定为 ，对应的连接 right child 的边的标签为 。那么，一个字符串对应的 bit string 为从根到该叶节点的唯一通路上的边的标签的序列。

例子

Kenneth Rosen - Discrete Mathematics and Its Applications - 8th edition - Chapter 11.2 - Figure 5

对于这棵树，其中 对应的编码分别是

Huffman Coding

那么哈夫曼编码是什么呢？其实是为了解决生成一颗比较"好"的 Prefix Tree，来实现更短的 bit string 编码长度，哈夫曼编码是一种基本的数据压缩算法，通过压缩编码长度，我们便能减小压缩文件的大小。

原理

先给出算法的伪代码

Kenneth Rosen - Discrete Mathematics and Its Applications - 8th edition - Chapter 11.2 - Algorithm2

这是一个贪心的算法，其通过某个字符串出现的频率（概率）来建立前缀树，容易知道，我们如果让出现频率越高的字符的编码越短，那么压缩比自然就越大，而这个算法实现中，是从叶节点建起，也就是每次将两子树合并到一个新的根节点上，那么可以知道，因为越先合并的节点，在树的越深的层，也就意味着更长的编码，那么反向思维，我们应该先从出现频率低的字符开始。由此来保证每次两个子树的总权重（出现频率）和是最小的，于是可以获得一个全局最优。

这有一个值得注意的问题：这里给出的算法并未指定存在两子树权重相等时的行为，在实际实现中应当指定，但这并不会影响编码效果。

M-ary Huffman Coding（m 叉树的 huffman Coding）

m 叉树的的算法与二叉树并不完全相同

m-ary

其中主要差别在于对于 -ary， 个符号的编码体系，在初始步骤中，由权重最小的单个顶点组成的 棵树被组合成一棵以这些顶点为叶子的有根树。

根据定义: A vertex of a rooted tree is called a leaf if it has no children.
一棵树只有 个 vertex（root），似乎也能被称作 leaf.

对于 的情况，其实 ，那么其实合成一颗 个叶子节点的有根树我们只需要将它本身作为根节点即可（ 因为如果我们构造一颗 2 个顶点，由一个根节点连接一个叶节点的树时，到这个叶节点的路径上就多了一条边，这条边是可以省去的，这样是成立的是对 来说的，当 时，编码无意义（），有效编码情况下应当是 ）。因此此时我们可以合并前两步，直接选择两个最小的权重作为叶节点并合并为一颗有根树。

对于 的情况，，当其不等于 时，按照计算得的个数建立有这么多个叶节点的根树，而等于 时，每一步都可以直接取 个最小权值作为叶节点。

实现

• 要图的结构，还是先放放