Huffman编码字典构造
Huffman编码字典构造
Huffman编码的构造
对符号集的元素进行排序,使
- If
K=2 - 赋值
cα0="0" 和cα1="1" - else
- 创建一个新的符号集
AX′={α′1,α2,⋯,αK−1} ,分配满足fX′={fX(α0)+fX(α1),x=α′fX(x),其他
的概率fX′ 。递归调用编码构造算法,找到对应AX′ 和fX′ 的优化编码cα′1,cα2,⋯,cαK−1 。通过在cα′1 后增加“0”和“1”扩展编码,分别得到cα0 和cα1 。
end
上述算法就是Huffman编码的字典构造方法。
Huffman字典计算示例
假定
计算该符号集的Huffman编码字典。
下图是手算Huffman字典的方法:
在开发私有codec时,如果用到Huffman编码,则最好需要通过大规模的样本获得概率分布数据。只要获得概率数据,无需编程、无需手算就可以获得编码效率最高的Huffman字典。