压缩格式有哪些（压缩文件的作用和目的）

　　我把自己以往的文章汇总成为了Github，欢迎各位大佬starhttps：github。comcrisxuanbestJavaer已提交此篇文章
　　此篇文章是《程序员需要了解的硬核知识》第五篇文章，历史文章请戳
　　程序员需要了解的硬核知识之内存
　　程序员需要了解的硬核知识之CPU
　　程序员需要了解的硬核知识之二进制
　　程序员需要了解的硬核知识之磁盘
　　之前的文章更多的介绍了计算机的硬件知识，会有一些难度，本篇文章的门槛会低一些，一起来看一下计算机中都有哪些压缩算法认识压缩算法
　　我们想必都有过压缩和解压缩文件的经历，当文件太大时，我们会使用文件压缩来降低文件的占用空间。比如上传文件的限制是100MB，我这里有个文件夹无法上传，但是我解压完成后的文件一定会小于100MB，那么我的文件就可以上传了。
　　此外，我们把相机拍完的照片保存到计算机上的时候，也会使用压缩算法进行文件压缩，文件压缩的格式一般是JPEG。
　　那么什么是压缩算法呢？压缩算法又是怎么定义的呢？在认识算法之前我们需要先了解一下文件是如何存储的文件存储
　　文件是将数据存储在磁盘等存储媒介的一种形式。程序文件中最基本的存储数据单位是字节。文件的大小不管是xxxKB、xxxMB等来表示，就是因为文件是以字节BByte为单位来存储的。
　　文件就是字节数据的集合。用1字节（8位）表示的字节数据有256种，用二进制表示的话就是0000000011111111。如果文件中存储的数据是文字，那么该文件就是文本文件。如果是图形，那么该文件就是图像文件。在任何情况下，文件中的字节数都是连续存储的。
　　压缩算法的定义
　　上面介绍了文件的集合体其实就是一堆字节数据的集合，那么我们就可以来给压缩算法下一个定义。
　　压缩算法（compactionalgorithm）指的就是数据压缩的算法，主要包括压缩和还原（解压缩）的两个步骤。
　　其实就是在不改变原有文件属性的前提下，降低文件字节空间和占用空间的一种算法。
　　根据压缩算法的定义，我们可将其分成不同的类型：
　　有损和无损
　　无损压缩：能够无失真地从压缩后的数据重构，准确地还原原始数据。可用于对数据的准确性要求严格的场合，如可执行文件和普通文件的压缩、磁盘的压缩，也可用于多媒体数据的压缩。该方法的压缩比较小。如差分编码、RLE、Huffman编码、LZW编码、算术编码。
　　有损压缩：有失真，不能完全准确地恢复原始数据，重构的数据只是原始数据的一个近似。可用于对数据的准确性要求不高的场合，如多媒体数据的压缩。该方法的压缩比较大。例如预测编码、音感编码、分形压缩、小波压缩、JPEGMPEG。
　　对称性
　　如果编解码算法的复杂性和所需时间差不多，则为对称的编码方法，多数压缩算法都是对称的。但也有不对称的，一般是编码难而解码容易，如Huffman编码和分形编码。但用于密码学的编码方法则相反，是编码容易，而解码则非常难。
　　帧间与帧内
　　在视频编码中会同时用到帧内与帧间的编码方法，帧内编码是指在一帧图像内独立完成的编码方法，同静态图像的编码，如JPEG；而帧间编码则需要参照前后帧才能进行编解码，并在编码过程中考虑对帧之间的时间冗余的压缩，如MPEG。
　　实时性
　　在有些多媒体的应用场合，需要实时处理或传输数据（如现场的数字录音和录影、播放MP3RMVCDDVD、视频音频点播、网络现场直播、可视电话、视频会议），编解码一般要求延时50ms。这就需要简单快速高效的算法和高速复杂的CPUDSP芯片。
　　分级处理
　　有些压缩算法可以同时处理不同分辨率、不同传输速率、不同质量水平的多媒体数据，如JPEG2000、MPEG24。
　　这些概念有些抽象，主要是为了让大家了解一下压缩算法的分类，下面我们就对具体的几种常用的压缩算法来分析一下它的特点和优劣几种常用压缩算法的理解RLE算法的机制
　　接下来就让我们正式看一下文件的压缩机制。首先让我们来尝试对AAAAAABBCDDEEEEEF这17个半角字符的文件（文本文件）进行压缩。虽然这些文字没有什么实际意义，但是很适合用来描述RLE的压缩机制。
　　由于半角字符（其实就是英文字符）是作为1个字节保存在文件中的，所以上述的文件的大小就是17字节。如图
　　（这里有个问题需要读者思考一下：为什么17个字符的大小是17字节，而占用空间却很大呢？这个问题此篇文章暂不讨论）
　　那么，如何才能压缩该文件呢？大家不妨也考虑一下，只要是能够使文件小于17字节，我们可以使用任何压缩算法。
　　最显而易见的一种压缩方式我觉得你已经想到了，就是把相同的字符去重化，也就是字符重复次数的方式进行压缩。所以上面文件压缩后就会变成下面这样
　　从图中我们可以看出，AAAAAABBCDDEEEEEF的17个字符成功被压缩成了A6B2C1D2E5F1的12个字符，也就是121770，压缩比为70，压缩成功了。
　　像这样，把文件内容用数据重复次数的形式来表示的压缩方法成为RLE（RunLengthEncoding，行程长度编码）算法。RLE算法是一种很好的压缩方法，经常用于压缩传真的图像等。因为图像文件的本质也是字节数据的集合体，所以可以用RLE算法进行压缩RLE算法的缺点
　　RLE的压缩机制比较简单，所以RLE算法的程序也比较容易编写，所以使用RLE的这种方式更能让你体会到压缩思想，但是RLE只针对特定序列的数据管用，下面是RLE算法压缩汇总
　　文件类型压缩前文件大小压缩后文件大小压缩比率文本文件14862字节29065字节199图像文件96062字节38328字节40EXE文件24576字节15198字节62
　　通过上表可以看出，使用RLE对文本文件进行压缩后的数据不但没有减小反而增大了！几乎是压缩前的两倍！因为文本字符种连续的字符并不多见。
　　就像上面我们探讨的这样，RLE算法只针对连续的字节序列压缩效果比较好，假如有一连串不相同的字符该怎么压缩呢？比如说ABCDEFGHIJKLMNOPQRSTUVWXYZ，26个英文字母所占空间应该是26个字节，我们用RLE压缩算法压缩后的结果为A1B1C1D1E1F1G1H1I1J1K1L1M1N1O1P1Q1R1S1T1U1V1W1X1Y1Z1，所占用52个字节，压缩完成后的容量没有减少反而增大了！这显然不是我们想要的结果，所以这种情况下就不能再使用RLE进行压缩。哈夫曼算法和莫尔斯编码
　　下面我们来介绍另外一种压缩算法，即哈夫曼算法。在了解哈夫曼算法之前，你必须舍弃半角英文数字的1个字符是1个字节（8位）的数据。下面我们就来认识一下哈夫曼算法的基本思想。
　　文本文件是由不同类型的字符组合而成的，而且不同字符出现的次数也是不一样的。例如，在某个文本文件中，A出现了100次左右，Q仅仅用到了3次，类似这样的情况很常见。哈夫曼算法的关键就在于多次出现的数据用小于8位的字节数表示，不常用的数据则可以使用超过8位的字节数表示。A和Q都用8位来表示时，原文件的大小就是100次8位3次8位824位，假设A用2位，Q用10位来表示就是2100310230位。
　　不过要注意一点，最终磁盘的存储都是以8位为一个字节来保存文件的。
　　哈夫曼算法比较复杂，在深入了解之前我们先吃点甜品，了解一下莫尔斯编码，你一定看过美剧或者战争片的电影，在战争中的通信经常采用莫尔斯编码来传递信息，例如下面
　　接下来我们来讲解一下莫尔斯编码，下面是莫尔斯编码的示例，大家把1看作是短点（嘀），把11看作是长点（嗒）即可。
　　莫尔斯编码一般把文本中出现最高频率的字符用短编码来表示。如表所示，假如表示短点的位是1，表示长点的位是11的话，那么E（嘀）这一数据的字符就可以用1来表示，C（滴答滴答）就可以用9位的110101101来表示。在实际的莫尔斯编码中，如果短点的长度是1，长点的长度就是3，短点和长点的间隔就是1。这里的长度指的就是声音的长度。比如我们想用上面的AAAAAABBCDDEEEEEF例子来用莫尔斯编码重写，在莫尔斯曼编码中，各个字符之间需要加入表示时间间隔的符号。这里我们用00加以区分。
　　所以，AAAAAABBCDDEEEEEF这个文本就变为了A6次B2次C1次D2次E5次F1次字符间隔164位6次8位2次9位1次6位2次1位5次8位1次2位16次106位14字节。
　　所以使用莫尔斯电码的压缩比为141782。效率并不太突出。用二叉树实现哈夫曼算法
　　刚才已经提到，莫尔斯编码是根据日常文本中各字符的出现频率来决定表示各字符的编码数据长度的。不过，在该编码体系中，对AAAAAABBCDDEEEEEF这种文本来说并不是效率最高的。
　　下面我们来看一下哈夫曼算法。哈夫曼算法是指，为各压缩对象文件分别构造最佳的编码体系，并以该编码体系为基础来进行压缩。因此，用什么样的编码（哈夫曼编码）对数据进行分割，就要由各个文件而定。用哈夫曼算法压缩过的文件中，存储着哈夫曼编码信息和压缩过的数据。
　　接下来，我们在对AAAAAABBCDDEEEEEF中的AF这些字符，按照出现频率高的字符用尽量少的位数编码来表示这一原则进行整理。按照出现频率从高到低的顺序整理后，结果如下，同时也列出了编码方案。
　　字符出现频率编码（方案）位数A601E511B2102D2112C11003F11013
　　在上表的编码方案中，随着出现频率的降低，字符编码信息的数据位数也在逐渐增加，从最开始的1位、2位依次增加到3位。不过这个编码体系是存在问题的，你不知道100这个3位的编码，它的意思是用1、0、0这三个编码来表示E、A、A呢？还是用10、0来表示B、A呢？还是用100来表示C呢。
　　而在哈夫曼算法中，通过借助哈夫曼树的构造编码体系，即使在不使用字符区分符号的情况下，也可以构建能够明确进行区分的编码体系。不过哈夫曼树的算法要比较复杂，下面是一个哈夫曼树的构造过程。
　　自然界树的从根开始生叶的，而哈夫曼树则是叶生枝哈夫曼树能够提升压缩比率
　　使用哈夫曼树之后，出现频率越高的数据所占用的位数越少，这也是哈夫曼树的核心思想。通过上图的步骤二可以看出，枝条连接数据时，我们是从出现频率较低的数据开始的。这就意味着出现频率低的数据到达根部的枝条也越多。而枝条越多则意味着编码的位数随之增加。
　　接下来我们来看一下哈夫曼树的压缩比率，用上图得到的数据表示AAAAAABBCDDEEEEEF为0000000000001001001101011010101010101111，40位5字节。压缩前的数据是17字节，压缩后的数据竟然达到了惊人的5字节，也就是压缩比率51729如此高的压缩率，简直是太惊艳了。
　　大家可以参考一下，无论哪种类型的数据，都可以用哈夫曼树作为压缩算法
　　文件类型压缩前压缩后压缩比率文本文件14862字节4119字节28图像文件96062字节9456字节10EXE文件24576字节4652字节19可逆压缩和非可逆压缩
　　最后，我们来看一下图像文件的数据形式。图像文件的使用目的通常是把图像数据输出到显示器、打印机等设备上。常用的图像格式有：BMP、JPEG、TIFF、GIF格式等。BMP：是使用Windows自带的画笔来做成的一种图像形式JPEG：是数码相机等常用的一种图像数据形式TIFF：是一种通过在文件中包含标签就能够快速显示出数据性质的图像形式GIF：是由美国开发的一种数据形式，要求色数不超过256个
　　图像文件可以使用前面介绍的RLE算法和哈夫曼算法，因为图像文件在多数情况下并不要求数据需要还原到和压缩之前一摸一样的状态，允许丢失一部分数据。我们把能还原到压缩前状态的压缩称为可逆压缩，无法还原到压缩前状态的压缩称为非可逆压缩。
　　一般来说，JPEG格式的文件是非可逆压缩，因此还原后有部分图像信息比较模糊。GIF是可逆压缩
　　另外，cxuan肝了六本PDF，公号回复cxuan，领取作者全部PDF。