《数据压缩技术概论》电子课件讲义

数据压缩技术概论 压缩技术简史 压缩技术基础 Huffman编码 算术编码 工z77和工zw算法 JPEc算法 通用压缩工具比较

数据压缩技术概论 ▪ 压缩技术简史 ▪ 压缩技术基础 ▪ Huffman编码 ▪ 算术编码 ▪ LZ77和LZW算法 ▪ JPEG算法 ▪ 通用压缩工具比较

压缩技术分 通用数据压缩(均为无损压缩) 多媒体数据压缩(无损和有损压缩) 基于统计模型 基于字典模型图像压缩 音频和视频压缩 的压缩技术 的压缩技术 MPEG等 Huffman算术编码 编码 值图像 彩色图像矢量图像 RLE编码 PostScript JB|G等 JPEG等WMF z77 Z78LZW 灰度图像 CAD等 FELICS JPEG等

压缩技术分 类 通用数据压缩（均为无损压缩） 多媒体数据压缩（无损和有损压缩） 基于统计模型 的压缩技术 基于字典模型 的压缩技术 Huffman 编码 算术编码 LZ77 LZ78 LZW 图像压缩 音频和视频压缩 MPEG等 二值图像 CCITT JBIG等 灰度图像 FELICS JPEG等 彩色图像 RLE编码 JPEG等 矢量图像 PostScript WMF CAD等

乐缩技术的应用 人工智能(专家系统/知识树) 编译(JAWA) 程序设计算法/空间和时间效率) 全文索引(倒排索引表) 密码学(消除数据的原始特征) 文件系统(压缩扇区 音频(MP3) 数据库(B+树 视频(MPEG/RM) 归档(TARZ|P) 图像 (GIF/TIFF/JPEG) 存储(压缩池) 电报、传真(CC|T 通讯 Modem/网络协议)

压缩技术的应用 电报、传真(CCITT) 通讯(Modem/网络协议) 存储(压缩池) 文件系统(压缩扇区) 图像(GIF/TIFF/JPEG) 音频(MP3) 数据库 视频(MPEG/RM) (B+树) 归档(TAR/ZIP) 密码学(消除数据的原始特征) 全文索引(倒排索引表) 编译(JAVA) 程序设计(算法/空间和时间效率) 人工智能(专家系统/知识树)

压缩技术起源 信息压缩技术的起源 比计算机的发明早几千年

压缩技术起源 信息压缩技术的起源…… 比计算机的发明早几千年……

信息论 通过采用一定 信息存在冗余 的模型和编码方法, 可以降低这种冗余度 贝尔实验室的 Claude shannon和MIT的 RM. Fano 几乎同时提出了最早的对符号进行有效编码 从而实现数据压缩的 Shannon-Fano编码方法

信息论 信息存在冗余 通过采用一定 的模型和编码方法， 可以降低这种冗余度 贝尔实验室的 Claude Shannon 和 MIT 的 R.M.Fano 几乎同时提出了最早的对符号进行有效编码 从而实现数据压缩的 Shannon-Fano 编码方法

D.A. Huffman 1952年发表论文:“最小冗余度代码的构造方法” A Method for the Construction of Minimum Redundancy Codes UNIX系统上一个不太为现代人熟知的压缩程序 COMPACT就是 Huffman0阶自适应编码的具体实现 80年代初, Huffman编码又在CP/M和DOS系统 中实现,其代表程序叫SQ Huffman代;60年优,70年代乃至80年代的早

D.A.Huffman 1952 年 发表论文：“最小冗余度代码的构造方法” A Method for the Construction of Minimum Redundancy Codes UNIX 系统上一个不太为现代人熟知的压缩程序 COMPACT 就是 Huffman 0 阶自适应编码的具体实现 80 年代初，Huffman 编码又在 CP/M 和 DOS 系统 中实现，其代表程序叫 SQ Huffman时代：60 年代、70 年代乃至 80 年代的早期

接近极限——熵 80年代早期,数学家们设计出算术编码方法( Arithmetic Coding 算术编码是部分匹配预测( Predication by Partial matching PPM技术的变体 可以证明,算术编码得到的压缩效果可以最大地减小 信息的冗余度,用最少量的符号精确表达原始信息内容 口但是,在同样的计算机系统上,算术编码虽然可以得到 最好的压缩效果,却要消耗也许几十倍的计算时间

接近极限——熵 80年代早期，数学家们设计出算术编码方法(Arithmetic Coding) 可以证明，算术编码得到的压缩效果可以最大地减小 信息的冗余度，用最少量的符号精确表达原始信息内容 ❑ 但是，在同样的计算机系统上，算术编码虽然可以得到 最好的压缩效果，却要消耗也许几十倍的计算时间 算术编码是部分匹配预测(Predication by Partial matching, PPM)技术的变体

以色列人 归co2y和 Abraham Lempe 1977年发表论文:“顺序数据压缩的一个通用算法” A Universal algorithm for Sequential Data Compression 1978年发表论文:“通过可变比率编码的独立序列的压缩” Compression of Individual sequences via Variable-Rate Coding 字编码的代:L277和278压缩算法分

以色列人 Jacob Ziv 和 Abraham Lempel 1978 年 发表论文：“通过可变比率编码的独立序列的压缩” Compression of Individual Sequences via Variable-Rate Coding 字典编码时代：LZ77和LZ78压缩算法 1977 年 发表论文：“顺序数据压缩的一个通用算法” A Universal Algorithm for Sequential Data Compression

LZW算法 Terry welch 1984年发表论文:“高性能数据压缩技术” A Technique for High-Performance Data Compression Welch实现了LZ78算法的一个变种—LzW算法 UNIX:使用LZW算法的 Compress程序 MS-DOS:ARC程序,以及 PK Ware、 PKARO等仿制品

LZW算法 Terry Welch Welch 实现了 LZ78 算法的一个变种 —— LZW算法 UNIX：使用 LZW 算法的 Compress 程序 MS-DOS：ARC 程序，以及PKWare、PKARC 等仿制品。 1984 年 发表论文：“高性能数据压缩技术” A Technique for High-Performance Data Compression

j通用数据压缩 80年代中期以后,对Lz77算法进行改进 Haruyasu Yoshizaki( Yoshi) H] LHarc Robert Jung的ARJ 从 PKZip到 Winzip 通用数据压缩格式标准 z 工277,z78,工团W一起垄断当今的通用数据压缩领线

通用数据压缩 80年代中期以后，对LZ77算法进行改进 Haruyasu Yoshizaki(Yoshi) 的 LHarc Robert Jung 的 ARJ 从PKZip到WinZip： 通用数据压缩格式标准 —— ZIP LZ77、LZ78、LZW 一起垄断当今的通用数据压缩领域