LosslessDataCompression 山东大学潘荣江panrj@/~prj •数据压缩的概念•信息论基础•熵编码 –RLE编码–霍夫曼编码–算术编码–LZW编码 内容
2 多媒体信息的数据量 •多媒体计算机要处理的信息主要有文字、声音、图形、图像、动画、视频等，其中与视觉有关的约占总信息量的85% •连续媒体(音频、视频)需要处理和传送的数据量大的惊人 –对于分辨率为640*480的彩色电视画面，每秒30帧，则一秒钟的数据量为：640*480*24bit*30frames/s=221.12Mbits •播放时，需要221Mbps的通信线路。
•存储时，1张CD可存640MB，仅可以存放23秒的数据。
•多媒体系统必须采用压缩过的音频和视频数据。
数据压缩 •压缩的目的是减小存储容量和降低数据传输率，使得现有计算机和通信网络的指标与性能方面达到要求。
•How？ –去除冗余数据 CODEC Input EncoderCompressedDecoder Message Message OutputMessage
4 基本概念 数据：使用约定的符号对客观事物的数量、属性、位置及其相互关系的抽象表示，以便于进行保存、传递和处理。
数据量：表达每个信息所需符号个数的总和存储空间：在计算机中，存储空间是指存储数据 所需要的字节数，存储空间和数据量有直接关系。
•带宽 –在模拟通信中，通常指信号所占据的频率区间的宽度，又称为频宽，以赫兹（Hz）为单位。
例如模拟语音电话的信号带宽为3400Hz，一个PAL-D电视频道的带宽为8MHz。
–在数字通信中，指的是比特率(bitrate)，即每秒钟传输数据的位数，单位是bps(bitspersecond)，有时也指每秒传送的字节数，单位是Bps(bytespersecond)。
•数据量与带宽的关系： 数据量=带宽×传输数据所需要的时间。
数据和信息的关系：数据是信息的表达方式，是信息的载体。
数据压缩(press)：就是以较少位数的数据来表示原始数据信息的过程。
数据可以是文字，语音，图像、视频、图形、动画以及各种采集或生成的数字序列。
各种类型数据有其共性也有其特性，因此所采用的压缩方法不尽相同。
多媒体中主要研究图像和视频的压缩方法。
多媒体数据中的冗余 种类 统计特性 空间冗余时间冗余 信息熵冗余 图像结构冗余 知识冗余 视觉冗余 听觉冗余 其它 原因像素间相关性时间方向上的相关性编码造成的冗余图像本身的构造包含的冗余收发两端对事物的共同认识导致的冗余人的视觉特性导致的冗余人的听觉特性导致的冗余其他因素形成的冗余 主要方法变换编码、预测编码帧间预测、运动补偿统计编码轮廓编码、区域分割基于知识的编码非线性量化、比特分配
8 a图像 编码冗余 3255325532553255325532553255325532553255 325533325533325533325533325533 32553150325533 3255315032553332553150325533 b图像的数据表示 若每个像素值用8位表示，则总数据量n1864512b 若用0表示出现次数最多的
3，用一位二进制的1表示255，用两位二进制的10表示出现次数最少的150，则表示整幅图像只需要 n21401212367b 冗余445b 空间冗余 •空间冗余又称为像素冗余或几何冗余，描述图像具有局部自相似这个特性，也就是说图像中的一点的颜色和周围邻域内的像素点的颜色值相等或接近，单个像素携带的信息相对较小。
•这是静态图像存在的最主要的一种数据冗余。
一幅图像记录了画面上可见景物的颜色。
同一景物表面上各采样点的颜色之间往往存在着空间连贯性，从而产生了空间冗余。
空间冗余示例(长度，像素值)（8，3） 3255325532553255325532553255325532553255 325531503255315032553150 325533325533325533325533325533 325533325533325533 对于有连续相等灰度值的情况，采用(相等点个数,灰度值)组合的编码方式。
空间冗余示例 【1，2，3，4，5，6，7，8，9】111111111 (9,1) 对于灰度值相近的情况，可以利用对当前点与前一个点的差进行编码的方法。
在实际应用中，当前点的值可能与前几个点的灰度值相关，此时可以采用当前点与前几个像素点灰度值的加权和的差，进行编码，这就是预测编码的思想。
k e(i)f(i)ajf(ij)j
0 变换编码示例 a原始数据 b变换域 图像像素间有较强的相关性，可以通过一种变换把这相关性去掉，让图像的信息集中在少数几个系数上，这样也可以减少冗余，达到对图像进行压缩的目的。
这就是变换编码思想。
心理视觉冗余 •人观察图像的目的就是获得有用的信息，但人眼并不是对所有的视觉信息具有相同的敏感度。
•在实际应用中，人也不是对所有的信息具有相同的关心度。
在特定场合，一些信息相对另外一些信息来说，就不那么重要，这些相对不重要的信息就是心理视觉冗余。
a52K心理视觉冗余压缩b28K 人眼的分辨力是有限的 时间冗余 •视频是由一段有序的图像组成的，在这个序列中相邻两幅图像的拍摄间隔仅为为40毫秒（PAL制），在这么短时间内，相邻两幅幅图像之间变化不大，具有较大的相关性，这反映为时间冗余。
•在视频的相邻帧间，往往包含相同的背景和移动物体，因此，后一帧数据与前一帧数据有许多共同的地方，即在时间上存在大量的冗余。
•下图为时间冗余示例，相邻两帧图像差别很小，背景不变，只有小球和手在动，并且幅度很小。
t帧 t+1帧 时间冗余示例 • 视频压缩主要是基于时间冗余特性进行的，利用前面帧或者后面帧来预测当前帧，然后对预测误差采用静态图像的压缩方法进行压缩。
现行的各种视频标准都是基于这种思想的。
数据压缩的发展史 莫尔斯码香农霍夫曼 算术编码LZW JPEG1992JPEG2000 静止图像 国际标准 SItT标aUn准d-Tard(V(VeHersr.is2oi6on1n11))(V(VeHersr.is2oi6on1n22))H.263HH.2.26633++H.263++ 联合Jo制int定ITITUU-T-/ISO/IEC S标tan准dards H.262/MPEG-2H.264/MPEG-4AVC ISS标OMta/准PInEdCaGrdMPEG-1(VM(版ePrEs本iGo-n14)1)(VM(版ePrEs本iGo-n24)2) 视频图像 198819901992199419961998200020022004 压缩的分类 •无损压缩与有损压缩 –无损压缩也称无失真压缩或熵（不变）压缩，指信息熵在压缩和解压缩过程中不会损失。
–有损压缩也称为有失真压缩。
•无损压缩(LosslessCompression)(InputOutput) –使用压缩数据进行重构(还原，解压缩)后的数据与原来数据完全相同 –无损压缩用于要求数据压缩没有失真的场合。
例如：可执行文件的压缩，GIF,PNG,PCM。
–根据目前的技术水平，无损压缩算法一般可以把数据压缩到原来的1/2～1/5 19 有损压缩(LossyCompression) •有损压缩(InputOutput) –使用压缩后的数据进行重构，重构后的数据与原来的数据有所不同，但不影响人对原始资料表达的信息的理解，不会造成误解。
–适用于重构信号不一定非要和原始信号完全相同的场合。
例如，图像和声音的压缩就可以采用有损压缩，因为其中包含的数据往往多于我们的视觉系统和听觉系统所能接收的信息，丢掉一些数据而不至于对声音或者图像所表达的意思产生误解，但可大大提高压缩比。
目前已经有把数据压缩到原来的几百分之一的压缩算法。
20 常用无损和有损压缩方法 种类无损压缩有损压缩 压缩方法行程编码（RLE）霍夫曼编码（Huffman）词典编码（LZW）算术编码无损预测编码变换编码矢量量化编码有损预测编码运动补偿预测 压缩算法质量评价 通常情况下，衡量一个压缩算法的性 能，主要从四个方面考虑：
1.压缩率
2.码率
3.保真度
4.算法复杂度 压缩（率）比 •压缩比pressionratio)是衡量数据压缩方法压缩程度的一个重要指标,反映了数据的压缩效率。
通常将Cr定义为压缩前后数据量之比。
Cr值越大，压缩效率越高。
压缩前的数据量压缩前的每个像素平均码长 Cr压缩后的数据量压缩后的每个像素平均码长 视频码率 •视频码率是指视频文件在单位时间内使用的数据流量，单位是位每秒（bps），它是视频编码中画面质量控制中最重要的部分。
在同样分辨率情况下，视频文件的码率越大，压缩比就越小。
•视频码率与视频文件大小（数据量）之间的关系是： 编码后的视频文件数据量=视频码率×时间。
数据保真度 •在图像压缩中，通常利用心理视觉冗余放弃图像中一些不重要的细节，进行有损压缩。
在解码端，恢复出来的图像和原始图像不可能完全一样，这就要我们定义一些信息损失测度来描述解码图像与原始图像的偏离程度，这些测度称为图像的保真度准则。
常用的准则分为两大类：客观保真度准则和主观评价准则。
•客观保真度准则是对解码后图像与原始图像的误差进行定量计算，可用函数形式描述。
客观保真度准则有时也称为客观失真度准则。
常用的客观保真度准则包括3种。
1）均方根误差： erms MN(f(x,y)fˆ(x,y))2 x1y
1 MN 2)均方信噪比： MN fˆ(x,y)
2 SNR x1y
1 ms MN (f(x,y)fˆ(x,y))
2 x1y
1 3)峰值信噪比PSNR： PSNR10log f 2max 10MN (f(x,y)fˆ(x,y))
2 x1y
1 MN 两幅图像的均方根误差越小，PSNR就越大，图像失真度就越小。
•PSNR是目前最普遍和最广泛使用的图像质量客观测度，不过许多实验结果都显示，PSNR无法和人眼看到的视觉质量完全一致，有可能PSNR较高者看起来反而比PSNR较低者差。
这是因为人眼的视觉对于误差的敏感度并不是绝对的，其感知结果会受到许多因素的影响（例如：人眼对空间频率较低的差异敏感度较高；人眼对亮度差异的敏感度比色度高；人眼对一个区域的感知结果会受到其周围邻近区域的影响），因此研究与主观感觉一致的图像客观保真度准则一直是热点。
主观评价准则 •主观评价是指观察者依据自己的感觉对图像质量进行评价。
尽管客观保真度准则提供了一种简单、方便的评估信息损失的方法，但很多解压图最终是供人观看的。
事实上，具有相同客观保真度的不同图像，在人的视觉中可能产生不同的视觉效果。
这是因为客观保真度是一种统计平均意义下的度量准则，对于图像中的细节无法反映出来，而人的视觉系统具有独特的特性，能够觉察出来。
这种情况下，用主观的方法来测量图像的质量更为合适。
•图像质量的主观评价通常按ITU-R500号标准进行。
常用的方法是向一组（人数通常超过20人）精心挑选的观察者展示图像，并将他们对该图的评价综合平均起来得到一个统计的质量评价结果。
图像主观质量的评价结果用一定数量的观察者的平均分数来表示，这个平均分数又被称为平均感觉分MOS(meanopinionscore) 静止图像质量主观评价等级 图像等级主观评价干扰和杂波可见度
5 优 感觉不到
4 良 能看出图像质量的变化，但并不妨碍观看
3 中 能明显看出图像质量变坏，对观看稍有妨碍，但 能容忍
2 差 对观看有妨碍
1 劣 非常严重地妨碍观看 视频图像质量主观评分标准 评分
654321 评价 说明 优秀图像质量非常好，如同人能想象出的最好质量。
良好图像质量高，观看舒服，有干扰但不影响观看。
可用图像质量可接受，有干扰但不太影响观看。
刚可看图像质量差，干扰有些妨碍观看，观察者希望改进。
差图像质量很差，妨碍观看的干扰始终存在，几乎无法观看。
不能用图像质量极差，不能使用。
算法复杂度 •衡量一个压缩算法的好坏，不但要看它的压缩率和保真度，还希望算法简单。
算法简单意味着算法运行快并且存储空间消耗少。
通常把衡量算法运行快慢的测度称为时间复杂度；衡量空间占用多少的测度称为空间复杂度。
•一个算法在存储器上所占用的存储空间，包括存储算法本身所占用的存储空间、算法的输入输出数据所占用的存储空间、算法在运行过程中临时占用的存储空间这三个方面。
代码区（codearea）全局数据区堆区（heaparea）栈区（stackarea） 存放程序代码存放程序的全局数据和静态数据存放程序的动态数据存放程序的局部数据 算法运行时所占用内存空间分布 信息论基础 信息论基础 •信息：通常指具有新内容、新知识的消息。
•信源：信息的来源。
根据信源的不同，其输出的消息有各 种类型，如文本、语音、图像等。
消息需要经过转换成适合于信道传输的信号才能进行传输•信道：信息传播的途径。
•信宿：能接收信息的事物。
信息的接受者，可以是人也可以是机器，如收音机、电视机、计算机等。
•信息系统＝信源＋信道＋信宿。
36 信源可以按其信号取值集合和信号取值时刻的离散性或连续性分类，也可以按其统计特征来分类，通常是两者结合在一起。
信源发出的信号经过时间采样和幅值量化，即信号的个数和取值都是可列的，则该信源称为离散信源，否则称为连续信源。
信源发出的信号中，每个信息单元之间是相互独立的，则该信源称为独立信源（或无记忆信源），否则称为不独立信源（或有记忆信源）。
•编码器 编码器将信息转换成利于传输与存储的形式。
其数学描述如下图所示。
码组 S{s1,s2,s3,,sN} 信信号元 符号集 编码器 si
X 信源符号集 A{a1,a2,a3, X{x1,x2,,xi, W{w1,w2,w3,,wN} 码字 ,aN} 码元 信源符号 } •例输入信号表示一幅图像的连续6个像素点，灰度值分别是10，20，10，20，20，30，用二进制0和1对其编码，输出为｛01，1，01，1，1，00｝。
s是信号，s中的10，20，10，20，20，30每一个称为信元。
由于灰度图像的取值范围是0至255之间，因此信源符号集是{0,1,
2,…,255}，信源符号是0至255之间的任意整数。
码元集是｛0，1｝，而码元是0或者
1。
码组是｛01，1，01，1，1，00｝，而10的码字是01，20的码字1，30的码字是00，码长分别是2，1，
2。
信息量 •信源发出的消息是不确定的，与概率有关。
•事件发生的概率越小，猜测它有没有发生的困难 程度就越大，不确定性就越大，一旦它出现必然使人感到意外，给人的信息量就越大；•当消息的概率很小，即几乎不可能的消息出现了，则会给人以巨大的信息量。
•发生概率等于1的必然事件，就没有不确定性，不具有任何信息量。
40 信息的度量 •用自信息I(x0)表示x0信息量的多少，度量信息不确定性，不确定性通常由x0发生的概率P(x0)来描述，因此可以确定I(x0)是P(x0)的一个函数。
I(x)log21log2p(x)p(x) 信息量的单位 •信息论中常用的对数底是
2，则信息量的单位是比特(bit)。
–如果p(ui)＝0.5,I(ui)＝1bit，1比特信息量就是两个互不相容的等概率事件之一发生时所提供的信息量。
•若取自然对数e为底，则信息量的单位为奈特(nat)。
•若以10为对数底，则信息量的单位为笛特(det)。
42 •单个信号符号的信息用自信息衡量，那么对信源产生的信源符号序列的信息用什么衡量呢？一个简单的做法是将每个信源符号的自信息加起来求平均，即信源符号s序列的平均信息量H(s)的数学描述为：
M I(s(i))Nx出现的次数 H(s)i
1  k I(xk)
M k
1 M
N N  p(xk)I(xk)p(xk)log2p(xk) k
1 k
1 熵（Entropy） •在信息论，香农借鉴热力学的概念，把平均信息量称为“信息熵”（InformationEntropy），用以衡量信息的不确定性。
信息熵可以理解为信源发出的一个符号所携带的平均信息量。
•一个系统越是有序，信息熵就越低；反之，一个系统越是混乱，信息熵就越高。
所以，信息熵也可以说是系统有序化程度的一个度量。
如果信源各个符号出现的概率相等，则信息熵达到最大。
熵（Entropy） •信源S的熵定义为每一个事件所携带的平均信息量 H(s)pilog2(1/pi)i Pi是符号Si在S中出现的概率；log2(1/Pi)表示包含在符号Si中的信息量，也就是编码符号Si所 需要的位数。
•香农第一定理（可变长无失真信源编码定理）：采用无失真最佳信源编码可使每个信源符号的编码位数尽可能地小，但它的极限是原始信源的熵值。
超过了这一极限就不可能实现无失真的解码。
信息熵给出了无失真编码时，每个符号所需平均码长的下限。
45 Entropy •Entropyisthecentralconceptinthefieldof“informationtheory”,pioneeredbyClaudeShannon •Entropyshowsthatthereisafundamentallimittolosslesspression April30,1916-February24,2001 46 EntropyExample •【例1】p(S){0.5,0.125,0.125,0.125,0.125}H(S)0.5*log24*0.125log8
2 •【例2】一幅用256级灰度表示的图像，如果每一个象素点灰度的概率均为Pi=1/256，编码每一个象素点就需要8位。
47 •【例3】有一幅40个象素组成的灰度图像，灰度共有5级，40个象素中出现灰度
A、B、
C、D、E的象素数如表所示。
如果用3位表示5个等级的灰度值，也就是每个象素用3位表示，编码这幅图像总共需要120位。
符号 ABCDE 出现次数157765 H(S)=(15/40)×log2(40/15)+(7/40)×log2(40/7)+…+(5/40)×log2(40/5)=2.196， 每个符号用2.196位表示，40个象素需用87.84位。
48 熵编码 行程编码 •行程（游程，游长，Run-Length）指的是信号中信源符号连续重复出现的个数（长度）。
•如果给出了行程和信源符号及信源符号出现的位置，便能恢复出原始数据，这就是行程编码又称为游程编码（RunLengthEncoding,RLE），它是相对简单的编码技术，用于去除图像的空间冗余。
–例如对信号ddeee采用行程编码，则码组是：3a1b6c2d3e。
行程算法原理 •行程编码的码组构成形式 {(l1,g1),(l2,g2),,(lN,gN)} •码字(li,gi)：第一项行程li用来记录原始数据中连续的相同的信源符号的个数；第二项记录信源符号gi。
原始信号的长度等于所有行程长度之和。
灰度值 li l2 l
N l1 l
3 g1g2g3gigN位置 行程编码示意 •行程编码对于拥有大面积，相同颜色区域的图像，非常有效。
•如果图像中的数据非常分散，则行程编码不但不能压缩数据，反而会增加图像文件的大小。
如对数据{abcde}采用行程编码，则编码后的码组为{1a1b1c1d1e}，数据量不但没有减少，反而增加了一倍。
•行程编码比较适合二值图像的编码，1980年，国际电报电话咨询委员会（CCITT）针对传真类应用，发布了压缩和传递二值图像的CCITTGroup3标准，在该标准中以水平方向的行程编码为基础，采用去除编码冗余的霍夫曼压缩方法来对行程进行编码。
目前收发传真还是采用该标准。
•由于行程编码简单，在其它类图像的编码中，也尽量创造利于使用行程编码的条件，对其进行相应改进。
–例如在静态图像JPEG编码标准中，针对量化后的数据出现大量零的情况，就采用了行程编码和霍夫曼编码相结合的方式进行编码。
–图像文件格式BMP、PCX和TIFF也都支持行程编码。
PCX文件对行程编码的规定 •编码时的最大行程长度为63，如果行程长度大于63，则必须分多次存储。
•对于长度大于1的行程，编码时先存入其行程长度（长度L加上192），再存入该行程的代表值，行程长度和行程的代表值分别占一字节。
•对于长度为1的行程，即单个像素，如果该像素的值小于或等于192，则编码时直接存入该像素值，而不存储长度信息；否则，先存入193，再存入该像素值，这样做的目的是为了避免该像素值被误认为长度信息了。
•通过这些规定，在一定程度上提高了行程编码的效率。
霍夫曼(Huffman)编码 编码方法(从下到上，1952年)。
1根据符号概率的大小按由大到小顺序对符号进行排序2把概率最小的两个符号组合成一个节点，3重复步骤
2，形成一棵“树”，4从根节点开始到相应于每个符号的“树叶”，从上到下标 上“0”(左/上枝)或者“1”(右/下枝)，至于哪个为“1”哪个为“0”则无关紧要，最后的结果仅仅是分配的代码不同，而代码的平均长度是相同的。
56 例HELLO 解码 •霍夫曼码的码长可变，但不需要额外附加同步代码。
–例如，码串中的第1位为
0，那么肯定是符号
L，因为表示其他符号的代码没有一个是以0开始的。
同样，如果出现“110”，那么它就代表符号
E。
•在解码时，只需先从码组中读取l位码字，然后在码书中查找相匹配的码字，若存在码字对应的信源符号，则输出，否则，读取l+1位，再查找，依此类推，便完成解码过程。
58 解码步骤： a)设待译码字长度l=1；b)从码组w中读取l位编码符号，构建待译码字；c)在码书(codebook)中查找是否存在待译码字，若不存在，则l=l+
1，否则输出对应的信源符号，并从码组中删除开始的l位编码符号，l=1；d)判断是否为空，若不为空，执行步骤
2，否则结束。
霍夫曼编码特点 ①编出来的码都是异字头码(唯一前缀代码)，保证了码的唯一可译性。
②由于编码长度可变，译码时间较长。
③编码长度不统
一，硬件实现有难度。
④对不同信号源的编码效率不同，当信号源的符号概率为2的负幂次方时，达到100％的编码效率；若信号源符号的概率相等，则编码效率最低。
⑤由于0与1的指定是任意的，故由上述过程编出的最佳码不是唯一的，其平均码长是一样的，不影响编码效率与数据压缩性能。
⑤霍夫曼编码的码字最小长度为
1，这不能充分接近压缩的理想下限。
⑥霍夫曼编码需要事先知道每个信源符号的出现概率，在进行实时传输时，需要随时调整符号出现的概率，但每次更新概率，霍夫曼的码书就得重新计算。
⑦霍夫曼编码假定每个信元之间是相互独立的，而在实际中信元之间往往是相关的，信元之间存在空间冗余，霍夫曼编码没有充分利用这一个特性进行编码。
HuffmanCoding的问题 ①错误传播(errorpropagation)：霍夫曼码没有错误保护功能。
在译码时，如果码串中没有错误，就能一个接一个地正确译出代码。
但如果码串中发生错误，不但这个码本身译错，更糟糕的是一错一大串。
②霍夫曼码是可变长度码，因此很难随意查找或调用压缩文件中间的内容，然后再译码。
尽管如此，霍夫曼码还是得到广泛应用。
62 算术编码 •算术编码不是将单个信源符号映射成一个码字，而是将整个序列编码为[0,1]之间的实数 •两个基本参数：符号的概率和它的编码间隔。
–信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，这些间隔包含在0到1之间。
–编码过程中的间隔决定了符号压缩后的输出。
•基本思想： –把整个信源表示为0到1之间的一个区间，其长度等于该序列的概率 –在该区间内选择一个代表性的小数，转化为二进制作为实际的编码输出。
63 ArithmeticCodingEncoder •BEGIN low=0.0; high=1.0; range=1.0; while(symbol!
=terminator){ get(symbol);low=low+range*Range_low(symbol);high=low+range*Range_high(symbol);range=high-low;} outputacodesothatlow<=code 66 ArithmeticCodingDecoder •BEGIN getbinarycodeandconverttodecimalvalue=value(code); Do{ findasymbolssothatRange_low(s)<=valueC 0.3 0.16015625
A 0.0 0.80078125
E 0.55 0.8359375
E 0.55 0.953125 $ 0.9 High Range 0.5 0.2 0.2 0.2 0.85 0.3 0.85 0.3 1.0 0.1 算术编码中需要注意的几个问题 •
由于实际的计算机的精度不可能无限长（多数机器都有16位、32位或者64位的精度），运算中出现溢出是一个明显的问题，可使用比例缩放方法解决。
•算术编码器对整个消息只产生一个码字，这个码字是在间隔[0,1)中的一个实数，因此译码器在接受到表示这个实数的所有位之前不能进行译码。
•算术编码也是一种对错误很敏感的编码方法，如果有一位发生错误就会导致整个消息译错。
69 •算术编码可以是静态的或者自适应的。
•在静态算术编码中，信源符号的概率是固定的•在自适应算术编码中，信源符号的概率根据编码 时符号出现的频繁程度动态地进行修改，在编码期间估算信源符号概率的过程叫做建模。
–事先知道精确的信源概率是很难的，而且是不切实际的。
当压缩消息时，我们不能期待一个算术编码器获得最大的效率，所能做的最有效的方法是在编码过程中估算概率。
因此动态建模就成为确定编码器压缩效率的关键。
70 词典编码 •词典编码主要模仿查词典的行为，用词语在词典中的位置号来代替词语，例如用地址号25来代替“中华人民共和国”七个字。
若数据中重复的词语多，就可以实现压缩，减少数据量了。
在解码时，只需根据地址号将词典相应地址的词语读出来，就可以解码了。
•词典编码就是用简单的代号代替信号中信元序列（短语），这种编码方法实际上就是利用了信元符号之间的相关性进行压缩的。
短语与代号的对应表就是词典。
•词典编码是一种无损压缩方法。
•利用词典编码方法进行压缩主要涉及两个问题：如何构造词典和如何查词典。
•词典构造和查找方式的不同便产生了不同的词典编码方法，如LZ77算法，LZSS算法，LZ78算法和LZW算法。
这些算法中最著名的当属LZW编码方法。
•LZW（Lempel-Ziv-Welch）是AbrahamLempel、JacobZiv和TerryWelch创造的一种通用无损数据压缩算法。
LZW算法已广泛应用于通用数据压缩中，如压缩软件WinRAR、WinZip以及图像压缩格式GIF和TIFF格式、PDF文件格式和PNG文件格式。
LZW算法原理 •LZW算法的词典是根据输入的数据动态创建的。
–先将可能的信源符号创建一个初始词典，–然后在编码过程中，遇到词典中没有的短语（信元序列）就加到词典之中，动态创建词典。
LZW算法短语的构造规则 •1）短语由两部分构成：从信号中分解出的且在词典中能找到的最长的短语（信元序列）和下一个输入的信元符号。
•2）后进入词典的短语的第一个符号是先它一个进入词典的短语的最后一个符号。

4 A
1 B 前
5 B
2 A
6 AB
B 4
7 B
2 C 短语进入词典顺序
8 C
A 3
9 AB
A4 10 ABBA6 后 短语构造示意（每个短语框上方标号是短语索引号，框中每个短语下方的数字是其索引号） 词典的规律 1）短语可表示为，其中n表示短语前半部分在词典中的索引号（地址号），a表示一个信源符号。
在LZW算法中，短语长度通常是固定的，即n和a的长度固定； 2）短语的第一个码元是初始词典中的基本符号；3）词典中的短语按先后顺序首尾相连。
•ALGORITHM:LZWCompression •BEGIN • s=nextinputcharacter; • whilenotEOF • { • c=nextinputcharacter; • //searchforthelongestsequence • ifs+cexistsinthedictionary • s=s+c; • else//newword • { • outputthecodefors; • addstrings+ctothedictionarywitha newcode; • s=c;//thelastsymbolofthemostrecentdictionary entryisthefirstsymbolofthenextparseblock • } • } • outputthecodefors; •END 例利用LZW构造短语规则对信号s={“ABABBABCABABBA”}进行词典编码 ①假设初始词典：
A，B，C的码字(地址标号)分别为1，2，3；②读入信元“A”，到词典中查找是否存在（第一个肯定存在），若存在，记录符号“A”；③读下一个信元“B”，与前一个合成为一个短语“AB”，到词典中查找，若存在，则再读（这样做的目的是构造最长的可识别的短语）；否则，将短语加入到词典中，标号
4，同时输出前一个信元“A”的标号
1，并记载短语的最后一个符号“B”（这样做的目的是让短语首尾相连）； ④继续读下一个符号“A”，与前一个符号“B”合成短语“BA”，词典中没有，将“BA”加入到词典中，记为标号
5，输出前一个符号“B”的标号
2，记录符号“A”； ⑤读入下一个符号“B”，与记录的符号合成短语“AB”，词典中有，则读下一个符号“B”，形成短语“ABB”。
词典中不存在“ABB”，则加入到词典中，标记为
6，输出前一个短语“AB”的符号
4，记录符号“B”， ⑥读入下一个符号“A”，形成短语“BA”，词典中存在，读入下一个符号“B”，形成短语“BAB”，词典中不存在，将“BAB”加入到词典中，标号为
7，输出前一个符号的短语“BA”标号
6，记录“B”；⑦依此类推，完成对信号的编码 W={124523461} 词典表 码字短语
1 A 初 始
2 B 字 典
3 C
4 AB
5 BA
6 ABB
7 BAB
8 BC
9 CA 10ABA 11ABBA 编码过程 输入 输出前一个短语的最后一个字母
A B 1B（加入短语AB）
A 2A（加入短语BA）
B B 4B（加入短语ABB）
A B 5B（加入短语BAB）
C 2C（加入短语BC）
A 3A（加入短语CA）
B A 4A（加入短语ABA）
B B
A 6A（加入短语ABBA） EOF1 LZW解码算法 LZW解码过程主要受编码过程中短语的构造规则影响 在编码过程中，当前要加入词典的短语由先前输出的短语(s)和当前读入的一个信元符号构成，因此在解码过程中，每读入一个码字，要判断是否在词典中。
①若当前码字在词典中，就把码字所代表的短语entry输出，并且将先前输出的短语(s)和当前码字所代表短语的第一个符号(entry[0])合成一个新的短语s+entry[0]加入到词典中。
②若当前码字不在词典中，则将先前输出的短语(s)和刚入词典短语的最后一个符号合并成一个新短语加入到词典中。
因为刚入词典短语的最后一个字符与先前输出的短语(s)的第一个字符相同，因此当前新短语就是s与s[0]构成。
•LZW解码算法 BEGIN s=NIL;//前一个码字所代表短语whilenotEOF{ k=nextinputcode;//当前码字 entry=dictionaryentryfork; //当前码字对应的短语 /*exceptionhandler*/if(entry==NULL)//当前码字不在词典 entry=s+s[0]; outputentry;if(s!
=NIL)//构造新短语 addstrings+entry[0]todictionarywithanewcode;s=entry;} END 82 Example:LZWpressionforstring“ABABBABCABABBA”. 输入编码：124523461.
S K Entry/output NIL
1 A
A 2
B B
4 AB AB
5 BA BA
2 B
B 3
C C
4 AB AB
6 ABB ABB
1 A A
EOF Code 123 4567891011 String ABC ABBAABBBABBCCAABAABBA 83 例子：编码“ABABBABCABBABBAC”.
S C Output ABAABBBABCAABABBAABABBABBA
B 1
A 2
B B
4 A
B 5
C 2
A 3
B B
A 6
B B
A C 10 Code123456789 10 11 StringABC ABBAABBBABBCCA ABBA ABBAC 84 •解码
S K NIL
1 A
2 B
4 AB
5 BA
2 B
3 C
6 ABB 10 Entry/output ABABBABCABB?
Code 123 45678910 String ABC ABBAABBBABBCCAABBA 85 •ThisexampleillustratesthatwheneverthesequenceofsymbolstobecodedisCharacter,String,Character,String,Character,andsoon,theencoderwillcreateanewcodetorepresentCharacter+String+Characteranduseitrightaway,beforethedecoderhashadachancetocreateit!
Whenthisurs,thevariables=Character+String. •Whentheinputcodehasnotbeendefinedinthedecoder’sdictionary,itwillsimplyassumethatthecoderepresentsthesymbolss+s[0];thatis,Character+String+Character. LZW编码的几个问题 1）词典的长度 在具体应用中，一般都会规定词典长度位数，例如12位。
对于以字节（8位）为压缩单元（如图像的灰度），词典的长度为212=4096，索引的长度为12位，词典的前256个保存单个灰度值，剩下的3840个分配给压缩过程中出现的灰度值串。
在词典满了以后（新字符串超过4096），输出一个清除词典的标记LZW_CLEAR，清空词典，开始新的编码。
2）短语的长度 词典中短语的长度可能会很长，所以将短语表示成形式，其中n是前一个短语的索引号，a是一个符号，则短语的长度可以是固定的。
例如对图像压缩，a表示图像灰度值，需要8位，n表示码字12位，则一个短语的长度就是20位。
3）查词典 编码时，需要确定短语是否在词典中？若词典长度很长，每次顺序查找很费时间，可通过哈希函数（散列、杂凑）的方法来减少查表的次数，从而提高效率。
习题
1、计算Entropy及Huffman编码 符号 频率 Huffman编码 a1 1/2
0 a2 1/4 10 a3 1/8 110 a4 1/8 111 H
(S)1log221log241log281log28
2 4
8 8 112131371.75bits24884 89
2、HuffmanCoding Character X6X3X4X5X1X7X2 Probability 0.250.20.150.150.10.10.05 0.45 1.00.25 0.15 0.55 0.3 Char X6 X3 X4 X5 X1 X7 X2 Code101100101101000000001 0 11 10 01
0 1 10
0 90
3、假设有符号表[
A,B,C]，已知概率分布是PA=0.5,PB=0.4,PC=0.1
(1)用Huffman编码对消息BBB进行编码所需要的位数及输出结果
(2)用算术编码对消息BBB进行编码所需要的位数及输出结果 HuffmanCode:A-
0,B-10,C-11
4、写出下列字符串的LZW编码结果。
位置
1 2
3 4
5 6
7 8
9 字符ABBABABAC 词典 当前字符C当前前缀P输出
(1)
A － －
(2)
B － －
(3)
C － －
(4)AB
A A
B AB,B
(1)
(5) BB
B BB,B
(2)
(6) BA
A BA,A
(2)
(7) ABA
B AB
A ABA,A
(4)
(8) ABAC
B A
C ABABAABAC,C
(7) -- --
(3) 93