戴維·霍夫曼

他發明了著名的“霍夫曼編碼”

著名的“霍夫曼編碼”的發明人戴維·霍夫曼 (David Albert Huffman)已於1999年10月17日因癌症去世，享年74歲。但他作為資訊理論的先驅，對計算機科學、通信等學科所作出的巨大貢獻將永遠為世人所銘記。

1925年生於俄亥俄州，從小聰慧好學，他在俄亥俄州立大學畢業時只有17歲。然後他進入MIT一邊工作，一邊深造，霍夫曼編碼就是他在1952年做博士論文時發明的。這是一種根據字母的使用頻率而設計的變長碼，能大大提高信息的傳輸效率，至今仍有廣泛的應用。為了說明霍夫曼編碼的原理，我們以僅有6個字元的信息傳輸為例。在等長編碼情況下，每個字元需要3個二進位位。在字元出現概率不同的情況下，我們可以設計出不等長的碼，如圖所示，從而大大降低發送一個訊息所需要的總字元數。因為如圖所示的編碼，雖然每個字元所需的二進位位的算術平均數為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)。

戴維·霍夫曼(David E. Hoffman)，《華盛頓郵報》編輯，駐白宮記者，報道過里根、布希的任期，涵蓋美蘇首腦峰會；蘇聯解體時負責報道國外新聞，后駐耶路撒冷，全程報道“奧斯陸協議”簽訂;1995年到2001年，負責《華盛頓郵報》莫斯科記者站，2002年出版《寡頭：新俄羅斯的財富與權力》;2010年出版本書，獲美國新聞出版界的最高榮譽普利策獎，戈爾巴喬夫為本書接受了兩次採訪，里根也接受了數次採訪。