常用的无损数据压缩方法.ppt

6.3 常用的无损数据压缩方法v6.3.1 Huffman编码 v6.3.2 算术编码 v6.3.3 行程RLE编码 v6.3.4 词典编码Date16.3.1 Huffman编码v基本原理 § 依据信源字符出现的概率大小来构造代码，对 出现概率较大的信源字符，给予较短码长，而 对于出现概率较小的信源字符，给予较长的码 长，最后使得编码的平均码字最短Date26.3.1 Huffman编码v具体的编码步骤 § 将信源出现的概率由大到小排序 § 将两处最小概率组合相加，形成新概率 § 将新概率与未编码的字符一起重新排序 § 重复步骤2、3，直到出现的概率和为1 § 分配代码• 代码分配从最后一步开始反向进行，对最后两个概 率一个赋予0代码，一个赋予1代码记录下从树的 根到每个信源符号终节点的0和1序列至于哪个为“1”哪个为 “0”则无关紧要，最后 的结果仅仅是分配的 代码不同，而代码的 平均长度是相同的 Date36.3.1 Huffman编码vHuffman编码中求平均码长的方法： § 概率×码长Date46.3.1 Huffman编码vHuffman编码练习一: § 设输入图像的灰度级{a1,a2,a3,a4,a5,a6}出现的 概率分别是0.4、0.2、0.12、0.15、0.1、0.03。

试进行哈夫曼编码，并计算平均码字长度Date5Huffman编码练习一答案最终编码结果为： a1 =1, a2 =011 , a3 =001, a4 =010, a5 =0001, a6 =00001 010010Date6Huffman编码练习一答案v据公式 图像信源熵为： § H(X) = -(0.4×log20.4+0.2×log20.2+0.12×log20.12+ 0.15×log20.15+0.1×log20.1+0.03×log20.03) = 2.25 bit v根据哈夫曼编码结果，平均码字长度： § Lc=0.4×1+0.2×3+0.15×3+0.12×3+0.1×4+0.03×4 =2.33 v编码效率、压缩比和冗余度分别为： § 96.6%、1.2、3.4%r = 1-η = 3.4%Date76.3.1 Huffman编码vHuffman编码注意事项§ 哈夫曼编码没有错误保护功能，在译码时，如 果码串中没有错误，那么就能一个接一个的正 确译出代码但如果码串中有错误，哪怕仅是 1位出现错误，不但这个码本身译错，后面的 译码可能全错，这种现象称为错误传播（ Error Propagation）。

§ 哈夫曼编码是可变长度码，很难随意查找或调 用压缩文件中间的内容，然后再译码，这就需 要在存储代码之前加以考虑Date86.3.2 算术编码v算术编码（arithmetic coding AC）是利用0 和1之间的间隔来表示信源编码的一种方法 ，其编码值是间隔的上、下限包含的相同 二进制编码过程中的间隔决定了符号压 缩后的输出 v算术编码用到两个基本的参数 § 符号的概率和它的编码间隔 v信源符号的概率决定压缩编码的效率，也 决定编码过程中信源符号的间隔，而这些 间隔包含在0到1之间 Date96.3.2 算术编码v编码过程: § 设信源符号为{A, B, C, D}，其概率分别为{ 0.1, 0.4, 0.2, 0.3 }，按概率可把间隔[0, 1]分成4个子 间隔：[0, 0.1), [0.1, 0.5), [0.5, 0.7), [0.7, 1]，其 中[x,y)表示半开放间隔，即包含x不包含y，如 下表所示 符号ABCD 概率0.10.40.20.3 初始编码间 隔[0,0.1 )[0.1,0.5 )[0.5,0.7 )[0.7,1]Date106.3.2 算术编码v如果消息序列的输入为：CADACDB，其 编码过程如下： § 首先输入的符号是C，找到它的编码范围是 [0.5, 0.7)； § 由于消息中第2个符号A的编码范围是[0, 0.1)， 因此它的间隔就取[0.5, 0.7 )的第一个1/10作为 新间隔[0.5, 0.52 ) ； § 编码第3个符号D时取新间隔为[0.514, 0.52 )； § 编码第4个符号A时，取新间隔为[0.514, 0.5146 ) ，…。

Date116.3.2 算术编码符号ABCD 概率0.10.40.20.3 初始编码间 隔[0,0.1 )[0.1,0.5 )[0.5,0.7 )[0.7,1]Date126.3.2 算术编码v消息的编码输出可以是最后一个间隔中的任 意数，整个编码过程如下图所示最后在 [0.5143876,0.514402)中选择一个数作为编码 输出值：0.51439 v解码时，解码器由编码输出值：0.51439，可 马上解得一个字符为C，然后依次得到唯一 解A,D,A,C,D,BDate136.3.2 算术编码步 骤译码间隔译码10.51439在间隔 [0.5, 0.7)10 20.51439在间隔 [0.5, 0.7)的第1个1/1000 30.51439在间隔[0.5, 0.52)的第7个1/1011 40.51439在间隔[0.514, 0.52)的第1个1/1000 50.51439在间隔[0.514, 0.5146)的第5个1/1010 60.51439在间隔[0.5143, 0.51442)的第7个1/1011 70.51439在间隔[0.51439, 0.5143948)的第1个1/1001 8译码消息：10 00 11 00 10 11 01 译码过程如下：Date146.3.2 算术编码v在算术编码中需要注意的几个问题：§ 由于计算机精度不可能无限长，运算中容易出现 溢出，但多数机器都有16位、32位或者64位的精度，因此可使用比例缩放方法解决。

§ 算术编码器对整个消息只产生一个码字，这个码 字是在间隔[0, 1)中的一个实数，因此译码器在接受到所有位之前不能进行译码§ 算术编码也是一种对错误很敏感的编码方法，如 果有一位发生错误就会导致整个消息译错Date156.3.3 行程长度编码 vRLE（Run-Length Encoding）是一个针对 包含有顺序排列的多次重复的数据的压缩 方案其原理就是把一系列的重复值用一 个单独的值再加上一个计数值来取代，行 程长度就是连续且重复的单元数目如果 想得到原始数据，只需展开这个编码就可 以了 Date166.3.3 行程长度编码v例如，计算机制作图像中，不需要存储每 一个像素的颜色值，而仅存储一个像素的 颜色值以及具有相同颜色的像素数目就可 以，或者存储一个像素的颜色值，以及具 有相同颜色值的行数，这种压缩编码称为 行程编码具有相同颜色的连续的像素数 目称为行程长度Date176.3.3 行程长度编码v如图所示，假定一幅灰度图像，第n行的像 素值为：v用RLE编码方法得到的代码为： 3150841160代码红色斜体表示的数字是 行程长度，后面的数字代表像素的颜色值 例如红色斜体字50代表有连续50个像素 具有相同的颜色值，它的颜色值是8。

Date186.3.3 行程长度编码v对比RLE编码前后的代码数可以发现，在 编码前要用73个代码表示这一行的数据， 而编码后只要用10个代码表示代表原来的 73个代码，压缩前后的数据量之比约为7:1 ，即压缩比为7:1这说明RLE确实是一种 压缩技术，而且编码技术实用Date196.3.3 行程长度编码vRLE的性能好坏主要取决于图像本身的特 点RLE压缩编码尤其适用于计算机生成 的图像，对减少图像文件的存储空间非常 有效 v然而，由于颜色丰富的自然图像在同一行 上具有相同颜色的连续像素往往很少，而 连续几行都具有相同颜色值的连续行数就 更少，如果仍然使用RLE编码方法，不仅 不能压缩图像数据，反而可能使原来的图 像数据变得更大 Date206.3.3 行程长度编码v译码时按照与编码时采用的相同规则进行 ，还原后得到的数据与压缩前的数据完全 相同因此，RLE属于无损压缩技术 v它被用于BMP、JPEG/MPEG、TIFF和 PDF等编码之中，还被用于机Date216.3.4 词典编码v词典编码属于无损压缩技术，其根据是数 据本身包含有重复代码序列这个特性词 典编码的种类较多，归纳起来有两类。

§ 第一类词典编码 • LZ77、LZSS § 第二类词典编码 • LZ78、LZWDate22第一类词典编码v第一类词典编码的基本思想是查找正在压 缩的字符序列是否在前面输入的数据中出 现过，如果是，则用指向早期出现过的字 符串的“指针”替代重复的字符串Date23第一类词典编码v这里所指的“词典”是指用以前处理过的数 据来表示编码过程中遇到的重复部分 § 这类编码中的所有算法都是以Abraham Lempel和Jakob Ziv在1977年开发和发表的称 为LZ77算法为基础的 § LZSS算法——LZ77的改进方法Date24LZ77算法v输入数据流(input stream):待压缩的字符序列 v字符(character):输入数据流中的基本单元 v编码位置(coding position):输入数据流中当前 要编码的字符位置，前向缓冲器的开始字符 v前向缓冲器(lookahead buffer):存放从编码位置 到输入数据流结束的字符序列的存储器 v窗口(Window):包含W个字符的窗口，字符从 编码位置开始向后数 v指针(Pointer):指向窗口中的匹配串且含长度。

Date25LZ77算法vLZ77编码算法的核心是查找从前向缓冲器开 始的最长的匹配串具体执行步骤如下： § 把编码位置设置到输入数据流的开始 § 查找窗口中最长的匹配串 § 输出(Pointer， Length) Characters，其中Pointer 是指向窗口中匹配串的指针，Length表示匹配字 符的长度，Characters是前向缓冲器中第1个不匹 配的字符 § 如果前向缓冲器不是空的，则把编码位置和窗口 向前移Length+1个字符，然后返回到步骤2 Date26LZ77算法待编码的 数据流 位置1 2 3 4 5 6 7 8 9 10 字符 A A B C B B A B CC编码过程 步骤 位置 匹配串 字符输出1 1 -- A (0，0) A 2 2 A B (1，1) B 34 -- C (0，0) C 45 B B (2，1) B 57 A B C C (5，3) C 告诉译码 器回退5个 字符,然后 拷贝3个字 符“ABC”Date27LZ77算法v“步骤”栏表示编码步骤 v“位置”栏表示编码位置 v“匹配”栏表示窗口中找到的最长的匹配串。

v“字符”栏表示匹配之后在前向缓冲器中的第1个字符 v“输出”栏以(Back_chars， Chars_length) Explicit_character格式输出 § 其中(Back_chars， Chars_length)是指指向匹配串的指针， 告诉译码器“在这个窗口中向后退Back_chars个字符然后拷 贝Chars_length个字符到输出”，Explicit_character是真实 字符 § 例如，输出“(5，2) C”告诉译码器回退5个字符，然后拷贝2 个字符“AB” Date28LZ77算法v解压算法 ——解码 § 当碰到编码字符串时，解压算法使用，和 ，字段将编码替换成实际的正文字符串Date29LZ77 算法练习v给定一个报文 : abcdbbccaaabaeaaabaee， 请用LZ77算法对该报文序列进行编码！vvOutput : Output : (0,0,a)(0,0,b)(0,0,c)(0,0,d)(3,1,b)(4,1,c)(8,1,。