输入第2个字符x2＝a1，i=1，它的子间隔I2＝[l2 , r2)=[l1 +)＝[0.5, 0.625)，由此可得d2=0.125。左右边界的二进制数分别表示为：L＝0.5=0.100 … (B)，R＝0.101… (B)。按照步骤2，u2＝v2＝0，发送0，而u3和v3不相同，因此在发送0之后就转到步骤3。

输入第3个字符，x3=a3，i=3, 它的子间隔I3＝[l3 , r3)=[)＝[0.59375, 0.609375)，由此可得d3=0.015625。左右边界的二进制数分别表示为：L＝0.59375=0.10011 (B)，R＝0.609375=0.100111 (B)。按照步骤2，u3＝v3＝0，u4＝v4＝1，u5＝v5＝1，但u6和v6不相同，因此在发送011之后转到步骤3。

…

发送的符号是：10011…。被编码的最后的符号是结束符号。

就这个例子而言，算术编码器接受的第1位是“1”，它的间隔范围就限制在[0.5, 1)，但在这个范围里有3种可能的码符a2, a3和a4，因此第1位没有包含足够的译码信息。在接受第2位之后就变成“10”，它落在[0.5, 0.75)的间隔里，由于这两位表示的符号都指向a2开始的间隔，因此就可断定第一个符号是a2。在接受每位信息之后的译码情况如下表4-08所示。

表4-08 译码过程表

接受的数字 间隔 译码输出
1 [0.5, 1) -
0 [0.5, 0.75) a2
0 [0.5, 0.609375) a1
1 [0.5625, 0.609375) -
1 [0.59375, 0.609375) a3
… … …

在上面的例子中，我们假定编码器和译码器都知道消息的长度，因此译码器的译码过程不会无限制地运行下去。实际上在译码器中需要添加一个专门的终止符，当译码器看到终止符时就停止译码。

在算术编码中有几个问题需要注意：


 由于实际的计算机的精度不可能无限长，运算中出现溢出是一个明显的问题，但多数机器都有16-, 32-或者64位的精度，因此这个问题可使用比例缩放方法解决。
 
 算术编码器对整个消息只产生一个码字，这个码字是在间隔[0, 1)中的一个实数，因此译码器在接受到表示这个实数的所有位之前不能进行译码。
 
 算术编码也是一种对错误很敏感的编码方法，如果有一位发生错误就会导致整个消息译错。
 

算术编码可以是静态的或者自适应的。在静态算术编码中，信源符号的概率是固定的。在自适应算术编码中，信源符号的概率根据编码时符号出现的频繁程度动态地进行修改，在编码期间估算信源符号概率的过程叫做建模。需要开开发态算术编码的原因是因为事先知道精确的信源概率是很难的，而且是不切实际的。当压缩消息时，我们不能期待一个算术编码器获得最大的效率，所能做的最有效的方法是在编码过程中估算概率。因此动态建模就成为确定编码器压缩效率的关键。

4.3 RLE编码

现实中有许多这样的图象，在一幅图象中具有许多颜色相同的图块。在这些图块中，许多行上都具有相同的颜色，或者在一行上有许多连续的象素都具有相同的颜色值。在这种情况下就不需要存储每一个象素的颜色值，而仅仅存储一个象素的颜色值，以及具有相同颜色的象素数目就可以，或者存储一个象素的颜色值，以及具有相同颜色值的行数。这种压缩编码称为行程编码，常用RLE(Run Length Encoding)表示，具有相同颜色并且是连续的象素数目称为行程长度。

为了叙述方便，假定一幅灰度图象，第n行的象素值为：

用RLE编码方法得到的代码为：80315084180。代码中用黑体表示的数字是行程长度，黑体字后面的数字代表象素的颜色值。例如黑体字50代表有连续50个象素具有相同的颜色值，它的颜色值是8。

对比RLE编码前后的代码数可以发现，在编码前要用73个代码表示这一行的数据，而编码后只要用11个代码表示就可以了，就是用11个代码代表原来的73个代码，压缩前后的数据量之比约为7:1，即压缩比为7:1。这说明RLE确实是一种压缩技术，而且这种编码技术相当直观，也非常经济。RLE所能获得的压缩比有多大，这主要是取决于图象本身的特点。如果图象中具有相同颜色的图象块越大，图象块数目越少，获得的压缩比就越高。反之，压缩比就越小。

译码时按照与编码时采用的相同规则进行，不言而喻，还原后得到的数据与压缩前的数据完全相同。由此可见RLE是无损压缩技术。

RLE压缩编码尤其适用于计算机生成的图象，对减少图象文件的存储空间非常有效。然而，RLE对颜色丰富的自然图象就显得力不从心，在同一行上具有相同颜色的连续象素往往很少，而连续几行都具有相同颜色值的连续行数就更少。如果仍然使用RLE编码方法，不仅不能压缩图象数据，反而可能使原来的图象数据变得更大。请注意，这并不是说RLE编码方法不适用于自然图象的压缩，相反，在自然图象的压缩中还真少不了RLE，只不过是不能单纯使用RLE一种编码方法，需要和其它的压缩编码技术联合应用。

4.4 词典编码

有许多场合，开始时不知道要编码数据的统计特性，也不一定允许你事先知道它们的统计特性。因此，人们提出了许许多多数的据压缩方法，企图用来对这些数据进行压缩编码，在实际编码过程中以尽可能获得最大的压缩比。这些技术统称为通用编码技术。词典编码(Dictionary Encoding)技术就是属于这一类，这种技术属于无损压缩技术。

4.4.1 词典编码的思想

词典编码(dictionary encoding)的根据是数据本身包含有重复代码这个特性。例如文本文件和光栅图象就具有这种特性。词典编码法的种类很多，归纳起来大致有两类。第一类词典法的想法是企图查找正在压缩的字符序列是否在以前输入的数据中出现过，然后用已经出现过的字符串替代重复的部分，它的输出仅仅是指向早期出现过的字符串的“指针”。这种编码思想如图4-06所示。

这里所指的“词典”是指用以前处理过的数据来表示编码过程中遇到的重复部分。这类编码中的所有算法都是以Abraham Lempel和Jakob Ziv在1977年开发和发表的称为LZ77算法为基础的，例如1982年由Storer和Szymanski改进的称为LZSS算法就是属于这种情况。

第二类算法的想法是企图从输入的数据中创建一个“短语词典(dictionary of the phrases)”，这种短语不一定是像“严谨勤奋求实创新”和“国泰民安是坐稳总统宝座的根本”这类具有具体含义的短语，它可以是任意字符的组合。编码数据过程中当遇到已经在词典中出现的“短语”时，编码器就输出这个词典中的短语的“索引号”，而不是短语本身。这个概念如图4-07所示。

.Ziv和A.Lempel在1978年首次发表了介绍这种编码方法的文章。在他们的研究基础上，Terry A.Weltch在1984年发表了改进这种编码算法的文章，因此把这种编码方法称为LZW(Lempel-Ziv Walch)压缩编码，首先在高速硬盘控制器上应用了这种算法。

4.4.2 LZ77算法

为了更好地说明LZ77算法的原理，首先介绍算法中用到的几个术语：


 输入数据流(input stream)：要作压缩的字符序列。
 字符(character)：输入数据流中的基本单元。
 编码位置(coding position)：输入数据流中当前要编码的字符位置，指前向查看缓冲存储器中的开始字符。
 前向缓冲存储器(lookahead buffer)：存放从编码位置到输入数据流结束的字符序列的存储器。
 窗口(Window)：指包含W个字符的窗口，字符是从编码位置开始向后数也就是最后处理的字符数。
 指针(Pointer)：指向窗口中的匹配串且含长度的指针。

go on

LZ77编码算法的核心是查找从前向缓冲存储器开始的最长的匹配串。编码算法的具体执行步骤如下：


 把编码位置设置到输入数据流的开始位置。
 
 查找窗口中最长的匹配串。
 
 输出(Pointer, Length) Characters，其中Pointer是指向窗口中匹配串的指针，Length表示匹配字符的长度，Characters是前向缓冲存储器中的不匹配的第1个字符。
 
 如果前向缓冲存储器不是空的，则把编码位置和窗口向前移Length+1个字符，然后返回到步骤2。
 

例：待编码的数据流如表4-09所示，编码过程如表4-10所示。现作如下说明：


 “步骤”栏表示编码步骤。
 “位置”栏表示编码位置，输入数据流中的第1个字符为编码位置1。
 “匹配”栏表示窗口中找到的最长的匹配串。
 “字符”栏表示匹配之后在前向缓冲存储器中的第1个字符。
 “输出”栏以(Back_chars, Chars_length) Explicit_character格式输出。其中(Back_chars, Chars_length)是指指向匹配串的指针，告诉译码器“在这个窗口中向后退Back_chars个字符然后拷贝Chars_length个字符到输出”，Explicit_character是真实字符。例如，表4-10中的输出“(5,2) C”告诉译码器回退5个字符，然后拷贝2个字符“AB”

表4-09待编码的数据流

位置
 1
 2
 3
 4
 5
 6
 7
 8
 9
 
字符  
 A
 A
 B
 C
 B
 B
 A
 B
 C
 

表4-10 编码过程

步骤
 位置
 匹配串  
 字符  
 输出  
 
1
 1
 --
 A
 (0,0) A
 
2
 2
 A
 B
 (1,1) B
 
3
 4
 --
 C
 (0,0) C
 
4
 5
 B
 B
 (2,1) B
 
5
 7
 A B
 C
 (5,2) C
 

4.4.3 LZSS算法

LZ77通过输出真实字符解决了在窗口中出现没有匹配串的问题，但这个解决方案包含有冗余信息。冗余信息表现在两个方面，一是空指针，二是编码器可能输出额外的字符，这种字符是指可能包含在下一个匹配串中的字符。LZSS算法以比较有效的方法解决这个问题，它的思想是如果匹配串的长度比指针本身的长度长就输出指针，否则就输出真实字符。由于输出的压缩数据流中包含有指针和字符本身，为了区分它们就需要有额外的标志位，即ID位。

LZ77编码算法的具体执行步骤如下：


 把编码位置置于输入数据流的开始位置。
 
 在前向缓冲存储器中查找与窗口中最长的匹配串
① Pointer ：=匹配串指针。
② Length ：=匹配串长度。
 
 判断匹配串长度Length是否大于等于最小匹配串长度(Length?MIN_LENGTH) ，
如果“是”：输出指针，然后把编码位置向前移动Length个字符。
如果“否”：输出前向缓冲存储器中的第1个字符，然后把编码位置向前移动一个字符。
 
 如果前向缓冲存储器不是空的，就返回到步骤2。