精华内容
下载资源
问答
  • rle压缩解压算法
    千次阅读
    2020-06-09 00:38:52

    4、RLE压缩解压算法
    涉及知识点:文件读写、位操作、内存管理、结构体定义、RLW算法、命令行参数
    要求:
    编写一个程序,可以在命令行输入参数,完成指定文件的压缩解压
    命令行参数如下
    rle file1 –c(-d) file2
    第一个参数为可执行程序名称,第二个参数为原始文件名,第三个参数为压缩或解压缩选项,第四个参数为新文件名

    主体思路如下:
    为了实现RLE算法,我们可以使用 [个数][数据] 的最基本的方式执行,但是,当不重复的数据过多时,比如说ABCDEF,那么文件的长度在压缩后就会增长一倍!所以,我们需要改变策略,同样是使用
    [个数][数据] 的方法,当重复数据个数大于3时,我们才选择将其压缩为[个数][重复数据]的方式,否则使用[个数] ([非重复数据]*个数)来记录数据,这样,至少可以保证非重复数据过多时,文件压缩后不会过大。

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define MAX 65536000
    //储存文件 
    //由于使用的是char来存储数据,char的最大值也就只有255,
    //其中char的首位我们需要用来记录接下来的数据,所以能够记录的最大长度也就只有127
    unsigned char file1[MAX];
    unsigned char file2[MAX];
    
    //判断是否超过3位相同 
    int Judge(unsigned char* src, int left) {
        if (left < 2)
            return 0;
        if (*src == *(src + 1) && *src == *(src + 2))
            return 1;
        return 0;
    }
    
    //不重复时的长度 
    int GetCnt(unsigned char* src, int left) {
        if (left <= 2)
            return left + 1;
        else {
            int cnt = 0,
                leftcnt = left;
            unsigned char* g = src;
            //不存在超3位相同 
            while (Judge(g, leftcnt) == 0) {
                g++;
                leftcnt--;
                cnt++;
                //达到最大长度,直接返回 
                if (cnt >= 128)
                    return cnt;
                if (leftcnt == 0)
                    return cnt + 1;
            }
            return cnt;
        }
    }
    //编码 
    int Encode(unsigned char* src, int srcsize, unsigned char* dst, int dstsize) {
        unsigned char* srcbuf = src;
        unsigned char* dstbuf = dst;
        int srcleft = srcsize - 1;	//剩余数据量
        int dstleft = dstsize;	//剩余储存量
        int cnt = -1;
        int flag = 0;
        while (srcleft >= 0){
            flag = 0;
            cnt = -1;
            if (Judge(srcbuf, srcleft) == 1) {
                //截取重复长度
                while (srcleft >= 0) {
                    if (cnt == 127)
                        break;
                    cnt++;
                    if (*srcbuf == *(srcbuf + 1)) {
                        srcleft--;
                        srcbuf++;
                    }
                    else {
                        if (cnt == 127) {
                            flag = 1;
                        }
                        break;
                    }
                }
    			//首位置1
                *dstbuf = cnt | 128;
                dstbuf++;
                *dstbuf = *srcbuf;
                dstbuf++;
                dstleft -= 2;
    
                if (cnt != 127 || flag == 1) {
                    srcbuf++;
                    srcleft--;
                }
    
            }
            else {
            	//获取不重复片段的长度
                int num = GetCnt(srcbuf, srcleft);
                int i;
                *dstbuf = num - 1;
                dstbuf++;
                for (i = 0; i < num; i++) {
                    *dstbuf = *(srcbuf + i);
                    dstbuf++;
                }
                srcbuf += num;
                srcleft -= num;
                dstleft -= num + 1;
            }
        }
        return dstsize - dstleft;
    }
    //解码 
    int Decode(unsigned char* src, int srcsize, unsigned char* dst, int dstsize) {
        int srcleft = srcsize;
        int dstleft = dstsize;
        int i;
        unsigned char* srcbuf = src;
        unsigned char* dstbuf = dst;
        int  len;
    
        unsigned char tmp;
        while (srcleft >= 0) {
            len = *srcbuf + 1;
            if (len > 129) {
                //重复片段
                tmp = *(srcbuf + 1);
                for (i = 0; i < len - 128; i++) {
                    *dstbuf = tmp;
                    dstbuf++;
                }
                //更新数据
                srcbuf += 2;
                srcleft -= 2;
                dstleft -= len - 128;
    
            }
            else {
    
                srcbuf++;
                for (i = 0; i < len; i++) {
                    *dstbuf = *srcbuf;
                    dstbuf++;
                    srcbuf++;
                }
                srcleft -= 1 + len;
                dstleft -= len;
            }
        }
        return dstsize - dstleft;
    }
    int main(int argc, char** argv) {
        FILE* f1;
        FILE* f2;
        f1 = fopen(argv[1], "rb");
        if(f1 == NULL){
        	printf("ERROR!\n");
        	return 0;
    	}
        int t = 0;
        int a = 0;
        //读取文件 
        while ((a = fgetc(f1)) != EOF) {
            file1[t++] = a;
        }
        f2 = fopen(argv[3], "wb");
        int size = t;
        if( strcmp(argv[2], "-d") == 0){
        	size = Decode(file1, size, file2, MAX);
    	}else{
        	size = Encode(file1, size, file2, MAX);
    	}
    	fwrite(file2, size, sizeof(unsigned char), f2);
        return 0;
    }
    
    更多相关内容
  • RLE压缩解压算法

    2021-07-23 11:21:51
    编写一个程序,可以在命令行输入参数,完成指定文件的压缩解压,命令行参数如下:rle file1 –c(-d) file2 第一个参数为可执行程序名称,第二个参数为原始文件名,第三个参数为压缩或解压缩选项,第四个参数为新...

    题目要求

    编写一个程序,可以在命令行输入参数,完成指定文件的压缩解压,命令行参数如下:rle file1 –c(-d) file2
    第一个参数为可执行程序名称,第二个参数为原始文件名,第三个参数为压缩或解压缩选项,第四个参数为新文件名。

    涉及知识点

    文件读写、位操作、内存管理、结构体定义、RLW 算法、命令行参数

    (一)原题解析

    问题分析
    题目已经提示了要求用 RLE 算法结合位运算来实现解压缩,我们知道所有文件的本质都是二进制文件,这道题需要通过位操作和 RLE 算法直接压缩二进制代码。现在的问题有:

    1. 什么是 RLE 算法?如何用 C 语言实现 RLE 算法?
    2. 如何按照二进制的方式分块读入文件并在文件压缩和解压缩后输出?

    解决方案(思路)
    RLE 算法的本质在于区分连续字节块和非连续字节块,用单独的字节来存储连续字节块和非连续字节块的长度。对于其原理和代码实现,我们一起来看一下。
    对于单个文件,传入文件后通过文件指针每次读入一定数量的字节数据,这些字节数据传入函数进行压缩编码或者解压解码后再把新数据写入指定的新文件。

    算法分析
    根据输入的命令行参数进行对应操作。

    若为压缩操作则将指定要压缩的文件名和要输出的文件名传入 Compression 函数,分别创建两个文件指针指向输入和输出文件,两个申请的内存空间中 inbuf 用于存储待压缩的数据块,outbuf 用于存储待输出的数据块。然后用 fread 函数每次读入定长的字节数,并用 length 记录成功读入的字节数。把读取的字节数 length、指向两块申请的内存空间 inbuf 和 outbuf、存储待输出数据块的数组 outbuf 的大小传入 RLe_Encode 函数进行压缩编码。在 RLe_Encode 函数内建立输入指针 src指向 inbuf。循环遍历 inbuf 数组直到 inbuf 剩余字节为 0。循环时用 IsrepetitionStart函数判断,若连续的三个字节数据相同时则利用 GetRepetitionCount 函数得到重复的个数并将连续字节块和记录连续字节块的字节写入输出数组 outbuf 同时移动数组指针。否则利用 GetNonRepetitionCount 函数得到不重复的个数并逐个写入 outbuf 数组。

    若为解压缩操作则将指定要解压的文件名和要输出的文件名传入 Decompression函数,分别创建两个文件指针指向输入和输出文件。两个申请的内存空间中 inbuf用于存储待解压缩的字节块,outbuf 用于存储待输出的字节块。然后用 fread 函数每次读入定长的字节数,并用 length 记录成功读入的字节数。把读取的字节数length、指向两块申请的内存空间 inbuf 和 outbuf、存储待输出数据块的数组 outbuf的大小传入 RLe_Decode 函数进行解压缩解码。在 RLe_Decode 函数内建立输入指针 src 指向 inbuf,循环遍历 inbuf 数组,若发现连续重复标记则则将标识字节后面的数据重复复制 n 份写入 outbuf。否则说明是非连续数据,将标识字节后面的 n 个数据复制到 outbuf。n 值由存储长度信息的字节块的值确定。

    (二)RLE 压缩算法原理与 C 语言实现

    RLE 算法实现
    RLE 压缩算法(简称 RLE 算法)的基本思路是把数据按照线性序列分成两种情况:一种是连续的重复数据块,另一种是连续的不重复数据块。

    RLE 算法的原理就是用一个表示块数的属性加上一个数据块代表原来连续的若干块数据,从而达到节省存储空间的目的。一般 RLE 算法都选择数据块的长度为 1 字节,表示块数的属性也用 1 字节表示,对于颜色数小于 256 色的图像文件或文本文件,块长度选择 1 字节是比较合适的。

    连续重复数据的处理
    RLE 算法有很多优化和改进的变种算法,这些算法对连续重复数据的处理方式基本上都是一样的。对于连续重复出现的数据,RLE 算法一般用两字节表示原来连续的多字节重复数据。我们用一个例子更直观地说明 RLE 算法对这种情况的处理,假如原始数据有 5 字节的连续数据:

    [data] [data] [data] [data] [data]

    则压缩后的数据就包含块数和 [data] 两字节,其中 [data] 只存储了一次,节省了存储空间:

    [5] [data]

    需要注意的是,一般 RLE 算法都采用插入一个长度属性字节存储连续数据的重复次数,因此能够表达的极大值就是 255 字节,如果连续的相同数据超过 255 字节时,就从第 255 字节处断开,将第 256 字节以及 256 字节后面的数据当成新的数据处理。

    随着 RLE 算法采用的优化方式不同,这个长度属性字节所表达的意义也不同,对于本节给出的这种优化算法,长度属性字节的最高位被用来做一个标志位,只有 7 位用来表示长度。

    连续非重复数据的处理
    对于连续的非重复数据,RLE 算法的处理方法一般是不对数据进行任何处理,直接将原始数据作为压缩后的数据存储。

    假如有以下 5 字节的连续非重复数据:

    [datal] [data2] [data3] [data4] [data5]

    按照这种处理方法,最后的数据和原始数据一样:

    [data1] [data2] [data3] [data4] [data5]

    现在有一个问题。在 RLE 算法解码的时候,如何区分连续重复和非重复数据?解决方法是把连续非重复数据也当成一组数据整体考虑。首先给连续重复数据和连续非重复数据都附加一个表示长度的属性字节,并利用这个长度属性字节的最高位来区分两种情况。

    长度属性字节的最高位如果是 1,则表示后面紧跟的是个重复数据,需要重复的次数由长度属性字节的低 7 位(最大值是 127)表示。长度属性字节的最高位如果是 0,则表示后面紧跟的是非重复数据,长度也由长度属性字节的低 7 位表示。

    采用这种优化方式,压缩后的数据非常有规律,两种类型的数据都从长度属性字节开始,除了标志位的不同,后跟的数据也不同。第一种情况后跟一个字节的重复数据,第二种情况后跟的是若干个字节的连续非重复数据。

    算法实现

    数据压缩的编码过程实现
    原理
    釆用前面给出的优化方式,编码算法不仅要能够识别连续重复数据和连续非重复数据两种情况,还要能够统计出两种情况下数据块的长度。

    编码算法从数据的起始位置开始向后搜索,如果发现后面是重复数据且重复次数超过 2,则设置连续重复数据的标志并继续向后查找,直到找到第一个与之不相同的数据为止,将这个位置记为下次搜索的起始位置,根据位置差计算重复次数,最后长度属性字节以及一个字节的原始重复数据一起写入压缩数据;如果后面数据不是连续重复数据,则继续向后搜索查找连续重复数据,直到发现连续重复的数据且重复次数大于 2 为止,然后设置不重复数据标志,将新位置记为下次搜索的起始位置,最后将长度属性字节写入压缩数据并将原始数据逐字节复制到压缩数据。然后从上一步标记的新的搜索起始位开始,一直重复上面的过程,直到原始数据结束。

    代码及其分析
    代码说明
    Rle_Encode() 函数是 RLE 算法的实现。

    IsRepetitionStart() 函数
    IsRepetitionStart() 函数判断从 src 开始的数据是否是连续重复数据。根据算法要求,只有数据重复出现两次以上才算作连续重复数据,因此IsRepetitionStart() 函数检査连续的 3 字节是否是相同的数据,如果是则判定为出现连续重复数据。之所以要求至少要 3 字节的重复数据才判定为连续重复数据,是为了尽量优化对短重复数据间隔出现时的压缩效率。

    举个例子,对于这样的数据“AABCCD”,如果不采用这个策略,最终的压缩数据应该是 : [0x82][A][0x01][B][0x82][C][0x01][D]

    :此时 A 重复次数为 2,保存长度数据的字节数据为 10000010,开头的 1 表示为重复数据块,转换为十六进制为[0x82]

    压缩后数据长度是 8 字节。如果采用这个策略,则上述数据就被认定为连续非重复数据,会被压缩为: [0x06][A][A][B][C][C][D]

    压缩后数据长度是 7 字节,这样的数据越长,效果越明显。

    GetRepetitionCount() 函数
    如果是连续重复数据,则调用 GetRepetitionCount() 函数计算出连续重复数据的长度,将长度属性字节的最高位置 1 并向输出缓冲区写入一个字节的重复数据,具体做法是将 GetRepetitionCount() 函数的返回值 count|0x80 得到最高位置 1 的长度属性字节。

    GetNonRepetitionCount() 函数
    如果不是连续重复数据,则调用 GetNonRepetitionCount() 函数计算连续非重复数据的长度,将长度属性字节的最高位置 0 并向输出缓冲区复制连续的多个非重复数据。

    数据解压缩的编码过程实现
    代码说明
    Rle_Decode() 函数是解压缩算法的实现代码,每组数据的第一字节是长度标识字节,其最高位是标识位,低 7 位是数据长度属性,根据标识位分别进行处理即可。

    因为两种情况下的压缩数据首部都是 1 字节的长度属性标识,只要根据这个标识判断如何处理就可以了。首先从压缩数据中取出 1 字节的长度属性标识,然后判断是连续重复数据的标识还是连续非重复数据的标识,具体做法是通过位操作,也就是标识字节&0x80 是否等于 0x80 来判断标识字节最高位是否是 1):

    如果是连续重复数据,则将标识字节后面的数据重复复制 n 份写入输出缓冲区;如果是连续非重复数据,则将标识字节后面的 n 个数据复制到输出缓冲区。n 的值是标识字节与 0x7F 做与操作后得到,因为标识字节低 7 位就是数据长度属性。

    具体代码

    方法一

    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    /*编码算法从数据的起始位置开始向后搜索,
    如果发现后面是重复数据且重复次数超过 2,则设置连续重复数据的标志并继续向后查找,
    直到找到第一个与之不相同的数据为止,将这个位置记为下次搜索的起始位置,
    根据位置差计算重复次数,最后长度属性字节以及一个字节的原始重复数据一起写入压缩数据;
    如果后面数据不是连续重复数据,则继续向后搜索查找连续重复数据,
    直到发现连续重复的数据且重复次数大于 2 为止,然后设置不重复数据标志,将新位置记为下次搜索的起始位置,
    最后将长度属性字节写入压缩数据并将原始数据逐字节复制到压缩数据。
    然后从上一步标记的新的搜索起始位开始,一直重复上面的过程,直到原始数据结束。*/
    int IsrepetitionStart(unsigned char *src,int srcLeft){	//判断是否为有重复数超过3的重复数据 
        if(srcLeft<3){	//剩余数据数不足3返回0 
            return 0;
        }
        if((src[0]==src[1])&&(src[1]==src[2])){	
            return 1;
        }
        return 0;
    }
    int  GetRepetitionCount(unsigned char *src,int srcLeft){	//获得重复数据个数 
        int repeatedbuf=src[0];		//repeatedbuf表示重复的值 
        int length=1;	//	长度 
        while(length<srcLeft&&length<0x7f&&src[length]==repeatedbuf){	//长度标识占一字节,高位表示 重复与否,因此length最大为127 
            length++;
        }
        return length;	//返回的length<=127,important 
    }
    int GetNonRepetitionCount(unsigned char *src,int srcLeft){	//获得不重复数据个数 
        if(srcLeft<3){
            return srcLeft;
        }
        int length=2;
        int a=src[0],b=src[1];
        while(length<srcLeft&&length<0x7f&&((a!=b)||(b!=src[length]))){	//三个连续数不全相等 
            a=b;
            b=src[length];
            length++;
        }
        return length;
    }
    int Rle_Encode(unsigned char *inbuf,int inSize,unsigned char *outbuf,int onuBufSize)	//压缩算法,返回压缩后数据大小 
    {	//传入:输入数据缓冲区首地址,输入数据大小, 输出缓冲区首地址, 输出数据大小 
        unsigned char *src=inbuf; //定义指针遍历输入数据 
        int i;
        int encSize=0;	//输出缓冲区大小 
        int srcLeft=inSize;       
        while(srcLeft>0){         
            int count=0;
            if(IsrepetitionStart(src,srcLeft)){ //有重复 
                if((encSize+2)>onuBufSize){	//输出缓冲区空间不够了
                    return -1;
                } 
                count=GetRepetitionCount(src,srcLeft); 
                outbuf[encSize++]=count|0x80;  //按位或运算,保证高位为1,传入输出缓冲区,(即为长度标识)   
                outbuf[encSize++]=*src;    //   即为数据标识      
                src+=count;  //设置新的搜索位置                          
                srcLeft-=count;	//更新剩余数据数
            }
    		else{	//无重复 
                count=GetNonRepetitionCount(src,srcLeft); 
                if((encSize+count+1)>onuBufSize){ 
                    return -1;
                }
                outbuf[encSize++]=count;
                for(i=0;i<count;i++){	//逐个复制这些数据      
                    outbuf[encSize++]=*src++;
                }
                srcLeft-=count;
            }
        }
        return encSize;
    }
    int Rle_Decode(unsigned char *inbuf,int inSize,unsigned char *outbuf,int onuBufSize){	//解压算法 
        unsigned char *src=inbuf;
        int i;
        int decSize=0;	//输出缓冲区大小 
        int count=0;
        while(src<(inbuf+inSize)){
            unsigned char sign=*src++;	//定义指针遍历输入数据 
            int count=sign & 0x7F;	//获取长度标识,按位与运算,保留常量(转换为二进制形式)的后7位数
            if((decSize+count)>onuBufSize){ //输出缓冲区空间不够了
                return -1;	
            }
            if((sign&0x80)==0x80){ //连续重复数据标志         
                for(i=0;i<count;i++){
                    outbuf[decSize++]=*src;
                }
                src++;
            }else{
                for(i=0;i<count;i++){
                    outbuf[decSize++]=*src++;
                }
            }           
        }
        return decSize;
    }
    int Compression(char*Inputfilename,char*Outputfilename){	//文件压缩	
        FILE *Input=fopen(Inputfilename, "rb");	//源文件 
        FILE *Output=fopen(Outputfilename, "wb");	//目标文件 
        if (Input==NULL||Output==NULL){
            printf("We can't open the file successfully!");
        }
        unsigned char*inbuf;	//输入缓存区 
        unsigned char*outbuf;	//输出缓存区 
        inbuf =(unsigned char*)malloc((sizeof(unsigned char))*1024*1024*1024);
        outbuf=(unsigned char*)malloc((sizeof(unsigned char))*1024*1024*1024);
        int length;
        while ((length=fread(inbuf, sizeof(unsigned char),1024,Input))!= 0){	//length表示读入的数据块数目 ,这块用while我不太明白 
                int tmp=Rle_Encode(inbuf,length,outbuf,1024*1024*1024);
                if(tmp==-1){
                    return -2;
                }
                fwrite(outbuf, sizeof(unsigned char),tmp,Output);	//输出缓冲区数据写入目标文件 
        }
        fclose(Input);
        fclose(Output);
    }
    
    int Decompression(char*Inputfilename,char*Outputfilename){	//文件解压 
        FILE *Input=fopen(Inputfilename, "rb");
        FILE *Output=fopen(Outputfilename, "wb");
        if (Input==NULL||Output==NULL){
             printf("We can't open the file successfully!");
        }
        unsigned char*inbuf;	//输入缓存区 
        unsigned char*outbuf;	//输出缓存区 
        inbuf=(unsigned char*)malloc((sizeof(unsigned char))*1024*1024*1024);
        outbuf=(unsigned char*)malloc((sizeof(unsigned char))*1024*1024*1024);
        int length;
        while((length=fread(inbuf, sizeof(unsigned char),1024*1024*1024,Input))!=0){
                int tmp=Rle_Decode(inbuf,length,outbuf,1024*1024*1024);
                if(tmp==-1){
                    return -2;
                }
                fwrite(outbuf, sizeof(unsigned char),tmp,Output);
        }
        fclose(Input);
        fclose(Output);
    }
    int main(int argc,char**argv)
    {
        if(strcmp(argv[2],"-c")==0){
           Compression(argv[1],argv[3]);
        }else if(strcmp(argv[2],"-d")==0){
           Decompression(argv[1],argv[3]);
        }  
        return 0;
    }
    
    

    方法二

    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    int IsRepetitionStart(unsigned char *src,int srcLeft){
    	if(srcLeft<3){	//剩余数据数不足3返回0 
            return 0;
        }
        if((src[0]==src[1])&&(src[1]==src[2])){	
            return 1;
        }
        return 0;
    }
    
    int GetRepetitionCount(unsigned char *src,int srcLeft){//获得重复数据个数
    	int repeatedbuf=src[0];		//repeatedbuf表示重复的值 
        int length=1;	//	长度 
        while(length<srcLeft&&length<0x7f&&src[length]==repeatedbuf){	//长度标识占一字节,高位表示 重复与否,因此length最大为127 
            length++;
        }
        return length;	//返回的length<=127
    } 
    
    int GetNonRepetitionCount(unsigned char *src,int srcLeft){//获得不重复数据个数
    	if(srcLeft<3){
            return srcLeft;
        }
        int length=2;
        int a=src[0],b=src[1];
        while(length<srcLeft&&length<0x7f&&((a!=b)||(b!=src[length]))){	//三个连续数不全相等 
            a=b;
            b=src[length];
            length++;
        }
        return length;
    }
    
    int Rle_Encode(unsigned char *inbuf,int inSize,unsigned char *outbuf,int onuBufSize){
    	unsigned char *src=inbuf;//建立输入指针src指向inbuf
    	int i;
        int encSize=0;	//输出缓冲区大小 
        int srcLeft=inSize;       
        while(srcLeft>0){         
            int count=0;
    		// 使用IsrepetitionStart函数判断是否有重复
            if(IsRepetitionStart(src,srcLeft)){  //有重复 
                if((encSize+2)>onuBufSize){	//输出缓冲区空间不够了
                    return -1;
                } 
                count=GetRepetitionCount(src,srcLeft); //利用GetRepetitionCount函数得到重复的个数并将连续字节块和记录连续字节块的字节写入输出数组outbuf 
                outbuf[encSize++]=count|0x80;  //按位或运算,保证高位为1,传入输出缓冲区,(即为长度标识)   
                outbuf[encSize++]=*src;    //   即为数据标识      
                src+=count;  //设置新的搜索位置                          
                srcLeft-=count;	//更新剩余数据数
            }
    		else{	//无重复 
                count=GetNonRepetitionCount(src,srcLeft); //得到不重复的个数并逐个写入 outbuf 数组
                if((encSize+count+1)>onuBufSize){ 
                    return -1;
                }
                outbuf[encSize++]=count;
                for(i=0;i<count;i++){	//逐个复制这些数据      
                    outbuf[encSize++]=*src++;
                }
                srcLeft-=count;
            }
        }//循环遍历inbuf数组直到inbuf剩余字节为0 
    	return encSize;	
    }//压缩算法 
    
    int Compression(char *filename,char *outfile){
    	FILE *in,*out;//定义指向文件的指针 
    	char now,temp;
    	int filelen=1;//重复出现字符次数 
    	
    	if(!(in=fopen(filename,"rb"))){//以二进制方式打开只读文件
    		printf("文件打开失败\n");//若原文件不存在则进行提示 
    	}else{
    		out=fopen(outfile,"wb");//二进制方式打开只写文件 
    	}
    	
    	int length;//记录成功读入的字节数
    	unsigned char*inbuf;	//存储待压缩的数据块 
        unsigned char*outbuf;	//存储待输出的数据块
        
        inbuf =(unsigned char*)malloc((sizeof(unsigned char))*1024*1024*1024);
        outbuf=(unsigned char*)malloc((sizeof(unsigned char))*1024*1024*1024);//申请开辟内存存储空间 
        
        while((length=fread(inbuf,sizeof(unsigned char),1024,in))!= 0){//用fread函数每次读入定长的字节数
    	    int tmp=Rle_Encode(inbuf,length,outbuf,1024*1024*1024);//将存储待输出数据块的数组outbuf的大小传入RLe_Encode函数进行压缩编码 
    		if(tmp==-1){
    	        return -2;
    	    }
    	    fwrite(outbuf, sizeof(unsigned char),tmp,out);	//输出缓冲区数据写入目标文件
    	}
    	
    	fclose(in);
    	fclose(out);//关闭文件 
    }//文件压缩
    
    int Rle_Decode(unsigned char *inbuf,int inSize,unsigned char *outbuf,int onuBufSize){
    	unsigned char *src=inbuf;
        int i;
        int decSize=0;	//输出缓冲区大小 
        int count=0;
        while(src<(inbuf+inSize)){
            unsigned char sign=*src++;	//定义指针遍历输入数据 
            int count=sign & 0x7F;	//获取长度标识,按位与运算,保留常量(转换为二进制形式)的后7位数
            if((decSize+count)>onuBufSize){ //输出缓冲区空间不够了
                return -1;	
            }
            if((sign&0x80)==0x80){ //连续重复数据标志         
                for(i=0;i<count;i++){
                    outbuf[decSize++]=*src;
                }
                src++;
            }else{
                for(i=0;i<count;i++){
                    outbuf[decSize++]=*src++;
                }
            }           
        }
        return decSize;
    }//解压算法 
    
    int Decompression(char*filename,char*outfile){
    	FILE *in=fopen(filename, "rb");
        FILE *out=fopen(outfile, "wb");
        int length;
        
        if(!(in=fopen(filename,"rb"))){
    		printf("文件打开失败\n");
    	}else{
    		out=fopen(outfile,"wb"); 
    	}
    	
        unsigned char*inbuf;	//输入缓存区 
        unsigned char*outbuf;	//输出缓存区 
        
        inbuf=(unsigned char*)malloc((sizeof(unsigned char))*1024*1024*1024);
        outbuf=(unsigned char*)malloc((sizeof(unsigned char))*1024*1024*1024);
        
        while((length=fread(inbuf, sizeof(unsigned char),1024*1024*1024,in))!=0){
                int tmp=Rle_Decode(inbuf,length,outbuf,1024*1024*1024);
                if(tmp==-1){
                    return -2;
                }
                fwrite(outbuf, sizeof(unsigned char),tmp,out);
        }
        
        fclose(in);
        fclose(out);
    }//文件解压 
    
    int main(int argc,char**argv)
    {
    	if(strcmp(argv[2],"-c")==0){
    		Compression(argv[1],argv[3]);
    	}else if(strcmp(argv[2],"-d")==0){
    		Decompression(argv[1],argv[3]);
    	}
    	
    	return 0;
    }
    

    后记

    代码写过很久了,隐约记得哪个代码好像有一点问题,但是懒得检查了 ,大家可以看解题思路,个人觉得还是写的比较完整的。欢迎指正。

    展开全文
  • RLE压缩解压算法 涉及知识点:文件读写、位操作、内存管理、结构体定义、RLW算法、命令行参数 要求: 编写一个程序,可以在命令行输入参数,完成指定文件的压缩解压 命令行参数如下 rle file1 –c(-d) file2 第一个...

    RLE压缩解压算法

    涉及知识点:文件读写、位操作、内存管理、结构体定义、RLW算法、命令行参数
    要求:
    编写一个程序,可以在命令行输入参数,完成指定文件的压缩解压
    命令行参数如下
    rle file1 –c(-d) file2
    第一个参数为可执行程序名称,第二个参数为原始文件名,第三个参数为压缩或解压缩选项,第四个参数为新文件名

    #include <cstdio>
    #include <cstdlib>
    
    #define T 10000
    #define M 128
    int IsRepeat(const unsigned char *str, int number);
    
    int GetRepeatNumber(const unsigned char *str, int number);
    
    int GetNotRepeatNumber(const unsigned char *str, int number);
    
    int Rle_encode(const unsigned char *str, int ori_num, unsigned char *stm, int cur_num);
    
    int Rle_decode(const unsigned char *str, int ori_num, unsigned char *stm, int cur_num);
    
    unsigned char ori_str[T];
    unsigned char cur_stm[T];
    
    int main(int argc, char ** argv)
    {
        //printf("%d\n", 10);
    
        if (argc != 4) return -1;
        //初始化
        //printf("%d\n", 122);
        FILE *fp ;
        FILE *new_file;
        //printf("%d\n", 222);
        //打开文件
    
        if ((fp = fopen(argv[1], "rb")) == nullptr)
        {
            fprintf(stderr, "Error in opening file %s", argv[1]);
            exit(EXIT_FAILURE);
        }
        if ((new_file = fopen(argv[3], "wb")) == nullptr)
        {
            fprintf(stderr, "Error in opening file %s", argv[3]);
            exit(EXIT_FAILURE);
        }
        //printf("%d\n", 11);
        //读取数据
        int i = 0;
        while (fread(&ori_str[i], sizeof(unsigned char), 1, fp) == 1)
        {
            i++;
        }
    
        //rewind(fp);
    
        /*
        while (ori_str[i] != '\000')
        {
            i++;//?
        }*/
        //printf("%d\n", 12);
    
        //压缩解压缩
        //printf("%c %c", *argv[2], *(argv[2] + 1));
        if (*(argv[2] + 1) == 'c')Rle_encode(ori_str, i, cur_stm, T);
        else if (*(argv[2] + 1) == 'd') Rle_decode(ori_str, i, cur_stm, T);
        else {
            fprintf(stderr, "Error in cmdlet ");
        }
        //写入数据
        //printf("%d\n", 13);
        unsigned int j = 0;
        while (cur_stm[j] != '\000')
        {
            fwrite(&cur_stm[j], sizeof(unsigned char), 1, new_file);
            j++;
        }
        //关闭文件
        if (fclose(fp) != 0 || fclose(new_file) != 0)
        {
            printf("Error in closing file %s or %s\n", argv[1], argv[3]);
        }
        //printf("%d\n", 14);
        return 0;
    }
    //有重复是返回1
    int IsRepeat(const unsigned char *str, int number)
    {
        //小于3认为没有重复
        if (number < 3) return 0;
        if (str[0] == str[1] && str[1] == str[2]) return 1;
        return 0;
    }
    
    int GetRepeatNumber(const unsigned char *str, int number)
    {
        if (number < 3) return 0;
        int j = 0;
        while (str[0] == str[j++] && j <= number && j <= 127);
        return --j;
    }
    
    int GetNotRepeatNumber(const unsigned char *str, int number)
    {
        if (number < 3) return number;
        int k = 0;
        while ((str[k + 1] != str[k + 2] || str[k] != str[k + 1]) && k < number - 2 && k <= 125) k++;
        return k + 2;
    }
    
    int Rle_encode(const unsigned char *str, int ori_num, unsigned char *stm, int cur_num)
    {
        int ori_num_tmp = ori_num;
        int enSize_str = 0;//原数据已参与编码长度
        int enSize_stm = 0;//新数据长度
    
        while (ori_num_tmp - enSize_str > 0)
        {
            //空间不足
            if (cur_num - enSize_stm < 3)
                return -1;
    
            if (IsRepeat(&str[enSize_str], ori_num_tmp - enSize_str))
            {
                int count_repeat = GetRepeatNumber(&str[enSize_str], ori_num_tmp - enSize_str);
                stm[enSize_stm++] = count_repeat;
                stm[enSize_stm++] = str[enSize_str];
                enSize_str += count_repeat;
            }
            else
            {
                int count_not_repeat = GetNotRepeatNumber(&str[enSize_str], ori_num_tmp - enSize_str);
                stm[enSize_stm++] = count_not_repeat + M;
    
                /*if (enSize_stm + count_not_repeat < cur_num)
                    return -1;*///?
    
                while (count_not_repeat--)
                {
                    stm[enSize_stm++] = str[enSize_str++];
                }
            }
        }
        return 0;
    }
    
    int Rle_decode(const unsigned char *str, int ori_num, unsigned char *stm, int cur_num)
    {
        int ori_num_tmp = ori_num;
        int deSize_stm = 0;
        int deSize_str = 0;
    
        while (ori_num_tmp - deSize_str > 0)
        {
            //空间不足
            if (cur_num - deSize_stm < 3)
                return -1;
    
            if (int(str[deSize_str]) > M)
            {
                int i = int(str[deSize_str]) - M;//不重复长度
                while (i--)
                {
                    stm[deSize_stm++] = str[++deSize_str];
                }
                deSize_str++;
            }
            else {
                int k = int(str[deSize_str]);
                while (k--) {
                    stm[deSize_stm++] = str[deSize_str + 1];
                }
                deSize_str += 2;
            }
        }
        return 0;
    }
    /*scanf("%s", ori_str);
    
        int i = 0;
        while (ori_str[i++]);
        i--;
    
        Rle_encode(ori_str, i, cur_stm, T);
    
        int k = 0;
        while (cur_stm[k++]);
        k--;
    
        Rle_decode(cur_stm, k, ori_str, T);
        int j = 10;
        while (j--)
        {
            printf("%c", cur_stm[9 - j]);
        }*/
    

    ps:如有错误敬请指正,欢迎评论区交流或者发私信
    邮箱1654407501@qq.com,QQ号同邮箱

    展开全文
  • RLE压缩解压算法的完整实现

    千次阅读 多人点赞 2020-06-12 18:41:17
    和第四题一样同样是各种东拼西凑的结果,...编写一个程序,可以在命令行输入参数,完成指定文件的压缩解压 命令行参数如下 rle file1 –c(-d) file2 第一个参数为可执行程序名称,第二个参数为原始文件名,第三个参数

    和第四题一样同样是各种东拼西凑的结果,希望对一部分人有帮助。要用的话请至少改一下变量名和函数顺序并且搞懂为什么,不要直接抄袭。在此感谢陈德创大佬的无私帮助以及陈万庆老师提供的音频测试文件
    看之前请先搞懂RLE算法的原理和部分代码实现
    RLE算法原理及C语言实现

    原题:

    涉及知识点:文件读写、位操作、内存管理、结构体定义、RLW算法、命令行参数

    要求:

    编写一个程序,可以在命令行输入参数,完成指定文件的压缩解压

    命令行参数如下

    rle file1 –c(-d) file2
    

    第一个参数为可执行程序名称,第二个参数为原始文件名,第三个参数为压缩或解压缩选项,第四个参数为新文件名

    问题分析

    题目已经提示了要求用RLE算法结合位运算来实现解压缩,经过思考可以知道所有文件的本质都是二进制文件,这道题需要通过位操作和RLE算法直接压缩二进制代码。现在的问题有:

    1.什么是RLE算法?如何用C语言实现RLE算法?

    2.如何按照二进制的方式分块读入文件并在文件压缩和解压缩后输出?

    解决方案(思路)

    RLE算法的本质在于区分连续字节块和非连续字节块,用单独的字节来存储连续字节块和非连续字节块关的长度。对于其原理和代码实现,我在阅读了文档后自己进行了整理并写了一篇博客,链接如下。由于报告的篇幅原因就没有把全文内容附在报告内,后面的内容会直接引用博客中的概念和代码。

    https://blog.csdn.net/zimuzi2019/article/details/106583064

    对于单个文件,传入文件后通过文件指针每次读入一定数量的字节数据,这些字节数据传入函数进行压缩编码或者解压解码后再把新数据写入指定的新文件

    算法分析

    根据输入的命令行参数进行对应操作

    • 若为压缩操作则将指定要压缩的文件名和要输出的文件名传入Compression函数,分别创建两个文件指针指向输入和输出文件,两个申请的内存空间中inbuf用于存储待压缩的数据块,outbuf用于存储待输出的数据块。然后用fread函数每次读入定长的字节数,并用length记录成功读入的字节数。把读取的字节数length,指向两块申请的内存空间inbuf和outbuf,存储待输出数据块的数组outbuf的大小传入RLe_Encode函数进行压缩编码。在RLe_Encode函数内建立输入指针src指向inbuf。循环遍历inbuf数组直到inbuf剩余字节为0。循环时用IsrepetitionStart函数判断,若连续的三个字节数据相同时则利用GetRepetitionCount函数得到重复的个数并将连续字节块和记录连续字节块的字节写入输出数组outbuf同时移动数组指针。否则利用GetNonRepetitionCount函数得到不重复的个数并逐个写入outbuf数组。

    • 若为解压缩操作则将指定要解压的文件名和要输出的文件名传入Decompression函数,分别创建两个文件指针指向输入和输出文件。两个申请的内存空间中inbuf用于存储待解压缩的字节块,outbuf用于存储待输出的字节块。然后用fread函数每次读入定长的字节数,并用length记录成功读入的字节数。把读取的字节数length,指向两块申请的内存空间inbuf和outbuf,存储待输出数据块的数组outbuf的大小传入RLe_Decode函数进行解压缩解码。在RLe_Decode函数内建立输入指针src指向inbuf,循环遍历inbuf数组,若发现连续重复标记则则将标识字节后面的数据重复复制n份写入outbuf。否则说明是非连续数据,将标识字节后面的n个数据复制到outbuf。n值由存储长度信息的字节块的值确定。

    源代码:

    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    int IsrepetitionStart(unsigned char *src,int srcLeft){
        if(srcLeft<3){
            return 0;
        }
        if((src[0]==src[1])&&(src[1]==src[2])){
            return 1;
        }
        return 0;
    }
    
    int  GetRepetitionCount(unsigned char *src,int srcLeft){
        int repeatedbuf=src[0];
        int length=1;
        while(length<srcLeft&&length<0x7f&&src[length]==repeatedbuf){
            length++;
        }
        return length;
    }
    
    int GetNonRepetitionCount(unsigned char *src,int srcLeft){
        if(srcLeft<3){
            return srcLeft;
        }
        int length=2;
        int a=src[0],b=src[1];
        while(length<srcLeft&&length<0x7f&&((a!=b)||(b!=src[length]))){
            a=b;
            b=src[length];
            length++;
        }
        return length;
    }
    
    int Rle_Encode(unsigned char *inbuf,int inSize,unsigned char *outbuf,int onuBufSize)
    {
        unsigned char *src=inbuf; 
        int i;
        int encSize=0;
        int srcLeft=inSize;       
        while(srcLeft>0){         
            int count=0;
            if(IsrepetitionStart(src,srcLeft)){ 
                if((encSize+2)>onuBufSize){      
                    return -1;
                } 
                count=GetRepetitionCount(src,srcLeft); 
                outbuf[encSize++]=count|0x80;          
                outbuf[encSize++]=*src;             
                src+=count;                            
                srcLeft-=count;
            }else{
                count=GetNonRepetitionCount(src,srcLeft); 
                if((encSize+count+1)>onuBufSize){ 
                    return -1;
                }
                outbuf[encSize++]=count;
                for(i=0;i<count;i++){           
                    outbuf[encSize++]=*src++;
                }
                srcLeft-=count;
            }
        }
        return encSize;
    }
    
    int Rle_Decode(unsigned char *inbuf,int inSize,unsigned char *outbuf,int onuBufSize){
        unsigned char *src=inbuf;
        int i;
        int decSize=0;
        int count=0;
        while(src<(inbuf+inSize)){
            unsigned char sign=*src++;
            int count=sign & 0x7F;
            if((decSize+count)>onuBufSize){ 
                return -1;
            }
            if((sign&0x80)==0x80){          
                for(i=0;i<count;i++){
                    outbuf[decSize++]=*src;
                }
                src++;
            }else{
                for(i=0;i<count;i++){
                    outbuf[decSize++]=*src++;
                }
            }           
        }
        return decSize;
    }
    
    int Compression(char*Inputfilename,char*Outputfilename){
        FILE *Input=fopen(Inputfilename, "rb");
        FILE *Output=fopen(Outputfilename, "wb");
        if (Input==NULL||Output==NULL){
             printf("We can't open the file successfully!");
        }
        unsigned char*inbuf;
        unsigned char*outbuf;
        inbuf =(unsigned char*)malloc((sizeof(unsigned char))*1024*1024*1024);
        outbuf=(unsigned char*)malloc((sizeof(unsigned char))*1024*1024*1024);
        int length;
        while ((length=fread(inbuf, sizeof(unsigned char),1024,Input))!= 0){
                int tmp=Rle_Encode(inbuf,length,outbuf,1024*1024*1024);
                if(tmp==-1){
                    return -2;
                }
                fwrite(outbuf, sizeof(unsigned char),tmp,Output);
        }
        fclose(Input);
        fclose(Output);
    }
    
    int Decompression(char*Inputfilename,char*Outputfilename){
        FILE *Input=fopen(Inputfilename, "rb");
        FILE *Output=fopen(Outputfilename, "wb");
        if (Input==NULL||Output==NULL){
             printf("We can't open the file successfully!");
        }
        unsigned char*inbuf;
        unsigned char*outbuf;
        inbuf =(unsigned char*)malloc((sizeof(unsigned char))*1024*1024*1024);
        outbuf=(unsigned char*)malloc((sizeof(unsigned char))*1024*1024*1024);
        int length;
        while((length=fread(inbuf, sizeof(unsigned char),1024*1024*1024,Input))!=0){
                int tmp=Rle_Decode(inbuf,length,outbuf,1024*1024*1024);
                if(tmp==-1){
                    return -2;
                }
                fwrite(outbuf, sizeof(unsigned char),tmp,Output);
        }
        fclose(Input);
        fclose(Output);
    }
    
    int main(int argc,char**argv)
    {
        if(strcmp(argv[2],"-c")==0){
           Compression(argv[1],argv[3]);
        }else if(strcmp(argv[2],"-d")==0){
           Decompression(argv[1],argv[3]);
        }  
        return 0;
    }
    

    测试数据(输入,输出):

    压缩txt文本文件

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    压缩bmp图形文件

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    压缩mp3音频文件(感想陈万庆老师提供的英语听力测试文件!)

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    尝试播放后会发现解压的音频可以正常播放(我听过一遍,确实一样,嗯),和原内容一样
    在这里插入图片描述

    展开全文
  • C语言程序设计之RLE压缩解压算法

    千次阅读 2020-06-08 17:41:58
    先介绍一下RLE压缩算法: 游程编码(Run-Length Encoding, RLE)又称行程长度编码或者变动长度编码法,在控制理论中对于二值图像而言是一种编码方法,对连续的黑,白向像素以不同的码字进行编码。游程编码是一种简单...
  • RLE压缩解压算法 1. 问题描述 编写一个程序,可以在命令行输入参数,完成指定文件的压缩解压,命令行参数如下:rle file1 –c(-d) file2 第一个参数为可执行程序名称,第二个参数为原始文件名,第三个参数为压缩或解...
  • RLE压缩算法

    千次阅读 2021-11-18 10:33:51
    RLE全称(run-length encoding),翻译为游程编码,又译...如图为RLE算法描述 RLE在用于二进制多重复的情况下比较好, 特点是可以做到无损压缩, 但是用于字符多且重复性差的情况下可能做到事倍功半, 比如 ABCDEFG经压缩
  • 本文简要地介绍了什么是RLE压缩算法(行程长度压缩算法)以及解决该算法的两种方法,包括该算法的反演,供大家参考和学习。(含源码及详细讲解)
  • RLE压缩算法C语言实现

    2011-12-03 16:31:37
    RLE压缩算法C语言实现 RLE压缩算法C语言实现 RLE压缩算法C语言实现
  • RLE压缩算法C#详细教程 一、前言 什么是RLE算法 RLE(Run LengthEncoding)行程长度压缩算法是一个简单高效的无损数据压缩算法,其基本思路是把数据看成一个线性序列,而这些数据序列组织方式分成两种情况:一种是...
  • matlab解压代码RLE_Compression_Algorithm Matlab RLE 压缩算法 Matlab RLE 实现(压缩、解压缩)并计算比率。 //压缩文件 首先,您将在 Matlab 中运行此代码并将文件保存在您的路径中。 您调用 Compress('in your ...
  • RLE压缩算法详解

    2021-03-14 11:22:31
    RLE压缩算法(下简称RLE算法)的基本思路是把数据按照线性序列分成两种情况:一种是连续的重复数据块,另一种是连续的不重复数据块。RLE算法的原理就是用一个表示块数的属性加上一个数据块代表原来连续的若干块数据,...
  • C语言课程设计---RLE压缩算法RLE算法的介绍RLE全称(run-length encoding),翻译为游程编码,又译行程长度编码,又称变动长度编码法(run coding),在控制论中对于二值图像而言是一种编码方法,对连续的黑、白像素数...
  • RLE算法压缩解压源代码文件

    热门讨论 2011-11-10 08:06:14
    RLE算法压缩解压源代码文件
  • 西电C语言程序设计实验之RLE压缩算法

    千次阅读 多人点赞 2021-05-27 22:38:31
    RLE压缩解压算法 编写一个程序,可以在命令行输入参数,完成指定文件的压缩解压 命令行参数如下: rle file1 –c(-d) file2 第一个参数为可执行程序名称,第二个参数为原始文件名,第三个参数为压缩或解压缩选项,第...
  • 无损压缩算法专题——RLE算法实现

    千次阅读 2020-01-04 23:16:29
    一、前言 本文是基于我的另一篇博客《无损压缩算法专题——无损压缩算法介绍》的基础上来实现的,RLE算法最简单的理解就是用(重复数,数据值...二、PCX图像文件的RLE压缩方式 如果图像数据有连续相同的值,则用两...
  • 提出了一种直接面向IEEE COMTRADE格式的海量故障录波数据并行压缩解压算法。算法给出了COMTRADE数据文件中时间信息无损恢复公式,提出了针对状态量数据的优化RLE编码。对高频模拟量数据采用提升格式小波变换,用硬...
  • 2.压缩算法RLE算法 RLE算法是使用“数据 * 重复次数”来表示数据的一种方法。比如数据AAAAASSRRR,使用RLE算法表示为:A5S2R3,从10个字节压缩到6个字节。 但这种算法只适用于有重复字节出现的文件,比如图像文件,...
  • 丰富JE的博客,把上大学时候的一个算法,搬过来,大概是2007年07月写的/*闲来无事,写个RLE程序玩玩*/package com.homework.comperssion;import java.io.FileInputStream;import java.io.FileOutputStream;import ...
  • 【前言】 ...由于鄙人知识浅薄,在这里仅分析ZRAM中使用的压缩算法,收集于大神,在这里做总结。 【压缩算法】 查看手机目前收集中支持的ZRAM压缩算法: cat sys/block/zram0/comp_algorithm ...
  • #include #include struct RleNode {  int count;  char ch;  struct RleNode * next;...//压缩字符串 struct RleNode* encode(char *str) {  char *ptr = str;  int num = 1;  int i
  • 突袭游戏PCK工具。。BMP压缩RLE算法
  • 基本压缩解压功能大全.包括Huffuman算法,RLE算法,LZ算法,rice算法,shannon算 法.带有测试文件.
  • 现在市面上的算法资料也五花八门,种类繁多,小编也整理了一份不同于市面且有意思的算法资料,不能说多全面,但是是小编花了很长时间整理归纳出来的,自我感觉还行。分享给同事及群里反响都不错,所以小编打算分享...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 870
精华内容 348
关键字:

rle压缩解压算法