90岁程序员获奖:无损压缩算法的「鼻祖」

2023-11-06 16:40

本文主要是介绍90岁程序员获奖:无损压缩算法的「鼻祖」,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

最爱在地铁里改BUG的程序员是?

????老师说的没毛病????

 黑马视频号 

近日,国际电气与电子工程学会(Institute of Electrical and Electronics Engineers,简称 IEEE)宣布,授予 IEEE 终身 Fellow Jacob Ziv 2021 年度 IEEE 荣誉勋章。

Jacob Ziv

这位如今已 90 岁的前辈,是一位以色列科学家,他开发了通用无损压缩算法 Lempel-Ziv,为后来的 GIF、PNG 和 ZIP 文件的开发奠定了坚实的基础。

无损压缩算法发展史

20 世纪 70 年代,随着互联网及 PC 时代的来临,如何在有限内存空间的设备上节省出更多的空间,并减少对带宽的占用,让文件在较低的网络带宽下实现更快的传输,成为彼时 IT 行业亟需解决的一大难题。

正因此,数据压缩技术也从背后逐渐走入大众视野,并开始在计算机领域扮演重要角色。

现如今,想必很多人都知道,数据压缩主要有两种类型:一种是有损压缩,一种是无损压缩。

所谓有损压缩,主要是利用了人类对图像或声波中的某些频率成分不敏感的特性,允许压缩过程中损失一定的信息,日常生活中,我们常见的语言、图像、视频压缩其实都是有损压缩的方式。

与有损压缩相比,无损压缩要更为复杂一些,对此,IEEE 官方使用了「魔术」一词来形容这门技术,其中原因主要是因为无损压缩技术是利用数据的统计冗余进行压缩,在解压之后,可完全恢复原始数据而不引起任何失真。

这就像一位魔术师拿着魔术棒一挥,手中的东西不见了,再一挥,又原封不动地出现了,无损压损技术就像表演魔术一样。而 Jacob Ziv 就是这位在数据压缩领域拿着魔术棒的大师。

不过,在 Jacob Ziv 这位魔术师带来奇特的魔术之前,压缩算法也经历了百年的发展历程(http://ethw.org/History_of_Lossless_Data_Compression_Algorithms):

· 事实上,发明于 1838 年的 Morse code,是最早的数据压缩实例。

· 随着大型机的兴起,数学家香农和 Robert Fano(CSAIL的计算先驱和创始人)发明了 Shannon-Fano(香农-范诺)编码算法。他们的算法基于符号(symbol)出现的概率来给符号分配编码(code)。一个符号出现的概率大小与对应的编码成反比,从而用更短的方式来表示符号。

· 1951 年,作为麻省理工的一名学生,David Huffman 选择写学期论文而非期末考试的方式来完成学业任务,彼时他的论文题目是寻找二叉编码的最优算法。不过,遗憾的是,经过几个月的努力后依然没有任何成果,Huffman 决定放弃所有论文相关的工作,开始学习为参加期末考试做准备。就在那时,Huffman 偶然间找到一个与 Shannon-Fano 编码相类似但是更有效的编码算法,这种编码方式效率高、运算速度快。

· 后来到了 20 世纪 70 年代,随着在线存储的出现,哈夫曼编码得到了广泛应用。不过,经过不断地尝试,不少科学家发现哈夫曼编码所得的编码长度只是对信息熵(描述信源的不确定度)计算结果的一种近似,还无法真正逼近信息熵的极限。同时,它需要两次通过数据文件:一次计算文件的统计特征,第二次编码数据。将字典与编码数据一起存储,增加了压缩文件的大小。

1977 年,来自以色列的 Jacob Ziv 和 Abraham Lempel 两位技术大神打破传统的设计思想,创造出一种哈夫曼编码更有效的压缩算法,并以两个人名字来命名。

同时,他们还发表了一篇名为《A Universal Algorithm for Sequential Data Compression》(顺序数据压缩的一个通用算法 ,https://www2.cs.duke.edu/courses/spring03/cps296.5/papers/ziv_lempel_1977_universal_algorithm.pdf)的论文,揭晓了独创的 LZ77 算法,这也是第一个使用字典来压缩数据的算法。

次年,Jacob Ziv 和 Abraham Lempel 再次发表一篇改进版的论文(《Compression of Individual Sequences via Variable Rate Coding》),并带来了 LZ78 的压缩算法。与 LZ77 不同,LZ78 解析输入数据,生成一个静态字典,不像 LZ77 动态产生。该算法成为 80 年代初使用的 Unix 压缩程序的基础;影响了 90 年代的 WinZip 和 Gzip,为 GIF、TIFF 图片格式的开发带来了一定的指引。

如果没有这些算法的存在,现在的我们不一定能够使用更为便捷的网络就可以发送大型数据文件,或还停留在将大型数据文件拷贝到光盘上进行传输时代;听音乐时,还有可能需要 CD 而不是通过流式传输......

 Ziv 的过往经历

这一切都需要感谢 Jacob Ziv 和 Abraham Lempel。"LZ 算法是第一个成功的通用压缩算法",一位支持 Ziv 获奖的工程师如是说。这些算法以及 Jacob Ziv 对它们的分析,为后续关于通用算法的大多数工作奠定了基础。

回顾 Ziv 的过往经历,其跨越了半个世纪,将自己全身心地投入到压缩算法领域中。

1931 年,出生在当时由英国统治的巴勒斯坦城市 Tiberias(现属于以色列)的 Ziv,在很小的时候,Ziv 就对电力和电子产品有着浓厚的兴趣,譬如,在练习小提琴的时候,他会尝试把乐谱架变成一盏灯。此外,他还试图用钢琴弹奏的金属零件制作一个马可尼发射机。

1948 年,第一次阿以战争爆发时他在读高中,后来被征召到前线短暂地服过役。由于一群母亲组织抗议,他才从前线回到了后方,在空军受训担任雷达技师。战争结束后,他进入以色列理工学院学习电气工程。

在 1955 年完成硕士学位后,Ziv 重返国防界,并加入了以色列国防研究实验室(现为拉斐尔先进防御系统),开发用于导弹和其他军事系统的电子元件。

1959 年,Ziv 被选为以色列国防实验室为数不多的出国留学的研究人员之一。那时,Ziv 计划继续从事通信工作,但他不再只对硬件感兴趣。

偶然机遇之下,他阅读了《信息理论》(Prentice-Hall,1953年)的书籍,他决定将信息理论作为他关注的焦点。然而,除了麻省理工学院之外,还有什么地方可以研究信息理论呢?

当然还是麻省理工!于是,1960 年,Ziv 进入 MIT 读博,在信息理论方面深造,在毕业返回以色列后进入了国防部担任通信部门主管。

1968 年,他返回美国,进入了贝尔实验室。

两年后,Ziv 和几个同事一起加入了以色列理工学院。就是在这里,他遇到了 Abraham Lempel,两个人共同讨论了如何改进无损数据压缩。

Ziv 和 Lempel 都想知道他们是否可以开发一种无损数据压缩算法,该算法适用于任何类型的数据,不需要预处理,并且能够实现数据的最佳压缩,这个目标被称为 Shannon 熵的对象定义。在设想时,他们并不清楚是否可以实现他们的目标。于是,他们决定找出答案。

在深入研究几年后,随着 LZ77 和 LZ78 的出现,代表了其研究成功。Ziv 和 Lempel 开创了通用源编码,一系列无需知道固有信息压缩数据的算法,减少了从不失真和失真数据重建图像所需的数据率。

对此,斯坦福大学从事信息理论的电气工程教授 Tsachy Weissman 表示:"在他们发表作品时,算法清晰优雅,易于实现,计算复杂度低,这一事实几乎无关紧要。更多的是关于理论结果,为接下来的研究带来重要意义。"

另外,Ziv 还促成了错误校正代码的低计算复杂性解码理论。

并于:

  • 1993 年,因精确科学而被授予以色列奖(Israel Prize);

  • 1995 年,因其“对信息理论、数据压缩的理论和实践的贡献”获得 IEEE 理查德 · 汉明奖章;

  • 1997 年,获得 IEEE 信息论学会的克劳德 · 香农奖;

  • 2008 年,获得 BBVA 基金会知识前沿奖。

如今,凭借「其对信息理论和数据压缩技术的重要贡献和杰出的研究领导地位」,被授予 2021 年度 IEEE 荣誉勋章,可谓实至名归,向依旧奋战在研究一线的前辈致敬!

内容来源:CSDN(ID:CSDNnews)

参考:

https://spectrum.ieee.org/the-institute/ieee-member-news/ieee-medal-of-honor-goes-to-data-compression-pioneer-jacob-ziv

https://spectrum.ieee.org/geek-life/profiles/from-winzips-to-cat-gifs-jacob-zivs-algorithms-have-powered-decades-of-compression

 播妞好课推荐 

????????????

资深讲师,让你少走弯路

黑马各学科基础班优惠价 28 元

30万学员遍布BAT等互联网大厂

扫码抢占名额

课程老师1对1服务,全程免费

????????????

黑马程序员丨好口碑IT教育

JavaEE

HTML&JS+前端

Python+大数据开发

人工智能开发

UI/UE设计

软件测试

新媒体+短视频直播运营

产品经理

Linux云计算+运维开发

智能机器人软件开发

电商视觉运营设计

_

· 推荐阅读 ·

阿里P7:三流员工卖命,二流员工卖时间,一流员工 ...

2021-04-30

特斯拉失控200次致死175人,网友直呼:大瓜来了!

2021-04-29

你真的会白嫖吗?播妞今天帮你省下几万块(18套免费领)

2021-04-28

点个在看,播妞爱你们呦

这篇关于90岁程序员获奖:无损压缩算法的「鼻祖」的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/357832

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费

90、k8s之secret+configMap

一、secret配置管理 配置管理: 加密配置:保存密码,token,其他敏感信息的k8s资源 应用配置:我们需要定制化的给应用进行配置,我们需要把定制好的配置文件同步到pod当中容器 1.1、加密配置: secret: [root@master01 ~]# kubectl get secrets ##查看加密配置[root@master01 ~]# kubectl get se

dp算法练习题【8】

不同二叉搜索树 96. 不同的二叉搜索树 给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。 示例 1: 输入:n = 3输出:5 示例 2: 输入:n = 1输出:1 class Solution {public int numTrees(int n) {int[] dp = new int

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数,每次操作将其分成2^q份,对于每一份内部的数进行翻转(逆序),每次操作完后输出操作后新序列的逆序对数。 图一:  划分子问题。 图二: 分而治之,=>  合并 。 图三: 回溯: