2.常用数据压缩技术.pptVIP

常用数据压缩技术 主要内容 香农-范诺编码 Huffman编码 算术编码 行程编码(Run Length Encoding) 词典编码 预测编码 变换编码 O、香农-范诺编码 熵(Entropy)的概念 熵是信息量的度量方法，表示一条信息中真正需要编码的信息量。熵的单位是bits。事件发生的可能性越小（数学上就是概率越小），表示某一事件出现的消息越多。 某个事件的信息量用Ii ＝ -log2 pi 表示， 其中pi 为第 i 个事件的概率， 0 pi ≤ 1 O、香农-范诺编码 信源S 的熵 按照香农(Shannon)的理论，信源 S 的熵定义为其中 为符号S i 在S中出现的概率。 表示包含在S i 中的信息量，也就是编码S i 所需要的位数。 按照香农的理论，熵是平稳信源的无损压缩效率的极限。例如，一幅用256级灰度表示的图像，如果每一个像素点灰度的概率均为 pi=1/256，编码每一个像素点就需要8位（比特，bit）。 [例]对下面这条只出现了 a、b、c 三个字符的字符串：aabbaccbaa，字符串长度为 10，字符 a b c 分别出现了 5、3、2 次，则 a、b、c 在信息中出现的概率分别为 0.5 0.3 0.2，他们的熵分别为： Ea = -log2(0.5) = 1 Eb = -log2(0.3) = 1.737 Ec = -log2(0.2) = 2.322整条信息的熵也即表达整个字符串需要的位数为： Ea * 5 + Eb * 3 + Ec * 2 = 14.855 位 如果用计算机中常用的 ASCII 编码，表示上面的字符串需要整整80位！ 信息为什么能被压缩而不丢失原有的信息内容呢？简单地讲，用较少的位数表示较频繁出现的符号，这就是数据压缩的基本准则。 [例] 有一幅40个象素组成的灰度图像，灰度共有5级，分别用符号A、B、C、D和E表示，40个象素中出现灰度A的象素数有15个，出现灰度B的象素数有7个，出现灰度C的象素数有7个等等，如表所示。如果用3个位表示5个等级的灰度值，也就是每个象素用3位表示，编码这幅图像总共需要120位。 香农-范诺编码算法步骤 按照符号出现的概率减少的顺序将待编码的符号排成序列。 将符号分成两组，使这两组符号概率和相等或几乎相等。 将第一组赋值为0，第二组赋值为1。 对每一组，重复步骤2、3的操作。 一、Huffman编码 Huffman编码属于信息熵编码的方法之一； 信息熵编码又称统计编码,它是根据信源符号出现概率的分布特性而进行的压缩编码； 信息熵编码基本思想: 在信源符号和码字之间建立明确的一一对应关系，以便在恢复时能准确地再现原信号，同时要使平均码长或码率尽量小； 信息熵编码的代表 Huffman编码 算术编码 一、 Huffman编码 Huffman编码的理论基础是Huffman定理； Huffman定理（1952年Huffman提出的） 在变长编码中,对出现概率大的信源符号赋于短码字,而对于出现概率小的信源符号赋于长码字。如果码字长度严格按照所对应符号出现概率大小逆序排列,则编码结果平均码字长度一定小于任何其它排列方式。 也称为最佳编码，平均码长最短。 Huffman编码步骤 (1) 将信源符号按概率递减顺序排列； (2) 把二个最小概率相加作为新符号的概率，并按(1) 重排； (3) 重复(1)、(2)，直到概率为1； (4) 在每次合并信源时，将合并的信源分别赋“0”和“1”(如概率大的赋“0”,概率小的赋“1”)； (5) 寻找从每一信源符号到概率为1处的路径，记录下路径上的“1”和“0”； (6)写出每一符号的“1”、“0”序列(从树根到信源符号节点)。 Huffman编码示例 二、算术编码 20世纪60年代初，Elias提出了算术编码（Arithmetic Coding）的概念。 1976年，Rissanen和Pasco首次介绍了它的实用技术。其基本原理是：将编码的信息表示成实数0和1之间的一个间隔(Interval) ，信息越长，编码表示它的间隔就越小，表示这一间隔所需的二进制位就越多。 算术编码对整条信息（无论信息有多么长），其输出仅仅是一个数，而且是一个介于 0 和 1 之间的二进制小数。例如算术编码对某条信息的输出为 1010001111，那么它表示小数 0.1010001111，也即十进制数 0.64。 算术编码示例 采用固定模式符号概率分配如下： 字符: a e i o u 概率: 0.2 0.3