第4章_统计编码_1.ppt

* * * * * * * * 缺点 ： 对数据量较大的信息，静态统计要消耗大量的时间； 必须保存统计出的结果以便解码时构造相同的编码树，或者直接保存编码树本身，而且，对于每次静态统计，都有不同的结果，必须分别予以保存，这要消耗大量的空间（这意味着压缩效率的下降）； 静态统计模型统计出的频率是字符在整个文件中的出现频率，往往反映不出字符在文件中不同局部出现频率的变化情况，使用这一频率进行压缩，大多数情况下得不到太好压缩效果，文件有时甚至在压缩后反而增大了。 一种有效的“静态统计模型”的替代方案 如果要压缩的所有信息在分布上存在着共同的特征，使用语言学家事先已经建立好的字母频率表来进行压缩和解压缩，不但不用保存多份统计信息，而且一般说来对该类文件有着较好的压缩效果。 比如我们要压缩的是普通的英文文本，那么，字母 a 或者字母 e 的出现频率应当是大致稳定的。 这种方案除了适应性不太强以外，偶尔还会有一些尴尬的时候。 缺点 ： If Youth，throughout all history， had a champion to stand up for it； to show a doubting world that a child can think；and， possibly， do it practically； you wouldnt constantly run across folks today who claim that a child dont know anything. - Gadsby by E.V.Wright, 1939. 发现什么问题了吗？整段话中竟没有出现一次英文中出现频率最高的字母 e 。 对英文或中文文本，有一种比较实用的静态模型：不是把字符而是把英文单词或中文词语作为统计频率和编码的单位进行压缩。 这种压缩方式可以达到相当不错的压缩效果，并被广泛地用于全文检索系统。 自适应模型 无需为解压缩预先保存任何信息，整个编码是在压缩和解压缩过程中动态创建的，而且自适应编码由于其符号频率是根据信息内容的变化动态得到的，更符合符号的局部分布规律，因此在压缩效果上比静态模型好许多。 根据已经编码的符号频率决定下一个符号的编码。 算术编码、字典编码等更为适合采用自适应模型 但是，采用自适应模型必须考虑编码表的动态特性，即编码表必须可以随时更新以适应符号频率的变化。对于 Huffman 编码来说，我们很难建立能够随时更新的二叉树， 霍夫曼码的局限性 霍夫曼编码 文本文件压缩 二进制文件压缩 适用于 经过符号合并 局限性: ① 输入符号数受限于可实现的霍夫曼码表尺寸 ; ② 译码复杂度; ③ 需要知道输入符号集的概率分布； ④ 由于码长不等，还存在一个输入与输出的速率 匹配问题。 4.3 游程编码 游程长度(RL: Run Length,简称游程或游长)： 由字符(或信号采样值)构成的数据流中各字符重复出现而形成的字符串的长度。 用二进制码字给出形成串的字符、串的长度及串的位置等信息，以此来恢复出原来的数据流。 游程长度编码(RLC)： 游程编码类型： 变长游程编码 使用位数是固定的，即RL位数是固定的，如果灰度连续相同的个数超过了固定位数所能表示的最大值，则进入下一轮游程编码； 定长游程编码 对不同范围的游程采用不同位数的编码，即表示RL位数不固定。 基本的游程编码 基本的RLC压缩方法： 最初出现在 IBM 3780 BYSYNC (Binary Synchronous Communication)通信协议中。 基本的RLC数据结构： X Sc RL 数 据 流 ··· 图4.9 基本的RLC数据结构 其中 X ： 代表数据字符； Sc： Sc {X}，表示有一个字符在此位置； RL： 代表串（游程）的长度，字符重复出现的次数； 只有当RL 3时, 才有数据压缩效益。 编码时：先判断RL值，再决定是否RLC； 解码时：根据每一X后的码字是否为Sc，再 决定下一个字的含义。 Assumption: Long sequences of identical symbols. Example, RLC压缩效能: 取决于数据流中重复字符出现次数、平均游程长度及所采用的编码结构。 平均重复 长度 重复出现10次的压缩比 重复出现20次的压缩比 重复出现30次的压缩比 重复出现40次的压缩比 重复出现50次的压缩比 4 1.010 1.020 1.031 1.042 1.053 5 1.020 1.042 1.064 1.073 1.111 6 1.031 1.064 1.099 1.136 1.176 7 1.042 1.087 1.