[工学]数据压缩第4章 统计编码_sxq1.ppt

本章内容 文件的冗余度类型 编码器的数字描述 变长码的基本分析 唯一可译码的存在 唯一可译码的构造 Shannon-Fano 编码 习题： 4.2 霍夫曼编码 霍夫曼码的构造 注意：哈夫曼的编法并不唯一 每次对缩减信源两个概率最小的符号分配“0”和“1”码元是任意的，所以可得到不同的码字。只要在各次缩减信源中保持码元分配的一致性，即能得到可分离码字。 不同的码元分配，得到的具体码字不同，但码长ki不变，平均码长也不变，所以没有本质区别； 缩减信源时，若合并后的新符号概率与其他符号概率相等，从编码方法上来说，这几个符号的次序可任意排列，编出的码都是正确的，但得到的码字不相同。不同的编法得到的码字长度ki也不尽相同。 信源编码基本定理 霍夫曼编码选择模型 霍夫曼码的局限性 4.3 游程编码 基本的游程编码 二值图像的游程编码 游程编码的局限性 把 X 延长到 X 3 ，有图4.8所示 X 3 的最佳编码： 图4.8 3单元延长信号的最佳编码 P(x1, x1, x1) =0.729 P(x1, x1, x2) =0.081 P(x1, x2, x1) =0.081 P(x2, x1, x1) =0.081 0.010 0.109 1 1 1 0 0 0 P(x1, x2, x2) =0.009 P(x2, x1, x2) =0.009 P(x2, x2, x1) =0.009 P(x2, x2, x2) =0.001 0.018 0.028 0.162 0.271 1.00 0 0 1 1 1 0 0 1 W 3 11111 11110 11101 110 101 100 0 11100 W 3平均长度为: l3 =0.729+0.081?3?3 +5?( 3?0.09+0.001)=1.598 bit/pel W 3的每一个元素代表三个消息单元, 因此平均每一个消息单元的符号个数是: l3 /3 = 1.598/3 = 0.5327 bit/pel η3 =H(X)/ l3=88.0 % 编码效率提高到: 继续下去,就可使 lK /K ? 0.469, 或η=100% 进一步减小 l/K , 利用信号的前后关联减小下限, 即利用: H(X, Y )≤H(X)+H(Y) (3.2-13) H(X | Y )≤H(X) (3.2-11b) 或: 可以减小下限,从而减小l/K 要求知道P(X), P(X,Y) 或 P(X|Y) 才能进行最佳编码。 如果信号继续有关联可供利用，继续延长，会使下限变得很小。 信源编码理论： ① 给定消息单元集合X、符号集合A和X的概率分布P(X)， 可以采用最佳编码，使代码W 的平均长度满足; ② 如果把X 延长至 X K ,则不必考虑信号前后的关联性, 就可以是代表一个消息单元的符号个数 l /K 任意接近 下限 H(X)/logm; ③ 如果利用延长信号X K的前后关联,可使下限减小。 具体实现时，如果将信号延长得过长，会使实际设备复杂到不合理的程度。 静态统计模型 在编码前统计要编码的信息中所有字符的出现概率，然后根据统计出的信息建立编码树，进行编码 。 缺点 ： 对数据量较大的信息，静态统计要消耗大量的时间； 必须保存统计出的结果以便解码时构造相同的编码树，或者直接保存编码树本身，而且，对于每次静态统计，都有不同的结果，必须分别予以保存，这要消耗大量的空间（这意味着压缩效率的下降）； 静态统计模型统计出的频率是字符在整个文件中的出现频率，往往反映不出字符在文件中不同局部出现频率的变化情况，使用这一频率进行压缩，大多数情况下得不到太好压缩效果，文件有时甚至在压缩后反而增大了。 一种有效的“静态统计模型”的替代方案 如果要压缩的所有信息在分布上存在着共同的特征，使用语言学家事先已经建立好的字母频率表来进行压缩和解压缩，不但不用保存多份统计信息，而且一般说来对该类文件有着较好的压缩效果。 比如我们要压缩的是普通的英文文本，那么，字母 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