Loading [MathJax]/jax/output/CommonHTML/config.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >我从来不理解 “压缩算法”,直到有人这样向我解释它

我从来不理解 “压缩算法”,直到有人这样向我解释它

作者头像
wade
发布于 2021-07-08 06:25:12
发布于 2021-07-08 06:25:12
6.2K0
举报
文章被收录于专栏:coding个人笔记coding个人笔记

·大家对于压缩应该并不陌生,几乎每天都跟压缩打交道

常见的压缩软件:7-zip,WinRAR,2345好压

常见的压缩格式:.zip,.rar,.tar.gz

压缩软件有很多,但是都是同一个目的,为了减小文件占用的存储空间

除了上面这些压缩格式,像.jpg,.mp3,.avi这些,也都是有着压缩的作用,只不过跟上面.zip这些相比,它们执行的是有损压缩

1 有损压缩

有损压缩是利用了人类对图像或声波中的某些频率成分不敏感的特性,允许压缩过程中损失一定的信息,虽然不能完全恢复原始数据,但是所损失的部分对理解原始图像的影响缩小,却换来了大得多的压缩比,有损压缩广泛应用于语音,图像和视频数据的压缩。

也就是说,当一个文件进行有损压缩后,他就会永远丢失一部分的数据,无论如何都没办法再将这个被有损压缩的文件百分百还原到他原来的样子,既然有损压缩会永远丢失数据,我们为什么还需要有损压缩呢?

因为有损压缩后可以获得更高的性价比,我们完全可以接受丢失的部分数据,这些丢失的数据并不会对我们的使用产生什么影响

比如我们几乎每天聊天都会用到的表情包,就是有损压缩的功劳,这些表情包一旦出现马赛克就再也无法还原,但却拥有更好的可用性和传播性

2 无损压缩

是利用数据的统计冗余进行压缩,压缩后可完全恢复原始数据而不引起任何失真,但压缩率是受到数据统计冗余度的理论限制,一般为2:1到5:1,这类方法广泛用于文本数据,程序和特殊应用场合的图像数据(如指纹图像,医学图像等)的压缩。

无损压缩的入门难度并不算很高,但是想要搞好它却非常难,而且不同的压缩算法能够实现的压缩率和压缩的速度也有比较大的差别

发展到今天的无损压缩算法,能把文件压缩到原来的30%-40%已经是很厉害的了,而且压缩比例越高,解压也就越麻烦

zstd (Zstandard)是一款免费的开源,快速实时数据压缩程序,它是用C语言编写的无损压缩算法,具有更好的压缩比,由Facebook开发

计算机里,文件是由各种不同的代码组成的,而压缩的基本原理就是通过寻找规律,从而简化代码里字符的排列组合,于是就出现了各种各样的压缩算法

比如:游程编码,字典算法,哈夫曼编码。。。

举个例子:

有下面一组数据

bbbbbbyytttttedddaaannccccccceee

想要对它进行压缩,大家是不是看一眼就知道要怎么做了

=> 6b3y5t1e3d3a2n7c4e

可以用重复的次数加上字符本身来进行压缩,这段本身要占34位字符的数据就被压缩成了只有18个字符位的数据,减少了16个字符的位置

这种最简单的压缩方式就是游程编码(Run Length Encoding,RLE)但是这个算法有个很大的缺点,如果没有成堆出现的重复字符,在经过游程编码压缩后,最坏的情况,压缩后的文件甚至是压缩前大小的两倍

字典算法将文件中出现频率比较高的单词拿出来,生成一个字典列表(类似key-value的键值对),再用特殊的代码来表示这个单词

比如说,你有个朋友叫 ’沃德天·沃卫申么·拉末帅·夫斯基‘

如果你每提一次他的名字就得说一遍的话,那这不令人烦躁?

可以起个绰号:00,下次提到他的名字的时候用00就完事了,压缩后的长度少了很多

当然这不是目前人类能想到的最优解

哈夫曼编码(Huffman Coding)1952年,还在读博士的哈夫曼,在完成《信息论》期末作业的时候,顺便~在字典算法的基础上做了优化,他认为,越是经常出现的东西,越应该用简短的字符来替换表示它,所以就诞生了压缩领域的经典算法——哈夫曼编码压缩。

简单的讲,就是越经常出现的内容,越要用少的内容来描述它,占位也就越少,而不常见的内容,描述的长度也就相对越长,占位也就越多

举个例子,有下面一组数据

1,50,20,50,50,18,50,25,32,18

如果要对这组数据使用哈夫曼编码进行压缩,首先根据这些数字出现的次数排列

50,18,1,20,25,32

把它们看成一个个节点,节点下面的蓝色是该数字出现的次数

首先找到出现次数最小的两个节点,左边支路为0右边为1

把这俩节点看成一个新的节点,出现的次数就是两个节点出现次数的和

再找到出现次数最小的两个节点,重复上面的步骤

最终生成的哈夫曼树

我们就能得到这些数字的哈夫曼编码

  • 50:00
  • 18:01
  • 1:100
  • 20:101
  • 25:110
  • 32:111

1,50,20,50,50,18,50,25,32,18

上面这组数据在经过哈夫曼编码压缩后就变成了

100,00,101,00,00,01,00,110,111,01

将原始数据转成二进制进行比较

1,110010,10100,110010,110010,10010,110010,11001,100000,10010

明显节省了很多空间

其实每种压缩算法都有各自的优势,而我们日常中接触的压缩文件,大部分都是多种压缩算法共同努力的结果

3 压缩炸弹

压缩炸弹:一个很小很小非常小,只有几十kb大的压缩文件,在被解压后却像炸弹一样,无限套娃,炸出几百万GB的源文件

一个叫42.zip的文件,初始大小就只有42kb,用解压密码42完全解压之后,足足有4.5PB那么大,

被解压后,这个42.zip会出现16个压缩包,每个压缩包里面又有16个相同的压缩包,循环5次之后,就会得到16的5次方,也就是1048576个文件,而这些最终的文件每个都有4.3GB那么大,所以最终能得到1048576*4.3GB约等于4.5PB,普通的电脑肯定是扛不住的

附上42.zip的下载链接(谨慎使用) https://unforgettable.dk/

还有更猛的

droste.zip

它更小,只有28kb大,但是它一旦被解压,就会无限套娃一样,解压出一份一模一样的压缩文件出来,再自动解压,又出来一个一模一样的,就这样一直重复下去。。。硬盘就直接炸了

这个文件的原理就是把自己当作结果输出出来

但是根据信息论创始人克劳德·艾尔伍德·香农提出的信息熵函数,文件压缩是有极限的

别看上面那两个文件压缩比例很高,但实际上信息熵很少,因为里面全是大量刻意重复的数据,而压缩就是一个消除冗余的过程,所以这种文件也就能压缩到非常小了

那有没有压缩比例高,但又不是刻意重复数据的文件呢?

在2000年左右制作的一部3D影片“彗星撞地球”,就展示了惊人的压缩比

《彗星撞地球》百度网盘资源(谨慎使用):https://pan.baidu.com/s/1sj8Z7p7

如果直接放出来的话,差不多有15G,而它被压缩完之后只有64KB,少了250000倍

影片的制作人Warez,用一个只有64kb的.exe文件就实现了,在解压运行的时候可以调用显卡、cpu还有内存,进行实时渲染,将影片当场一帧一帧地渲染出来

像这样的压缩方式,还运用到某些游戏中,像赛博朋克2077这种,所以需要一台配置足够好的电脑才能跑得起来

回到上面讲到的42.zip和droste.zip这类文件,它们的作用是什么?

在2000年左右,这些压缩文件实际上是用来攻击别人计算机的

一些电脑病毒的制造者,专门利用杀毒软件会扫描压缩文件内部的特性,会把压缩炸弹带着病毒一起发到目标的电脑上

压缩炸弹本身又很小,非常好传输,但实际扫描起来却非常花时间,病毒就趁着杀毒软件逐个扫描4.5PB的文件时候侵犯电脑

当然现在的杀毒软件已经足够强大到能够避开这类压缩炸弹的套路

相关链接:

https://blog.csdn.net/weixin_30783913/article/details/97260476

https://www.cnblogs.com/zhouie/p/10702591.html

https://blog.csdn.net/fanyun_01/article/details/80211799

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2021-07-02,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 coding个人笔记 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
90 岁程序员:他的压缩算法改变了世界!
近日,国际电气与电子工程学会(Institute of Electrical and Electronics Engineers,简称 IEEE)宣布,授予 IEEE 终身 Fellow Jacob Ziv 2021 年度 IEEE 荣誉勋章。
GitHubDaily
2021/05/19
4440
90 岁程序员:他的压缩算法改变了世界!
程序员需要了解的硬核知识之压缩算法
我们想必都有过压缩和 解压缩文件的经历,当文件太大时,我们会使用文件压缩来降低文件的占用空间。比如微信上传文件的限制是100 MB,我这里有个文件夹无法上传,但是我解压完成后的文件一定会小于 100 MB,那么我的文件就可以上传了。
cxuan
2019/11/12
1.2K0
​十种常用的图像压缩算法。
数据压缩是保留相同或绝大部分数据前提下减小文件大小的过程。它的原理是消除不必要的数据或以更高效的格式重新组织数据。在进行数据压缩时,你可以选择使用有损方法或无损方法。有损方法会永久性地擦除掉一些数据,而无损方法则能保证持有全部的数据。使用哪类方法取决于你要让你的文件保持多大的精准度。本文会为你介绍6种不同的无损数据压缩算法,以及4种基于深度学习的图像/视频压缩算法。六款无损数据压缩算法无损压缩算法通常被用于归档或其他高保真目的。这些算法能够让你在确保文件可被完整恢复的同时减少文件大小。有很多种无损压缩算法供你选择。下面介绍6种常用的算法。1.LZ77LZ77算法发布于1977年。作为很多其他无损压缩算法的基础,它使用了“滑动窗口”的概念。在这个概念中,LZ77管理了一个字典。该字典使用三元组的方式:偏移量(Offset):短语起始处于文件开头之间的距离行程长度(Run length):组成短语的字符数偏离字符:表明新短语的标记符,匹配结束后,前向缓冲区中的第一个符号当文件被解析时,字典会被实时更新以反映最新的压缩数据和大小。举个例子,如果一个文件包含字符串"abbadabba",那么被压缩到字典中的项就是"abb(0,1,'d')(0,3,'a')"。你可以看下下表的拆解过程:这个例子中,被压缩后的数据并不比初始数据小多少。但一般情况下,当文件很长时,这种压缩效果就会显现出来。2. LZR LZR由Michael Rodeh于1981年提出,它是在LZ77的基础上发展而来。这个算法目标是成为LZ77的一个线性时间替换算法,但编码后Udell指针可能指向文件的任意偏移量,意味着需要耗费可观的内存,因此表现不如LZ77。3. LZSSLZSS,全称Lempel-Ziv-Storer-Szymanski,于1982年提出。它也是旨在提升LZ77的一个算法。它引入了一个方法能够检测是否真的减少了文件大小。如果未能起到压缩效果,就保持原来的输入格式。LZSS还移除了对偏离字符的使用,只使用<偏移量,长度>对。这个压缩算法广泛用于归档格式,如RAR以及网络数据的压缩。4. DEFLATEDEFLATE算法于1993年提出。作者是Phil Katz。该算法结合了LZ77或LZSS预处理器与霍夫曼编码。霍夫曼编码是1952年提出的诉法。它是一种熵编码,主要基于字符出现频度分配编码。5. LZMALZMA算法,全称是Lempel-Ziv Markov chain Algorithm(LZMA),于1998年提出,是LZ77的改进版,旨在实现.7z格式的7-ZIp文件归档。它使用链式压缩方法,在比特而非字节级别上应用修改后的LZ77算法。该压缩算法的输出稍后被算数编码进行处理以便后续进一步压缩。根据具体的实现不同,可能会引入其他的压缩步骤。6. LZMA2LZMA2算法于2009年提出,是LZMA的改良版。它提升了LZMA在多线程能力上的性能以及提升了处理不可压缩类型数据的表现。 四种基于深度学习的图像/视频压缩算法除了上面介绍的静态压缩算法,还有基于深度学习的压缩算法可供选择。1. 基于多层感知机的压缩算法多层感知机(Multi-Layer Perceptron,MLP)技术使用多层神经元来获取、处理以及输出数据。它能够被应用到数据降维任务和数据压缩。首个基于MLP的算法于1988年被提出,目前已经被应用到:二进制编码——标准的双符号编码量化——限制从连续集到离散集的输入特定领域内的转换——像素级的数据变更MLP算法利用分解神经网络上一步的输出来确定最佳的二进制码组合。后面,使用预测技术优化这个方法。预测技术能够通过反向传播基于相邻数据来提升数据准确度。 2. DeepCoder -- 基于视频压缩的深度神经网络DeepCoder是一个基于卷积神经网络(CNN)的框架,它是传统视频压缩技术的替代。该模型为预测信号和残留信号使用单独的CNN。它使用标量量化技术和一个传统的文件压缩算法——霍夫曼编码——将编码特征映射到一个二进制流中。一般认为,该模型的性能要优于著名的H.264/AVC视频编码规范。 3. 基于CNN的压缩算法CNN是分层的神经网络,通常用于图像识别和特征检测。当应用到压缩时,这些神经网络使用卷积操作来计算相邻像素点之间的相关性。CNN展示出了比基于MLP算法更好的压缩结果,提升了超分辨率下的性能以及减少了伪影。另外,基于CNN的压缩还提升了JPEG图像的品质,因为它减少了峰值信噪比(PSNR)和结构相似性(SSIM)。基于CNN的压缩通过使用熵估计法还实现了HEVC的性能。 4. 基于生成式对抗网络(GAN)的压缩算法GAN属于神经网络的一种,它使用两个神经网络彼此竞争的方式来产生更精确的分析和预测。最早基于GAN的压缩算法于2017年被提出。这些算法的文件压缩比例是其他常见方法(如JPEG、WebP等)的2.5倍。你可
小白学视觉
2024/12/05
5150
​十种常用的图像压缩算法。
ZIP压缩算法详细分析及解压实例解释(下)
来源:esingchan - 博客园 链接:www.cnblogs.com/esingchan/p/3958962.html(点击尾部阅读原文前往) 7、ZIP中对CL进行再次压缩的方法 这里仍然沿用Huffman的想法,因为CL也是一堆整数,那么当然可以再次应用Huffman编码。不过在这之前,PK对CL序列进行了一点处理。这个处理也是很精巧的。 CL序列表示一系列整数对应的码字长度,对于literal/length来说,总共有0-285这么多符号,所以这个序列长度为286,每个符号都有一个码字长度,当然
智能算法
2018/04/02
2.9K0
ZIP压缩算法详细分析及解压实例解释(下)
ZIP压缩算法详细分析及解压实例解释(上)
来源:esingchan - 博客园 链接:www.cnblogs.com/esingchan/p/3958962.html(点击尾部阅读原文前往) 最近自己实现了一个ZIP压缩数据的解压程序,觉得有必要把ZIP压缩格式进行一下详细总结,数据压缩是一门通信原理和计算机科学都会涉及到的学科,在通信原理中,一般称为信源编码,在计算机科学里,一般称为数据压缩,两者本质上没啥区别,在数学家看来,都是映射。 一方面在进行通信的时候,有必要将待传输的数据进行压缩,以减少带宽需求;另一方面,计算机存储数据的时候,为了减少
智能算法
2018/04/02
3.3K0
ZIP压缩算法详细分析及解压实例解释(上)
Gzip 详解:压缩算法的原理与应用
Gzip 是一种常见的文件压缩工具和格式,最初由 Jean-loup Gailly 和 Mark Adler 开发。它通常用于减少文件的大小,以便更高效地传输数据,尤其是在网络传输中。Gzip 的主要目标是通过减少冗余信息来实现数据压缩,从而加快数据传输速度,并减少存储空间的使用。
繁依Fanyi
2024/09/07
1.2K0
你所能用到的无损压缩编码(一)
      这个系列将结合C/C++介绍无损压缩编码的实现,正如Charles Petzold在<CODE:Hidden Language of Computer Hardware and Software>里所表达出来的意思一样,计算机最本质的能力就是将各种信息通过电路的开合转换成为一系列的数字,然后对其按照一定的规则进行编码,利用这些编码记录一些动作或者数据,完成人们想要的功能。计算机的指令是一种编码,数据也是一种编码,正如人类用各自民族特有的符号组成自己的语言一样,计算机也是依靠着编码形成了自己的语言
一心一怿
2018/04/16
2.1K0
你所能用到的无损压缩编码(一)
音频格式的汇总及压缩比较
数字音源,也就是数字音频格式,最早指的是CD,CD经过压缩之后,又衍生出多种适于在随身听上播放的格式,这些压缩过的格式,我们可以分为两大类:有损压缩的和无损压缩的。这里所说的压缩,是指把PCM编码的或者是WAV格式的音频流经过特殊的压缩处理,转换成其他格式,从而达到减小文件体积的效果。有损/无损,是指经过压缩过后,新文件所保留的声音信号相对于原来的PCM/WAV格式的信号是否有所削减。
ZONGLYN
2019/08/08
11K0
十款性能最佳的压缩算法
数据压缩是保留相同或绝大部分数据前提下减小文件大小的过程。它的原理是消除不必要的数据或以更高效的格式重新组织数据。在进行数据压缩时,你可以选择使用有损方法或无损方法。有损方法会永久性地擦除掉一些数据,而无损方法则能保证持有全部的数据。使用哪类方法取决于你要让你的文件保持多大的精准度。
Spark学习技巧
2021/03/05
8.3K0
十款性能最佳的压缩算法
数据压缩算法
之前在听到数据压缩的时候, 想着肯定是某些高深莫测的算法, 能够完成数据的压缩这种事情, 最近看了看, 嗯, 至少咱还是能看懂的.
烟草的香味
2020/06/09
2K0
基于 FPGA 的压缩算法加速实现
本设计中,计划实现对文件的压缩及解压,同时优化压缩中所涉及的信号处理和计算密集型功能,实现对其的加速处理。本设计的最终目标是证明在充分并行化的硬件体系结构 FPGA 上实现该算法时,可以大大提高该算法的速度。我们将首先使用C语言进行代码实现,然后在Vivado HLS中综合实现,并最终在FPGA板(pynq-z2)上进行硬件实现,同时于jupyter notebook中使用python来进行功能验证。
FPGA技术江湖
2025/07/08
1300
基于 FPGA 的压缩算法加速实现
15.计算机科学导论之数据压缩学习笔记
此部分包含第15、16、17和18章,包含了计算机中传输的数据压缩(有损与无损)、网络数据在传输过程中如何保证其数据安全, 讨论计算理论,即哪些是可计算的,哪些是不可计算的,最后介绍当前热门的人工智能(AI)的观点,加深我们对计算机数据处理的的认识,为后续学习扩展基础认识。
全栈工程师修炼指南
2023/02/03
1.2K0
跟我一起探索 HTTP-HTTP 协议中的数据压缩
数据压缩是提高 Web 站点性能的一种重要手段。对于有些文件来说,高达 70% 的压缩比率可以大大减低对于带宽的需求。随着时间的推移,压缩算法的效率也越来越高,同时也有新的压缩算法被发明出来,应用在客户端与服务器端。
用户1418987
2023/10/16
3260
跟我一起探索 HTTP-HTTP 协议中的数据压缩
压缩算法简介
压缩算法是一种通过减少数据量来节省存储空间或传输数据的技术。压缩算法可以分为两种类型:有损压缩和无损压缩。 有损压缩算法会牺牲一定的数据精度或质量,在压缩数据的同时丢失一些信息。这种算法适用于音频、视频等多媒体数据,例如JPEG和MP3等格式。 无损压缩算法则能够完全还原原始数据,不会造成数据丢失。这种算法适用于需要准确还原数据的场景,如文档、代码等,例如ZIP和GZIP等格式。 常见的压缩算法包括哈夫曼编码、Lempel-Ziv算法、Run-Length Encoding(RLE)等。这些算法通过不同的方式对数据进行编码和解码,以实现数据压缩和解压缩的目的。
FPGA开源工作室
2024/06/21
5190
压缩算法简介
数据压缩的元老——哈夫曼树精解
数据结构从逻辑结构上可以分为:集合、线性表、树、图 集合中常用的数据结构是背包等。 线性表包括栈、链表、队列等。 树包括堆、二叉树、哈夫曼树等。 图包括有向图、无向图、最小生成树、最短路径等(就职于高德地图的算法工程师,图的知识必须完全掌握(ง •̀_•́)ง)。 背包、栈、链表和队列在之前的一篇博文《基础大扫荡——背包,栈,队列,链表一口气全弄懂》中介绍了一下。二叉树和堆在《面向程序员编程——精研排序算法》中的堆排序部分仔细介绍过。 图若在未来有机会用到我会去研究一下,目前为止我的经历中用到图结构
文彬
2018/05/08
1.7K0
数据压缩的元老——哈夫曼树精解
深度学习助力数据压缩,一文读懂相关理论
本文对数据压缩的「前世今生」进行简要的回顾,重点分析基于深度学习的有损压缩、无损压缩方法,对基于深度学习的数据压缩进行了探讨和展望。
机器之心
2019/10/30
1.6K0
深度学习助力数据压缩,一文读懂相关理论
这个开发者易忽略的优化点,腾讯视频竟靠它省上千万元
👉腾小云导读 在互联网行业降本增效的大背景下,如何结合业务自身情况降低成本是每个业务都需要思考的问题。腾讯视频业务产品全平台日均覆盖人数超2亿。图片作为流媒体之外最核心的传播介质,庞大的业务量让静态带宽成本一直居高不下——腾讯视频各端日均图片下载次数超过 100 亿次,平均图片大小超 100kb,由此带来的图片静态带宽成本月均超千万。本文将详细介绍腾讯视频业务产品借助腾讯云数据万象来优化静态带宽成本过程中的挑战与解决方案,输出同领域通用的经验方法,希望可以对广大开发爱好者有所启发。 👉看目录,点收藏 1 背
云存储
2023/03/29
7930
这个开发者易忽略的优化点,腾讯视频竟靠它省上千万元
面向智能工厂的工业数据压缩研究
在智能工厂逐渐推广应用中,数字化信息的数据量相当庞大,对存储器的存储容量、网络带宽以及计算机的处理速度都有较高的要求,完全通过增加硬件设施来满足现实需求是不可能的,必须采用有效的压缩技术实现数据在网络中的轻量传输。
用户7623498
2020/08/04
6140
面向智能工厂的工业数据压缩研究
Lepton 无损压缩原理及性能分析
本文主要介绍无损压缩图片的概要流程和原理,以及Lepton无损压缩在前期调研中发现的问题和解决方案。
2020labs小助手
2022/07/05
7410
《C++ 驱动:人工智能数据实时压缩与解压缩之路》
在人工智能(AI)蓬勃发展的时代,数据的高效处理成为了构建强大智能系统的核心要素之一。数据量呈爆炸式增长,对存储和传输资源形成巨大压力,实时压缩与解压缩技术应运而生,成为优化数据处理流程的关键环节。C++语言以其卓越的性能、精细的内存控制和高效的执行效率,在实现人工智能数据的实时压缩与解压缩方面,展现出无可比拟的优势,为 AI 应用的高效运行提供了强有力的支持。
程序员阿伟
2024/12/10
4040
《C++ 驱动:人工智能数据实时压缩与解压缩之路》
相关推荐
90 岁程序员:他的压缩算法改变了世界!
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档