第4章离散无记忆信源无失真编码4.1基本要求通过本章学习，了解信源编码的基本术语和基本概念，掌握码的唯一可译性、码树和Kraft不等式等重要概念、定长无失真编码定理及其思想、变长编码定理（香农第一定理及其思想、三种重要的变长编码方法：霍夫曼编码、费诺编码和香农编码。掌握几种实用的无失真信源编码方法：游程编码、算术编码和基于字典的编码。4.22学习要点4.2.1信源编码的基本术语码元：信道能够传送的符号x称为码元。码元集：所有码元组成的集合X={2"x）称为码元集。信源编码：把信源U输出的符号u,变换成码元序列w,。码字：码元序列w,称为码字。码或码字集：所有码字组成的集合W={w,W2，"wg）称为码或码字集。码长：码字w,所含码元的个数称为该码字的码长，记为l，单位是“码元/符号”或“r进制单位/符号”。定长码：如果所有码字均有相同的码长1，即l,=l，=…=l=1，则称为定长码。变长码：不是所有码字的码长均相同的编码，称为变长码。平均码长I：对码W中所有码字的码长求统计平均，得平均码长T。T-ZP(w,),=ZP(u,),(4.1)码元/符号i=11=1平均码长「小说明平均一个码元所携带的信息量大，信息的允余就小。编码后的信息率：编码后平均一个码元携带的信息量即为编码后的信息率，记为R。H(U)bit/码元(4.2)R= H(X)=A编码效率：定义编码后的实际信息率与编码后的最大信息率之比为编码效率，记为n。。118
118 第 4 章 离散无记忆信源无失真编码 4.1 基本要求 通过本章学习，了解信源编码的基本术语和基本概念，掌握码的唯一可译性、码树和 Kraft 不等式等重要概念、定长无失真编码定理及其思想、变长编码定理（香农第一定理） 及其思想、三种重要的变长编码方法：霍夫曼编码、费诺编码和香农编码。掌握几种实用的 无失真信源编码方法：游程编码、算术编码和基于字典的编码。 4.2 学习要点 4.2.1 信源编码的基本术语 码元：信道能够传送的符号 i x 称为码元。 码元集：所有码元组成的集合 1 2 X {,} r xx x 称为码元集。 信源编码：把信源U 输出的符号ui 变换成码元序列 wi 。 码字：码元序列 wi 称为码字。 码或码字集：所有码字组成的集合 1 2 { , , } W ww w q 称为码或码字集。 码长：码字 wi 所含码元的个数称为该码字的码长，记为 i l ，单位是“码元/符号”或“ r 进 制单位/符号”。 定长码：如果所有码字均有相同的码长l ，即 1 2 q ll ll ，则称为定长码。 变长码：不是所有码字的码长均相同的编码，称为变长码。 平均码长 l ：对码W 中所有码字的码长求统计平均，得平均码长 l 。 1 1 ( ) () q q ii ii i i l Pwl Pu l 码元/符号 （4.1） 平均码长 l 小说明平均一个码元所携带的信息量大，信息的冗余就小。 编码后的信息率：编码后平均一个码元携带的信息量即为编码后的信息率，记为 R 。 ( ) ( ) H U R HX l bit /码元 （4.2） 编码效率：定义编码后的实际信息率与编码后的最大信息率之比为编码效率，记为c
RH(X)H(U)/TH(U)(4.3)n. =TlogrRmaxH max(X)logr码的允余度：。=1-n。。4.2.2信源编码的基本概念4.2.2.1奇异码和非奇异码含有相同码字的码称为奇异码，否则称为非奇异码。4.2.2.2续长码和非续长码任一码字都不是另一码字的续长（加长），这种码称为非续长码：有些码字是在另一些码字后面添加码元（续长）得来的，称为续长码。4.2.2.3即时码码字的最后一个码元出现时，译码器能立即判断一个码字已经结束并译码，这种码称为即时码或立即码。4.2.2.4唯一可译码（UDC，UniquelyDecodableCode）码字组成的任意有限长码字序列可被译成唯一的信源符号序列。4.2.2.5各种码之间的关系奇异码非唯一可译码信源编码非奇异码『定长唯一可译码变长即时码（非续长码）和非即时码（部分续长码）4.2.2.6Kraft不等式对于任一r进制非续长码（或唯一可译码），各码字的码长l，，i=1,2，"，9，必须满足Kraft不等式：rs(4.4)反过来，若上式成立，就一定能构造一个r进制非续长码（或唯一可译码）。4.2.3定长无失真编码定理用r元符号表对离散无记忆信源U的次扩展信源进行定长编码，N长符号序列对应的119
119 max max () () () ( ) log log c R H X HU l HU R H X r lr （4.3） 码的冗余度： 1 c c 。 4.2.2 信源编码的基本概念 4.2.2.1 奇异码和非奇异码 含有相同码字的码称为奇异码，否则称为非奇异码。 4.2.2.2 续长码和非续长码 任一码字都不是另一码字的续长（加长），这种码称为非续长码；有些码字是在另一些 码字后面添加码元（续长）得来的，称为续长码。 4.2.2.3 即时码 码字的最后一个码元出现时，译码器能立即判断一个码字已经结束并译码，这种码称 为即时码或立即码。 4.2.2.4 唯一可译码（UDC，Uniquely Decodable Code） 码字组成的任意有限长码字序列可被译成唯一的信源符号序列。 4.2.2.5 各种码之间的关系 奇异码 非唯一可译码 信源编码 非奇异码 定长 唯一可译码 变长即时码（非续长码）和非即时码（部分续长码） 4.2.2.6 Kraft 不等式 对于任一 r 进制非续长码（或唯一可译码），各码字的码长 i l ，i q 1,2, , ，必须满足 Kraft 不等式： 1 1 i q l i r （4.4） 反过来，若上式成立，就一定能构造一个 r 进制非续长码（或唯一可译码）。 4.2.3 定长无失真编码定理 用 r 元符号表对离散无记忆信源U 的次扩展信源进行定长编码， N 长符号序列对应的
码长为l，若对于任意小的正数6，有不等式>H(U)+(4.5)Nlogr就几乎能做到无失真编码，且随着序列长度N的增大，译码差错率趋于0。反过来，若<H(U)-28(4.6)N-logr就不可能做到无失真编码，且随着N的增大，译码差错率趋于1。4.2.4无失真变长编码定理（香农第一定理）用r元符号表对离散无记忆信源U的N次扩展信源进行变长编码，记N长符号序列对应的平均码长为1w，那么，要做到无失真编码，平均码长必须满足≥H,(U)(4.7)N另一方面，一定存在唯一可译码，其平均码长满足<H,(U)+1(4.8)NN信源无失真变长编码定理是信息理论的重要定理，它给出了信源有效编码的基本界限。信源序列长度N趋于无穷时平均码长的极限：lim/=limk(4.9)=H(U)N→NN→编码效率的极限为H(U)H,(U)2=100%limlim n。= llim(4.10)1N-TlogrN→00N→a4.2.5变长编码方法4.2.5.1霍夫曼编码（Huffman）霍夫曼编码是1952年由霍夫曼提出，是一种非续长码，其平均码长最短，因此是最佳编码。1）二进制霍夫曼编码编码过程如下：（1）将信源符号按概率大小排序；（2）对概率最小的两个符号求其概率之和，同时给两符号分别赋予码元“0”和“1”120
120 码长为 Nl ，若对于任意小的正数 ，有不等式 ( ) log Nl H U N r （4.5） 就几乎能做到无失真编码，且随着序列长度 N 的增大，译码差错率趋于 0。反过来，若 ()2 log Nl H U N r （4.6） 就不可能做到无失真编码，且随着 N 的增大，译码差错率趋于 1。 4.2.4 无失真变长编码定理（香农第一定理） 用 r 元符号表对离散无记忆信源U 的 N 次扩展信源进行变长编码，记 N 长符号序列对 应的平均码长为 Nl ，那么，要做到无失真编码，平均码长必须满足 ( ) N r l H U N （4.7） 另一方面，一定存在唯一可译码，其平均码长满足 1 ( ) N r l H U N N （4.8） 信源无失真变长编码定理是信息理论的重要定理，它给出了信源有效编码的基本界限。 信源序列长度 N 趋于无穷时平均码长的极限： lim lim ( ) N r N N l l HU N （4.9） 编码效率的极限为 ( ) ( ) lim lim lim 100% log r c NN N H U H U lr l （4.10） 4.2.5 变长编码方法 4.2.5.1 霍夫曼编码（Huffman） 霍夫曼编码是 1952 年由霍夫曼提出，是一种非续长码，其平均码长最短，因此是最佳 编码。 1）二进制霍夫曼编码 编码过程如下： （1）将信源符号按概率大小排序； （2）对概率最小的两个符号求其概率之和，同时给两符号分别赋予码元“0”和“1”；
（3）将“概率之和”当作一个新符号的概率，与剩下符号的概率一起，形成一个缩减信源，再重复上述步骤，直到“概率之和”为1为止；（4）按上述步骤实际上构造了一个码树，从树根到端点经过的树枝即为码字。霍夫曼编码构造了一个非续长码，采用概率匹配方法来决定各码字的码长，概率大的符号对应于短码，概率小的符号对应于长码，从而使平均码长最短，但编出的码字并不唯一。2）r进制霍夫曼编码对于r进制霍夫曼编码，信源符号数q应满足(4.11)q=(r-1)o+r其中θ为信源缩减的次数。可通过给信源添加概率为零的符号满足上式。4.2.5.2费诺编码（Fano）费诺编码也是构造一个码树，因此编出的码也是非续长码，但不一定是最佳码。编码步骤如下：（1）将信源符号按概率从大到小排序：（2）将信源符号分成2组，使2组信源符号的概率之和尽量接近，并给2组信源符号分别赋码元“0”和“1”；（3）把各小组的信源符号再细分为2组并赋码元，方法与第一次分组相同：（4）继续分组，直到每一小组只含一个信源符号为止：（5）由此即可构造一个码树，所有终端节点上的码字组成费诺码。费诺编码的平均码长比霍夫曼编码略长，编码效率稍有下降。一般来讲，费诺编码不是平均码长最短意义下的最佳编码，可将其看作准最佳编码。4.2.5.3香农编码香农编码的步骤如下：（1）将信源符号按概率从大到小排序：（2）按下式求第i个信源符号对应的码长l，并取整；(4.12)-log P(u,)≤l,<-log P(u,)+1（3）按下式求第i个信源符号的累加概率P；[P =0(4.13)[P=P(u)i=23,..,qk=l（4）将累加概率P转换成二进制数：121
121 （3）将“概率之和”当作一个新符号的概率，与剩下符号的概率一起，形成一个缩减 信源，再重复上述步骤，直到“概率之和”为 1 为止； （4）按上述步骤实际上构造了一个码树，从树根到端点经过的树枝即为码字。 霍夫曼编码构造了一个非续长码，采用概率匹配方法来决定各码字的码长，概率大的 符号对应于短码，概率小的符号对应于长码，从而使平均码长最短，但编出的码字并不唯一。 2）r 进制霍夫曼编码 对于 r 进制霍夫曼编码，信源符号数 q 应满足 qr r ( 1) （4.11） 其中 为信源缩减的次数。可通过给信源添加概率为零的符号满足上式。 4.2.5.2 费诺编码（Fano） 费诺编码也是构造一个码树，因此编出的码也是非续长码，但不一定是最佳码。编码步 骤如下： （1）将信源符号按概率从大到小排序； （2）将信源符号分成 2 组，使 2 组信源符号的概率之和尽量接近，并给 2 组信源符号 分别赋码元“0”和“1”； （3）把各小组的信源符号再细分为 2 组并赋码元，方法与第一次分组相同； （4）继续分组，直到每一小组只含一个信源符号为止； （5）由此即可构造一个码树，所有终端节点上的码字组成费诺码。 费诺编码的平均码长比霍夫曼编码略长，编码效率稍有下降。一般来讲，费诺编码不是 平均码长最短意义下的最佳编码，可将其看作准最佳编码。 4.2.5.3 香农编码 香农编码的步骤如下： （1）将信源符号按概率从大到小排序； （2）按下式求第i 个信源符号对应的码长 i l ，并取整； log ( ) log ( ) 1 Pu l Pu ii i （4.12） （3）按下式求第i 个信源符号的累加概率 Pi ； 1 1 1 0 ( ) 2,3, , i i k k P P Pu i q （4.13） （4）将累加概率 Pi 转换成二进制数；
（5）取P二进制数小数点后l个二进制数字，作为第i个信源符号的码字。三种方法中，霍夫曼编码效率最高，费诺编码效率次之，香农编码效率最低。香农编码的实用价值不大，但却有很深远的理论意义，同时，也是算术编码的基础。4.2.6几种实用的无失真信源编码4.2.6.1游程编码游程编码主要用于黑、白二值文件的传真。白纸黑字的二值文件采用二元码进行编码，表示背景（白色）时像素为码元“0”，表示内容（黑字）时像素为码元“1”。参照国际标准：一张A4幅面的二值文件，可分1188行，每行1728个像素。重复出现的同类像素的长度称为游程长度（Run-length）。信源符号中重复出现的黑游程和白游程可归一化为统一的编码单元，其单元结构如下：符号码标识码游程长度实际文件的行扫描中，由于文件的二值性，黑、白游程总是交替出现，在第一游程的类型预先规定后，进行游程编码就可省去原单元结构中的“符号码”及“标识码”，仅保留游程长度数据。4.2.6.2MH码MH码是CCITT提出的文件、传真类一维数据压缩编码的国际标准，是由游程编码及霍夫曼编码结合而成的一种改进型霍夫曼码。MH码使用固定编码表进行编码，即在信源与信宿两端，利用预先确定的编码表各自独立进行编码和解码。MH码在编码中对游程长度进行分割，相应将长游程码（游程长度>64）分割为结尾码（终止码）和组合码（形成码）两部分，如表4.1及表4.2所示。表4.1MH码表(一）结尾码RL长度白游程码字RL长度黑游程码字黑游程码字白游程码字0001101013200001101110001101100000110101010001110103300010010000001101011201111134000100110000110100103103510000001010000001101001140113610110001010100001101010051100370011000101100000110101016111000103800010111000011010110122
122 （5）取 Pi 二进制数小数点后 i l 个二进制数字，作为第i 个信源符号的码字。 三种方法中，霍夫曼编码效率最高，费诺编码效率次之，香农编码效率最低。香农编码 的实用价值不大，但却有很深远的理论意义，同时，也是算术编码的基础。 4.2.6 几种实用的无失真信源编码 4.2.6.1 游程编码 游程编码主要用于黑、白二值文件的传真。 白纸黑字的二值文件采用二元码进行编码，表示背景（白色）时像素为码元“0”，表示 内容（黑字）时像素为码元“1”。 参照国际标准：一张 A4 幅面的二值文件，可分 1188 行，每行 1728 个像素。 重复出现的同类像素的长度称为游程长度（Run length) 。 信源符号中重复出现的黑游程和白游程可归一化为统一的编码单元，其单元结构如下： 符号码 标识码 游程长度 实际文件的行扫描中，由于文件的二值性，黑、白游程总是交替出现，在第一游程的类 型预先规定后，进行游程编码就可省去原单元结构中的“符号码”及“标识码”，仅保留游 程长度数据。 4.2.6.2 MH 码 MH 码是 CCITT 提出的文件、传真类一维数据压缩编码的国际标准，是由游程编码及 霍夫曼编码结合而成的一种改进型霍夫曼码。 MH 码使用固定编码表进行编码，即在信源与信宿两端，利用预先确定的编码表各自独 立进行编码和解码。 MH 码在编码中对游程长度进行分割，相应将长游程码（游程长度> 64）分割为结尾码 （终止码）和组合码（形成码）两部分，如表 4.1 及表 4.2 所示。 表 4.1 MH 码表(一) 结尾码 RL 长度 白游程码字 黑游程码字 RL 长度 白游程码字 黑游程码字 0 00110101 0000110111 32 00011011 000001101010 1 000111 010 33 00010010 000001101011 2 0111 11 34 00010011 000011010010 3 1000 10 35 00010100 000011010011 4 1011 011 36 00010101 000011010100 5 1100 0011 37 00010110 000011010101 6 1110 0010 38 00010111 000011010110
73911110001100101000000011010111840100110010100101001000001101100941101000001000010101000000110110110420011100001000010101100001101101011430000101010000010110000001101101112440010000000111001011010000010101004513000011000001000000010000000101010114461101000000011100000101000001010110154711010100001100000001010000001010111164810101000000101110000101100000110010017491010110000011000010100100000011001011850010011100000010000101001100000101001019510001100000011001110101010000000101001120520001000010101010000110100000000010010021530010111000011011000010010000000011011122540000011000001101110010010100000011100055230000100000001010000101100000000010011124560101000000000101110101100100000010100025570000001100001010110101101000000101100026580010011000011001010010110110000010110012759010010000001100101101001010000000101011286000110000000110011000100101100000010110029610000001000001100110100110010000001011010306200000011000001101000001100110000011001103163 0001101000000110100100110100000001100111表4.2MH码表（二）组合基干码RL长度白游程码字RL长度黑游程码字白游程码字黑游程码字64110110000001111960000000111001101101010012810010102401101010100001100100000000111010019201011110880110101100000001110101000011001001256115201101110000010110110110101110000001110110320001101100000001100111216011011000000000111011138412800011011100000011010001101100100000010100104480110010013440000001101010110110100000001010011123
123 7 1111 00011 39 00101000 000011010111 8 10011 00101 40 00101001 000001101100 9 10100 000100 41 00101010 000001101101 10 00111 0000100 42 00101011 000011011010 11 01000 0000101 43 00101100 000011011011 12 001000 0000111 44 00101101 000001010100 13 000011 00000100 45 00000100 000001010101 14 110100 00000111 46 00000101 000001010110 15 110101 000011000 47 00001010 000001010111 16 101010 0000010111 48 00001011 000001100100 17 101011 0000011000 49 01010010 000001100101 18 0100111 0000001000 50 01010011 000001010010 19 0001100 00001100111 51 01010100 000001010011 20 0001000 00001101000 52 01010101 000000100100 21 0010111 00001101100 53 00100100 000000110111 22 0000011 00000110111 54 00100101 000000111000 23 0000100 00000101000 55 01011000 000000100111 24 0101000 00000010111 56 01011001 000000101000 25 0101011 00000011000 57 01011010 000001011000 26 0010011 000011001010 58 01011011 000001011001 27 0100100 000011001011 59 01001010 000000101011 28 0011000 000011001100 60 01001011 000000101100 29 00000010 000011001101 61 00110010 000001011010 30 00000011 000001101000 62 00110011 000001100110 31 00011010 000001101001 63 00110100 000001100111 表 4.2 MH 码表（二）组合基干码 RL 长度 白游程码字 黑游程码字 RL 长度 白游程码字 黑游程码字 64 11011 0000001111 960 011010100 0000001110011 128 10010 00001100100 1024 011010101 0000001110100 192 010111 000011001001 1088 011010110 0000001110101 256 0110111 000001011011 1152 011010111 0000001110110 320 00110110 000000110011 1216 011011000 0000001110111 384 00110111 000000110100 1280 011011001 0000001010010 448 01100100 000000110101 1344 011011010 0000001010011
51201100101000000110110014001101101100000010101005760110100000000011011011472010011000000000101010164015360110011100000010010100100110010000001011010704160001100110000000010010110100110100000001011011768011001101166400000010011000110000000001100100832172801101001000000010011010100110110000001100101896011010011EOL0000001110010000000000001000000000001而对于加宽的纸型规定了一套加宽的MH组合码，如表4.3所示。表4.3MH码表（三）供加大纸宽用的组合基干码（17922560，黑、白相同）游程长度游程长度组合基干码码字组合基干码码字1792224000000001000000000010110185600000001100230400000001011119200000000110123680000000111001984000000010010243200000001110120482496000000010011000000011110211225600000000101000000000111112176000000010101其具体编码规则如下：（1）游程长度在0~63之间时，码字直接由相应的终止码表示：（2）游程长度在64~1728之间时，码字由一个组合码加上一个终止码构成；（3）每行必须以白游程开始，以一个同步码EOL结束，且每页文件也必须以同步码EOL开始（用以清洗系统，防止误差扩散）：（4）连续6个EOL表示文件页传输的结束。4.2.6.3算术编码算术编码是一种概率统计匹配编码，其编码的码长与信源序列的概率成反比，码字与信源序列的累积概率分布函数值相关。算术编码的编、解码均得以通过累积概率分布函数的计算来实现，无须生成或传输编码表。算术编码是香农编码方法与累积概率分布函数的递推算法的结合，是香农编码的思想方法在信源序列上的应用。确定码长1为(4.14)P(u)124
124 512 01100101 0000001101100 140 011011011 0000001010100 576 01101000 0000001101101 1472 010011000 0000001010101 640 01100111 0000001001010 1536 010011001 0000001011010 704 011001100 0000001001011 1600 010011010 0000001011011 768 011001101 0000001001100 1664 011000 0000001100100 832 011010010 0000001001101 1728 010011011 0000001100101 896 011010011 0000001110010 EOL 000000000001 000000000001 而对于加宽的纸型规定了一套加宽的 MH 组合码，如表 4.3 所示。 表 4.3 MH 码表（三）供加大纸宽用的组合基干码（1792～2560，黑、白相同） 游程长度 组合基干码码字 游程长度 组合基干码码字 1792 00000001000 2240 000000010110 1856 00000001100 2304 000000010111 1920 00000001101 2368 000000011100 1984 000000010010 2432 000000011101 2048 000000010011 2496 000000011110 2112 000000010100 2560 000000011111 2176 000000010101 其具体编码规则如下： （1）游程长度在 0~63 之间时，码字直接由相应的终止码表示； （2）游程长度在 64~1728 之间时，码字由一个组合码加上一个终止码构成； （3）每行必须以白游程开始，以一个同步码 EOL 结束，且每页文件也必须以同步码 EOL 开始（用以清洗系统，防止误差扩散）； （4）连续 6 个 EOL 表示文件页传输的结束。 4.2.6.3 算术编码 算术编码是一种概率统计匹配编码，其编码的码长与信源序列的概率成反比，码字与信 源序列的累积概率分布函数值相关。算术编码的编、解码均得以通过累积概率分布函数的计 算来实现，无须生成或传输编码表。 算术编码是香农编码方法与累积概率分布函数的递推算法的结合，是香农编码的思想方 法在信源序列上的应用。 确定码长l 为 ( ) 1 log P u l （4.14）
其中：P（u）表示信源符号序列π的概率，符号「表示取大于或等于该值的最小整数。从信源符号全序列出发，将各信源符号序列依累积概率分布函数的大小映射到10.1）区间，每个符号序列均有一个小区间与之对应，可在小区间内取点（比如区间的左端点）来代表该符号序列。将此点的累积概率分布函数值用二进制数表示，取小数点后的前1位，即是信源符号序列的算术码。码长1的确定体现了算术编码与信源符号序列的概率匹配关系：序列的概率越大,分配的码长越短。4.2.6.4基于字典的编码1）LZ编码LZ码是由两位以色列人兰佩尔（A.Lemple）与齐费（J.Z.V）共同提出，其基本的思路与查字典极为相似，即通过“单词”简短的位置信息，间接地表达“单词”的内容。基于字典的LZ编码方法实质上是一种映射，它将原有确切意义的长信源符号序列映射为字典精短的位置序号，通过传递位置序号完成对长信源符号序列内容的传达。LZ算法中字典的内容是由被压缩文件直接生成，一边编码，一边将新发生的“单词"添加到字典中，因而LZ算法不需要保存字典，是一种自适应的算法。2）LZW码LZW算法是韦尔奇（T.A.Welch）对LZ算法的一种修正，它保留了LZ算法原有的自适应性。为了使长短不一的“单词”更便于处理，专门为“单词”建立了一种通用的格式：（1）每个“单词”均由前缀字符串和尾字符串两部分组成。（2）前缀字符串为字典中已有的“单词”，尾字符是本“单词”的最后一个字符。（3）对本身已经是单节的“单词”，没有前缀词时则在前面加上一个空前缀，并规定字典最后一个“单词”为“空”。LZW的解码算法同样表现为一种基于字典的自适应的算法，由于LZW编码的输出压缩文件中仅包含码字，并无包含字典。因而解码过程同样表现为一边解码，一边生成字典。LZW算法是一种简单的通用编码方法，由于编码方法不依赖于信源的概率分布，并且编码方法简单，速度快，特别是具有自适应的功能，使得这种算法得到越来越广泛的应用。目前市场上常用的Winzip、ARJ、ARC等著名压缩软件都是LZW码的改进与应用。125
125 其中: P(u )表示信源符号序列u 的概率，符号 表示取大于或等于该值的最小整数。 从信源符号全序列出发，将各信源符号序列依累积概率分布函数的大小映射到[0,1) 区 间，每个符号序列均有一个小区间与之对应，可在小区间内取点（比如区间的左端点）来代 表该符号序列。将此点的累积概率分布函数值用二进制数表示，取小数点后的前l 位，即是 信源符号序列的算术码。 码长l 的确定体现了算术编码与信源符号序列的概率匹配关系: 序列的概率越大,分配 的码长越短。 4.2.6.4 基于字典的编码 1）LZ 编码 LZ 码是由两位以色列人兰佩尔（A. Lemple）与齐费（J.Z.V）共同提出，其基本的思路 与查字典极为相似，即通过“单词”简短的位置信息，间接地表达“单词”的内容。 基于字典的 LZ 编码方法实质上是一种映射，它将原有确切意义的长信源符号序列映射 为字典精短的位置序号，通过传递位置序号完成对长信源符号序列内容的传达。 LZ 算法中字典的内容是由被压缩文件直接生成，一边编码，一边将新发生的“单词”添 加到字典中，因而 LZ 算法不需要保存字典，是一种自适应的算法。 2）LZW 码 LZW 算法是韦尔奇（T.A.Welch）对 LZ 算法的一种修正，它保留了 LZ 算法原有的自 适应性。为了使长短不一的“单词”更便于处理，专门为“单词”建立了一种通用的格式： （1）每个“单词”均由前缀字符串和尾字符串两部分组成。 （2）前缀字符串为字典中已有的“单词”，尾字符是本“单词”的最后一个字符。 （3）对本身已经是单节的“单词”，没有前缀词时则在前面加上一个空前缀，并规定字 典最后一个“单词”为“空”。 LZW 的解码算法同样表现为一种基于字典的自适应的算法，由于 LZW 编码的输出压 缩文件中仅包含码字，并无包含字典。因而解码过程同样表现为一边解码，一边生成字典。 LZW 算法是一种简单的通用编码方法，由于编码方法不依赖于信源的概率分布，并且 编码方法简单，速度快，特别是具有自适应的功能，使得这种算法得到越来越广泛的应用。 目前市场上常用的 Winzip、ARJ、ARC 等著名压缩软件都是 LZW 码的改进与应用