压缩算法

认识压缩算法
想必都有过压缩和解压缩文件的经历，当文件太大时，我们会使用文件压缩来降低文件的占用空间。比如微信上传文件的限制是100MB，有个文件夹无法上传，但是我解压完成后的文件一定会小于100MB，那么我的文件就可以上传了。

此外，我们把相机拍完的照片保存到计算机上的时候，也会使用压缩算法进行文件压缩，文件压缩的格式一般是JPEG。

那么什么是压缩算法呢？压缩算法又是怎么定义的呢？在认识算法之前我们需要先了解一下文件是如何存储的。

文件存储
文件是将数据存储在磁盘等存储媒介的一种形式。程序文件中最基本的存储数据单位是字节。文件的大小用xxxKB、xxxMB等来表示，就是因为文件是以字节B = Byte 为单位来存储的。

文件就是字节数据的集合。用1字节(8 位)表示的字节数据有256种，用二进制表示的话就是00000000-11111111。如果文件中存储的数据是文字，那么该文件就是文本文件。如果是图形，那么该文件就是图像文件。在任何情况下，文件中的字节数都是连续存储的。

压缩算法的定义
上面介绍了文件的集合体其实就是一堆字节数据的集合，那么我们就可以来给压缩算法下一个定义。压缩算法(compaction algorithm) 指的就是数据压缩的算法，主要包括压缩和解压缩的两个步骤。

其实就是在不改变原有文件属性的前提下，降低文件字节空间和占用空间的一种算法。根据压缩算法的定义，我们可将其分成不同的类型。

有损和无损

• 无损压缩
  能够无失真地从压缩后的数据重构，准确地还原原始数据。可用于对数据的准确性要求严格的场合，如可执行文件和普通文件的压缩、磁盘的压缩，也可用于多媒体数据的压缩。该方法的压缩比较小。如差分编码、RLE、 Huffman编码、LZW编码、算术编码。
• 有损压缩
  有失真，不能完全准确地恢复原始数据，重构的数据只是原始数据的一个近似。可用于对数据的准确性要求不高的场合，如多媒体数据的压缩。该方法的压缩比较大。例如预测编码、音感编码、分形压缩、小波压缩、JPEG/MPEG。
• 对称性
  如果编解码算法的复杂性和所需时间差不多，则为对称的编码方法，多数压缩算法都是对称的。但也有不对称的，一 般是编码难而解码容易，如Huffman编码和分形编码。但用于密码学的编码方法则相反，是编码容易，而解码则非常难。
• 帧间与帧内
  在视频编码中会同时用到帧内与帧间的编码方法，帧内编码是指在一帧图像内独立完成的编码方法，同静态图像的编码，如JPEG；而帧间编码则需要参照前后帧才能进行编解码,并在编码过程中考虑对帧之间的时间冗余的压缩，如MPEG。
• 实时性
  在有些多媒体的应用场合，需要实时处理或传输数据(如现场的数字录音和录影、播放MP3/RMVCD/DVD、视频/音频点播、网络现场直播、可视电话、视频会议)， 编解码一般要求延时≤50 ms。这就需要简单/快速/高效的算法和高速/复杂的CPU/DSP芯片。
• 分级处理
  有些压缩算法可以同时处理不同分辨率、不同传输速率、不同质量水平的多媒体数据，如JPEG2000、MPEG-2/4。

这些概念有些抽象，主要是为了让大家了解一下压缩算法的分类，下面我们就对具体的几种常用的压缩算法来分析一下它的特点和优劣。

RLE算法的机制
接下来就让我们正式看一下文件的压缩机制。 首先让我们来尝试AAAAAABBCDDEEEEEF 这17个半角字符的文件(文本文件) 进行压缩。虽然这些文字没有什么实际意义，但是很适合用来描述RLE 的压缩机制。

由于半角字符(其实就是英文字符)是作为1个字节保存在文件中的，所以上述的文件的大小就是17字节。如图：

那么，如何才能压缩该文件呢？大家不妨也考虑一下，只要是能够使文件小于17字节，我们可以使用任何压缩算法。

最显而易见的一种压缩方式我觉得你已经想到了，就是把相同的字符去重化，也就是字符* 重复次数的方式进行压缩。所以上面文件压缩后就会变成下面这样：

从图中我们可以看出，AAAAAABBCDDEEEEEF 的17个字符成功被压缩成A6B2C1D2E5F1的12个字符，也就是12/ 17 = 70%，压缩比为70%，压缩成功了。

像这样，把文件内容用数据*重复次数的形式来表示的压缩方法成为RLE(Run Length Encoding, 行程长度编码)算法。RLE算法是一种很好的压缩方法，经常用于压缩传真的图像等。因为图像文件的本质也是字节数据的集合体，所以可以用RLE算法进行压缩。

RLE算法的缺点
RLE的压缩机制比较简单，所以RLE算法的程序也比较容易编写，所以使用RLE的这种方式更能让你体会到压缩思想，但是RLE只针对特定序列的数据管用，下面是RLE算法压缩汇总：

通过上表可以看出，使用RLE对文本文件进行压缩后的数据不但没有减小反而增大了！几乎是压缩前的两倍！因为文本字符种连续的字符并不多见。

就像上面我们探讨的这样，RLE 算法只针对连续的字节序列压缩效果比较好，假如有一连串不相同的字符该怎么压缩呢？比如说ABCDEFGHIJKLMNOPQRSTUVWXYZ ，26个英文字母所占空间应该是26个字节，我们用RLE压缩算法压缩后的结果为
A1B1C1D1E1F1G1H1I1J1K1L1M1N101P1Q1R1S1T1U1V1W1X1Y1Z1，所占用52个字节，压缩完成后的容量没有减少反而增大了！这显然不是我们想要的结果，所以这种情况下就不能再使用RLE进行压缩。

可逆压缩和非可逆压缩
最后，我们来看一下图像文件的数据形式。图像文件的使用目的通常是把图像数据输出到显示器、打印机等设备上。常用的图像格式有: BMP 、JPEG 、TIFF 、GIF 格式等。

• BMP :是使用 Windows自带的画笔来做成的一种图像形式
• JPEG:是数码相机等常用的一种图像数据形式
• TFF: 是一种通过在文件中包含"标签"就能够快速显示出数据性质的图像形式
• GIF: 是由美国开发的一种数据形式，要求色数不超过256个

图像文件可以使用前面介绍的RLE算法和哈夫曼算法，因为图像文件在多数情况下并不要求数据需要还原到和压缩之前一模一样的状态，允许丢失一部分数据。我们把能还原到压缩前状态的压缩称为可逆压缩，无法还原到压缩前状态的压缩称为非可逆压缩：

一般来说， JPEG格式的文件是非可逆压缩，因此还原后有部分图像信息比较模糊。GIF 是可逆压缩我们大家知道，计算机的五大基础部件是存储器、控制器 、运算器 、输入和输出设备 ，其中从存储功能的角度来看，可以把存储器分为内存和磁盘，内存我们上面已经介绍过了，那么下篇文章我们来介绍一下磁盘以及内存和磁盘的关系。