文章目录
- 认知压缩算法
- 文件存储器
- 压缩算法的定义
- 了解几种常见的压缩算法
- RLE算法的机理
- RLE算法的缺点
- 霍夫曼算法和莫尔斯编码
- 用二叉树实现霍夫曼算法
- 哈夫曼树可以提高压缩比。
- 可逆压缩和不可逆压缩
我把之前的文章总结到Github里了，欢迎大家到star https://Github . com/crisxuan/best Java提交这篇文章。
本文是“程序员需要知道的硬核知识”第五篇。请在这篇历史文章上盖章。
程序员需要知道的核心知识的记忆
具有程序员需要了解的核心知识的CPU
程序员需要知道的核心知识的二进制系统
程序员需要知道的核心知识磁盘
上一篇介绍的电脑硬件知识比较多，会比较难。这篇文章的门槛会更低。让我们来看看计算机中的压缩算法。
认知压缩算法
想必我们都经历过压缩和解压文件的体验。当文件过大时，我们会使用文件压缩来减少文件空间空。例如，上传文件的限制是100 MB。我这里有一个文件夹不能上传，但是我解压后的文件肯定小于100 MB，所以我的文件是可以上传的。
此外，当我们将相机拍摄的照片保存到计算机中时，我们也使用压缩算法来压缩文件。文件压缩格式一般是JPEG。
那么压缩算法是什么呢？压缩算法是如何定义的？在我们知道算法之前，我们需要知道文件是如何存储的。
文件存储器
文件是在存储介质(如磁盘)中存储数据的一种形式。程序中存储数据的最基本单位是字节。文件大小是否用xxxKB、xxxMB等表示。，是因为文件存储在字节B = Byte中。
文件是字节数据的集合。1字节(8位)表示的字节数据有256种，二进制为0000 0000-1111 1111。如果存储在文件中的数据是文本，那么该文件就是文本文件。如果是图形，则该文件是图像文件。在任何情况下，文件中的字节数都是连续存储的。
压缩算法的定义
上面介绍了文件的集合实际上是字节数据的集合，所以我们可以定义压缩算法。
压缩算法是指数据压缩算法，主要包括压缩和恢复(解压缩)两个步骤。
其实就是在不改变原有文件属性的情况下，减少文件字节空和占用空的算法。
根据压缩算法的定义，我们可以将它们分为不同的类型:
有损和无损
无损压缩:可以不失真地重构压缩后的数据，准确地恢复原始数据。可以用在对数据精度要求比较严格的地方，比如可执行文件和普通文件的压缩，磁盘的压缩，多媒体数据的压缩。这种方法的压缩比很小。例如差分编码、RLE、霍夫曼编码、LZW编码和算术编码。
有损压缩:是失真的，不能完全准确地恢复原始数据，重建的数据只是原始数据的近似。可以用在对数据精度要求不高的地方，比如多媒体数据的压缩。这种方法的压缩比较大。例如预测编码、感知编码、分形压缩、小波压缩、JPEG/MPEG。
对称
如果编解码算法的复杂度和所需时间差不多，就是对称编码方式，大部分压缩算法都是对称的。但也有不对称的，一般都是很难编码，很容易解码的，比如霍夫曼编码，分形编码。然而，在密码学中使用的编码方法是相反的。它很容易编码，但很难解码。
帧间和帧内
在视频编码中，将同时使用帧内和帧间编码方法。帧内编码是指在一帧图像中独立完成的编码方式，与静止图像的编码相同，如JPEG。帧间编码在编解码前需要参考前后帧，编码过程中要考虑帧间时间冗余的压缩，比如MPEG。
实时的
在一些多媒体应用中，需要实时处理或传输数据(如现场数字录音和录像、播放MP3/RM/VCD/DVD、视频/音频点播、网络直播、可视电话、视频会议)，编解码器一般要求延迟≤ 50 ms，这就需要简单/快速/高效的算法和高速/复杂的CPU/DSP芯片。
分级处理
一些压缩算法可以同时处理不同分辨率、不同传输速率和不同质量水平的多媒体数据，如JPEG2000和MPEG-2/4。
这些概念有些抽象，主要是让大家了解压缩算法的分类。下面我们来分析几种常见压缩算法的特点和优缺点。
了解几种常见的压缩算法
RLE算法的机理
接下来，让我们正式看看文件压缩机制。首先，我们试着压缩AAAAAABBCDDEEEEEF，一个17个字符的半角文件(文本文件)。虽然这些话没有什么实际意义，但是非常适合用来描述RLE的压缩机制。
由于半角字符(实际上是英文字符)作为一个字节存储在文件中，所以上面提到的文件的大小是17个字节。数字
(这里有一个问题让读者思考:为什么17个字符的大小是17个字节，却在空之间占据了很大的空间？这个问题本文暂且不讨论)
那么，我们如何压缩文件呢？让我们考虑一下，我们可以使用任何压缩算法，只要它可以使文件小于17个字节。
最明显的压缩方法，我想你已经想到了，就是重复相同的字符，也就是按照重复的次数来压缩字符。所以上面的文件压缩后会变成这样。
从图中我们可以看到，AAAAAABBCDDEEEEEF的17个字符被成功压缩成了A6B2C1D2E5F1的12个字符，即12/17 = 70%，压缩比为70%，压缩成功。
这样，以数据*重复次数的形式表示文件内容的压缩方法就变成了RLE(游程编码)算法。RLE算法是一种很好的压缩方法，常用于压缩传真图像等。因为图像文件的本质也是字节数据的集合，所以可以用RLE算法进行压缩。
RLE算法的缺点
RLE的压缩机制比较简单，所以RLE算法的程序也比较好写，所以这种使用RLE的方式可以让你更好的实现压缩的想法，但是RLE只对特定序列的数据有效。以下是RLE算法的压缩概要。
类型压缩前的文件大小压缩后的文件大小文件大小压缩比文本文件14862字节29065字节199%图像文件96062字节38328字节40%EXE文件24576字节15198字节62%
从上表可以看出，RLE压缩文本文件的数据不减反增！几乎是压缩前的两倍！因为在文本字符中很少看到连字符。
正如我们上面讨论的，RLE算法只对连续的字节序列有效。如果有一系列不同的字符，如何压缩？比如ABCDEFGHIJKLMNOPQRSTUVWXYZ，这26个英文字母在空之间应该是26个字节，RLE压缩算法压缩出来的结果是a1 B1 C1 D1 E1 f1 h1 i1 k1 L1 O1 Q1 r 1t 1 w1 x1 y1z 1，占用52个字节。压缩后容量不减反增！这显然不是我们想要的结果，因此在这种情况下，RLE不能再用于压缩。
霍夫曼算法和莫尔斯编码
下面介绍另一种压缩算法，即霍夫曼算法。在你能理解霍夫曼算法之前，你必须丢弃半角英文数字的一个字符是一个字节(8位)的数据。我们先来看看霍夫曼算法的基本思想。
文本文件由不同类型的字符组成，不同字符出现的次数不同。比如一个文本文件，A出现100次左右，Q只用了3次，很常见。霍夫曼算法的关键在于，出现多次的数据用小于8位的字节数表示，不常用的数据可以用大于8位的字节数表示。当A和Q都用8位表示时，原始文件的大小是100乘以8位3乘以8位= 824位。如果A用2比特表示，Q用10比特表示，那么就是2 * 100 3 * 10 = 230比特。
不过需要注意的是，最后磁盘的存储总是用8位作为一个字节来保存文件。
霍夫曼算法比较复杂。在进一步了解莫尔斯电码之前，我们先吃点甜点，学习一下。你一定看过美剧或者战争片。莫尔斯电码在战争通信中经常被用来传递信息，比如如下。
接下来，我们来谈谈莫尔斯编码。下面是一个莫尔斯电码的例子。大家可以把1想成一个短点(勾)，把11想成一个长点(点)。
莫尔斯电码一般将文本中出现频率最高的字符称为短码。如表所示，如果表示短点的位是1，表示长点的位是11，那么e (tick)的字符可以用1表示，c (tick)可以用9位110101101表示。在实际的莫尔斯编码中，如果短点的长度为1，长点的长度为3，短点和长点之间的间隔为1。这里的长度是指声音的长度。比如我们想用上面AAAAABBCDDEEEEEF的例子用莫尔斯电码重写。在莫尔斯电码中，代表时间间隔的符号需要加在每个字符之间。我们在这里用00来区分它们。
因此，文本AAAAAABBCDDEEEEEF变为A * 6次B * 2次C * 1次D * 2次E * 5次F * 1次字符间隔* 16 = 4位* 6次8位* 2次9位* 1次6位* 5次8位* 1次2位* 16次= 106位= 14字节。
所以使用莫尔斯码的压缩比是14/17 = 82%。效率不是很突出。
用二叉树实现霍夫曼算法
刚才提到，莫尔斯编码是根据每个字符在日常文本中出现的频率来确定代表每个字符的编码数据的长度。但是，在这个编码系统中，对于AAAAAABBCDDEEEEEF这样的文本，它并不是最高效的。
我们来看看霍夫曼算法。霍夫曼算法是指为每个压缩的目标文件构造一个最佳的编码系统，并基于这个编码系统进行压缩。所以用什么样的编码(霍夫曼编码)来划分数据，要看每个文件。霍夫曼编码信息和压缩数据存储在由霍夫曼算法压缩的文件中。
接下来我们按照高频的字符用尽可能少的数字编码的原则，对AAAAAABBCDDEEEEEF中的字符A-F进行整理。按照出现频率从高到低的顺序排列，结果如下，还列出了编码方案。
字符频率代码的位数(方案)A601E511B2102D2112C11003F11013
在上表的编码方案中，随着频率的降低，字符编码信息的数据比特数逐渐增加，从最初的1比特和2比特依次增加到3比特。但是，这个编码系统有问题。你不知道100的3位数代码。意思是用1，0，0这三个码来代表E，A，A？还是用10和0来代表B和A？或者用100代表c。
在哈夫曼算法中，借助哈夫曼树构造编码系统，即使不使用字符区分符号，也能构造出区分清晰的编码系统。但是霍夫曼树的算法比较复杂。下面是一个哈夫曼树的构建过程。
在自然界中，树木是从根部长出叶子的，而霍夫曼树是多叶的树枝。
哈夫曼树可以提高压缩比。
使用霍夫曼树后，出现频率越高，数据占用的比特数越少，这也是霍夫曼树的核心思想。从上图第二步可以看出，当分支连接数据时，我们从频率低的数据开始。这意味着低频率的数据到达具有更多分支的根。分支越多，编码位数越多。
接下来，我们来看看霍夫曼树的压缩比。利用上图得到的数据，显示AAAAAABBCDDEEEEEF为0000000000 100100 110 10101 010101 111，40位= 5字节。压缩前的数据是17字节，压缩后的数据达到了惊人的5字节，即压缩比= 5/17 = 29%。如此高的压缩比简直令人惊叹。
可以参考一下。无论是哪种数据，霍夫曼树都可以作为压缩算法。
压缩前的文件类型和压缩后的压缩比文本文件14862字节4119字节28%图像文件96062字节9456字节10%EXE文件24576字节4652字节19%
可逆压缩和不可逆压缩
最后，我们来看看图像文件的数据形式。使用图像的目的通常是将图像数据输出到显示器、打印机和其他设备。常用的图像格式有BMP、JPEG、TIFF、GIF等。
BMP ： 是使用 Windows 自带的画笔来做成的一种图像形式JPEG：是数码相机等常用的一种图像数据形式TIFF: 是一种通过在文件中包含\”标签\”就能够快速显示出数据性质的图像形式GIF： 是由美国开发的一种数据形式，要求色数不超过 256个
在图像文件中可以使用前面介绍的RLE算法和霍夫曼算法，因为在大多数情况下，图像文件不要求数据恢复到压缩前的状态，允许丢失一些数据。我们把能恢复到压缩前状态的压缩称为可逆压缩，不能恢复到压缩前状态的压缩称为不可逆压缩。
一般来说，JPEG文件是不可逆压缩的，所以恢复后的一些图像信息比较模糊。GIF是可逆压缩。
另外，cxuan保存了6份PDF，公司回复cxuan接收作者所有的PDF。