数据压缩(1) —— 概述

本节内容: 数据压缩,是指在不丢失信息的前提下,缩减数据量以减少存储空间,提高传输、存储和处理效率的一种技术方法。或者是按照一定的算法对数据进行重新组织,减少数据的冗余和存储的空间。本系列博文具体学习经典的压缩算法以及最近流行的算法,并应用到FASTQ下一代基因数据的压缩过程中。

压缩技术

压缩,是为了减少存储空间而把数据转换成比原始格式更紧凑形式的过程。能实现数据压缩的本质原因就是数据的冗余性。

无损压缩

无损压缩是指使用压缩后的数据进行重构(或者叫做还原,解压缩),重构后的数据与原来的数据完全相同;无损压缩用于要求重构的信号与原始信号完全一致的场合。一个很常见的例子是磁盘文件的压缩。根据目前的技术水平,无损压缩算法一般可以把普通文件的数据压缩到原来的1/2~1/4。一些常用的无损压缩算法有霍夫曼(Huffman)算法和LZW(Lenpel-Ziv & Welch)压缩算法。

有损压缩

有损压缩是指使用压缩后的数据进行重构,重构后的数据与原来的数据有所不同,但不会让人对原始资料表达的信息造成误解。有损压缩适用于重构信号不一定非要和原始信号完全相同的场合。例如,图像和声音的压缩就可以采用有损压缩,因为其中包含的数据往往多于我们的视觉系统和听觉系统所能接收的信息,丢掉一些数据而不至于对声音或者图像所表达的意思产生误解,但可大大提高压缩比。

性能测量

  • 压缩比:压缩前后数据文件的大小比较

  • 压缩/解压时间:压缩/解压缩文件所需要的时间

  • 并行化:利用多核CPU或多线程实现加速

  • 失真: 有损压缩中原数据与重构结果之间的差别

信息论与熵编码

数据模型

信息的定义是度量一个数据片段复杂度的量。一个数据集拥有越多的信息,它就越难被压缩。稀有的概念和信息的概念是相关的,因为稀有符号的出现比常见符号的出现提供了更多的信息。

我们把压缩算法降低信息负载的有效性,称为它的效率。一个效率更高的压缩算法相比效率低的压缩算法,能够更多地降低特定数据集的大小。

概率模型

设计一个压缩方案的最重要一步,是为数据创建一个概率模型。这个模型允许我们测量数据的特征,达到有效的适应压缩算法的目的。

熵定义为给定模型的最小编码率,它建立在字母表和它的概率模型之上:

$$H(G,P) = - \sum_{i=0}^nP(X_i)\log_2(P(X_i)) X_i \in G $$

拥有更多罕见符号的模型,比拥有较少并且常见符号的模型的熵要高。更进一步,熵值更高的模型比熵值低的模型更难压缩。

编码实例

Huffman压缩算法

huffman压缩算法可以说是无损压缩中最优秀的算法。它使用预先二进制描述来替换每个符号,长度由特殊符号出现的频率决定。其中出现次数比较多的符号需要很少的位来表示,而出现次数较少的符号则需要较多的位来表示。

huffman压缩算法的原理:利用数据出现的次数构造Huffman二叉树,并且出现次数较多的数据在树的上层,出现次数较少的数据在树的下层。于是,我们就可以从根节点到每个数据的路径来进行编码并实现压缩。

如:

符号 概率 码子
B 0.4 0
D 0.3 10
A 0.2 110
C 0.1 111

平均编码率显著地降低到了1.9比特/符号.

字典方法

这种类型的编码器使用一个字典来保存最近发现的符号。当遇到一个符号时,首先会在字典中查找它,检查是否已经存储过了。如果是,那么输出将只包含字典入口的引用(通常是一个偏移量),而不是整个符号。

使用字典方法的压缩方案包括LZ77 and LZ78,它们是很多不同的无损压缩方案的基础。

在一些情况下,会使用一个滑动窗口来自适应地追踪最近发现的符号。这种情况下,一个符号只在相对较近发现时才会保存在字典中。否则,符号被剔除(之后再出现可能会重新加入字典)。这个过程防止符号字典变得过大,并利用了一个事实,即序列中的符号会在相对短的窗口内重复出现。

算术编码

算术编码是一种无损数据压缩方法,也是一种熵编码的方法。和其它熵编码方法不同的地方在于,其他的熵编码方法通常是把输入的消息分区为符号,然后对每个符号进行编码,而算术编码是直接把整个输入的消息编码为一个数,一个满足(0.0 ≤ n < 1.0)的小数n。

游程编码

统计某一节字节在整个字节表中出现的次数,并以该字节和出现的次数作为编码的依据。

如:输入字符ASSDDRRZZZZZO => A1S2D2R2Z5O1

对于上述方法,有人提出:如果字节表中出现连续不重复的数据,就会因为设置太多的字节次数为而达不到压缩的效果。 再想的坏一点,如果字符表中的各个字符只出现一次,也就是全部不重复,那么经过RLE编码之后,不仅没有实现压缩, 反倒是增加了一倍。比如“ABCDEFG”,如果用上述方法,那么经过压缩后应为:A1B1C1D1E1F1G1,针对上述问题, 人们对算法做了一些改进。

改进算法的核心思想是:我们知道一个字节是八位,那么用最高位来当做一个标志位,这个标志位如果为1, 则表示后面跟的是重复的数据,如果为0则表示后面跟的是非重复的数据;我们用低七位来表示这个数据重复的次数。 用下一个字节来表示这个字节数据。

如输入AAABBBBBCABCDDD=>0X83 A 0X85 B 0X41 C A B C 0X83 D

增量编码

对于给定一系列增量数字,如[0,1,2,3,4,5,6,7] => [0,1,1,1,1,1,1,1],熵减为1

符号分组

S = "TOBEORNOTTOBEORTOBEORNOT" => [TO,BE,OR,NOT] , H(S)=1.98

排列

B [5, 7, 1, 4, 6, 3, 2, 0][0,1,2,3,4,5,6,7]的一个排列,对其采用擦除码(Elimination Coding)编码,结果如下:

擦除码实例