文档介绍：无损数据压缩技术无损压缩?无损压缩:是指使用压缩后的数据进行重构(或者叫做还原, 解压缩),重构后的数据与原来的数据完全相同; ?无损压缩用于要求重构的信号与原始信号完全一致的场合。–磁盘文件的压缩。数据压缩到原来的 1/2 ~ 1/4 。–霍夫曼(Huffman) 算法和 LZW(Lenpel-Ziv & Welch) 压缩算法。有损压缩?有损压缩:指使用压缩后的数据进行重构,重构后的数据与原来的数据有所不同,但不影响人对原始资料表达的信息造成误解。?有损压缩适用于重构信号不一定非要和原始信号完全相同的场合。–图像和声音的压缩(因为其中包含的数据往往多于我们的视觉系统和听觉系统所能接收的信息,丢掉一些数据而不至于对声音或者图像所表达的意思产生误解, 但可大大提高压缩比)。熵 ,它表示某一事件出现的消息越多,事件发生的可能性就越小,数学上就是概率越小。 I i =-log 2P i表示,其中 P i为第 i 个事件的概率, 0< P i <1信源 S的熵 (Shannon) 的理论,信源 S的熵定义为: H(s )=?=? iPiLog2(1/Pi) 其中 Pi是符号 Si在S中出现的概率; Log2(1/Pi) 表示包含在 Si中的信息量,也就是编码 Si所需要的位数。例如,一幅用 256 级灰度表示的图像,如果每一个象素点灰度的概率均为 1/256 ,编码每一个象素点就需要 8位。举例应用?例:有一幅 40个象素组成的灰度图像,灰度共有 5级,分别用符号 A、B、C、D和E表示, 40个象素中出现灰度 A的象素数有 15个,出现灰度 B的象素数有 7个,出现灰度 C 的象素数有 7个,出现灰度 D和E的象素数为 6个和 5个。如果用 3个位表示 5个等级的灰度值,也就是每个象素用 3位表示,编码这幅图像总共需要 120 位。?H(S ) = (15/40) * log 2 (40/15) + (7/40) * log 2 (40/7) + …… + (5/40) * log 2 (40/5) = 这就是说每个符号用位表示, 40个象素需用位。香农-范诺算法编码图4-01 香农-范诺算法编码举例 ABCD E 霍夫曼编码?从下到上的编码方法初始化,根据符号概率的大小按由大到小顺序对符号进行排序,把概率最小的两个符号组成一个节点?例:有一幅 40个象素组成的灰度图像,灰度共有 5级,分别用符号 A、B、C、D和E表示, 40个象素中出现灰度 A的象素数有 15个,出现灰度 B的象素数有 7个,出现灰度 C的象素数有 7个,出现灰度 D和E的象素数为 6个和 5个。 5E 6D 7C 7B 15 A 编码概率出现次数符号霍夫曼编码?霍夫曼码的码长虽然是可变的,但却不需要另外附加同步代码。例如,码串中的第 1位为 0,那末肯定是符号A,因为表示其他符号的代码没有一个是以 0开始的, 因此下一位就表示下一个符号代码的第 1位。同样, 如果出现“ 110 ”,那么它就代表符号 D。如果事先编写出一本解释各种代码意义的“词典”,即码簿,那么就可以根据码簿一个码一个码地依次进行译码。?采用霍夫曼编码时有两个问题值得注意: ①霍夫曼码没有错误保护功能,在译码时,如果码串中没有错误,那么就能一个接一个地正确译出代码。但如果码串中有错误,哪仅是 1位出现错误,不但这个码本身译错,更糟糕的是一错一大串,全乱了套,这种现象称为错误传播(error propagation) 。计算机对这种错误也无能为力,说不出错在哪里,更谈不上去纠正它。②霍夫曼码是可变长度码,因此很难随意查找或调用压缩文件中间的内容,然后再译码, 这就需要在存储代码之前加以考虑。?与香农-范诺编码相比,这两种方法都自含同步码,在编码之后的码串中都不须要另外添加标记符号,即在译码时分割符号的特殊代码。