很久以前就听说过数据压缩的极限是熵值,一直没能理解,刚才把Shannon’s source coding theorem看了一下,总算懂一点了。

设定是,\(\Sigma_1, \Sigma_2\)是两个alphabets,编码(codes)\(f\)是从\(\Sigma_1\)到\(\Sigma_2^*\)的映射。令\(a = |\Sigma_2|\),为了简单起见,这里假设\(\Sigma_2 = \{0, 1\}\) (so \(a = 2\)). 并且,我们要求f是uniquely decodable codes(见置底链接)。\(\Sigma_1\)可以看成是原文的字母表,不妨令\(\Sigma_1 = \{s_1, \dots, s_n\}\),并设\(s_i\)出现的概率是\(p_i\)。令随机变量\(X\)的取值范围是\(\Sigma_1\),且\(\Pr[X = s_i] = p_i\)。令随机变量\(S = |f(X)|\)。Shannon’s source coding theorem说,如果f是最优的,那么\(H(X) \leq E[S] < H(X) + 1\)。

Uniquely decodable codes的要求很合理,因为这个定理的适用范围是无损,是必须正确解码。而这个定理说的是,最优码率不可能比熵值更优,并且有一个非常接近熵值的且为uniquely decodable codes的编码(其实也为prefix codes),而且还可以把这个编码显式构造出来。

证明用到了Gibbs’ inequality和Kraft’s inequality。Gibbs的很易懂,Kraft的有点乱,其实说的是

  • 所有uniquely decodable codes都满足性质\(\sum_{i = 1}^n r^{-l_i} \leq 1\)。
  • 对所有满足该性质的\({l_i}\)都可以构造出一个prefix codes(prefix codes也是uniquely decodable codes)。

嗯,是这么个关系。

Links: