• 无损压缩鼻祖Lempel去世,享年86岁
  • 发布于 2个月前
  • 252 热度
    0 评论
  • 旧巷
  • 0 粉丝 21 篇博客
  •   
无损压缩鼻祖去世了,享年86岁。他就是Abraham Lempel,来自以色列的科学家。正是因为他和同事发明的LZ77/LZ78压缩算法,才有了Zip、GIF、PNG、TIFF、MP3、PDF等直到今天还在流行的文件格式。

他生前曾就职的的以色列理工学院评价他为“学院成立100年来最伟大的研究员之一”,并称很少有科学家“像他一样在技术发展以及我们的日常生活领域中都产生了如此大的影响”。

共同发明LZ77/LZ78,彻底改写数据压缩领域
Lempel教授于1936年出生于波兰。23岁的时候他进入以色列理工学院,经过八年的学习,拿到博士学位。就在毕业十年之际,41岁的他成为母校的全职教授,负责电气工程和计算机科学专业的教学(随后又担任了三年计算机学院院长)。这一年,正是他和同事Jacob Ziv发明LZ77算法的那一年,也就是1977年。

正如其名,“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奖章,后者主要表彰他在“数据压缩方面的开创性工作”。

57岁被惠普聘用,贡献了8项专利
在改写数据压缩领域之后,Lempel教授并没有“闲着”。1993年,已经57岁的他被惠普公司聘用。仅过了一年,他就出来创立了惠普以色列实验室(HP Labs Israel),并担任其董事长直到71岁。在此期间,惠普以Lempel教授的名义注册了8项专利。如今,Lempel教授已于上周日(2月5日)辞世,离87岁生日就还差一周时间。

用户评论