熵编码
熵编码(entropy encoding)是一类利用数据的统计信息进行压缩的无语义数据流之无损编
码。本章先介绍熵的基本概念，然后介绍香农-范诺(Shannon-Fano)编码、哈夫曼(Huffman)编
码、算术编码(arithmetic coding)、行程编码(RLE)和 LZW 编码等常用的熵编码方法。
1 熵
熵(entropy)本来是热力学中用来度量热力学系统无序性的一种物理量（热力学第二定律：
孤立系统内的熵恒增）：
对可逆过程，
�
��� 0,
T
dQ
dS
T
dQ
S
（孤立系统）
其中，S 为熵、Q 为热量、T 为绝对温度。
（信息）熵 H 的概念则是美国数学家 Claude Elwood Shannon（香农 /仙农 / 向农）于
1948 年在他所创建的信息论中引进的，用来度量信息中所含的信息量：（为自信息量
i
i
p
sI
1
log)(
2
�
的均值/数学期望）
�
�
i
i
i
p
pSH
1
log)(
2
其中，H 为信息熵（单位为 bit），S 为信源，p
i
为符号 s
i
在 S 中出现的概率。
例如，一幅 256 级灰度图像，如果每种灰度的像素点出现的概率均为 p
i
=1/256，则
82log256log
1
log
8
222
����
i
p
I
)(82log
256
1
256256log
256
11
log
8
2
255
0
2
255
0
2
bit
p
pH
ii
i
i
�����
��
��
即编码每一个像素点都需要 8 位(I )，平均每一个像素点也需要 8 位(H)。
2 Shannon-Fano 编码
按照 Shannon 所提出的信息理论，1948 年和 1949 年分别由 Shannon 和 MIT 的数学教授
Robert Fano 描述和实现了一种被称之为香农-范诺(Shannon-Fano)算法的编码方法，它是一种
变码长的符号编码。
算法
