霍夫曼編碼又譯為哈夫曼編碼、赫夫曼編碼,是壹種用於無損數據壓縮的熵編碼(權編碼)算法。
在計算機數據處理中,霍夫曼編碼使用變長編碼表對源符號(如文件中的壹個字母)進行編碼,其中變長編碼表是通過壹種評估來源符號出現機率的方法得到的,出現機率高的字母使用較短的編碼。
反之出現機率低的則使用較長的編碼,這便使編碼之後的字符串的平均長度、期望值降低,從而達到無損壓縮數據的目的。
例如,在英文中,e的出現機率最高,而z的出現概率則最低。當利用霍夫曼編碼對壹篇英文進行壓縮時,e極有可能用壹個比特來表示,而z則可能花去25個比特(不是26)。用普通的表示方法時,每個英文字母均占用壹個字節,即8個比特。
二者相比,e使用了壹般編碼的1/8的長度,z則使用了3倍多。倘若我們能實現對於英文中各個字母出現概率的較準確的估算,就可以大幅度提高無損壓縮的比例。
霍夫曼編碼的優缺點
1、霍夫曼編碼優點
霍夫曼編碼的碼長雖然是可變的,但卻自帶同步代碼。例如,碼串中的第1位為0,那末肯定是符號A,因為表示其他符號的代碼沒有壹個是以0開始的,因此下壹位就表示下壹個符號代碼的第1位。
同樣,如果出現“110”,那麽它就代表符號D。如果事先編寫出壹本解釋各種代碼意義的“詞典”,即碼簿,那麽就可以根據碼簿壹個碼壹個碼地依次進行譯碼。
2、霍夫曼編碼缺點
霍夫曼編碼沒有錯誤保護功能,在譯碼時,如果碼串中沒有錯誤,那麽就能壹個接壹個地正確譯出代碼。但如果碼串中有錯誤,哪僅是1位出現錯誤,不但這個碼本身譯錯,更糟糕的是壹錯壹大串,全亂了套,這種現象稱為錯誤傳播。
計算機對這種錯誤也無能為力,說不出錯在哪裏,更談不上去糾正它。另外霍夫曼碼是可變長度碼,因此很難隨意查找或調用壓縮文件中間的內容,然後再譯碼,這就需要在存儲代碼之前加以考慮,硬件實現有難度。
以上內容參考:百度百科—霍夫曼編碼