行程长度压缩

行程长度压缩
原理是将一扫描行中的颜色值相同的相邻像素用一个计数值和那些像素的颜色值来代替。例如: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 3．0、3．1的位图文件中采用了这种压缩方法。该压缩方法编码也是以两个字节为基本单位。其中第一个字节规定了用第二个字节指定的颜色重复次数。如编码0504表示从当前位置开始连续显示5个颜色值为04的像素。当第二个字节为零时第二个字节有特殊含义:0表示行末；
1表示图末；2转义后面2个字节，这两个字节分别表示一像素相对于当前位置的水平位移和垂直位移。这种压缩方法所能压缩的图像像素位数最大为8位(256色)图像。
3．BI_RLE压缩方法:
该方法也用于WINDOWS 3．0/3．1位图文件中，它与BI_RLE8编码类似，唯一不同是:BI_RLE4的一个字节包含了两个像素的颜色，因此，它只能压缩的颜色数不超过16的图像。因而这种压缩应用范围有限。
4．紧缩位压缩方法(Packbits):
该方法是用于Apple公司的Macintosh机上的位图数据压缩方法，TIFF规范中使用了这种方法，这种压缩方法与BI_RLE8压缩方法相似，如1c1c1c1c2132325648压缩为:831c2181325648，显而易见，这种压缩方法最好情况是每连续128个字节相同，这128个字节可压缩为一个数值7f。这种方法还是非常有效的。

霍夫曼编码压缩也是一种常用的压缩方法。是1952年为文本文件建立的，其基本原理是频繁使用的数据用较短的代码代替，很少使用的数据用较长的代码代替，每个数据的代码各不相同。这些代码都是二进制码，且码的长度是可变的。如:有一个原始数据序列， ABACCDAA则编码为A(0)，B(10)，C(110)，D111)，压缩后为010011011011100 。 产生霍夫曼编码需要对原始数据扫描两遍，第一遍扫描要精确地统计出原始数据中的每个值出现的频率，第二遍是建立霍夫曼树并进行编码，由于需要建立二叉树并遍历二叉树生成编码，因此数据压缩和还原速度都较慢，但简单有效，因而得到广泛的应用。

LZW压缩技术比其它大多数压缩技术都复杂，压缩效率也较高。其基本原理是把每一个第一次出现的字符串用一个数值来编码，在还原程序中再将这个数值还成原来的字符串，如用数值0x100代替字符串"abccddeee"这样每当出现该字符串时，都用0x100代替，起到了压缩的作用。至于0x100与字符串的对应关系则是在压缩过程中动态生成的，而且这种对应关系是隐含在压缩数据中，随着解压缩的进行这张编码表会从压缩数据中逐步得到恢复，后面的压缩数据再根据前面数据产生的对应关系产生更多的对应关系。直到压缩文件结束为止。LZW是可逆的，所有信息全部保留。
算术压缩方法
算术压缩与霍夫曼编码压缩方法类似，只不过它比霍夫曼编码更加有效。算术压缩适合于由相同的重复序列组成的文件，算术压缩接近压缩的理论极限。这种方法，是将不同的序列映像到0到1之间的区域内，该区域表示成可变精度(位数)的二进制小数，越不常见的数据要的精度越高(更多的位数)，这种方法比较复杂，因而不太常用。
JPEG(JointPhotographicExprertsGroup联合摄影专家组)JPEG标准与其它的标准不同，它定义了不兼容的编码方法，在它最常用的模式中，它是带失真的，一个从JPEG文件恢复出来的图像与原始图像总是不同的，但有损压缩重建后的图像常常比原始图像的效果更好。JPEG的另一个显著的特点是它的压缩比例相当高，原图像大小与压缩后的图像大小相比，比例可以从1 ％到80～90 ％不等。这种方法效果也好，适合多媒体系统。
这里我们来看一下这个压缩Gif文件的LZW算法:
/* LZW.C
void PackGif(FILE *fp,char far *ImageData,
unsigned int width,unsigned int depth,int BitsPerPixel)
{kk1}
register int i,j;
unsigned char ThisChar;
int code;
char far *bitmap = ImageData;

index = 1;
pixmask = 0xff;
remcnt = 0;
rem = 0;
InitCnt = 0;
First_Char = BitsPerPixel;
CLEAR = 1 << BitsPerPixel; . //256,16,or 4
EOI = CLEAR + 1;
oldcode = -1;
memset( CTfirst,0,4096 );
memset( CTlink,0,8192 );
memset( CTnext,0,8192 );

PackInit( CLEAR );
PutCode( fp,CLEAR );

for( i=0;i{kk1}
for( j=0;j{kk1}
ThisChar = bitmap[j];
code = LookupCT(oldcode,ThisChar);
if( code != -1)
oldcode = code;
else{kk1}
PutCode( fp,oldcode );
oldcode = (int) ThisChar;
}
if (nextcode>nextlim)
{kk1} if (reqcnt==12)
{kk1}
PutCode( fp,oldcode );
PutCode( fp,CLEAR ); /* Position */
PackInit(CLEAR); }
else {kk1} reqcnt ++;
nextlim = nextlim << 1;
if (reqcnt==12) nextlim--;
} } }
bitmap = farptr( bitmap,(long)width ); }
PutCode( fp,oldcode );
PutCode( fp,EOI );
Flush( fp );
fputc( 0,fp );
fputc( 0x3b,fp );
return ;
}