无损压缩是有极限的, 这个极限与1948年香农(Claude Elwood Shannon)提出的“信息熵”有关.
$$H(U)=E(-\log p_i)=-\sum^{n}_{i=1}\log p_i$$
其中$U$表示全集其中包含$n$种信号类型,$p_i$表示第$i$种信号出现的频率.

举个例子

拿大家都比较喜欢的一句话”hello world”举例. 我们分析其中包含的信息:
这是一个英文字符串, 由英文字母和符号组成. 将英文字母及符号看作信息的基本单位, 那么这个字符串中出现了’h’,’e’,’l’,’o’,’ ‘,’w’,’r’,’d’,8个字符其出现频率如下表所示:

字符	h	e	l	o		w	r	d
频次	1	1	3	2	1	1	1	1
频率($p$)	0.091	0.091	0.273	0.182	0.091	0.091	0.091	0.091

由此”hello world”的信息熵可以通过计算得到 :
$$H(“hello; world”)=E(-\log_2 p_i)= 0.314+0.314+0.511+0.447+0.314+0.314+0.314+0.314
=2.845$$
以上数值保留三位小数, 结果的单位是比特. 他的含义是’hello world’这个字符串中, 平均每个字符最少需要2.845个二进制位来表示.
也就是说, 为了表示”hello world”这个字符串需要$11*2.845=31.295$个二进制位, 为保证数据完整性我们进行上取整得到真实二进制位数为32位.

现在我们换个角度, 如果这个字符串存储在计算机中, 那么它的实际存储形式是二进制的ASCII码.
将”hello world”字符串转换为ASCII码二进制表示 :

	h	e	l	o		w	r	d
ASCII	104	101	108	111	32	119	114	100
二进制	01101000	01100101	01101100	01101111	00100000	01110111	01110010	01100100

“hello world”的字符串表示为二进制信号为:
0110100001100101011011000110110001101111001000000111011101101111011100100110110001100100
其中’0’,’1’两种信号的出现频率为:

字符	0	1
频次	43	45
频率	0.489	0.511

则”hello world”二进制表示的信息熵为:
$$H(“0110…100”)=E(-\log_2 p_i)=0.505+0.495=1.000$$
该结果表示上述的二进制信号每一位都需要一个二进制位来表示(废话), 也就是说用二进制ASCII码的方式表示”hello world”这个字符串最少需要$8*11=88$位二进制位.

以上, 我们似乎从两种角度得出了相悖的结论, 这是为什么呢?

回到第一个例子, “hello world”用32个二进制位如何表示显然不能直接使用ASCII码.
观察可知字符串中总共包含8种不同的字符, 可以给他们按0~7编号, 每个编号可以用3个二进制位来表示, 于是字符串可以用33个二进制位来表示, 比较接近32位的极限了.(另外如果使用哈夫曼编码也可以得到总码长32.023的二进制表示)

显而易见, 如果上述33位编码作为信息传递, 本质上传递的是一串二进制编码而非”hello world”这样的字符串. 想要切实得到目标字符串, 就需要发送方和接收方达成一些共识如下:

1. 传递的信息中每3位表示一个数值编码.
2. 8个编码与字符对照表(如 000对应’h’, 001对应’e’…)

这样的编码所能表达的范围仅为对应8个字符组合而成的字符串

类似的, 第二个例子中传递88位字符串也需要达成一些共识:

1. 传递的信息中每8位表示一个数值编码.
2. ASCII表

这样的编码所能表达的范围为256个ASCII字符组合而成的字符串

所以说, 虽然同样为了表示”hello world”这一信息, 第二个例子所承载的信息量上限高于第一个例子. 就像在白纸上写字, 我们接收文字信息的同时也知道了没写字的地方是空白的这一信息, 而大张的纸空白部分较小张纸更多. 这也是造成上述两个例子需要的实际二进制位数不同的原因.

理解信息熵公式

我们知道信息熵是衡量信息系统混乱程度的指标.
公式中包含$E(-\log p_i)$, 显然它计算的是一个期望.
我们将它的基本项 $-\log p_i$ 变形为 $\log \frac{1}{p_i}$. 其中$p_i$代表低i种信号出现的频率.
$\frac{1}{p_i}$可以表示如果系统中信号出现的平均出现频率为$p_i$时系统中可包含的信号种类.
$\log \frac{1}{p_i}$, 其中$\log$当log底数为2时, $\log_2 x$表示表达x数值所需要的最少二进制位数. 也即是说$\log \frac{1}{p_i}$表示 当系统中信号评价出现频率为$p_i$时每个信号所需的最少二进制位数.
由此, 信息熵公式中当$\log$的底数为2时可以理解为信息系统中每个信号所需的平均二进制位数, 单位为比特.

使用信息熵判断压缩极限的误区

前面提到无损压缩的极限与信息熵有关, 并不是意味着对一组数据直接计算信息熵就可以得出它的无损压缩极限.
例如一个字符串”UUUUUUUUUUUUUU…”,它的ASCII码二进制表示为”010101010101…”, 不论字符串有多长, 它的二进制表示中’0’和’1’各占50%, 用信息熵计算出的平均字符比特率为1, 那么它的压缩极限是$1*n$($n$为字符串长度)吗?
当然不是.
对这样全是重复内容的字符串我们显然可以用”n个U”这样很少的信息量来表示.

实际上, 信息熵公式中的$p_i$表示每种信号出现的概率, 而非绝对意义上每个字符或者每个二进制位出现的概率. 压缩数据时先对数据进行合理的划分, 而后根据划分每个部分出现的频率计算信息熵才合理.
换言之, 信息熵所反映的是信息在特定全集下的压缩率极限, 不能简单理解为压缩软件的压缩率极限.

(待续未完…)