无损压缩鼻祖去世了,没有他就没有今天的 Zip、PNG、MP3、PDF……
无损压缩鼻祖去世了,享年 86 岁。
他就是 Abraham Lempel,来自以色列的科学家。
正是因为他和同事发明的 LZ77 / LZ78 压缩算法,才有了 Zip、GIF、PNG、TIFF、MP3、PDF 等直到今天还在流行的文件格式。
他生前曾就职的的以色列理工学院评价他为“学院成立 100 年来最伟大的研究员之一”,并称很少有科学家“像他一样在技术发展以及我们的日常生活领域中都产生了如此大的影响”。
无数网友为他的离世哀悼。
有人还表示:
Lempel 教授于 1936 年出生于波兰。
23 岁的时候他进入以色列理工学院,经过八年的学习,拿到博士学位。
就在毕业十年之际,41 岁的他成为母校的全职教授,负责电气工程和计算机科学专业的教学(随后又担任了三年计算机学院院长)。
这一年,正是他和同事 Jacob Ziv 发明 LZ77 算法的那一年,也就是 1977 年(下图左为 Ziv,右为 Lempel)。
正如其名,“LZ77”中的“L”代表 Lempel 教授,“Z”代表他的同事 Ziv 教授,“77”则是发明年份。
如果你是计算机专业的学生,LZ77 算法一定出现过你的课本之上。
它的特点包括简单、易于实现,可以针对任何数据格式进行无损压缩,完全区别于此前已经诞生的各种有损压缩算法。
它主要采用的是基于字典的方式进行压缩。
简单来说,就是把数据中可以组成“短语”的一串字符加入“字典”,然后再有匹配的字符出现就采用标记来代替,由此就能实现压缩的目的。
在具体操作中,该算法会将数据分为“滑动窗口”和“数据缓冲区”。
每次处理数据的时候,先把一部分数据预载入缓冲区,然后依次载入滑动窗口区(有长度限制)。
如果后进入的字符在滑动窗口里面出现匹配的时候,就记进当前的短语字典中。
随着滑动窗口的不断向前,字典会不断变化,不停地滑动字符向前,寻找到更多与字典中的短语匹配的选项,然后用带有含义的标记符进行标记,最终就可以得到一段压缩好的表示结果。
例子如下图所示,粉色为滑动窗口区,蓝色为缓冲区。
从上面的原理我们可以看出,LZ77 的压缩比比较高,但由于要不停地找匹配选项,压缩过程有一些耗时,但又由于解压速度又非常快(标记会说明匹配项的明确位置),总体还是算得上非常高效的。
两位教授就以论文的形式将他们这一成果公布了出来。
很快,在 1978 年,他们又对 77 算法进行了更新,诞生了同样著名的 LZ78,也就是 LZ77 的第二个版本。
不管后来大家如何“修修补补”,衍生出更加高效和完善的 LZSS、LZW、LZH 等新算法,它们的原理都和 Lempel 教授和 Ziv 教授的思想没有什么差别。
因此,在这些算法上诞生的 TIFF、PNG、ZIP、MP3 等广为流传的压缩文件格式,都得感谢这两位老爷子的贡献。
这不,2004 年,IEEE 就宣布 LZ77 和 LZ78 算法成为电气和电子工程的“历史里程碑”。
Lempel 教授也因为所作贡献,拿了不少奖项,包括 IEEE 信息理论学会技术创新金禧奖和 2007 年的 IEEE Richard W. Hamming 奖章,后者主要表彰他在“数据压缩方面的开创性工作”。
在改写数据压缩领域之后,Lempel 教授并没有“闲着”。
1993 年,已经 57 岁的他被惠普公司聘用。
仅过了一年,他就出来创立了惠普以色列实验室(HP Labs Israel),并担任其董事长直到 71 岁。
在此期间,惠普以 Lempel 教授的名义注册了 8 项专利。
如今,Lempel 教授已于上周日(2 月 5 日)辞世,离 87 岁生日就还差一周时间。
悼念。
讣告地址:
https://www.technion.ac.il/en/2023/02/technion-mourns-prof-abraham-lempel/
参考链接:
本文来自微信公众号:量子位 (ID:QbitAI),作者:丰色