共有回帖数 0 个
-
关于压缩的定义什么的我就不多说了，直观上看，压缩的过程就是用较短的数据来表示较长的数据。这里我们了解一下信息熵的概念，信息熵，通俗的讲就是一段数据所包含的信息量。信息熵可以用相关的公式来定量计算，这里我们就不深入了，只是希望大家明白一个道理：无论是什么压缩算法（无损压缩），压缩后虽然数据长度会变小，但是数据所包含的信息熵是不变的（很多情况下还可能变大）。
既然一个较短的数据可以用来表示一个较长的数据，那么原先较长的数据必然存在冗余。这里我们举一个冗余的例子，如“中华人民共和国”，在现代文里用“中国”就能表示其全部意思，这就说明在“中化人民共和国”里有冗余数据。我们也可以基于这个例子构造一个压缩算法，把文章中的“中华人民共和国”全部替换成“中国”，这样文章长度减小了，但是意思完全不变。
下面我给大家介绍一个基于这个原理的很简单hello_compress，在每处理一个字符之前，我们会根据对之前数据的分析来推测下一个字符，如果推测结果和实际一样，就说明这个字符完全可以由前文推测出来，是冗余数据，我们在压缩结果写入一个bit位'1'来表示这个字符在解压时由前文推测的结果给出；如果推测和实际不一样，那么我们要写入一个bit位'0'表示这个字符不能推测出来，然后将这个字符写入压缩结果，解压时直接从压缩文件复制到解压结果中。
我们可以估计一下压缩效果：对于成功的推测，我们可以节省7个bit，对于失败的推测，我们将浪费1个bit。所以只要我们推测的成功率超过12.5%，就可以实现对数据的压缩。
下面是hello_compress的源代码，为了简化代码我把文件读写都用标准IO实现，使用时要通过文件重定向来读取和写入文件。
// file: hello_compress
#include stdio.h
#include string.h
int main(int argc, char** argv)
{
static char stdin_buffer[65536];
static char stdout_buffer[65536];
static unsigned char predict_map[256][256];
unsigned char prev_char1 = 0;
unsigned char prev_char2 = 0;
unsigned char block[8];
unsigned char flag_byte = 0;
int flag_pos = 0;
int block_pos = 0;
int i;
int next_char;
int out_char;
setbuffer(stdin, stdin_buffer, sizeof(stdin_buffer));
setbuffer(stdout, stdout_buffer, sizeof(stdout_buffer));
if(argc == 2 && strcmp(argv[1], "encode") == 0)
{
// compress
while((next_char = getchar()) != EOF)
{
// write to file if a flag_byte is full
if(flag_pos == 8)
{
putchar(flag_byte);
for(i = 0; i block_pos; i++)
{
putchar(block);
}
flag_byte = 0;
flag_pos = 0;
block_pos = 0;
}
// fill a flag byte
if(next_char == predict_map[prev_char1][prev_char2])
flag_byte |= (1 flag_pos);
else
block[block_pos++] = next_char;
flag_pos += 1;
predict_map[prev_char1][prev_char2] = next_char;
prev_char1 = prev_char2;
prev_char2 = next_char;
}
// write last block
if(flag_pos 0)
{
putchar(flag_byte);
for(i = 0; i block_pos; i++)
{
putchar(block);
}
}
}
else if(argc == 2 && strcmp(argv[1], "decode") == 0)
{
// decompress
while((next_char = getchar()) != EOF)
{
flag_byte = next_char;
for(i = 0; i 8; i++)
{
if(1 & (flag_byte i))
{
out_char = predict_map[prev_char1][prev_char2];
}
else
{
if((next_char = getchar()) != EOF)
out_char = next_char;
else
break;
}
putchar(out_char);
predict_map[prev_char1][prev_char2] = out_char;
prev_char1 = prev_char2;
prev_char2 = out_char;
}
}
}
else
{
fputs("argument: (encode|decode) in.file out.file", stderr);
}
return 0;
}
我们用炮姐的EGE代码（http://tcgraphics.svn.sourceforge.net/viewvc/tcgraphics/trunk/src/graphics.cpp?revision=9）来测试一下我们的hello_compress压缩效果。将hello_compress.c编译为hello_compress，然后在控制台执行./hello_compress encode graphics.cpp graphics.cpp.helloz压缩。可以看到原文件大小为220.1KB，压缩后为90.0KB，压缩率约为40.9%。在控制台执行./hello_compress decode graphics.cpp.helloz graphics_2.cpp可以进行解压。
下面我们来分析一下hello_compress代码，由于不能对文件直接写入bit，我们用一个8位的flag_byte来记录这些bit，记录满8个bit位时统一写入文件，block数组用来存放推测失败时的字符，和flag_byte一起写入文件。开头的setbuffer是为了增加标准IO的缓冲大小来加快读写速度，删去也不会对程序的正确性造成影响。
我们重点看一下预测数据的部分，prev_char1和prev_char2用来保存最近处理的两个字符，在压缩时，我们通过这两个字符在数组predict_map中定位，将读入的第三个字符存入表中，这样到下一次再出现这两个字符时我们就能推测出第三个字符，比如处理"I can can a can into a can“这句话，在处理第一个can后predict_map['c']['a']中就存放了字符'n'，这样处理第二个"can"的时候我们就能由"ca"推测出后面的"n"来。
对hello_compress的改进：
在下一章中我们这会讲到，通过前文来预测后文的结构称为“预测模型(predictor/model)”，而使用预测模型处理数据来去除数据冗余的结构称为“编码器(coder)”，这是一个压缩算法最重要的两个部分，在hello_compress中，我们使用的是简单记录最近的三字符短语的模型，编码器则是简单用一bit位来表示预测结果，所以这个hello_compress是一个简单、低效的压缩器。这里我们简单列举一下高级的模型和编码器：
模型有PPM(Prediction by Partial Matching)、DMC(Dynamic Markov Compression)、CTW(Context Weighting Tree)、CM(Context Mixing)等。
编码器有Shanon-Fano编码、Huffman编码、数字编码、区间编码等。
在后几节我可能会用高效的模型和编码器在实现一个与WinRAR效果相近的压缩器，现在我们先来继续看我们的hello_compress。
在hello_compress中，我们只用了两个字符来存放最近的数据(这两个字符被称为上下文Context)，我们可以增加到3个字符，但是predictor_map也要增加到3维，如果增加到4个字符的话，predictor_map就完全吃不消了，这里我们采用一个策略：减少每个字符的精确度，增加记录字符的个数。改进的程序如下：
// file: hello_compress_improved
#include stdio.h
#include string.h
int main(int argc, char** argv)
{
static char stdin_buffer[65536];
static char stdout_buffer[65536];
static unsigned char predict_map[65536];
unsigned short context = 0;
unsigned char block[8];
unsigned char flag_byte = 0;
int flag_pos = 0;
int block_pos = 0;
int i;
int next_char;
int out_char;
setbuffer(stdin, stdin_buffer, sizeof(stdin_buffer));
setbuffer(stdout, stdout_buffer, sizeof(stdout_buffer));
if(argc == 2 && strcmp(argv[1], "encode") == 0)
{
// compress
while((next_char = getchar()) != EOF)
{
// write to file if a flag_byte is full
if(flag_pos == 8)
{
putchar(flag_byte);
for(i = 0; i block_pos; i++)
{
putchar(block);
}
flag_byte = 0;
flag_pos = 0;
block_pos = 0;
}
// fill a flag byte
if(next_char == predict_map[context])
flag_byte |= (1 flag_pos);
else
block[block_pos++] = next_char;
flag_pos += 1;
predict_map[context] = next_char;
context = (context 4) ^ (next_char & 0xff);
}
// write last block
if(flag_pos 0)
{
putchar(flag_byte);
for(i = 0; i block_pos; i++)
{
putchar(block);
}
}
}
else if(argc == 2 && strcmp(argv[1], "decode") == 0)
{
// decompress
while((next_char = getchar()) != EOF)
{
flag_byte = next_char;
for(i = 0; i 8; i++)
{
if(1 & (flag_byte i))
{
out_char = predict_map[context];
}
else
{
if((next_char = getchar()) != EOF)
out_char = next_char;
else
break;
}
putchar(out_char);
predict_map[context] = out_char;
context = (context 4) ^ (out_char & 0xff);
}
}
}
else
{
fputs("argument: (encode|decode) in.file out.file", stderr);
}
return 0;
}
我们采用位“折叠”的办法，在同样65536个单位里面记录了最近3个半的字符(记录的精度有所降低)，用改进后的程序对EGE的graphics.cpp压缩，可以压到85.4KB，比改进前提高了4.6KB，压缩率为38.8%。看上去似乎改进效果不是很好，但这里我想说明的是，对编码器和预测模型的改进可以达到更好的压缩效果(这个改进的算法其实是PPP传输时候用的压缩算法)。目前好像已经有证明数字编码达到了熵的极限，而预测模型的探索还在不断进行中。这里也顺便说一下，任何算法都是不能对随机数据进行压缩的(因为所有的预测模型都失效了——根本预测不出来)。
这一章就讲到这里，计划下一章讲数字编码，再下一章介绍CM模型并附带一个给力的压缩器，最后一章讲一下LZ系列的字典压缩算法。
楼主 2015-11-19 21:05 回复
Copyright © 2010~2015 直线网 版权所有,All Rights Reserved.沪ICP备10039589号
意见反馈 |
关于直线 |
版权声明 |
会员须知
