信息论基础结课论文——不同压缩编码方法的适用场景

作者

yelexin

关键词

信息论，压缩，编码

摘要

许多经典压缩算法基于算数编码、PPM 编码、LZ 编码。在不同的压缩对象上有着不同的压缩效果，本文对这些常见的压缩编码在处理不同的压缩对象时的压缩率、速度表现进行比较。

绪论

我们会接触许多类型的文件，例如文本、文字图像、自然图像等。在传输这些信息的过程中，往往会对先数据进行压缩。对不同特征的数据，合理运用压缩方法，能够达到最佳压缩率。我们也会发现，对信息多次使用不同的压缩算法，并不能达到更好的压缩效果。

1.1 算术编码

算术编码是一种无损数据压缩方法，也是一种熵编码的方法。和其它熵编码方法不同的地方在于，其他的熵编码方法通常是把输入的消息分割为符号，然后对每个符号进行编码，而算术编码是直接把整个输入的消息编码为一个数，一个满足（0.0 ≤ n < 1.0）的小数 n。在给定符号集和符号概率的情况下，算术编码可以给出接近最优的编码结果。使用算术编码的压缩算法通常先要对输入符号的概率进行估计，然后再编码。这个估计越准，编码结果就越接近最优的结果。

1.2 PPM 编码

PPM(Prediction by Partial Matching)是一种上下文统计模型编码技术，其基本思想就是利用最近输入的几个字符(叫做上下文模型) ，来预测下一个字符。其中，模型的长度k可以从0到已输入字符的最大长度km不等。PPM算法分为建模和编码两个过程，对于k长度的上下文模型来说，首先要计算在输入字符串中，每个k长度的字符串后面不同字符出现的次数，然后可以得到该上下文模型的预测概率，即为建模过程。定义一个已知字符串模型的最大长度为k，当下一个输入的字符已经由该上下文模型预测出时，该输入字符出现的概率就是预测概率。而当下一个字符不能由上下文模型预测出时，输入字符的概率无法得到，这时，就需要用到“逃逸(escape)”概率。添加逃逸上下文预测模型是为了防止零概率字符的情况出现。“逃逸”概率将模型从k跳到k-1，如果k-1长度的模型能预测出该字符，就能得到相应的预测概率。如果不能，该过程将一直进行直到某个模型可以预测出该字符。为了保证无论出现什么字符，最后“逃逸”过程都能结束，最低长度的模型中必须包括字母表中所有的字符。逃逸上下文预测模型概率的计算方法有多种，每一种方法对应PPM一种类型。

1.3 LZ 编码

LZ77与LZ78是Abraham Lempel与Jacob Ziv在1977年以及1978年发表的论文中的两个无损数据压缩算法。这两个算法是大多数LZ算法变体如LZW、LZSS以及其它一些压缩算法的基础。与最小冗余编码器或者行程长度编码器不同，这两个都是基于字典的编码器。LZ77是“滑动窗”压缩算法，这个算法后来被证明等同于LZ78中首次出现的显式字典编码技术。
LZ77算法通过使用编码器或者解码器中已经出现过的相应匹配数据信息替换当前数据从而实现压缩功能。这个匹配信息使用称为长度-距离对的一对数据进行编码，它等同于“每个给定长度个字符都等于后面特定距离字符位置上的未压缩数据流。”（“距离”有时也称作“偏移”。）

编码器和解码器都必须保存一定数量的最近的数据，如最近2 KB、4 KB或者32 KB的数据。保存这些数据的结构叫作滑动窗口，因为这样所以LZ77有时也称作滑动窗口压缩。编码器需要保存这个数据查找匹配数据，解码器保存这个数据解释编码器所指代的匹配数据。所以编码器可以使用一个比解码器更小的滑动窗口，但是反过来却不行。

1.4 JPG 压缩

联合图像专家小组（英语：Joint Photographic Experts Group，缩写：JPEG）是一种针对照片影像而广泛使用的有损压缩标准方法。这个名称代表。此团队创立于1986年，1992年发布了JPEG的标准而在1994年获得了ISO 10918-1的认定。JPEG与视频音频压缩标准的MPEG（Moving Picture Experts Group）很容易混淆，但两者是不同的组织及标准。

色彩空间转换

首先，影像由RGB（红绿蓝）转换为一种称为YUV的不同色彩空间。这与模拟PAL制式彩色电视传输所使用的色彩空间相似，但是更类似于MAC电视传输系统运作的方式。但不是模拟NTSC，模拟NTSC使用的是YIQ色彩空间。

Y成分表示一个像素的亮度
U和V成分一起表示色调与饱和度。
YUV分量可以由PAL制系统中归一化（经过伽马校正）的R’,G’,B’经过下面的计算得到：

Y=0.299R’+0.587G’+0.114B’
U=-0.147R’-0.289G’+0.436B’
V=0.615R’-0.515G’-0.100B’
这种编码系统非常有用，因为人类的眼睛对于亮度差异的敏感度高于色彩变化。使用这种知识，编码器（encoder）可以被设计得更有效率地压缩影像。

缩减取样（Downsampling）

上面所作的转换使下一步骤变为可能，也就是减少U和V的成分（称为"缩减取样"或"色度抽样"（chroma subsampling）。在JPEG上这种缩减取样的比例可以是4:4:4（无缩减取样），4:2:2（在水平方向2的倍数中取一个），以及最普遍的4:2:0（在水平和垂直方向2的倍数中取一个）。对于压缩过程的剩余部分，Y、U、和V都是以非常类似的方式来个别地处理。

离散余弦变换（Discrete cosine transform）

下一步，将影像中的每个成分（Y, U, V）生成三个区域，每一个区域再划分成如瓷砖般排列的一个个的8×8子区域，每一子区域使用二维的离散余弦变换（DCT）转换到频率空间。

量化（Quantization）

人类眼睛在一个相对大范围区域，辨别亮度上细微差异是相当的好，但是在一个高频率亮度变动之确切强度的分辨上，却不是如此地好。这个事实让我们能在高频率成分上极佳地降低信息的数量。简单地把频率领域上每个成分，除以一个对于该成分的常量就可完成，且接着舍位取最接近的整数。这是整个过程中的主要有损运算。以这个结果而言，经常会把很多更高频率的成分舍位成为接近0，且剩下很多会变成小的正或负数。