戴維·霍夫曼
戴維·霍夫曼他發明了著名的“霍夫曼編碼”
著名的“霍夫曼編碼”的發明人戴維·霍夫曼 (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年出版本書，獲美國新聞出版界的最高榮譽普利茲獎，戈巴契夫為本書接受了兩次採訪，里根也接受了數次採訪。
