概念
层数:叶子节点为待编码的数据,根为第0层.
编码长度:第
L
L
L层数据编码后的长度为
L
L
L.
节点概率:若节点为叶子节点,则概率为叶子所编码数据的频率
f
i
f_i
fi.或者一种不太严谨的方式,叶子节点的概率为所编码数据的概率
p
i
p_i
pi.若节点为非叶子节点,概率为两个子节点的概率之和.
定理
定理1: 在哈夫曼树的构造过程中,高层节点的概率不高于低层节点的概率
定理2: 哈夫曼树根节点的概率为1
定理3: 若某个节点概率为
p
p
p,长度为
L
L
L,那么这个节点的概率满足
L
≤
lg
1
p
+
1
L\le \lg\frac{1}{p}+1
L≤lgp1+1
或
p
≤
(
1
2
)
L
−
1
p\le (\frac{1}{2})^{L-1}
p≤(21)L−1
例如,频率超过0.5的数据编码长度不会超过1,频率超过0.25的数据编码长度不会超过2等
定理3的证明:
使用反证法.若第l层的节点N不满足定理2,即
p
l
>
(
1
2
)
l
−
1
p_l>(\frac{1}{2})^{l-1}
pl>(21)l−1
根据定理1,N的父节点与N父节点的兄弟节点的概率不会小于
(
1
2
)
l
−
1
(\frac{1}{2})^{l-1}
(21)l−1,即N的爷爷节点概率不会小于
2
⋅
(
1
2
)
l
−
1
2\cdot (\frac{1}{2})^{l-1}
2⋅(21)l−1.利用数学归纳法易得,N第j层的祖先节点(j<l)满足关系
p
j
>
2
l
−
j
−
1
⋅
(
1
2
)
l
−
1
=
(
1
2
)
j
p_j>2^{l-j-1}\cdot (\frac{1}{2})^{l-1}= (\frac{1}{2})^{j}
pj>2l−j−1⋅(21)l−1=(21)j
这个式子表面第0层的概率
p
0
>
(
1
2
)
0
=
1
p_0> (\frac{1}{2})^{0}=1
p0>(21)0=1,与定理2矛盾.因此定理3总成立.
最大编码长度
哈夫曼编码后数据的长度计算方式为,对每一个数据出现的频率与数据编码长度求积,这些积的和即为编码长度.若第i个数据出现的概率为
p
i
p_i
pi,长度为
L
i
L_i
Li,则编码长度为
L
=
∑
i
p
i
⋅
L
i
L=\sum_i p_i\cdot L_i
L=i∑pi⋅Li
根据定理3,哈夫曼编码后的数据长度不会超过
∑
i
p
i
(
lg
1
p
i
+
1
)
=
∑
i
p
i
lg
1
p
i
+
∑
i
p
i
=
∑
i
p
i
lg
1
p
i
+
1
\sum_i p_i(\lg\frac{1}{p_i}+1)=\sum_i p_i\lg\frac{1}{p_i}+\sum_i p_i=\sum_i p_i\lg\frac{1}{p_i}+1
i∑pi(lgpi1+1)=i∑pilgpi1+i∑pi=i∑pilgpi1+1
单位为bit.注意到第一项是所谓的信息熵.若
p
i
p_i
pi全部都为
1
/
2
1/2
1/2的幂次(即
p
i
=
1
/
2
k
,
k
∈
N
p_i=1/2^k,k\in N
pi=1/2k,k∈N),则哈夫曼编码后的长度为
∑
i
p
i
lg
1
p
i
\sum_i p_i\lg\frac{1}{p_i}
∑ipilgpi1
