2.7 通用编码,一、分段编码（LZ码）二、匹配编码三、LZW算法,一、分段编码（LZ码）,分段规则： 使连着的信源符号尽可能少，但不能出现重复段 yj=yiur (j>i) 两个数可用一个数Nj （第j段段的码字）来表示 Nj=mi+r,特点：编码与符号概率无关编码效率比较高一、分段编码（LZ码）,第j段码长公式：,编码步骤：1.将信源序列分段2.计算Nj及第j段码长lj3.将Nj编成二进制码，取lj位为段的码字[例1] 设信源符号集U={a0,a1,a2,a3}，求信源序列S=a0a0a2a3a1a1a0a0a0a3a2的LZ编码分7段：a0, a0a2, a3, a1, a1a0, a0a0, a3a2,,信源序列码字：001 100 011 000 110 000 001 000 111 0,二、段匹配码（LZ78算法）,编码步骤：1.分段2.将段号和信源符号分别进行编码， 若组成二元码，段号所需码长 每个信源符号所需码长：,[例2] 设信源符号集U={a0,a1,a2,a3}，求信源序列S=a0a0a2a3a1a1a0a0a0a3a2 的匹配编码。
分7段：a0, a0a2, a3, a1, a1a0, a0a0, a3a2,C=7 段号所需码长：,m=4 信源符号所需码长：,00 00 10 11 01 01 00 00 00 11 10,信源序列编码序列：,000 00,0 010 010,010 11,0 110 1,10 001 00,1 010 000,110 111 0,,,,二、段匹配码,平均码长：当n很长时：,LZ78码是一种简单的通用编码，编码方法不需要知道信源的统计概率分布，而且编码方法简单，编译码速度快，又能达到最佳压缩编码效率,三、LZW算法,LZW编码算法步骤：1.串表初始化：将所有单个字符存入串表中，并给每个符号赋一个码字值；2.将第一个输入字符作为“前缀串”P；3.每个新输入的字符作为扩展字符S 若PS字符串不在串表中，输出P对应的码字，将PS存入串表并分配一个码字值；S→P； 若PS已在串表中，PS→P；4.重复步骤3，知道完成编码[例3] 由三元字符X、Y、Z组成的信源序列为： S=XYXYZYXYXYXXXXXXX 求LZW编码编码表（串表）,LZW算法是LZ78算法的使用修正形式，保留了LZ码的自适应性能，压缩效率大致相同，成为计算机文件压缩的标准算法。
且算法硬件实现容易本章重点内容,信息量、信息熵、互信息的概念及定义式克拉夫特不等式无失真变长信源编码定理（香农第一定理）主要的编码方法：Huffman码、费诺码、香农-费诺码、算术码、MH码、LZ码各种编码方法的平均码长和编码效率的计算本章难点,克拉夫特不等式: 表述了信源符号数与码字长度应满足什么条件才能构成即时码唯一可译码有相同不等式存在----麦克米伦不等式这两个不等式都只是描述了可构造性，不能作为判定的论据唯一可译码的判定准则：树图法：（即时码必为惟一可译码）尾随后缀法：（尾随后缀集合F中不含任一码字）,本章难点,0,10,F:{11,00,10,01,0,11,1,100,110,011,101},非惟一可译码,eg:1011001110..., F={0,00},惟一可译码,C3={1, 01, 001, 0001}, F=,。