熵编码

概述

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

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

霍夫曼编码

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

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

EXAMPLE

现在有四个叶节点：

• A：8
• B：6
• C：4
• D：1

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

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

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

整棵树的编码为：

• A：0
• B：10
• C：110
• D：111

构建最优二叉树的原理

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

然后再次重复这个过程，如果构成的新节点依然是最小的两个节点之一，那么构成的就是一个类似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（0,0.25），B（0.25,0.45），C（0.45,0.5）

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

• A（0,0.125），B（0.125,0.225），C（0.225,0.25）

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

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

解码原理

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

• 第一次解码，数字处在A的区间内，得到A，同时以A为目标区间进行划分得到
  • A（0,0.25），B（0.25,0.45），C（0.45,0.5）
• 第二次解码，数字处在A的区间内，得到A，同时以A为目标区间进行划分得到
  • A（0,0.125），B（0.125,0.225），C（0.225,0.25）
• 第三次解码，数字处在B的区间内，得到B，同时以B为目标区间进行划分
• 继续进行重复操作

对比

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

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