差分法求数据压缩

课程设计名称：差分法求数据压缩
题目:一数据文件中存放着若干个8位有符号数（补码），其相邻两数之间差值不超过-8至7。对这种变化缓慢的数据可采用差分方法进行压缩。即第一个数据不变，其后的数据取与前一数据的差值并用4位二进制补码表示，两个差值拼成一个字节，前一个差值放在高4位，后一个差值放在低4位。 例如： 原数据（X[n]）：0x23,0x27,0x2A,0x29,0x22，…… 压缩后（Y[n]）：0x23, 0x43, 0xF9 ，…… 1、编程按上述方法进行压缩，结果保存在另一文件中。 2、能够实现将压缩后的文件解压。

 

虽然是帮同学做一道题目，我还是认真分析了一下的。

首先，考虑测试用的文件。不能用UtraEditor去写16进制文件吧，况且我只知道它能以16进制方式显示文件内容……于是，我用内容为“abcdefghgfedcba”的文本文件作为测试文件。

其次，我分析了一下程序的基本流程。获取参数->读取文件->压缩/解压->写出文件。

 

在获取参数上，我考虑了两种方式。一种是直接用程序启动参数，在main函数参数列表里的。另一种是给用户提示信息，用户输入文件路径并回车确认输入。在使用第二种方式时我用到的C函数是char *fgets(char *s, int n, FILE *stream); 。

char input_file[256] = "";    // 定义保存文件路径的变量

printf("请输入文件路径：");    // 给出提示信息
fgets(input_file,256,stdin); // 读取控制台输入

 

其中stdin指控制台输入。这里还遇到一个问题，input_file获取的值需要trim操作，而C语言对字符传的操作米有trim函数。无奈，从网上拷了一个漂亮的实现。希望拷走的BODY同样用着愉快。

//////////////////////////////////////////////////////
char* trim(char* desc,char* src,char* seps)
{
char* token=NULL;
   /* Establish string and get the first token: */
   token = strtok(src, seps);
   while( token != NULL )
   {
      /* While there are tokens in "string" */
      strcat(desc,token);
      /* Get next token: */
      token = strtok( NULL, seps );
   }
   return desc;
}

 
文件读写用到的C函数是

FILE *stream=fopen(const char *filepath, const char *op);

int i=fgetc(FILE *stream);

int fputc(int i, FILE *stream);

int fclose(FILE *stream);

加入输出缓冲后用到的C函数是

int fwrite(const void* buf, int size, int count, FILE *stream);

缓冲区的实现分为三个步骤：定义缓冲区数组->将数据放到缓冲区->判断缓冲区是否已满（满就输出）->最后判断缓冲区是否为空（空就输出）。

byte buffer[1024];                           // 缓冲区
int index = 0;                                // 缓冲区下标

......

buffer[index] = chout;                  // 将数据放入缓冲区                
index++;                                      // ditto
if(1024 == index) {                      // 判断缓冲区是否已满 
   fwrite(buffer, 1024, 1, fpout);
    index = 0;                                // 清空缓冲区
}

......

if(index != 0) {                             // 判断缓冲区是否为空
    fwrite(buffer, index, 1, fpout);
}

 

这里需要注意的是，fwrite函数是针对内存操作的，一个int数组做缓冲区和一个byte数组做缓冲区是绝对不同的。虽然你写size=1;count=1024，但是对于int数组缓冲区来说只输出来256个数据。。。呵呵，这个地方真的很变态啊！！！

 

对于压缩和解压的算法实现上，我采用最保险的编程，尽量一行代码只操作一个变量。

 

// 压缩
    int ch,chfollow,tmp,chout=5;
    fputc((ch = fgetc(fpin)), fpout); //第一个数据不变
    long fs = filesize(fpin);  
    fputc(fs%2, fpout);    // 保存文件奇偶性
    while((chfollow = fgetc(fpin)) != EOF) {
		tmp = chfollow - ch;   // 计算差值
		if(tmp<0) {   // 将负差转化为正数
			tmp = 8 + (8 - (0 - tmp));
		}
    	if(chout<8 && chout>0){
    		chout = tmp << 4; // 保存高位
	    }else{
    		chout += tmp;  // 保存低位
    		
    		printf("%d ", chout);
			// fputc(chout, fpout);
    		buffer[index] = chout;
    		index++;
    		if(1024 == index) {
		    	fwrite(buffer, 1024, 1, fpout);
		    	index = 0;
		    }
    		
    		chout = 5;
    	}
    	ch = chfollow;
    }
    if(chout>8 || chout==0) {
    	printf("%d ", chout);
    	// fputc(chout, fpout);
    	buffer[index] = chout;
    	index++;
    	fwrite(buffer, index, 1, fpout);
    } else {
    	if(index != 0) {
    		fwrite(buffer, index, 1, fpout);
    	}
    }

 

// 解压
    int flag,ch,chfollow,tmp,chout=0;
    fputc((ch = fgetc(fpin)), fpout);   // 第一个数据不变
    flag = fgetc(fpin);     // 数据奇偶性
    while((chfollow = fgetc(fpin)) != EOF) {
    	printf("%d ", chfollow);
    	tmp = chfollow;
		
		chfollow = chfollow >> 4;  // 还原前一个数据
		chout = add(ch, chfollow);
		
    	buffer[index] = chout;
    	index++;
		
		tmp = tmp & 15;  // 还原后一个数据
		chout = add(chout, tmp);
		
		buffer[index] = chout;
    	index++;
    	
    	if(1024 == index) {
		    fwrite(buffer, 1024, 1, fpout);
		    index = 0;
		}
		
    	ch = chout;
    }
    if(index != 0) {
    	fwrite(buffer, index, 1, fpout);
    }
    if(0 == flag) {  // 根据奇偶性删除
    	fseek(fpout, -1, SEEK_CUR);
    	fputc(EOF, fpout);
    }

对于源文件长度奇偶性的分析可用与解压时对最后一位数据做更加精准的还原，这里不细分析。。。。。。

 

啊啊啊啊啊啊，就此，复习了C的文件读写，将当时Java文件压缩的小项目用C实现了一哈，感脚良好……