概述#

熵编码是一种独立于介质具体特征的无损数据压缩的方案。通过将输入的每一个字符分配一个唯一的前缀码，将输入的符号替换成对应的可变长度前缀无关的输出码来替代。

霍夫曼编码和算术编码是两种最常见的熵编码技术。

霍夫曼编码#

依据字符在整个文件中的出现概率进行编码。

统计所有字符的出现次数，作为节点的权。
树的路径长度：叶节点到根节点的距离
节点的带权路径长度：节点的权*路径长度
将所有叶节点的带权路径长度相加，就能得到整个二叉树的带权路径长度。
huffman-tree要求
- 所有节点都是叶节点。如果存在父节点，那么父节点编码是叶节点的前缀，就没法区别父节点和叶节点了。
- 能够出现的所有树中，带权路径长度最小。

现在有四个叶节点：

如果要构建最优二叉树，希望权比较大的节点出现在二叉树的靠近根节点的位置。

则二叉树从上到下依次是A，B，C，D。另外包括使得二叉树完整的空节点

整棵树的权为**8 * 1 + 6 * 2 + 4 3 +1 * 3 = 35*。

整棵树的编码为：

每次选取权最小的两个节点构成一个新的节点，认为这个节点是这两个节点的父节点，实际上是并不存在的空节点，但是这个节点代表着这两个节点的权。

然后再次重复这个过程，如果构成的新节点依然是最小的两个节点之一，那么构成的就是一个类似0,10,11这样的编码。

假设我们这里出现了三个字符ABC，ABC的概率分别是0.5，0.4，0.1。

我们规定A代表的区间是（0,0.5），B代表的区间是（0.5,0.9），C代表的区间是（0.9,1）。

现在输入的串为A A B A B C A B A B。

看到第一个输入字符为A，将此时A的区间作为目标区间，此时我们将原ABC的区间映射到输入字符A的区间中，也就是变成了

然后输入第二个字符为A，此时已经更新了A的区间，再次将原来的区间映射到目标区间(0,0.25)中。

继续进行操作，最终编码完成B之后，得到的目标区间是（0.1686, 0.16868）

在这个区间内随意选取一个数字，就是这一串的编码。

这个数字处在哪个区间内，就能解码出来哪个符号。

霍夫曼编码在编码时相对消耗资源，解码时需要显式的字典，用来对应每一个字符的二进制编码，需要额外空间但是解码需要的运行资源很少。

算术编码在编解码时都很消耗计算资源，并且需要大量的浮点运算，虽然不需要额外的存储空间，但是解码时对浮点运算能力的要求很高。