- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
2013-7-19
A B C 0.1 0.4 0.2 [0,0.1) [0.1,0.5) [0.5,0.7)
10
D 0.3 [0.7,1]
6.3.2 算术编码
如果消息序列的输入为：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 ) ，…。
2013-7-19
2
6.3.1 Huffman编码
具体的编码步骤
至于哪个为“1”哪个为 “0”则无关紧要，最后 将信源出现的概率由大到小排序。 的结果仅仅是分配的代 码不同，而代码的平均 将两处最小概率组合相加，形成新概率。 长度是相同的。
将新概率与未编码的字符一起重新排序。 重复步骤2、3，直到出现的概率和为1。 分配代码
2013-7-19
算术编码也是一种对错误很敏感的编码方法，如果有 一位发生错误就会导致整个消息译错。
15
6.3.3 行程长度编码
RLE（Run-Length Encoding）是一个针对包 含有顺序排列的多次重复的数据的压缩方案。 其原理就是把一系列的重复值用一个单独的值 再加上一个计数值来取代，行程长度就是连续 且重复的单元数目。如果想得到原始数据，只 需展开这个编码就可以了。
• 代码分配从最后一步开始反向进行，对最后两个概率一 个赋予0代码，一个赋予1代码。记录下从树的根到每个 信源符号终节点的0和1序列。
2013-7-19 3
6.3.1 Huffman编码
Huffman编码中求平均码长的方法：
概率×码长
2013-7-19
4
6.3.1 Huffman编码
Huffman编码练习一:
2013-7-19 20
6.3.3 行程长度编码
译码时按照与编码时采用的相同规则进行，还 原后得到的数据与压缩前的数据完全相同。因 此，RLE属于无损压缩技术。 它被用于BMP、JPEG/MPEG、TIFF和PDF等 编码之中，还被用于传真机。
2013-7-19
21
6.3.4 词典编码
词典编码属于无损压缩技术，其根据是数据本 身包含有重复代码序列这个特性。词典编码的 种类较多，归纳起来有两类。
6.3 常用的无损数据压缩方法
6.3.1 Huffman编码 6.3.2 算术编码 6.3.3 行程RLE编码 6.3.4 词典编码
2013-7-19
1
6.3.1 Huffman编码
基本原理
依据信源字符出现的概率大小来构造代码，对出现 概率较大的信源字符，给予较短码长，而对于出现 概率较小的信源字符，给予较长的码长，最后使得 编码的平均码字最短。
2013-7-19 26
LZ77算法
待编码的 数据流
位置 1 2 A 3 B 4 5 6 7 8 9 10 C 字符 A C B B A B C 输出
步骤 位置 匹配串 字符
编码过程
1 2 3 4 5
1 2 4 5 7
-A -B ABC
27
A B C B C
(0，0) A (1，1) B (0，0) C (2，1) B (5，3) C
2013-7-19
16
6.3.3 行程长度编码
例如，计算机制作图像中，不需要存储每一个 像素的颜色值，而仅存储一个像素的颜色值以 及具有相同颜色的像素数目就可以，或者存储 一个像素的颜色值，以及具有相同颜色值的行 数，这种压缩编码称为行程编码。具有相同颜 色的连续的像素数目称为行程长度。
2013-7-19
其中(Back_chars， Chars_length)是指指向匹配串的指针，告诉 译码器“在这个窗口中向后退Back_chars个字符然后拷贝 Chars_length个字符到输出”，Explicit_character是真实字符。 例如，输出“(5，2) C”告诉译码器回退5个字符，然后拷贝2个字
j 1 n
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 根据哈夫曼编码结果，平均码字长度：
Lc=0.4×1+0.2×3+0.15×3+0.12×3+0.1×4+0.03×4 =2.33
2013-7-19 11
6.3.2 算术编码
符号
A
B
C
D
概率
2013-7-19
0.1
[0,0.1)
0.4
[0.1,0.5) 12
0.2
[0.5,0.7)
0.3
[0.7,1]
初始编码间隔
6.3.2 算术编码
消息的编码输出可以是最后一个间隔中的任意数， 整个编码过程如下图所示。最后在 [0.5143876,0.514402)中选择一个数作为编码输出 值：0.51439。 解码时，解码器由编码输出值：0.51439，可马上 解得一个字符为C，然后依次得到唯一解 A,D,A,C,D,B。
2013-7-19 9
6.3.2 算术编码
编码过程:
设信源符号为{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，如下表所示。 符号 概率 初始编码间隔
这里所指的“词典”是指用以前处理过的数据 来表示编码过程中遇到的重复部分。
这类编码中的所有算法都是以Abraham Lempel和 Jakob Ziv在1977年开发和发表的称为LZ77算法为基 础的。 LZSS算法——LZ77的改进方法
2013-7-19
24
LZ77算法
输入数据流(input stream):待压缩的字符序列 字符(character):输入数据流中的基本单元。 编码位臵(coding position):输入数据流中当前要编 码的字符位臵，前向缓冲器的开始字符。 前向缓冲器(lookahead buffer):存放从编码位臵到 输入数据流结束的字符序列的存储器。 窗口(Window):包含W个字符的窗口，字符从编码 位臵开始向后数。 指针(Pointer):指向窗口中的匹配串且含长度。
17
பைடு நூலகம்.3.3 行程长度编码
如图所示，假定一幅灰度图像，第n行的像素 值为：
2013-7-19
用RLE编码方法得到的代码为：3150841160。 代码红色斜体表示的数字是行程长度，后面的 数字代表像素的颜色值。例如红色斜体字50代 表有连续50个像素具有相同的颜色值，它的颜 色值是8。
18
6.3.3 行程长度编码
c 2013-7-19
编码效率、压缩比和冗余度分别为： H 2.25 3 96.6% r = 1-η = 3.4% C 1.2 L 2.33
2.33 96.6%、1.2、3.4%
7
6.3.1 Huffman编码
Huffman编码注意事项
哈夫曼编码没有错误保护功能，在译码时，如果码 串中没有错误，那么就能一个接一个的正确译出代 码。但如果码串中有错误，哪怕仅是1位出现错误， 不但这个码本身译错，后面的译码可能全错，这种 现象称为错误传播（Error Propagation）。 哈夫曼编码是可变长度码，很难随意查找或调用压 缩文件中间的内容，然后再译码，这就需要在存储 代码之前加以考虑。
设输入图像的灰度级{a1,a2,a3,a4,a5,a6}出现的概率 分别是0.4、0.2、0.12、0.15、0.1、0.03。试进行哈 夫曼编码，并计算平均码字长度。
2013-7-19
5
Huffman编码练习一答案
a1 0.4 1 a2 0.2
1
0 0 P3
P5
1
0 P4 1 P2
a4
0.15
2013-7-19 8
6.3.2 算术编码
算术编码（arithmetic coding AC）是利用0和1 之间的间隔来表示信源编码的一种方法，其编 码值是间隔的上、下限包含的相同二进制。编 码过程中的间隔决定了符号压缩后的输出。 算术编码用到两个基本的参数
符号的概率和它的编码间隔。
信源符号的概率决定压缩编码的效率，也决定 编码过程中信源符号的间隔，而这些间隔包含 在0到1之间。
1
0
1 0 1 0 P1
a3
0.12
0
a5
0.1
最终编码结果为： a1 =1, a2 =011 , a3 =001, a4 =010, a5 =0001, a6 =0000
0
a6
0.03
01
2013-7-19
6
Huffman编码练习一答案
据公式
P( x j ) log2 P( x j图像信源熵为： )
译码
10 00 11 00 10 11 01
8
6.3.2 算术编码
在算术编码中需要注意的几个问题：
由于计算机精度不可能无限长，运算中容易出现溢出， 但多数机器都有16位、32位或者64位的精度，因此可 使用比例缩放方法解决。 算术编码器对整个消息只产生一个码字，这个码字是 在间隔[0, 1)中的一个实数，因此译码器在接受到所有 位之前不能进行译码。
