一、 行程长度压缩
原理是将一扫描行中的颜色值相同的相邻像素用一个计数值和那些像素的颜色值来代替。例如:aaabccccccddeee,则可用3a1b6c2d3e来代替。对于拥有大面积,相同颜色区域的图像,用RLE压缩方法非常有效。由RLE原理派生出许多具体行程压缩方法:
1.PCX行程压缩方法: 该算法实际上是位映射格式到压缩格式的转换算法,该算法对于连续出现1次的字节Ch,若Ch>0xc0则压缩时在该字节前加上0xc1,否则直接输出Ch,对于连续出现N 次的字节Ch,则压缩成0xc0+N,Ch这两个字节,因而N最大只能为ff-c0=3fh(十进制为63),当N大于63时, 则需分多次压缩。
2.BI_RLE8压缩方法:在WINDOWS的位图文件中采用了这种压缩方法。该压缩方法编码也是以两个字节为基本单位。其中第一个字节规定了用第二个字节指定的颜色重复次数。 如编码 0504表示从当前位置开始连续显示5个颜色值为04的像素。当第二个字节为零时第二个字节有特殊含义:0表示行末;1表示图末;2转义后面2个字节, 这两个字节分别表示下一像素相对于当前位置的水平位移和垂直位移。这种压缩方法所能压缩的图像像素位数最大为8位(256色)图像。
3.BI_RLE压缩方法: 该方法也用于WINDOWS位图文件中,它与 BI_RLE8编码类似,唯一不同是:BI_RLE4的一个字节包含了两个像素的颜色,因此,它只能压缩的颜色数不超过16的图像。因而这种压缩应用范围有限。
4.紧缩位压缩方法(Packbits):该方法是用于Apple公司的Macintosh机上的位图数据压缩 方法, TIFF 规范中使用了这种方法, 这种压缩方法与BI_RLE8压缩方法相似,如1c1c1c2132325648 压缩为:83 1c 21 81 32 56 48,显而易见, 这种压缩方法最好情况是每连续128个字节相同,这128个字节可压缩为一个数值7f。这种方法还是非常有效的。
二、霍夫曼编码压缩:
也是一种常用的压缩方法。是1952年为文本文件建立的,其基本原理是频繁使用的数据用较短的代码代替,很少使用的数据用较长的代码代替,每个数据的代码各不相同。这些代码都是二进制码,且码的长度是可变的。如: 有一个原始数据序列,ABACCDAA则编码为A(0),B(10),C(110),(D111),压缩后为010011011011100。产生霍夫曼编码需要对原始数据扫描两遍,第一遍扫描要精确地统计出原始数据中的每个值出现的频率,第二遍是建立霍夫曼树并进行编码,由于需要建立二叉树并遍历二叉树生成编码,因此数据压缩和还原速度都较慢,但简单有效,因而得到广泛的应用。
哈夫曼编码是无损压缩当中最好的方法。它使用预先二进制描述来替换每个符号,长度由特殊符号出现的频率决定。常见的符号需要很少的位来表示,而不常见的符号需要很多为来表示。
哈夫曼算法在改变任何符号二进制编码引起少量密集表现方面是最佳的。然而,它并不处理符号的顺序和重复或序号的序列。
三、LZW压缩方法
LZW压缩技术比其它大多数压缩技术都复杂, 压缩效率也较高。其基本原理是把每一个第一次出现的字符串用一个数值来编码,在还原程序中再将这个数值还成原来的字符 串,如用数值0x100代替字符串"abccddeee"这样每当出现该字符串时,都用0x100代替,起到了压缩的作用。 至于0x100与字符串的对应关系则是在压缩过程中动态生成的,而且这种对应关系是隐含在压缩数据中,随着解压缩的进行这张编码表会从压缩数据中逐步得到恢复,后面的压缩数据再根据前面数据产生的对应关系产生更多的对应关系。直到压缩文件结束为止。LZW是可逆的, 所有信息全部保留。
属于无损压缩编码,该编码主要用于图像数据的压缩(如GIF)。对于简单图像和平滑且噪声小的信号源具有较高的压缩比,并且有较高的压缩和解压缩速度。
LZW压缩技术把数据流中复杂的数据用简单的代码来表示,并把代码和数据的对应关系建立一个转换表,又叫“字符串表”。
转换表是在压缩或解压缩过程中动态生成的表,该表只在进行压缩或解压缩过程中需要,一旦压缩和解压缩结束,该表将不再起任何作用。
四、算术压缩方法
算术压缩与霍夫曼编码压缩方法类似,只不过它比霍夫曼编码更加有效。算术压缩适合于由相同的重复序列组成的文件,算术压缩接近压缩的理论极限。这种方法,是将不同的序列映像到0到1之间的区域内,该区域表示成可变精度(位数 )的二进制小数,越不常见的数据要的精度越高(更多的位数),这种方法比较复杂,因而不太常用。
五、Rice
对于由大word(例如:16或32位)组成的数据和教低的数据值,Rice编码能够获得较好的压缩比。音频和高动态变化的图像都是这种类型的数据,它们被某种预言预处理过(例如delta相邻的采样)。
尽管哈夫曼编码处理这种数据是最优的,却由于几个原因而不适合处理这种数据(例如:32位大小要求16GB的柱状图缓冲区来进行哈夫曼树编码)。因此一个比较动态的方式更适合由大word组成的数据。
Rice编码背后的基本思想是尽可能的用较少的位来存储多个字(正像使用哈夫曼编码一样)。实际上,有人可能想到Rice是静态的哈夫曼编码(例如,编码不是由实际数据内容的统计信息决定,而是由小的值比高的值常见的假定决定)。
编码非常简单:将值X用X个‘1’位之后跟一个0位来表示。
六、Lempel-Ziv (LZ77)
Lempel-Ziv压缩模式有许多不同的变量。基本压缩库有清晰的LZ77算法的实现(Lempel-Ziv,1977),执行的很好,源代码也非常容易理解。
LZ编码器能用来通用目标的压缩,特别对于文本执行的很好。它也在RLE和哈夫曼编码器(RLE,LZ,哈夫曼)中使用来大多数情况下获得更多的压缩。
在LZ压缩算法的背后是使用RLE算法用先前出现的相同字节序列的引用来替代。
简单的讲,LZ算法被认为是字符串匹配的算法。例如:在一段文本中某字符串经常出现,并且可以通过前面文本中出现的字符串指针来表示。当然这个想法的前提是指针应该比字符串本身要短。
例如,在上一段短语“字符串”经常出现,可以将除第一个字符串之外的所有用第一个字符串引用来表示从而节省一些空间。
一个字符串引用通过下面的方式来表示:
1. 唯一的标记
2. 偏移数量
3. 字符串长度
由编码的模式决定引用是一个固定的或变动的长度。后面的情况经常是首选,因为它允许编码器用引用的大小来交换字符串的大小(例如,如果字符串相当长,增加引用的长度可能是值得的)。
七、DEFLATE是同时使用了LZ77算法与哈夫曼编码(Huffman Coding)的一个无损数据压缩算法。它最初是由Phil Katz为他的PKZIP归档工具第二版所定义的,后来定义在RFC 1951规范中。
人们普遍认为DEFLATE不受任何专利所制约,并且在LZW(GIF文件格式使用)相关的专利失效之前,这种格式除了在ZIP文件格式中得到应用之外也在gzip压缩文件以及PNG图像文件中得到了应用。
DEFLATE压缩与解压的源代码可以在自由、通用的压缩库zlib上找到。
更高压缩率的DEFLATE是7-zip所实现的。AdvanceCOMP也使用这种实现,它可以对gzip、PNG、MNG以及ZIP文件进行压缩从而得到比zlib更小的文件大小。在Ken Silverman的KZIP与PNGOUT中使用了一种更加高效同时要求更多用户输入的DEFLATE程序。
PS:见维基百科http://zh.wikipedia.org/zh/DEFLATE
分享到:
相关推荐
基于JPEG标准的静态图像压缩算法概述,张元伟,刘彦隆,本文主要论述了基本JPEG标准的编码方法。其中包括采样、离散余弦变换、量化和熵编码等几个主要步骤,最后,用Visual C 编程实现把一�
随心压缩算法 介绍 Xpress 压缩算法具有三种变体,均专为提高速度而设计。最快的变体 Plain LZ77 实现了 LZ77 算法 ( UASDC )。较慢的变体 LZ77+Huffman 在 LZ77 数据上添加了 Huffman 编码通道。第三个变体 LZNT1 ...
它提供了广泛的压缩算法和工具,用于数据存储、传输和优化存储空间。 【使用人群】 适用于Java开发者、数据处理专家以及需要在Java应用中实现压缩和解压缩功能的用户。 【使用场景及目标】 commons-compress-1.18....
数据压缩是利用各种算法将数据冗余压缩到最小,并尽可能地减少失真,从而提高传输效率和节约存储空间。 数据压缩技术一般分为有损压缩和无损压缩。无损压缩是指重构压缩数据(还原,解压缩),而重构数据与原来数据...
关于图像压缩的算法介绍,内容容易理解,图文并茂
《C/C++常用算法手册》分3篇,共13章,“第1篇算法基础篇”介绍了算法概述,重点分析了数据结构和基本算法思想;“第2篇算法基本应用篇”详细讲解了算法在排序、查找、数值计算、数论、经典趣题和游戏中的应用;“第...
本人自己写的,内容包活概述,omp原理,具体设计,仿真结果及源程序。代码正确无误。
图像压缩对于有效传输图像和货物空间至关重要。 通过因特网访问多媒体数据的无线通信和交互式媒体的巨大或巨大的需求正在猛烈发展。 数据压缩是一种功能。... 这项工作希望能获得有关图像压缩算法的近距离报告和概述。
5.1.5曲线压缩算法的比较 5.1.6面域的数据压缩算法 5.2栅格数据的压缩 5.2.1链式编码 5.2.2游程长度编码 5.2.3块式编码 5.2.4差分映射法 5.2.5四叉树编码 5.3拓扑关系的生成 5.3.1基本数据结构 ...
第1章算法概述1.1用计算机求解问题与算法 1.1.1用计算机求解问题的步骤 1.1.2算法及其要素和特性 1.1.3算法设计及基本方法 1.1.4从算法到实现 1.2算法描述 1.2.1算法描述简介 1.2.2算法描述约定 1.2.3一个简单问题的...
压缩算法:通过选择不同的压缩算法,如DEFLATE算法用于ZIP格式,实现对文件的压缩。 流操作:使用Java的输入输出流(InputStream、OutputStream)来读取和写入文件内容。 异常处理:通过捕获并处理IOException等异常...
算法基础、数据结构、基本算法思路、排序算法、查找算法、基本数学问题、数据结构问题、数论问题、经典算法、游戏中的算法、密码学概述、压缩与解压缩算法、算法面试题等内容
算法基础篇 **章 算法和实现算法的Java语法 1.1 建立算法初步概念 1.1.1 什么是算法 1.1.2 算法的发展历史 1.1.3 算法的分类 ...**2章 压缩与解压缩算法 第3篇 算法面试篇 **3章 数学能力测试 **4章 算法面试题
3.3仿射变换3.4地图投影变换3.4.1概述3.4.2地球椭球体的相关公式3.4.3兰勃特投影3.4.4墨卡托投影3.4.5高斯一克吕格投影3.4.6通用横轴墨卡托投影思考题第4章空间数据转换算法4.1矢量数据向栅格数据...
第1章 算法概述. 1.1 算法与程序 1.2 算法复杂性分析 习题1 第2章 递归与分治策略 2.1 递归的概念 2.2 分治法的基本思想 2.3 二分搜索技术 2.4 大整数的乘法 2.5 Strassen矩阵乘法 2.6 棋盘覆盖 2.7 合并排序 2.8 ...
【摘要】MPEG音频层III压缩算法,是由ISO11172-3标准规定的一种高效、高保真的压缩编码算法。由于层III压缩算法的复杂度高,运算量大,为此提出了在实时应用中,基于数字信号处理器(Digital Signal Processor,...
MP3 压缩原理和 MP3Stego 算法概述 MP3 压缩原理概述分段压缩 编码PCM音 频信息 , 在每个内循环 中, 控制循环条件 根据掩体文件的 长度和LData, 使用decode解密 将需要解密的MP3文件复制至装有decode文件的目录下,...
6.3.3 压缩因子粒子群算法 115 6.3.4 离散粒子群算法 116 6.4 粒子群算法流程 116 6.5 关键参数说明 117 6.6 MATLAB仿真实例 120 参考文献 135 第7章 模拟退火算法 137 7.1 引言 137 7.2 模拟退火...
HTTP压缩采用通用的压缩算法如gzip等压缩HTML、JavaScript或 CSS文件。压缩的最大好处就是降低了网络传输的数据量,从而提高客户端浏览器的访问速度。当然,同时也会增加一点点服务器的负担。Gzip是比较常见的 一种...