当前位置: 首页 > 后端技术 > Java

90后程序员,他的压缩算法改变了世界!

时间:2023-04-01 17:32:53 Java

近日,电气与电子工程师协会(IEEE)宣布授予IEEE终身院士JacobZiv2021年IEEE荣誉勋章。这位90多岁的前辈是一位以色列科学家,他开发了通用的无损压缩算法Lempel-Ziv,为后来的GIF、PNG和ZIP文件的开发打下了坚实的基础。一、无损压缩算法发展史20世纪70年代,随着互联网和PC时代的到来,如何在内存空间有限的设备上节省更多的空间,减少带宽占用,让文件可以存储在更低的网络上实现带宽下更快的传输成为当时IT行业急需解决的重大问题。正因为如此,数据压缩技术才逐渐从后面进入大众的视野,并开始在计算机领域发挥重要作用。现在想必很多人都知道数据压缩主要有两种:一种是有损压缩,一种是无损压缩。所谓有损压缩,主要是利用了人类对图像或声波中的某些频率成分不敏感的特点,使得某些信息在压缩过程中丢失。在日常生活中,我们常见的语言、图像、视频压缩其实都是有损压缩方式。与有损压缩相比,无损压缩更为复杂。为此,IEEE官方用“神奇”一词来形容这项技术。主要原因是无损压缩技术利用数据的统计冗余性进行压缩,解压后可以完整还原原始数据,不会造成任何失真。就像是魔术师挥舞着魔法棒,手中的东西消失不见,再挥一挥,又完好无损地重新出现。无损压缩技术就像变魔术一样。而JacobZiv则是在数据压缩领域握有魔杖的大师。然而,在魔术师JacobZiv带来他的奇异魔法之前,压缩算法也经历了一个世纪的发展(http://ethw.org/History_of_Lo...):其实,1838年发明的摩尔斯电码,就是最早的例子的数据压缩。随着大型机的兴起,数学家香农和罗伯特法诺(计算先驱和CSAIL创始人)发明了香农-法诺(Shannon-Fano)编码算法。他们的算法根据出现的概率将代码分配给符号。一个符号出现的概率与对应的编码成反比,所以可以用更短的方式来表达这个符号。1951年,作为麻省理工学院的一名学生,大卫霍夫曼选择写学期论文而不是期末考试来完成他的学术任务。当时,他的论文题目是寻找二进制代码的最优算法。然而不幸的是,经过几个月的努力没有结果,霍夫曼决定放弃所有与论文相关的工作,开始学习准备期末考试。就在那时,霍夫曼偶然发现了一种与Shannon-Fano编码类似但更高效的编码算法,该算法高效且快速。后来,在20世纪70年代,随着在线存储的出现,霍夫曼编码得到广泛应用。然而,经过不断的尝试,许多科学家发现,通过哈夫曼编码得到的码长只是信息熵计算结果的一个近似值(描述来源的不确定性),并不能真正逼近信息熵的极限。同时,它需要两次遍历数据文件:一次计算文件的统计特征,第二次对数据进行编码。将字典与编码数据一起存储会增加压缩文件的大小。1977年,来自以色列的两位技术大师JacobZiv和AbrahamLempel打破了传统的设计思维,创造了一种具有更有效霍夫曼编码的压缩算法,并以两人的名字命名。同时,他们还发表了一篇名为《A Universal Algorithm for Sequential Data Compression》的论文(顺序数据压缩的通用算法:https://www2.cs.duke.edu/cour...并揭示了原始的LZ77算法,这也是首先是一种使用字典来压缩数据的算法,次年JacobZiv和AbrahamLempel再次发表了论文的改进版本(《Compression of Individual Sequences via Variable Rate Coding》),带来了LZ78的压缩算法,与LZ77不同的是,LZ78解析输入数据,生成静态字典,不像LZ77的动态生成,这个算法成为80年代初期使用的Unix压缩程序的基础;它影响了1990年代的WinZip和Gzip,为GIF和TIFF图像的发展带来了一定的指导方针格式。如果没有这些算法的存在,我们可能无法使用更方便的网络发送大数据文件,或者我们还处于将大数据文件复制到CD传输的时代;听音乐时,CD可能还需要而不是流式传输...2.Ziv的记录所有这一切都归功于JacobZiv和AbrahamLempel。“LZ算法是第一个成功的通用压缩算法”,一位支持Ziv获奖的工程师这样说。这些算法以及JacobZiv对它们的分析为大多数后续通用算法工作奠定了基础。回顾Ziv的过去,它跨越了半个世纪,全身心投入到压缩算法领域。Ziv于1931年出生在当时英国统治的巴勒斯坦城市太巴列(现为以色列的一部分)。在很小的时候,Ziv就对电力和电子产品产生了浓厚的兴趣。例如,在练习小提琴时,他会尝试将乐谱架变成一盏灯。此外,他还尝试用钢琴上弹奏的金属部件制作马可尼发射器。1948年第一次阿以战争爆发时,他还在读高中,并被征召到前线短暂停留。在一群母亲组织抗议后,他从前线返回后方,在空军接受雷达技术员培训。战后,他进入以色列理工学院学习电气工程。1955年完成硕士学位后,Ziv回到国防界,加入以色列国防研究实验室(现为RafaelAdvancedDefenseSystems),为导弹和其他军事系统开发电子元件。1959年,Ziv被选为少数出国留学的以色列国防实验室研究人员之一。那时,Ziv计划继续从事通信方面的工作,但他不再只对硬件感兴趣。一次偶然的机会,他读了《信息理论》(Prentice-Hall,1953)一书,决定将信息论作为自己的研究重点。但是,除了麻省理工学院,还有什么地方可以研究信息论呢?当然是麻省理工学院!于是,1960年,齐夫进入麻省理工学院攻读博士学位,进修信息论,毕业回国后进入国防部任通信司司长。1968年回到美国,加入贝尔实验室。两年后,Ziv和几位同事一起加入了以色列理工学院。正是在这里,他遇到了AbrahamLempel,两人讨论了如何改进无损数据压缩。Ziv和Lempel都想知道他们是否可以开发一种无损数据压缩算法,该算法适用于任何类型的数据,不需要预处理,并实现数据的最佳压缩,一种称为香农熵的对象定义。想象的时候,他们不知道自己的目标能否实现。所以,他们决定一探究竟。经过几年的潜心研究,LZ77和LZ78的出现代表了其研究的成功。Ziv和Lempel开创了通用源编码,这是一系列算法,可以在不知道固有信息的情况下压缩数据,从而降低从未失真和失真数据重建图像所需的数据速率。对此,从事信息论研究的斯坦福大学电气工程教授TsachyWeissman表示:“在他们发表他们的成果时,该算法清晰优雅、易于实现且计算复杂度低的事实是几乎无关紧要。更多的是关于理论结果。对未来研究的重要影响。”此外,Ziv还对纠错码的低计算复杂度解码理论做出了贡献。还有:1993年,以色列精密科学奖;1995年,IEEERichardHamming奖章,表彰“对信息理论、数据压缩理论和实践的贡献”;1997年,获得IEEE信息理论学会颁发的ClaudeShannon奖;2008年,获得BBVA基金会颁发的知识前沿奖。如今,他凭借“对信息论和数据压缩技术的重要贡献以及杰出的研究领导力”,被授予2021年IEEE荣誉勋章。参考资料:\https://spectrum.ieee.org/the...\https://spectrum.ieee.org/gee...\组织|苏蜜出品|CSDN(ID:CSDNnews)推荐:1.1000+Java面试题及答案(2021最新版)2.别再满脑子if/else了,试试策略模式,真香!!3.操!Java中xx≠null的新语法是什么?4、SpringBoot2.5发布,深色模式太炸了!5.《Java开发手册(嵩山版)》最新发布,赶快下载吧!感觉不错,别忘了点赞+转发!