数据压缩第3章统计编码.ppt

第三章统计编码 数据压缩的类型 可逆的无失真编码 不可逆的有失真编码 大多数计算机文件不允许在压缩过程中丢失信息 利用消息或消息序列出现概率的分布特性 注重寻找概率与码字长度间的最优匹配 语音 图像或其他物理过程的量化采样 本章讨论的内容 对于计算机文件 逻辑压缩 LogicalCompression 物理压缩 PhysicalCompression 由数据自身特点及设计者技巧来决定的 压缩表示法 这种技巧在数据库的数据结构设计中特别有效 减少计算机文件内部冗余度的统计编码方法 本章讨论的内容 1 基本原理 2 霍夫曼编码 3 游程编码 4 算术编码 本章内容 5 基于字典的编码 唯一可译码的构造 4 1基本原理 文件的冗余类型编码器的数字描述 变长码的基本分析 唯一可译码的存在 压缩必须 透明 恢复后的文件不允许有任何失真 文件的冗余度类型 本节所指的冗余度 专指对数据解释一无所知时由数据流中即可观察到的 与具体应用背景无关的冗余 了解文件的冗余度 意在考虑有针对性的编码方法 冗余类型 字符分布 CharacterDistribution 字符重复 CharacterRepetition 在典型的字符串中 某些符号要比其他符号出现的更频繁 在一份具体的文件中字符不会以等概率出现 字符的分布明显地因文件而异 影响到字符的统计特性 对于字符重复所形成的符号串常常有更紧凑的编码方式 例如 格式化文件中的空白 报表中的空格串和零串 业务图表中的线图包含成片的空白等 高使用率模式 High usagePatterns 位置冗余 PositionalRedundancy 这四类冗余度之间有重叠 某些符号序列会以较高的频率反复出现 可用较少的位数表示 从而得到时间和空间的净节约 若某些字符总是在各数据块中可预见的位置上出现 那么这些字符至少是部分冗余的 例如 光栅扫描图像中含有的竖线 报表文件中的某些字段的记录几乎总是相同的等等 图3 1一份零件报表中的冗余度的类型 编码器的数字描述 实际信源的编码过程 消息集X 元素x叫做信号单元或消息 输出集W 代码 码组或码书 元素w叫做码字 码字的符号集A 元素a叫做码元或者符号 以符号A构建代码W 建立X W对应关系 编码过程 例3 1 X x1 x2 x3 A 0 1 W w1 w2 w3 A2 00 01 10 11 假设用 构成代码W W到A2的映射关系为 完成步骤 R1 w1 01 w2 10 w3 11 R2 x1 w1 x2 w2 x3 w3 建立X与W的映射关系为 完成步骤 若xi dk dk 1 1 i n 0 k J 1 为一模拟信号 该编码器实际就是一个量化器 编码 就是将不同的消息用不同的码字来代替 或称为从消息集到码字集的一种映射 分组编码或块码的概念 码长 组成码字的符号个数 Li 2 1 i 3 等长 或定长 编码 采用相同长度的不同码字去代表一个消息集合中的不同消息 M元编码 或M进制 取M个不同字符来组成码字 最常用的有二元编码 或二进制 变长码的基本分析 对一个消息集合中的不同消息 采用不同长度的码字表示 不等长 或变长 编码 采用变长码可以提高编码效率 即对相同的信息量所需的平均编码长度可以短一些 平均码长 对P aj 大的aj用短码 对P aj 小的aj用长码 当这些信息符号互不相关时 平均码长比等长编码的码长短 1843年 莫尔斯电报码 表3 1莫尔斯码 莫尔斯码的形成 首先找到各消息符号的统计特性 再根据各符号出现的概率分布分配不同长度的码字 变长码在编码时要预先知道各种信息符号出现的概率 解码也远比等长码复杂 正确识别码字起点不容易 存在唯一可译性问题 译码实时性问题 匀速输入输出匹配的缓存问题 定义3 1 若W中任一有限长的码字序列 即有限长的一串W 可唯一地分割成一个一个码字 称为单义可译或唯一可译的 W也叫做单义代码 单义可译码 例3 2 考虑以下几种变长码 码A不是一一对应 码B是一一对应 但构成的序列不能被唯一分割 码C是唯一可译的 码D是在码B各码字 除了w1 之前加一个码元 0 成为唯一可译的 但平均码长增加0 5bit 码F即使从尾开始判断 也不是唯一可译的 问题 什么样的码才是唯一可译的 码E的译码要求等到收到全部序列 才能从尾开始进行判决 产生了时间上延时和存储容量的增加 唯一可译码的存在 目前还没有一个明确的判断唯一可译码的准则 只有一个判断不是唯一可译码的准则 定理3 1 Kraft不等式 长度为L1 L2 Ln的m进制唯一可译码存在的充分必要条件是 含义 要求Li比较大 码长不能过短 意味着码字可能的组合数多 不为别的码字的字首 3 1 1 Kraft不等式 只涉及唯一可译码的存在问题而并不涉及具体的码 可用来判定某一组码不是唯一可译的 但不能判定是唯一可译的 不满足Kraft不等式的码肯定不是唯一可译码 而满足的也不一定就是唯一可译的 但可以肯定若按这样的Li分配码组 则必存在有一个唯一可译码 也可能不止一个 对应于信源符号 例3 3 对于例3 2 问题 如何来确定码字长度 如何在确定了码字长度后找出唯一可译码 定理3 2 按符号 变长编码定理 对于符号熵为H X 的离散无记忆信源进行m进制不等长编码 一定存在一种无失真编码方法 其码字平均长度l满足 3 1 2 小于上限的单义代码总是存在的 当m 2 有 二进制编码定理 此时l叫编码速率 有时又叫比特率 对于m进制的不等长编码的编码速率定义为 3 1 4 3 1 3 定理3 2改述为 若H X R H X 就存在唯一可译的变长码 若R H X 则不存在唯一可译的变长码 其中 为任一正数 例3 4 例3 2信源的的熵为 码长的一种设计为 L1 1 L2 2 L3 L4 3 满足上述码长设计的码如 例3 2中的码C E F 满足Kraft不等式 如何做出具体的变长码是变长码的构造问题 唯一可译码的构造 唯一可译码的基本要求 码字非续长 对码字序列能做出唯一正确的分割 充分条件 若W中任一码字都不是另一个码字的字头 或换句话说 任一码字都不是由另一个码字加上若干个码元所构成 则W就叫作非续长码字或异字头码 PrefixConditionCode 例3 2中 码A 码B 码D 码E和码F都含有续长码 或同字头码 码C是异字头码 不过非异字头码也并非一定不是唯一可译 码D和码E就唯一可译 码D 各码组靠 逗号 码元0 分开 码E 为码C的 镜像 具有 异后尾 从后向前即具有唯一可译性 异字头条件保证译出的码字是唯一的且具有 即时性 减少了译码延时 异字头性质只是码字可分离的充分条件 非续长码也只是单义可译代码集合的一个子集 图3 3单义可译码与非续长码 二进制编码 通常可用二进码树 二叉树 来表示各码字的构成 串接的最大枝数为树的节数 图3 4的节数为3 用码树表述任何一个代码W 异字头条件就成为 W中所有的码字wi均只对应地配置在终端节点上 图3 5码C的树结构 异字头码 码E的树结构 非异字头码 此时码C为用尽的异字头码 有 倘若有一码字为 0 10 110 则该码为非用尽的异字头码 有 按照Kraft不等式的要求 对n个消息 x1 x2 xn 分配了编码长度L1 L2 Ln 即可用二进码树来生成异字头码 生成规律是 从根出发开始生出2枝 每一枝用一个码元aj A 0 1 来表示 枝尽节来 节外生枝 在第Li级端节点 Li级节点共有2Li个 上 配置信号单元xi i 1 2 n 从根开始直奔对应的端节点 沿途 联枝 所遇到的码元aj所构成的符号 即为对应于该信号单元xi的码字wi 异字头码无译码延时 构造简单 结论 任一唯一可译码 总可以用与各相应码字长度一样的异字头码代替 异字头码虽然只是唯一可译码的一种 但它具有代表性和普遍意义 在信息保持编码中广泛应用 长度为L1 L2 Ln的M进制异字头码存在的充要条件 也使Kraft不等式成立 3 2霍夫曼编码 1952年 霍夫曼 D A Huffman 提出霍夫曼编码 又称最佳编码 根据字符出现概率来构造平均长度最短的异字头码字 霍夫曼码的构造 理论基础 定理3 3 在变长编码中 若码字长度严格按照所对应符号出现概率的大小逆序排列 则其平均长度最短 例3 6 对一个7符号信源A a1 a2 a7 求其霍夫曼编码 信源符号出现概率a10 20a20 19a30 18a40 17a50 15a60 10a70 01 码长码字2112103011301030014000140000 编码步骤 将信源符号概率按递减顺序排列 将两个最小的概率进行相加 并继续这一步骤 直到概率达到1 0为止 在每对组合中的上部指定为1 或0 下部指定为0 或1 画出每个信源符号概率到1 0处的路径 记下沿路径的1和0 对于每个信源符号都写出1 0序列 则从右到左就得到霍夫曼编码 011a3 根 例3 6的Huffman二进码树 11a1 10a2 010a4 001a5 0001a6 0000a7 例3 6的信源熵为 霍夫曼编码的平均字长为 编码效率 注意 在哈夫曼编码过程中 对缩减信源符号按概率由大到小的顺序重新排列时 应使合并后的新符号尽可能排在靠前的位置 这样可使合并后的新符号重复编码次数减少 使短码得到充分利用 Huffman编码和译码过程 编码 输出Huffman码流 Huffman码表 传输 接收的Huffman码流缓冲器 信源符号序列 解码 解码后的字符序列 Huffman码表 信源编码基本定理 霍夫曼编码 变长的代码 只能分配接近log2pj的整数长码字 定长的数据段 当信源符号的概率pj 2 k 编码效率等于100 例3 7 对于二值图像 如传真机文件 输出非 黑 即 白 有 X x1 x2 白 黑 其概率与所传文件有关 假设对某页文件 有P x1 0 9 P x2 0 1 不考虑信号间的关联时 其信息熵为 此时W 0 1 无论用定长码还是最佳编码 平均码长至少为l1 1 bit 此时霍夫曼编码无压缩作用 编码效率为 1 H X l1 46 9 解决办法 定理3 4 信源编码定理 A a1 am XK X x1 xn 的延长 WK W w1 wn 的延长 其平均长度为lK P wi P xi P W P wi i 1 2 n 如果要求WK为单义代码 则 3 2 1 式 3 2 1 也叫做无失真编码的基本定理 含义 如果我们把X延长后再对K元组 K为延长长度 进行编码 那么不必利用数据前后的关联 只要K足够大 则代表每消息单元X的平均符号个数l K可以任意趋向于下限 例3 8 利用最佳编码 以例4 7来说明l K趋向于下限的情况 把X延长到X2 假定信源是离散无记忆信源 有图3 7所示X2的最佳编码 W2平均长度为 l2 0 81 0 09 2 0 09 3 0 01 3 1 29bit pel W2的每一个元素代表两个消息单元 因此平均每一个消息单元的符号个数是 l2 2 1 29 2 0 645bit pel 2 H X l2 2 72 7 编码效率提高到 把X延长到X3 有图3 8所示X3的最佳编码 W3平均长度为 l3 0 729 0 081 3 3 5 3 0 09 0 001 1 598bit pel W3的每一个元素代表三个消息单元 因此平均每一个消息单元的符号个数是 l3 3 1 598 3 0 5327bit pel 3 H X l3 3 88 0 编码效率提高到 继续下去 就可使lK K 0 469 或 100 进一步减小l K 利用信号的前后关联减小下限 即利用 H X Y H X H Y H X Y H X 或 可以减小下限 从而减小l K 要求知道P X P X Y 或P X Y 才能进行最佳编码 如果信号继续有关联可供利用 继续延长 会使下限变得很小 信源编码理论 给定消息单元集合X 符号集合A和X的概率分布P X 可以采用最佳编码 使代码W的平均长度满足 如果把X延长至XK 则不必考虑信号前后的关联性 就可以是代表一个消息单元的符号个数l K任意接近下限H X logm 如果利用延长信号XK的前后关联 可使下限减小 具体实现时 如果将信号延长得过长 会使实际设备复杂到不合理的程度 霍夫曼编码选择模型 静态统计模型 在编码前统计要编码的信息中所有字符的出现概率 然后根据统计出的信息建立编码树 进行编码 缺点 对数据量较大的信息 静态统计要消耗大量的时间 必须保存统计出的结果以便解码时构造相同的编码树 或者直接保存编码树本身 而且 对于每次静态统计 都有不同的结果 必须分别予以保存 这要消耗大量的空间 这意味着压缩效率的下降 静态统计模型统计出的频率是字符在整个文件中的出现频率 往往反映不出字符在文件中不同局部出现频率的变化情况 使用这一频率进行压缩 大多数情况下得不到太好压缩效果 文件有时甚至在压缩后反而增大了 一种有效的 静态统计模型 的替代方案 如果要压缩的所有信息在分布上存在着共同的特征 使用语言学家事先已经建立好的字母频率表来进行压缩和解压缩 不但不用保存多份统计信息 而且一般说来对该类文件有着较好的压缩效果 比如我们要压缩的是普通的英文文本 那么 字母a或者字母e的出现频率应当是大致稳定的 这种方案除了适应性不太强以外 偶尔还会有一些尴尬的时候 缺点 IfYouth throughoutallhistory hadachampiontostandupforit toshowadoubtingworldthatachildcanthink and possibly doitpractically youwouldn tconstantlyrunacrossfolkstodaywhoclaimthat achilddon tknowanything GadsbybyE V Wright 1939 发现什么问题了吗 整段话中竟没有出现一次英文中出现频率最高的字母e 对英文或中文文本 有一种比较实用的静态模型 不是把字符而是把英文单词或中文词语作为统计频率和编码的单位进行压缩 这种压缩方式可以达到相当不错的压缩效果 并被广泛地用于全文检索系统 自适应模型 无需为解压缩预先保存任何信息 整个编码是在压缩和解压缩过程中动态创建的 而且自适应编码由于其符号频率是根据信息内容的变化动态得到的 更符合符号的局部分布规律 因此在压缩效果上比静态模型好许多 根据已经编码的符号频率决定下一个符号的编码 算术编码 字典编码等更为适合采用自适应模型 但是 采用自适应模型必须考虑编码表的动态特性 即编码表必须可以随时更新以适应符号频率的变化 对于Huffman编码来说 我们很难建立能够随时更新的二叉树 霍夫曼码的局限性 局限性 输入符号数受限于可实现的霍夫曼码表尺寸 译码复杂度 需要知道输入符号集的概率分布 由于码长不等 还存在一个输入与输出的速率匹配问题 3 3游程编码 游程长度 RL RunLength 简称游程或游长 由字符 或信号采样值 构成的数据流中各字符重复出现而形成的字符串的长度 用二进制码字给出形成串的字符 串的长度及串的位置等信息 以此来恢复出原来的数据流 游程长度编码 RLC 游程编码类型 变长游程编码 使用位数是固定的 即RL位数是固定的 如果灰度连续相同的个数超过了固定位数所能表示的最大值 则进入下一轮游程编码 定长游程编码 对不同范围的游程采用不同位数的编码 即表示RL位数不固定 基本的游程编码 基本的RLC压缩方法 最初出现在IBM3780BYSYNC BinarySynchronousCommunication 通信协议中 基本的RLC数据结构 图3 9基本的RLC数据结构 其中 X 代表数据字符 Sc Sc X 表示有一个字符在此位置 RL 代表串 游程 的长度 字符重复出现的次数 只有当RL 3时 才有数据压缩效益 编码时 先判断RL值 再决定是否RLC 解码时 根据每一X后的码字是否为Sc 再决定下一个字的含义 Assumption Longsequencesofidenticalsymbols Example RLC压缩效能 取决于数据流中重复字符出现次数 平均游程长度及所采用的编码结构 表3 2基本的游程编码压缩比 二值图像的游程编码 二值图像 仅有黑 1 代表 白 0 代表 两个亮度值的图像 经扫描仪得到的气象图 工程图 地图 线路图等 文字组成的文件图像 灰度图像经过位平面分解或抖动处理后的图像 最常用的传输方式 传真 二值图像编码也往往指数字传真编码 二值图像的游程编码 数据字符X 白 黑 对二值图像每一扫描行 白像素游程 白长 黑像素游程 黑长 对不同长度的白长和黑长 按其出现概率的不同分别配以不同长度的码字 RLC利用多个像素之间的相关性 可得到较低的码率下限 二值图像的RLC的两种方式 不分白长和黑长 只根据长度进行编码 对白长和黑长分别编码 前CCITT建议 由于在实际图像中 白长和黑长的概率分布各异 此方法不是很有效 其最低比特率满足 3 3 1 其中 PW和PB分别是白像素和黑像素出现的概率 lW和lB分别是白长和黑长的平均像素数 平均长度 hWB为每个像素的熵值 编码过程 先对图像进行统计分别得出白长为i的概率PiW和黑长为i的概率PiB 然后根据霍夫曼原则按RL出现概率来分配码字 二值图像的RLC实为霍夫曼码的具体应用 由于各种RL的出现概率在行间 页间都不相同 且为求得概率 需要存储数据并做统计计算 难以实时编码 CCITT的T 4建议 推荐8幅标准传真样张为统计依据 根据各种RL的出现概率编出霍夫曼码表 称为改进型霍夫曼编码 MHC MH编码规则 见表4 7 RL 0 63 用一个相应的结尾码表示 RL 64 1728 用一个组合基干码加一个补充结尾码 RL 白 128 补充结尾码为0 白 00110101 其编码为 10010 00110101RL 白 129 补充结尾码为1 白 000111 其编码为 10010 000111 规定每行都从白游程开始 若实际扫描由黑开始 则需在行首加零长度白游程 每行结束要加同步码EOL 游程编码的局限性 对二值图像最为有效 但对数据文件就不那么显著 而对于课文实质已无使用价值 压缩字符与数值混合序列比较麻烦 要求区分计数字段和常规字符 需要较大容量的缓冲和较低误码的优质信道 连续色调图像的二维编码 连续色调图像的二维编码 原码 若ZZ k 0 反码 若ZZ k 0 由ZZ k 之间的零游程计数值得ZRL NNNN SSSS在 中已知 查表4 9 4 10可得NNNN SSSS码字 尾码 ZZ k 的B位 综合 和 可得AC系数编码 NNNN SSSS 尾码 若ZZ 5 B 3 得原码101若ZZ 2 B 2 得反码01 连续色调图像的二维编码 若最后一个 零游程 非零值 中只有零游程 则直接发送块结束码字 EOB 结束本块 否则无需加EOB码 一般情况NNNN ZRL 0 15 若ZRL 15 则先用ZRL 16即NNNN SSSS F 0得到码字 再对ZRL ZRL 16继续编码 得到NNNN SSSS码字 结合尾码就可得AC系数编码 连续色调图像的二维编码 例题 设某亮度图像块的量化系数矩阵按Z形扫描得到 K0123456789 303132 63ZZ k 125 20200010 10 而其前一亮度块的量化DC系数也为12 写出编码过程 解 1 DC系数编码 因为DIFF 0 查表4 2得其码字即为前缀码 00 2 AC系数编码 第一个非零值ZZ 1 5 查表4 8得SSSS 3 根据规则得尾码为原码101 与ZZ 0 间无零系数 故NNNN 0 NNNN SSSS 0 3查表4 9码字100 从而ZZ 1 5的编码为 NNNN SSSS 尾码 即100 101得100101 第二个非零值ZZ 2 2 SSSS 2 尾码为反码01 又与ZZ 1 无零系数 所以NNNN SSSS 0 2查表得码字为01 从而ZZ 1 ZZ 2 编码为0101 ZZ 3 ZZ 4 编码为1101110 ZZ 5 ZZ 8 编码为1110101 连续色调图像的二维编码 例题 设某亮度图像块的量化系数矩阵按Z形扫描得到 K0123456789 303132 63ZZ k 125 20200010 10 而其前一亮度块的量化DC系数也为12 写出编码过程 ZZ 31 1 查表得SSSS 1 尾码为反码0 由于NNNN 30 9 1 22 15 故先编ZRL 16 NNNN SSSS F 0查表得码字11111111001 此后NNNN 22 16 6 15再编码 NNNN SSSS 6 1查表得码字为1111011 所以ZZ 9 ZZ 31 编码为11111111001 11110110 此后无非零值 最直接用一个EOB结束本块 查表得码字为1010 3 综合前面 1 和 2 可知该图像块的编码为0010010101011101110111010111111111001111101101010 4 原始图像块要用8 8 8 512位 压缩后为49位 压缩比为10 45 1 游程编码总结 3 4算术编码 ArithmeticCoding 3 4 1多元符号算术编码原理3 4 2自适应模型算术编码3 4 3二进制算术编码3 4 4二进制算术解码3 4 5算术编码评价 算术编码定义 它是一种非分组编码算法 它是从全序列出发 采用递推形式的连续编码 它不是将单个的信源符号映射成一个码字 而是将整个输入序列的符号依据它们的概率映射为实数轴上区间 01 内的一个小区间 再在该小区间内选择一个代表性的二进制小数 作为实际的编码输出 例如算术编码对某条信息的输出为1010001111 那么它表示小数0 1010001111 也即十进制数0 64 85 3 4 1多元符号算术编码 1 码字刷新 C sai C s P ai A s 2 区间刷新 A sai p ai A s 设输入符号串s取自符号集S a1 a2 a3 am p ai p1 p2 p3 pm s后跟符号ai扩展成符号串sai 算术编码的迭代关系为 符号累积概率 初始条件 一 算术编码 3 4 1多元符号算术编码 当处理ai时 区间A s 宽度根据ai出现概率p ai 而变窄 符号序列越长 相应的子区间越窄 编码的位数越多 符号串每一步新扩展的码字C sai 都是由原符号串的码字C s 与新区间宽度A sai 的算术相加 算术码 由此得名 算术编码在传输任何信号ai之前 信号的完整范围是 3 4 1多元符号算术编码 例题1 设某信源取自符号集S a b c d e 表示编码结束 各符号概率和初始子区间如下 设待编码的为 dead 编码器和解码器的初值区间 0 1 表1 3 4 1多元符号算术编码 编码第一个字符d时 编码第二个字符e时 3 4 1多元符号算术编码 编码第三个字符a时 依此类推 结果如下表 3 4 1多元符号算术编码 最后在区间 0 61804 0 6184 中任取一个代表性的小数 譬如0 6183 转化成二进制小数0 1001111 最后编码输出1001111 91 3 4 1多元符号算术编码 编码 3 4 1多元符号算术编码 二 算术解码 解码器首先输入符号及区间 重构表1 然后输入其余码字 比如第一个数字是 6 解码器立即知道是形如0 6 的数字 该数字位于d的子区间 0 4 0 7 中 所以第一个符号就是d 然后从该数字中减去d子区间的低端值0 4 再除以d子区间宽度0 3 以消除符号d对码字的影响 结果是0 727667 告诉解码器下一个符号是e 因为e的子区间是 0 7 0 9 93 为了从码字中消除符号x的影响 解码器执行Code Code LowRange x Range的操作 Range是符号x的子区间宽度 表2总结了本例解码步骤 表2算术解码过程 94 3 4 2二进制算术编码 一 基本工作原理设编码初始化子区间为 0 1 MPS与LPS分配如图大概率PeMPS MostProbableSymbol 小概率QeLPS LeastProbableSymbol Pe 1 Qe设置 C A 令C 0A 1C寄存器的值为子区域的起始位置A寄存器的值为子区域的宽度 95 96 例题1 设输入信源为11011111 对其编码0为LPS Qe 0 001 b 1为MPS Pe 0 111 b初始状态 C 0 A 11 1为MPSC C AQe 0 1 0 001 0 001A APe 1 0 111 0 111 3 4 2二进制算术编码 97 2 1为MPSC C AQe 0 001 0 111 0 001 0 001111A APe 0 111 0 111 0 110001 3 4 2二进制算术编码 3 0为LPSC C 0 001111 A AQe 0 110001 0 001 0 000110001 98 头 0 0101 尾传送码字为0101 编码过程 3 4 2二进制算术编码 99 算术编码原理图 100 二进制解码 按QePe分成两个子区间 判断被解码的码字落在哪个区间 并赋予对应符号 设c 0 0101 b是被解码的值初始值A 1Qe 0 001当c 落在0 QeA之间 解码符号为D 0 C C A QeA 当c 落在QeA A之间 解码符号为D 1 C C QeA A A 1 Qe 3 4 3二进制算术解码 101 1 C 0 0101落在QeA A之间 解码符号为D 1C C QeA 0 0101 0 001 0 0011A A 1 Qe 0 111 2 C 0 0011落在QeA A之间 解码符号为D 1C C QeA 0 0011 0 000111 0 000101A A 1 Qe 0 111 0 111 0 110001 3 C 0 000101落在0 QeA之间 解码符号为D 0C C 0 000101A AQe 0 110001 0 001 0 000110001 3 4 3二进制算术解码 102 算术解码原理图 103 3 4 4算术编码评价 算术编码是一种非分组编码 编码方案众多 压缩效率最高 当信源符号概率接近时 建议用算术编码 信源的每一个符号对应 0 1 的一个子区间 该子区间的长度等于对应符号的出现的概率 算术编码把信源X的任一给定序列和 0 1 的一个子区间联系在一起 该子区间的长度等于这个序列的概率 算术编码比霍夫曼编码复杂 需要缓冲存储器 硬件实现难 比分组码的误差扩散更严重 要求有高质量的信道 或采用检错重发的方式 概率大的符号对应区间大 描述所需比特少 随着输入序列长度增加 平均编码所用比特数趋向信源熵 104 3 5基于字典的编码 以Huffman编码为代表的压缩模型都是基于对信息中单个字符出现频率的统计而设计的 直到70年代末期 这种思路在数据压缩领域一直占据着统治地位 在我们今天看来 这种情形在某种程度上显得有些可笑 但事情就是这样 一旦某项技术在某一领域形成了惯例 人们就很难创造出在思路上与其大相径庭的哪怕是更简单更实用的技术来 3 5 1LZ算法 1977年 JacobZiv和AbrahamLempel发表了论文 顺序数据压缩的一个通用算法 1978年 他们发表了该论文的续篇 通过可变比率编码的独立序列的压缩 这两篇论文提出的两个压缩技术被称为LZ77和LZ78算法 它们的思路和字典法颇为相似 因此 人们将基于这一思路的编码方法称作字典式编码 字典式编码不但在压缩效果上大大超过了哈夫曼编码 而且 对于好的实现 其压缩和解压缩的速度也异常惊人 LZ77算法 LZ77算法又称为 滑动窗口压缩 如下图 LZ77算法的基本流程 重复进行以下处理 直至所有数据处理完毕 1 从当前压缩位置开始 考察未编码的数据 并试图在滑动窗口中找出最长的匹配字符串 2 如果找到 输出三元符号组 off len c 其中off为窗口中匹配字符串相对窗口边界的偏移 len为可匹配的长度 c为下一个字符 将窗口向后滑动len 1个字符 3 如果未找到 输出三元符号组 0 0 c 其中c为下一个字符 将窗口向后滑动1个字符 假设窗口的大小为10个字符 我们刚编码过的10个字符是 abcdbbccaa 即将编码的字符为 abaeaaabaee 窗口 首先发现 可以和要编码字符匹配的最长串为ab off 0 len 2 ab的下一个字符为a 我们输出三元组 0 2 a a b a LZ77算法举例 现在将窗口向后滑动3 2 1 个字符 窗口中的内容为 dbbccaaaba 剩余字符为eaaabaee 下一个字符e在窗口中没有匹配 我们输出三元组 0 0 e LZ77算法举例 又将窗口向后滑动1个字符 其中内容变为 bbccaaabae 这时发现 要编码的aaabae在窗口中存在 off 4 len 6 其后的字符为e 可以输出 4 6 e LZ77算法举例 最后又将窗口向后滑动7个字符 这样 我们将可以匹配的字符串都变成了指向窗口内的指针 并由此完成了对上述数据的压缩 LZ77算法举例 LZ77算法的解压缩 LZ77算法的解压缩的过程十分简单 只要我们像压缩时那样维护好滑动的窗口 随着三元组的不断输入 我们在窗口中找到相应的匹配串 缀上后继字符c输出 如果off和len都为0则只输出后继字符c 即可还原出原始数据 LZ78算法 LZ78算法的基本思路与LZ77算法类似 也是利用已经处理过的编码信息 但它发生匹配时 不是保存一个三元组 而是一个二元组 匹配位置和不匹配的第一个字符 同时 还要将这个字符串保存到内存中 为此 它需要一个不断增长的编码字串表 字典 与LZ77相比 LZ78的最大优点是在每个编码步骤中减少了字符串比较的数目 而压缩率与LZ77类似