90 岁程序员:他的压缩算法改变了世界!
大数据DT
共 4339字,需浏览 9分钟
·
2021-08-05 03:00
导读:近日,国际电气与电子工程学会(Institute of Electrical and Electronics Engineers,简称 IEEE)宣布,授予 IEEE 终身 Fellow Jacob Ziv 2021 年度 IEEE 荣誉勋章。
事实上,发明于 1838 年的 Morse code,是最早的数据压缩实例。 随着大型机的兴起,数学家香农和 Robert Fano(CSAIL的计算先驱和创始人)发明了 Shannon-Fano(香农-范诺)编码算法。他们的算法基于符号(symbol)出现的概率来给符号分配编码(code)。一个符号出现的概率大小与对应的编码成反比,从而用更短的方式来表示符号。 1951 年,作为麻省理工的一名学生,David Huffman 选择写学期论文而非期末考试的方式来完成学业任务,彼时他的论文题目是寻找二叉编码的最优算法。不过,遗憾的是,经过几个月的努力后依然没有任何成果,Huffman 决定放弃所有论文相关的工作,开始学习为参加期末考试做准备。就在那时,Huffman 偶然间找到一个与 Shannon-Fano 编码相类似但是更有效的编码算法,这种编码方式效率高、运算速度快。 后来到了 20 世纪 70 年代,随着在线存储的出现,哈夫曼编码得到了广泛应用。不过,经过不断地尝试,不少科学家发现哈夫曼编码所得的编码长度只是对信息熵(描述信源的不确定度)计算结果的一种近似,还无法真正逼近信息熵的极限。同时,它需要两次通过数据文件:一次计算文件的统计特征,第二次编码数据。将字典与编码数据一起存储,增加了压缩文件的大小。
在他们发表作品时,算法清晰优雅,易于实现,计算复杂度低,这一事实几乎无关紧要。更多的是关于理论结果,为接下来的研究带来重要意义。
1993 年,因精确科学而被授予以色列奖(Israel Prize); 1995 年,因其“对信息理论、数据压缩的理论和实践的贡献”获得 IEEE 理查德 · 汉明奖章; 1997 年,获得 IEEE 信息论学会的克劳德 · 香农奖; 2008 年,获得 BBVA 基金会知识前沿奖。
评论