《数据压缩入门》笔记-Part 1-VLC

两个问题：

• 可通过用更少或更多的二进制位对某些符号编码来节省所需要的总空间；
• 当数据集中有重复符号时，方法不太有用。

在真实的数据集中，符号重复几乎无法避免。这就是为什么LOG2方法无法正确地表示一个数据集中所真正包含的信息内容。

摩尔斯码

1836年，3位美国人，画家Samuel F. B. Morse、物理学家Joseph Henry和机械师Alfred Vail，共同发明第一套电报系统。

英语中一些字母比其他字母用得更频繁。摩尔斯码为英语字母表中的每一个字符都分配或长或短的脉冲，某字母用得越频繁，其编码也就越短、越简单。

符号分配变长编码。，VLC最初实现之一，其目的则在于减少传输信息过程中所需要的总工作量。

概率、熵与码字长度

压缩数据要做的事情：给定一个数据集中的符号，将最短的编码分配给最可能出现的符号。

从表里得出的规律：

• 当$P(A)=P(B)$，也就是两个符号等可能出现时，数据集对应的熵取最大值 LOG2（符号的个数），此时数据集很难压缩；
• 其中一个符号出现的可能越大，数据集的熵值就越小，此时数据集也越容易压缩；
• 对只包含两个符号的数据集来说，两个符号互换概率不影响其熵值，可看到$H([0.9,0.1])$等于$H([0.1,0.9])$。

得到的启示：

• 随数据集的冗余度下降，它的熵在变大，其最大值为数据集中不同符号个数的LOG2值；
• 数据集中一个符号出现的概率越大，整个数据集的熵就越小，数据集也就越容易压缩；
• 码字的长度与符号的出现概率密切相关，而与符号本身没有太大关系。

VLC

对于给定的输入数据集，可先计算涉及的符号的出现概率，然后就可以通过VLC将字长最短的码字分配给最可能出现的符号，从而实现压缩数据。

存在两个问题没有解决：

• 怎样在应用程序中运用VLC来进行压缩呢？
• 对于给定的数据集，怎样构造VLC呢？

运用VLC

对数据进行VLC的3个步骤：

• 遍历数据集中的所有符号并计算每个符号的出现概率；
• 根据概率为每个符号分配码字，一个符号出现的概率越大，所分配的码字就越短；
• 再次遍历数据集，对每一个符号进行编码，并将对应的码字输出到压缩后的数据流中。

计算符号的概率：需要遍历数据集，并计算出每个符号出现的次数

为字符分配码字：根据出现的频数进行排序，给每个符号分配一个VLC，从VLC集中码字最短的开始。得出码字表，Codeword Table。

编码：处理完整个输入流之后，再将符号码字对应表添加到输出流的前面。

解码：编码的逆过程。由于码字的长度并非固定，解码时，会一二进制位一二进制位地读取数据，直到读取的二进制位流与其中的某个码字相匹配。一旦匹配，就会输出相应的符号，并继续读取下一个码字。

创建VLC

为了确保正确，在设计VLC集的码字时，必须考虑两个原则：

• 越频繁出现的符号，其对应的码字越短；
• 码字需满足前缀性质。

前缀性质：在某个码字被分配给一个符号之后，其他的码字就不能用该码字作为前缀。

换句话说，每个符号都能通过其码字前缀唯一地确定，只有这样，VLC才能正常工作。

前缀性质是VLC能正常工作所必须具有的性质。这也就意味着，与二进制表示相比，VLC要更长一些。

VLC示例

通用编码：Universal Codes，为正整数赋上一个长度可变的二进制码字。遵循原则：数值越小，其对应的码字也越短；基于一个假定：小整数比大整数出现得更频繁。

通用编码是一类特殊的前缀编码。每一种前缀编码都是唯一可译的和非奇异的。唯一可译码：Uniquely Decodable Codes。非奇异码：Nonsingular Codes。

二进制编码

习惯用$B(n)$来表示整数$n$的标准二进制表示，被称为beta编码或二进制编码，不满足前缀性质。

给定$0\sim n$的任意整数，都能用$1+floor(lb(n))$个二进制位来表示。即，只要提前知道$n$的值，就能通过固定长度表示法来避开前缀问题。如果不能提前知道数据集中有多少个不同的整数，就不能用固定长度表示法。

在纠错码方面，Elias教授1955年引入卷积码（convolutional codes），作为分组码（block codes）的一种替代方法。还建立二进制删除信道（binary erasure channel），并提出用纠错码的列表译码（list decoding of error-correcting codes）来代替唯一可译码。

一元码

任意正整数$n$，它的一元码表示都是$n-1$个1后面跟着1个0。

一元码满足前缀性质，因此可以将它作为VLC使用。

随着整数$n$加1，其一元码码字的长度也线性地加1，因此其码字的长度$L$总是等于$n$。而在二进制编码中，码字的长度每增加1个二进制位，能表示的整数则呈指数级增长。

因此，将一元码应用在那些前一个符号的出现概率是后一个符号2倍的数据集上，效果最佳。

解一元码时，只需要从输入流中一直读取直到遇到分隔符0，然后数一下1的个数再加上1，最后将这个值输出即可。

Elias Gamma编码

主要用于事先无法确定其上界的整数的编码，即不知道最大的整数会是多大。

最主要的思想是不再对整数直接编码，而是用其数量级作为前缀。这样一来，相应的码字就由两部分组成，即与此整数相当的2的次幂再加上余数。

与简单的一元编码类似，Elias Gamma编码对那些整数$n$的出现概率$P(n)=1/(2n^2)$的情形比较适用。

Elias Delta编码

Elias还在前面加上二进制的长度。

工作原理如下面步骤所示：

• 将要编码的数$n$用二进制表示；
• 数一下$n$的二进制位数，并将这个位数转化为二进制，作为C；
• 去掉$n$的二进制表示的最左边一位。可推断出这个值肯定是1；
• 将C的二进制表示加在去掉最左边一位后的$n$的二进制表示前；
• 在上一步骤所得的结果前加上C的二进制位数减1个0作为最终的编码。

其他编码方法

VLC存在以下问题，只能用于压缩数据流：

• 它们不按字节/字/整型对齐；
• 对于大的数值$n$，为方便解码，其码字长度的增长速度一般会超过$lb(n)$个二进制位；
• 解码速度很慢，每次只能读取一个二进制位。

避免压缩整数：escaping for compressed integers，1972年提出的概念。以此为基础的新的可变长度整数模型，在搜索引擎和其他海量数据系统中得到广泛应用。

Varint是一种表示整数的方法，它用一个或多个字节来表示一个整数，数值越小用的字节数越少，数值越大用的字节数越多。

该方法将几个字节连接起来表示整数，并用每个字节的MSB作为布尔标志，来判断当前的字节是否为该整数的最后一个字节；而每个字节的低7位则用来存储该数的二进制补码（two’s complement representation）。

Varint表示方法结合VLC的灵活性和现代计算机体系结构的高效率，是一种很好的混合方法。它既允许表示可变范围内的整数，同时还对自身的数据进行对齐以提高解码的效率，达到双赢。

最适合

当给定符号的概率分布期望不同时，这些VLC编码方法的表现也不同。

在为数据集选择一种VLC编码方法时，必须要先考虑数据集的整体大小和数据范围，并计算各个符号的出现概率。

在理想的概率设定下，符号总数相同时，使用不同的方法需要用多少二进制位来表示，如下图所示：