哈夫曼編碼,又稱霍夫曼編碼。
最佳編碼定理:在變字長碼中,對於出現概率大的信息符號編以短字長的碼;對於出現概率小的信息符號編以長字長的碼,如果碼字長度嚴格按照符號概率的大小的相反順序排列,則平均碼字長度一定小於按任何其他符號順序排列方式得到的碼字長度。
哈夫曼編碼步驟:
1、概率統計,得到n個不同概率的信號;
2、將n個信源信息符號的n個概率,按概率大小排序;
3、將最後兩個小概率相加,概率個數減少一個;
4、將減少後的個概率重新排序;
5、再將最後兩個小概率相加,概率個數再減一個;
6、如此反覆n減2次,得到只剩兩個概率序列;
7、以二進制碼元賦值,構成Huffman碼字。