90 岁程序员：他的压缩算法改变了世界！
导读：近日，国际电气与电子工程学会（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 基金会知识前沿奖。
评论