戴维·霍夫曼

“霍夫曼编码”的发明人

戴维·霍夫曼(David Albert Huffman)是“霍夫曼编码”的发明人。

个人简介

他发明了著名的“霍夫曼编码”。

他作为信息论的先驱,对计算机科学、通信等学科所作出的巨大贡献将永远为世人所铭记。

生平

1925年生于俄亥俄州,从小聪慧好学,他在俄亥俄州立大学毕业时只有17岁。然后他进入MIT一边工作,一边深造,霍夫曼编码就是他在1952年做博士论文时发明的。这是一种根据字母的使用频率而设计的变长码,能大大提高信息的传输效率,至今仍有广泛的应用。为了说明霍夫曼编码的原理,我们以仅有6个字符的信息传输为例。在等长编码情况下,每个字符需要3个二进制位。在字符出现概率不同的情况下,我们可以设计出不等长的码,如图1所示,从而大大降低发送一个讯息所需要的总字符数。因为所示的编码,虽然每个字符所需的二进制位的算术平均数为3.33,大于等长编码,但按出现概率的加权平均值,则为2.05,通信开销减少将近1/3。

变长码的关键问题是如何为每个字符设计编码,使得接收方在收到报文后能正确地译码,也就是能正确判断现在收到的一个二进制位是前一字符的末位还是一个新的字符的首位。在上面这个6个字符的简单例子中,判断当然是很容易的：每出现一个“0”,或连续出现的第5个“1”,就是一个字符的终止位。对于实际系统,字符集相当大,编码设计就没有那么容易而变得十分复杂了。但是霍夫曼成功地解决了这个难题,使变长码得以被实际采用。

霍夫曼编码方法的具体过程是：首先把信源的各个输出符号序列按概率递降的顺序排列起来,求其中概率最小的两个序列的概率之和,并把这个概率之和看做是一个符号序列的概率,再与其他序列依概率递降顺序排列(参与求概率之和的这两个序列不再出现在新的排列之中)。然后,对参与概率求和的两个符号序列分别赋予二进制数字0和1。继续这样的操作,直到剩下一个以1为概率的符号厅列。最后,按照与编码过程相反的顺序读出各个符号序列所对应的二进制数字组,就可分别得到各该符号序列的码字。

除了霍夫曼编码外,霍夫曼在其他方面也还有不少创造,比如他设计的二叉最优搜索树算法就被认为是同类算法中效率最高的,因而被命名为霍夫曼算法,是动态规划(dynamic programming)的一个范例。

霍夫曼在MIT一直工作到1967年。之后他转入加州大学的Santa Cruz分校,是该校计算机科学系的创始人,1970—1973年任系主任。1994年霍夫曼退休。

霍夫曼除了获得计算机先驱奖以外,还在1973年获得IEEE的McDowell奖。1998年IEEE下属的信息论分会为纪念信息论创立50周年,授予他Golden Jubilee奖。霍夫曼去世前不久的1999年6月,他还荣获以哈明码发明人命名的哈明奖章(Hamming Medal)。

全国各地天气预报查询

上海市

云南省

云南省

云南省