第三章 信源编码和数据压缩

上一章中讲述的编码问题属于等长编码问题。

先来看，在上一章当中我们给出的 I=\{1,2,\cdots,M\} ，相当于每次都只用一个元素来作为 \cal X^n 中那个对应元素的码字，而实际上当 \cal X 中元素比较多时，我们根本找不到那么多的不同码字。因此，首先需要考虑的是用 D- 进字母集来构造我们需要的 I 。

定义1 {\cal U}:=\{0,1,\cdots,D-1\} 称为 D- 进字母集。等长编码即是从 {\cal X}^n\to {\cal U}^k 的一个映射。我们定义 \[\frac{k}{n}\] 为此编码的码率，单位为 \log D 。

注 此处码率的定义与先前并不矛盾，因为事实上按照之前的定义，码率应为 \frac{k}{n}\log D ，不过这里的定义变成以 \log D 作为单位了而已。

不过既然用到了 D- 进字母集，那么我们自然会想：编码时也不是一定非得要用 k 个字母啊！比方说单独把 0 或者 1 拿出来，只要不引起混淆，它们也可以成为一个码字嘛。所以 D- 进字母集的引进，启示我们进一步去研究不等长的编码问题。

注 之前给出的编码问题，就是 k=1 的等长编码问题。

首先我们给出不等长编码及其平均码长的概念：

定义2 设 \cal X 为信源字母集， \cal U 是 D- 进字母集。 \cal U^* 是 \cal U 中全体的有限长序列构成的集合，则从 \cal X^n 到 \cal U^* 的映射 f 称为一个不等长编码，从 \cal U^* 低温等离子到 \cal X^n 的映射 \varphi 称为一个译码。用 l(x^n) 表示 f(x^n) 的码字长度，则 \bar l:=\sum\limits_{{x^n} \in {X^n}} {p({x^n})l({x^n})} 称为此编码的平均码长。

注1 我们研究的不等长编码一般都是 n=1 的情形。

注2 不难看出，在等长编码中，码率就精品店货源是平均码长(这句话我不知道对不对，书上没有写，但是看起来应该是这样的O.O)。

定义3 称从 \cal X^* 到 \cal U^* 的一个映射 f^* 为有限扩张编码，如果对 \cal X 中任意有限长序列成立

f^*(x_1,\cdots,x_m)=(f(x_1),\cdots,f(x_m)) 。

如果 f^* 是单射，则称 f 编出的码是唯一可译码。

利用定义2与定义3，我们重新给出信源编码定理的加强版：

定理1(信源编码定理plus) 设 X=\{X_k\} 是无记忆信源。

(1)若 R\ge H(X) ，则存在平均码长不小于 R 的唯一可译码。

(2)若 R<H(X) ，则不存在平均码长不超过 R 的唯一可译码。

注 这个plus版是我自己推广的，我也不知道对不对O.O

接下来我们来看一个例子：

例1 设随机变量

X\sim\left[ {\begin{array}{*{20}{c}} 1&2&3&4\\ \displaystyle{\frac{1}{2}}&{\displaystyle\frac{1}{4}}&{\displaystyle\frac{1}{8}}&{\displaystyle\frac{1}{8}} \end{array}} \right] ，

试分析用等长码和不等长码哪个对其编码更好(即平均码长更短)。

解 计算得 H(X)=1.75\rm bit 。若用等长码编码，则由信源编码定理，其码字长至少为 2 。故此时其码率(平均码长)也为 2 。

若用不等长码编码，不妨令 \[f(1,2,3,4) = (0,10,110,111)\] ，则可计算得平均码长也等于 1.75\rm bit ，它恰好等于 H(X) 。于是它就是平均码长最短的码，当然优于等长码。□

注 我们再考虑这样一个问题：在例1中，若令 \[f(1,2,3,4) = (0,1,00,11)\] ，则可计算得平均码长为 1.25<1.75=H(X) ，这是否与定理1矛盾呢？其实不然，因为这样编出的码并非唯一可译码(事实上 f^*(112211)=001101=f^*(3412) )。

是否唯一可译码就是好码呢？答案也是否定的，再来看下面的例子。

例2 设 f(1,2,3,4)=(0,566考试吧01,011,111) ，则它显然是唯一可译码，但是高速光耦如果编好的码的序列中出现了一个 0 ，译码器不一定能尽快(即在有限步内)判断出这到底是 1 ，还是 2 ，还是 3 ，必须得直到出现了下一个 0 后，再倒推回去。

而例1中的不等长码就没有这个毛病，只要见到 0 ，译码器就知道这个码字结束了，而就算见不到 0 ，只要连续出现 3 个 1 ，它也可以对应翻译成 4 。究其原因是因为，例1编出的码字集中，没有任何一个码字是另一个码字的前缀。下面我们给出这种码的严格定义。

定义4 称唯一可译码为即时码，如果 f 编出的码字集中，没有任何一个码字是其他码字的前缀。

注 显然即时码是唯一可译码，但反之不然。

下面我们用码树来研究即时码码长应满足的条件，并构造即时码。

如图就是一个码树，我们把 A 所在的那一层称为第 0 层， B 所在的称为第一层，以此类推。 A,B 它们所在的那些位置称为节点。可以看出每个节点都对应了一个码字，例如 C 对应的码字就是 22 。

若要构造一个即时码，则显然选取了一个节点作为码字后，它分支出的那些节点就不能再做码字。假设这棵树一共需要用到 M 层，则容易知道第 M 层共有 D^M 个节点。这 D^M 个节点中有些用于确定了长为 M 的码字，有些是其他码字分支出的节点，有些二者都不是。现在利用这个关系来建立不等式：

如果我在第 i 层确定了一个码字，则它延伸到第 M 层时，就有 D^{M-i} 个节点无法使用。因此设第 k 个码字的长为 l_k ，则它限制了第 M 层的 D^{M-l_k} 个码字无法使用。而所有的码字限制的第 M 层的节点数，加起来应当不超过 D^M 。因此我们有 \sum\limits_i {{D^{M - {l_i}}}} \le D^M 。

此即 \[\sum\limits_i {{D^{ - {l_i}}}} \le 1\] ，称为 \rm Kraft 不等式。

反过来，给定一个满足 \rm Kra笔记本如何重装系统ft 不等式的码长集，能否构造一个以它们为码长的即时码？回答是肯定的，证明在这里略去了，总之还是利用码树的性质。我们把以上的讨论总结为如下定理：

定理2( \rm Kraft 不等式) 存在码长为(l_1,\cdots,l_m)的D-进即时码当且仅当\[\sum\limits_{i = 1}^m {{D^{ - {l_i}}}} \le 1\]。

注1 定理2的结论对可列无穷码长集也成立。

注2 定理2的必要性对唯一可译码也成立。

在本节最后，我们来求平均码长何时最小。首先注意到，问题可转化为如下的多元最优化问题：设 X\sim p(x) 取值于有限集 \cal X ， X_i 对应的码字长为 l_i ，概率为 p_i ，要求

\[\begin{array}{l} \min \sum\limits_{i = 1}^m {{p_i}单摆周期{l_i}} \\ s.t.\sum\limits_{i = 1}^m {{D^{ - {l_i}}}} \le 1 \end{array}\]

于是可利用\rm Lagrange乘数法求解。具体过程从略，最优解为\[ - ({\log _D}{p_1}, \cdots ,{\log _D}{p_m})\]，

最优值(平均码长)为 H_D(X) ，即 X 的D- 进熵。

进而我们可以得到最优码长定理：

定理3(最优码长定理) 一个随机变量 X 的任何 D- 进即时码码长应满足 \bar L\ge H_D(X) 。并且等号成立当且仅当 D^{-l_i}=p_i 对所有 i 成立。

注 定理3提示我们，如果要构造平均码长最短的最优码，应当选取码字长 l_i ，使得 D^{-l_i} 充分接近 p_i 。在实际情况下 \[{\log _D}{p_i}\] 未必是整数，于是可以对都市重生小说排行榜其作上取整处理。这样构造的码称香农码。

从定理3我们又可以定义唯一可译码的冗余度了，因为如果平均码长大于 H_D(X) ，则说明没能最大程度地携带信息。

定义5 D 进唯一可译码的冗余度定义为 \bar L-H(X) ，相对冗余度定义为 1-\frac{H(X)}{\bar L} 。

哈夫曼码是编码理论下平均码长最短的码，是一种逐个元素编码的方法。它的基本思想是：让出现概率最小的那些字母匹配最长的码字，而出现概率最大的字母匹配最短的码字。接下来我们以 2 进 \rm Huffman 码为例，简述此编码方法：

算法1( 2 进 \rm Huffman 码)

步0 给定 X\sim p(X) ，其中 X 取值于有限集 \cal X ，令 m=||\cal X|| ；

步1 将所有信源字母排序，使得 p_1\le 篮球架多高p_2\le\cdots\le p_m；

步2 将 X_1 和 X_2 的码字前面一个添加 0 ，一个添加 1 (顺序任意)。如果它们中的某个是“大字母”，那么添加“ 1 ”的意思是将大字母中的所有字母对应的码字前面添加 “1”；

步3 将 X_1 与 X_2 看成一个大字母，其概率为 P=p_1+p_2 ；

步4 若 P=1 ，则编码已结束，否则令 m=m-1 ，转步1。

下面举一例作为应用：

例3 设 \[X \si薯条图片m \left( {\begin{array}{*{20}{c}} 1&2&3&4&月斜碧纱窗5&6\\ {0.24}&{0.2}&{0.18}&{0.16}&{0.14}&{0.08} \end{array}} \right)\] ，求三进 \rm Huffman 码。

解 编码过程如下图所示：

计算可得平均码长 \bar L=2 。□

但注意到对于此题，如果再加入一个概率为 0 的虚元素：

则平均码长变为 \bar L=1.76<2 ，比刚才更小了。一般地，我们有如下的定理：

定理4 在进行 D 进 \rm Huffman 编码时，如果最后剩下需编码的元素不足 D 个，则应在原信源中增加一些概率为 0 的虚元，使得最后剩下需编码的元素刚好 D 个，此时编出的码码长最短。

哈夫曼码简单易行，效率高。但也有许多不足之处，例如：

1.对单个字母进行编码时，平均码长与理论上的最优压缩率可能还有一定距离，此时仍然需要对 n 长序列再进行编码。

2.当 ||\cal X|| 很大时，算法不是很方便。

3.从硬件上看，需要缓冲储存器。

4.差错扩散：变长码一旦发生错误，某个码字的前缀可能成为另一个码字。并且可导致差工笔画家错后传。

考不考填空题我也不知道o.o

本节介绍一种利用累积分布函数来分配码字的构造性的编码方法，通常称香农-法诺码。首先我们给出累积分布函数的定义：

定义6 设 X\sim p(x) ，取值于有限字母集，则称

F(x):=\sum\limits_{a \le x} {p(a)}

为 X 的累积分布函数，称

\bar F(x):=F(x)-\frac{1}{2}p(x)

为 X 的修正累积分布函数。

由于 \bar F 单调增，因此可以考虑用 \bar F(x) 的二( D )进小数表示来作为 x 的码字。如果它们都有有限的二进小数表示，那么可以证明这样编出的码是唯一可译的即时码(证明略)。那么如果 \excel如何排序bar F(x) 没有有限二进小数表示怎么办？实际上我们可以取 x 的无限小数表示中的前 l(x) 位，其中 l(x) 应当满足： \[\bar F(x) - {\left\lfloor {\bar F(x)} \right\rfloor _{l(x)}} < \frac{1}{{{2^{l(x)}}}}\] 。

特别地可以取 \[l(x) = \left\lceil {\log \frac{1}{{p(x)}}} \right\rceil + 1\] 。则这样编出的码仍然是唯一可译即时码。并且可以证明，这样编出的码的平均码长不会超过熵 2\rm bit 以上。将以上讨论总结为如下的算法：

算法2(香农-法诺码)

步0 给定 X\sim p(x) ，并对字母作排序(任意顺序均可) X_1,\cdots,X_n ， 令k=1 ；

步1 计算 \bar F(x_k) ，并转化为二进小数；

步2 计算 \[l(x_k) = \left\lceil {\log \frac{1}{{p(x_k)}}} \right\rceil + 1\] ，令 \[f(x_k) = {\left\lfloor {\bar F(x_k)} \right\rfloor _{l(x_k)}}\] ；

步3 若 k=n ，则算法终止，输出 f ，否则令 k= k+1 ，转步1。

我们还是举一例作为算法的演示：

例4 设 \[X\sim\left( {\begin{array}{*{20}{c}} 1&2&3&4&5\\ {0.25}&{0.25}&{0.2}&{0.15}&{0.15} \end{array}} \right)\] ，试编出 2 进香农-法诺码。

解 编码过程如下图所示：

平均码长为 \bar L=3.5\rm bit ，而信源熵为 H(X)=2.28\rm bit ，只多了 1.22\rm bit 。□

对于 n 长序列，也可以用类似于香农-法诺码的方法进行编码，此时编码方法称为算术码。我们以 2 进信源为例，把它总结为如下的算法3：

算法3(*)( 2 进信源的算术码)

步0 给定 \[({X_1}, \cdots ,{X_n})\sim p({x_1}, \cdots ,{x_n})\] ，诸 X_i 均取自 {\cal X}手机屏幕碎了怎么办=\{0,1\} ，按字典序对所有 X^n 排序：规定(x_1,\cdots,x_n)先于(y_1,\cdots,y_n)当且仅当\[\overline {{x_1} \cdots {x_n}} < \overline {{y_1} \cdots {y_n}} \] ，用 x_n(i) 表示上述字典序下第 i 个向量，令 i=1 ； F(x_n(0))=0,\bar F(x_n(ml姿势0))=0 ，再令 j=1 ， z=0 。

步1 计算 F(x_n(i))=F(x_n(i-1))+p(x_n(i)) ；

步2 若 F(x_n(i))>p(z) ，则 g(x_n(i))=1 ，z=\overline{z1} ，否则 g(x_n(i))=0 ， z=\overline{z0} ；

步3 令 f(x_n(i))=\overline{f(x_n(i))g(x_n(i))} ，若 j< n ，令j=j+1，转步2；

步4 令 j=1,z=0 ；

步5 若 i< 2^n ，令 i = i+1 ，转步1，否则算法终止，输出 f 。

本节简介 \rm LZ 算法的基本原理，它是一种普适性的编码方法。在之前3.3和3.4节所提到的编码方法都需要提前知道信源的统计特性(即概率分布)，而 \rm LZ 算法并不需要知道信源的统计特性，可以用于处理不同的文本。

\rm LZ 算法的核心思路是：假设系统能够储存一段 n 长的记忆序列，如图：

那么我们现在要对方框后面的字符串进行编码，即从 d 开始编码。方框中的内容是之前已经编好了的，因此我们可以在方框里搜索一下，有没有哪个字符串和 d 之后的字符串是匹配的？如果脑力男人时代有多个的话，哪个是最大的匹配？找到最大的那个匹配字符串后，我们就可以把那个最大匹配的字符串的编码直接照搬过去。这就是 \rm LZ 算法的原理。

实际上最大匹配也就是" d\_ "这个字符串，如图：

注意到方框里的 d 在即将编码的 d 的前面 6 位，并且匹配的字符串长为 2 。因此我们不妨用有序数对 (1,2,6) 来表示。其中 1 表示找到匹配。在译码时只需把前面译好的码复制过来即可。

这个字符串处理好之后，就把窗口向右移手机处理器 2 位，继续判断后面的字符串是否能够找到匹配即可。事实上

前面方框里面根本找不到大 A ，所以肯定是没有匹配的。这样我们就记为 (0,A) ，它表示 A 在前面方框中找不到匹配。于是我们只能把 A 单独译出。

同理，这件事做完之后我们再把窗口右移一位，

可以发现最长匹配的字符串是“ \_wood ”，长度为 5 ，两个 "\_" 之间相差了 13 位，于是记为 (1,5,13) 即可。

以上即为 \rm LZ 算法的工作原理。在计算机中实际操作时，可用如下的算法来确最大匹配的字符串长度 L_{max} 及相差位数 \rho_{min} ：

那么现在只剩最后一个问题了，就是 (1,L,\rho) 和 (0,x_0) 需ubuntu安装gcc要编成二进码字。究竟需要多少位的码字呢？对此我们有如下的结论：

定理5 \rm LZ 算法中每个信源字母的平均码率不超过

\[\frac{{\left\lceil {logL} \right\rceil }}{{L + 1}} + \frac{{\left\lceil {{\mathop{\rm O}\nolimits} (\log \log L)} \right\rceil }}{{L + 1}} + \frac{{\left\lceil {\log n} \right\rceil }}{{L + 1}} + \frac{{\left\lceil {\lo房产证生成器g \left\| {\cal X} \right\|} \right\rceil }}{{L + 1}}\] 。

而可以证明，当 n\to\infty 时，上式趋于信源的熵率 H_\infty(X) 。因此从理论展会宣传上来看， \rm LZ 算法是最优的。

下面再简介一种 \rm LZ 算法的推广形式： \rm LZW 算法。我们还是用一个例子来讲述其原理：

假设信源序列发出的消息字符序列为：

\[x_0^{ + \infty } = {x_0}{x_1}{x_2} \cdots = babcabbabadbadc \cdots \]

那么我们一边编码，一边构造一个字典，以便于以后译码时查找。

首先，接收到的第一个字符是 b ，而我们现在还没有字典，故只能先把这个字符储存起来。于是把它记作 (0,b) 。同时， b 成为第一个码字，在字典中规定其序号为 1 。

第二个收到的字符是 a ，我们同样在字典中差找不到。故只能记作 (0,a) ，在字典中规定其序号为 2 。

再往后看，诶，又出现了一个 b ，而此时它已经在我们的字典里了，它的序号就是 1 ，故此时我们把它后面的 c 也加进来，把 bc 这个整体记作 (1,c) ，并记入字典，规定其序号为 3 。

同理，再往后是 ab ，我们把它记作 (2,b) ，记入字典，规定其序号为 4 ；

再往后是 ba ，记作 (1,a) ，字典序为 5 ；

再往后是 bad ，记作 (5,d) ，字典序为 6 ；

……

用表格的形式展示就是：

译码时，如果收到的码字是 (l,x) ，那么就在字典中查找第 l 个位置对应的序列，再将 x 加在后面就可以了。

最后，我们还是要将 (l,x) 编成码字。由上面的结论，需要 \[\left\lceil {\log l} \right\rceil + {\mathop{\rm O}\nolimits} (\log \log l)\] 比特来表示它。假设 n 长的整个信源序列被该方法分成了 l(n) 个码字，那么整个信源序列总共需要

\[l(n)(\log l(n) + \log \left\| {\cal X} \right\|)\]

比特，其码率为 \[\蒙古栎frac{{l(n)(\log l(n) + \log \left\| {\cal X} \right\|)}}{n}\] 比特。可以证明，当信源为平稳遍历信源时， n 趋于无穷时上式也依概率收敛到 H_\infty(X) 。