压缩_压缩包解密 - CSDN
  • .tar.gz 格式解压为tar-zxvfxx.tar.gz .tar.bz2格式解压为tar-jxvfxx.tar.bz2

    前言

    Linux常用命令中,有很多用于对文件的压缩或解压,本文将介绍这些解压缩命令中不常见却非常实用的用法。

    tar

    tar是linux中最常用的解压缩命令。tar命令可用于处理后缀名为tar,tar.gz,tgz,.tar.Z,tar.bz2的文件。
    涉及参数说明:

    -c 建立新的压缩文件
    -r 添加文件到已经压缩的文件
    -u 添加改变了和现有的文件到已经存在的压缩文件
    -x 从压缩的文件中提取文件
    -t 显示压缩文件的内容
    -z 支持gzip解压文件
    -j 支持bzip2解压文件
    -v 显示操作过程
    -k 保留源有文件不覆盖
    -C 切换到指定目录
    -f 指定压缩文件
    
    --delete            删除包中文件
    --strip-components  去除目录
    --add-file          向包中添加文件
    

    压缩

    归档tar包,不压缩

    tar -cvf test.tar test1.log test2.log #归档多个文件
    tar -cvf test.tar test/*  #归档test目录下所有文件
    tar -cvf test.tar *.log  #归档所有以.log结尾的文件 
    

    由于这种方式不会进行压缩,仅做了归档,因此速度极快,同时占用空间也较大。

    归档并压缩为tar.gz或tar.bz2

    这种方式打包对文件进行了压缩:

    tar -zcvf test.tar.gz file1 file2 #打包,并以gzip压缩
    tar -jcvf test.tar.bz2 file1 file2 #打包,并以bzip2压缩
    

    查看压缩包中的文件

    如果不想解压,只是想查看压缩包中的文件内容,可以使用-t参数:

    tar -tvf test.tar #可查看test包中有哪些文件
    

    打包后删除源文件

    有时候在打包后可能需要删除源文件,但一个个删除显得麻烦,我们可以使用--remove-files 选项:

    tar -zcvf test.tar.gz test.log --remove-files 
    

    打包除指定目录或文件以外的文件

    对于某些目录下的文件,可能只需要打包部分文件,因此可以使用--exclude选项排除一些不需要打包的文件:

    tar -zcvf test.tar.gz --exclude=test/*.log test/* #打包test目录下所有文件,排除以.log结尾的文件
    

    这里用到了--exclude选项,支持通配符和正则表达式,因此也非常强大。

    向压缩包中更新文件

    例如,压缩包中已经打入了test以及其他文件,现在你只想更新压缩包中的test文件,那么你可以使用--add-file选项:

    tar -tf test.tar --add-file=test #只针对tar包
    

    向tar包中增加文件

    向tar包中增加文件可使用-r参数:

    tar -rf test.tar testfile #在test.tar包中增加文件,只针对tar包
    

    删除压缩包中的文件

    在不解压的情况下,可使用--delete选项删除包中的文件:

    tar --delete -f test.tar  test1 #从test.tar中删除test1文件
    

    解压

    解压tar.gz和tar包到当前目录

    tar -xvf test.tar.gz
    tar -xvf test.tar 
    

    解压到指定目录

    tar -xvf test.tar.gz -C dir
    tar -xvf test.tar -C dir
    

    解压包中指定的文件

    例如test.tar.gz包中文件情况如下:

    1.txt
    log/
    log/1.log
    log/2.log
    log/2.log
    log/4.log
    log/5.log
    

    如果我们只需要解压出log目录下的1.log,只需要执行下面的命令:

    tar -xvf test.tar.gz log/1.log
    tar -xvf test.tar.gz log/1.log -C test #将1.log解压到test目录
    

    解压时去掉目录结构

    压缩包中的文件可能存在多级目录,常规方式解压出来后,对应目录也会存在。如果只想要压缩包的文件,可以去掉目录结构(注意:同一文件夹下文件名不能重):

    tar -xvf test.tar.gz --strip-components=1 #去掉一层目录
    

    解压时不覆盖原文件

    当前目录可能已经存在包中的文件,如果不想解压出来的文件覆盖当前已存在的文件,可使用-k参数(会抛出错误信息):

    tar -xvkf test.tar.gz
    

    特别提醒

    前面所提到的解压或者压缩带的f参数需要放在最后,因为它指定了压缩包名字,否则会出现解压或压缩失败。

    zip/unzip

    zip和unzip命令主要用于处理zip包。

    压缩

    涉及参数说明:

    -d 从压缩文件内删除指定的文件。
    -f 此参数的效果和指定"-u"参数类似,但不仅更新既有文件,如果某些文件原本不存在于压缩文件内,使用本参数会一并将其加入压缩文件中。
    -j 只保存文件名称及其内容,而不存放任何目录名称。
    -r 递归处理,将指定目录下的所有文件和子目录一并处理。
    -u 更换较新的文件到压缩文件内。
    -v 显示指令执行过程或显示版本信息。
    -y 直接保存符号连接,而非该连接所指向的文件,本参数仅在UNIX之类的系统下有效。
    - <压缩效率> 压缩效率是一个介于1-9的数值。
    

    压缩文件

    zip -r test.zip test/ #打包test目录下的文件
    zip -rj test.zip test/ #打包test目录下文件,且压缩包不带test目录
    

    指定压缩率打包文件

    zip -r8 test.zip test/* #数值(1-9)越大,压缩率越高,耗时越长
    

    打包符号链接文件

    前面的命令只能打包普通文件,如果想要打包符号链接文件,则需要使用参数-y:

    zip  -ry test.zip test
    

    向压缩包中增加或更新文件

    有时候需要向压缩包中增加文件,但又不想重新解压打包,可以使用参数-u:

    zip -u test.zip test2 #向test.zip 包中增加test2文件
    

    压缩时加密

    压缩时如果需要对压缩包进行加密,可使用-P参数:

    zip -r test.zip test1 test -P 66666 #使用密码66666加密
    

    删除压缩包的特定文件

    zip -d test.zip test  #删除test.zip包中的test文件
    

    解压

    涉及参数说明:

    -l 显示压缩文件内所包含的文件
    -j 只保存文件名称及其内容,而不存放任何目录名称。
    -o 以压缩文件内拥有最新更改时间的文件为准,将压缩文件的更改时间设成和该
    -v 显示指令执行过程或显示版本信息。
    -d 指定解压目录,目录不存在会创建
    

    查看压缩包中的文件信息

    unzip -l test.zip #可以看到压缩包中的文件名,日期等信息
    unzip -v test.zip #查看更多信息,例如crc校验信息等
    

    解压压缩包

    unzip -o test.zip -d dir #讲test.zip解压到dir目录
    

    解压包中指定的文件

    如果不知道需要解压的文件名,可先查看包中的文件,然后使用下面的方法:

    unzip -o test.zip "1.log" -d dir #解压包中的1.log文件到dir目录
    unzip -o tet.zip "*.log" -d dir  #解压包中所有的log文件
    

    解压时去掉目录结构

    压缩包中有多层目录结构,普通解压仍然会保留目录结构,如果只想要压缩包中的文件,可以使用-j参数:

    zip -oj test.zip -d ./temp  
    

    解压jar包

    jar包是java归档包,但同样可用unzip解压查看里面的文件:

    unzip -o java.jar -d dir
    

    gzip

    涉及参数说明:

    -k 保留源文件
    -d 解开压缩文件
    -r 递归处理,将指定目录下的所有文件及子目录一并处理
    -v 显示指令执行过程
    

    tar命令带有-z参数,并且打包成tar.gz文件时,便调用gzip进行了压缩。gzip对文本的压缩率约有60%~70%,压缩包文件常以gz为后缀。使用-k参数保留源文件:

    gzip -k ./* #当前目录下所有文件进行压缩,每个文件一个gz包
    gzip -rkv ./* 递归压缩
    

    解压也很简单:

    gzip -dv test.gz 
    

    bzip2

    tar命令使用-j参数将文件打包为tar.bz2时,便调用了bzip2进行压缩。bzip2压缩或解压后,会将源文件删除。如果需要保留源文件,可使用-k参数:

    bzip2 -zk test  #压缩test文件
    bzip2 -dk test.bz2  #解压
    

    rar/unrar

    rar和unrar命令并非linux发行版自带命令,需要另外安装。常见用法如下:

    rar a test.tar test  #将test文件压缩为test.tar
    rar e test.rar       #解压test.tar
    unrar x test.rar     #解压test.tar
    

    压缩率比较

    压缩率一般来说:

    tar.bz2>tar.gz>zip>tar
    

    压缩率越高,压缩以及解压的时间也就越长。

    总结

    对文件进行压缩能够节省磁盘空间,进行网络传输时,也能节省带宽,但是需要注意的是,空间和时间是需要根据实际应用进行权衡的。解压缩命令较多,为避免在其他平台使用不便,可选择常用命令进行压缩文件。

     

    展开全文
  • 关键词:5-5-5,5-6-5,游长编码优化,图像压缩、解压 背景有损量化这里介绍从8-8-8到5-5-5和5-6-5的量化压缩原理及其编程实现。无损压缩这里基于游长编码算法(利用像素的重复)首先提出一种简单改进算法,即在图像的...

    关键词:5-5-5,5-6-5,游长编码优化,图像压缩、解压

    背景

    有损量化这里介绍从8-8-8到5-5-5和5-6-5的量化压缩原理及其编程实现。无损压缩这里基于游长编码算法(利用像素的重复)首先提出一种简单改进算法,即在图像的各通道上进行游长编码,利用各通道像素值得重复性分别进行压缩,一定程度上提高了压缩性,因为两个相邻像素虽然不同,但他们的某个通道可能会相同,这种方法简单高效,但适应性差,主要利用了图像的空间冗余性;之后,提出压缩前的分块处理,为了减少图像各区域之间的巨大差异造成的重复性被分割削弱,先从二维上将图像分块,再对分块进行空间冗余压缩,也就是更加充分地利用图像的空间冗余性。

    Giuthub源码:https://github.com/jiangxh1992/QuantisationAndCompression

    English Version:http://jiangxh.top/articles/2016-10/compressionEN


    有损量化5-5-5和5-6-5

    压缩对象使图像的RGB通道值,每个值都是0~255之间的数字,分别使用8位保存,因此原始图像每个像素要使用3*8=24位,即‘8-8-8’。这里要将其量化压缩,使用16位来保存24位的信息,因此要损失部分精度,压缩率固定为1.50。

    这里写图片描述
    这里写图片描述
    这里写图片描述

    5-5-5指的是只使用低15位,剩下的一位弃用,这样每个通道一致的都压缩为5位;

    5-6-5则是充分使用了16位,其中G通道占6位,另外两通道各占5位。

    算法原理很简单:

    压缩时5-5-5是将每个通道的二进制值都右移3位(除以8),保留剩下的5位,然后依次放入16位数的低15位;解压时分别将各通道的5位二进制数取出并左移3位,低位补0还原成8位,因此低三位的数据丢失掉了。

    5-6-6和5-5-5同理,只是G通道的二进制数右移2两位(除以4),将剩下的6位和其他两通道的10位一同放入16位二进制数中。解压时同样是低位补0还原为8位。

    算法代码:

    程序背景说明:widthheight指的是导入的图片的尺寸(像素个数),Input是保存三个通道的像素值的数组,这里windows工程存储的三通道顺序为B,G,R,不是R,G,B。

    这里写图片描述

    5-5-5:

    unsigned char *CAppQuantize::Quantize555(int &qDataSize) {
    
        int i, j ;
        unsigned int r, g, b ;
        unsigned short rgb16 ;
    
        qDataSize = width * height * 2 ;
    
        unsigned char *quantizedImageData = new unsigned char[width * height * 2] ;
    
        for(j = 0; j < height; j++) {
            for(i = 0; i < width; i++) {
                b = pInput[(i + j * width) * 3 + 0] ;   // Blue Color Component
                g = pInput[(i + j * width) * 3 + 1] ;   // Red Color Component
                r = pInput[(i + j * width) * 3 + 2] ;   // Green COlor Component
                rgb16 = ((r >> 3) << 10) | ((g >> 3) << 5) | (b >> 3) ;
                quantizedImageData[(i + j * width) * 2 + 0] = rgb16 & 0xFF ;
                quantizedImageData[(i + j * width) * 2 + 1] = (rgb16 >> 8) & 0xFF ;
            }
        }
    
        return quantizedImageData ;
    }
    void CAppQuantize::Dequantize555(unsigned char *quantizedImageData, unsigned char *unquantizedImageData) {
    
        int i, j ;
        unsigned int r, g, b ;
        unsigned short rgb16 ;
    
        for(j = 0; j < height; j++) {
            for(i = 0; i < width; i++) {
                rgb16 = quantizedImageData[(i + j * width) * 2 + 0] | (((unsigned short) quantizedImageData[(i + j * width) * 2 + 1]) << 8) ;
                b = rgb16 & 0x1F;
                g = (rgb16 >> 5) & 0x1F ;
                r = (rgb16 >> 10) & 0x1F ;
                unquantizedImageData[(i + j * width) * 3 + 0] = (b << 3) ;
                unquantizedImageData[(i + j * width) * 3 + 1] = (g << 3) ;
                unquantizedImageData[(i + j * width) * 3 + 2] = (r << 3) ;
            }
        }
    }

    5-6-5:

    unsigned char *CAppQuantize::Quantize565(int &qDataSize) {
    
        int i, j;
        unsigned int r, g, b;
        unsigned short rgb16;
    
        qDataSize = width * height * 2 ;
        unsigned char *quantizedImageData = new unsigned char[width * height * 2] ;
    
        for (j = 0; j < height; j++) {
            for (i = 0; i < width; i++) {
                b = pInput[(i + j * width) * 3 + 0];    // Blue Color Component
                g = pInput[(i + j * width) * 3 + 1];    // Green Color Component
                r = pInput[(i + j * width) * 3 + 2];    // Red Color Component
                rgb16 = ((r >> 3) << 11) | ((g >> 2) << 5) | (b >> 3); // r分量和b分量右移3位,g分量右移2位
    
                quantizedImageData[(i + j * width) * 2 + 0] = rgb16 & 0xFF; // 高8位
                quantizedImageData[(i + j * width) * 2 + 1] = (rgb16 >> 8) & 0xFF;// 低8位
            }
        }
    
        return quantizedImageData ;
    }
    void CAppQuantize::Dequantize565(unsigned char *quantizedImageData, unsigned char *unquantizedImageData) {
    
        int i, j;
        unsigned int r, g, b;
        unsigned short rgb16;
    
        for (j = 0; j < height; j++) {
            for (i = 0; i < width; i++) {
                rgb16 = quantizedImageData[(i + j * width) * 2 + 0] | (((unsigned short)quantizedImageData[(i + j * width) * 2 + 1]) << 8);
                b = rgb16 & 0x1F;   // 保留高5位
                g = (rgb16 >> 5) & 0x3F;// 右移5位后保留高6位
                r = (rgb16 >> 11) & 0x1F;// 右移11位后保留高5位
                unquantizedImageData[(i + j * width) * 3 + 0] = (b << 3); // 左移3位,高位补0
                unquantizedImageData[(i + j * width) * 3 + 1] = (g << 2); // 左移2位,高位补0
                unquantizedImageData[(i + j * width) * 3 + 2] = (r << 3); // 左移3位,高位补0
            }
        }
    }

    通道游长编码无损压缩

    这里写图片描述

    压缩过程:

    压缩后的数据形式是:两个无符号8位二进制数为一组,第一个存储重复的个数,第二个存储通道值。

    分B,G,R三个通道依次进行,对于每个通道从第一个值开始,计算后面相同的值的个数,碰到新的不同值或者重复个数超出了8位数的表示上限,则将之前的重复值和通道值保存到一组压缩后的数据中,并开始下一组同样的计算压缩,直到所有数据全部压缩完。

    解压过程:

    解压也是分三个通道依次解压,由于三个通道的压缩数据都放在了同一个数组,因此先要找到G通道和R通道的开始位置offset_g和offset_r,寻找方法是循环同时累加计算前面通道各像素的重复个数,每当重复个数达到图片像素个数,下一个即时另一个通道的开始了。之后开始解压,每次从各通道取一个值组成一个像素,直到各通道同时取完,解压后的数据就是压缩前的原数据了,实现了图像的无损压缩。

    算法代码:

    无损压缩:

    unsigned char *CAppCompress::Compress(int &cDataSize) {
    
        unsigned char *compressedData ;
        cDataSize = width * height * 3 ;    
    
        // 存储压缩后的数据,最差的情况尺寸也不会到大于cDataSize * 2
        compressedData = new unsigned char[cDataSize * 2];
        // 实际压缩字符长度
        int compressedSize = 0;
    
        // 采用分通道游离的方法,按照每个通道相邻像素的重复性进行压缩
        // 1.b通道
        unsigned short curB = pInput[0];// 第一个像素的b
        unsigned short repeat = 1;// 重复次数
        for (int i = 1; i < cDataSize / 3; i++)
        {
            unsigned short nextB = pInput[i * 3 + 0];// 下一个像素的b
            if (nextB == curB && repeat < 127)
            {
                ++repeat;
                // 如果是最后一个则存储
                if (i == cDataSize / 3 - 1)
                {
                    // 存储最后一个b值组
                    compressedData[compressedSize] = repeat;
                    compressedData[compressedSize + 1] = curB;
                    // 增加编码数据长度
                    compressedSize += 2;
                }
            }
            else
            {
                // 存储上一个b值组
                compressedData[compressedSize] = repeat;
                compressedData[compressedSize + 1] = curB;
                // 增加编码数据长度
                compressedSize += 2;
                // 换下一种b值
                curB = nextB;
                repeat = 1;
                // 如果是最后一个
                if (i == cDataSize / 3 - 1)
                {
                    // 存储最后一个b值
                    compressedData[compressedSize] = 1;
                    compressedData[compressedSize + 1] = curB;
                    // 增加编码数据长度
                    compressedSize += 2;
                }
            }
        }
    
        // 2.g通道
        unsigned short curG = pInput[1];// 第一个像素的g
        repeat = 1;// 重复次数
        for (int i = 1; i < cDataSize / 3; i++)
        {
            unsigned short nextG = pInput[i * 3 + 1];// 下一个像素的g
            if (nextG == curG && repeat <= 127)
            {
                ++repeat;
                // 如果是最后一个则存储
                if (i == cDataSize / 3 - 1)
                {
                    // 存储最后一个g值组
                    compressedData[compressedSize] = repeat;
                    compressedData[compressedSize + 1] = curG;
                    // 增加编码数据长度
                    compressedSize += 2;
                }
            }
            else
            {
                // 存储上一个g值组
                compressedData[compressedSize] = repeat;
                compressedData[compressedSize + 1] = curG;
                // 增加编码数据长度
                compressedSize += 2;
                // 换下一种g值
                curG = nextG;
                repeat = 1;
                // 如果是最后一个
                if (i == cDataSize / 3 - 1)
                {
                    // 存储最后一个g值
                    compressedData[compressedSize] = 1;
                    compressedData[compressedSize + 1] = curB;
                    // 增加编码数据长度
                    compressedSize += 2;
                }
            }
        }
    
        // 3.r通道
        unsigned short curR = pInput[2];// 第一个像素的r
        repeat = 1;// 重复次数
        for (int i = 1; i < cDataSize / 3; i++)
        {
            unsigned short nextR = pInput[i * 3 + 2];// 下一个像素的r
            if (nextR == curR && repeat <= 127)
            {
                ++repeat;
                // 如果是最后一个则存储
                if (i == cDataSize / 3 - 1)
                {
                    // 存储最后一个g值组
                    compressedData[compressedSize] = repeat;
                    compressedData[compressedSize + 1] = curR;
                    // 增加编码数据长度
                    compressedSize += 2;
                }
            }
            else
            {
                // 存储上一个g值组
                compressedData[compressedSize] = repeat;
                compressedData[compressedSize + 1] = curR;
                // 增加编码数据长度
                compressedSize += 2;
                // 换下一种r值
                curR = nextR;
                repeat = 1;
                // 如果是最后一个
                if (i == cDataSize / 3 - 1)
                {
                    // 存储最后一个r值
                    compressedData[compressedSize] = 1;
                    compressedData[compressedSize + 1] = curR;
                    // 增加编码数据长度
                    compressedSize += 2;
                }
            }
        }
    
        // 取出压缩后的纯数据
        cDataSize = compressedSize;
        unsigned char *finalData = new unsigned char[cDataSize];
        for (int i = 0; i < cDataSize; i++)
        {
            unsigned char temp = compressedData[i];
            finalData[i] = temp;
        }
        delete compressedData;
        compressedData = finalData;
    
        return compressedData;
    }

    无损解压缩:

    void CAppCompress::Decompress(unsigned char *compressedData, int cDataSize, unsigned char *uncompressedData) {
    
        // 寻找g通道和r通道在压缩数据数组中的偏移坐标
        int offset_r = 0, offset_g = 0;
        int pixelCount = 0;
        for (int i = 0; i < cDataSize;)
        {
            int curRpeat = compressedData[i];
            pixelCount += curRpeat;
            i += 2;
            if (pixelCount == width*height)
            {
                offset_g = i;// g通道的开始坐标
            }
            if (pixelCount == width*height * 2)
            {
                offset_r = i;// r通道的开始坐标
            }
        }
    
        unsigned int b, g, r;
        int repeat;
        // 1.还原b通道
        for (int i = 0, j = 0; i < width*height, j < offset_g; j += 2)
        {
            // 恢复一组重复的b值
            repeat = compressedData[j];
            for (int p = 0; p < repeat; p++)
            {
                int d = compressedData[j + 1];
                uncompressedData[i * 3 + p*3 + 0] = compressedData[j + 1];
            }
            i += repeat;
        }
    
        // 2.还原g通道
        for (int i = 0, j = offset_g; i < width*height, j < offset_r; j += 2)
        {
            repeat = compressedData[j];
            for (int p = 0; p < repeat; p++)
            {
                int d = compressedData[j + 1];
                uncompressedData[i * 3 + p * 3 + 1] = compressedData[j + 1];
            }
            i += repeat;
        }
    
        // 3.还原r通道
        for (int i = 0, j = offset_r; i < width*height, j < cDataSize; j += 2)
        {
            repeat = compressedData[j];
            for (int p = 0; p < repeat; p++)
            {
                int d = compressedData[j + 1];
                uncompressedData[i * 3 + p * 3 + 2] = compressedData[j + 1];
            }
            i += repeat;
        }
    }

    效果分析:

    最好情况: 算法基于通道像素重复,最好的情况自然是纯色推图像。算法对于颜色比较单调的图像压缩效果较好;

    最差情况: 最差情况是三个通道相邻的两个像素的值都不同,这时候压缩后的数据刚好是原数据的两倍大小,每一个像素各通道值都额外用了一个8位存储重复个数,且重复个数都是1。

    压缩到六十四分之一:
    这里写图片描述

    压缩到三分之一:
    这里写图片描述

    压缩失败:
    这里写图片描述


    空间分割优化

    算法步骤:首先先后对图像进行横向、纵向或者横向、纵向扫描,扫描时对每一行或者每一列计算平均值,当平均值和上一行或者列差值大于阈值时,设置当前行列为一个边界。例如:如果先横向分割,后纵向分割,那么横向分割后将图像分成了几个子图像,之后再对每一个子图像进行同样的纵向分割,即可将图像分成内部类似的子图像区域。之后再对子图像进行空间冗余性压缩。图像分割效果大致如下:
    这里写图片描述

    示例代码:

    type cpp
    

    量化压缩与无损压缩组合

    直接使用该算法对图像压缩,面对色彩变化丰富的图像总是压缩失败的,但如果先对图像进行有损量化,再对量化后的图像进行无损压缩往往可以取得不错的效果。量化实际上是为无损压缩提高了容错性,本来两个通道值相差可能很小,如果能包容这微小的差异那么将大大提高压缩率。下图中打印的三个压缩率依次是:直接压缩的压缩率、有损量化的压缩率、对量化后的图像再进行无损压缩的压缩率。

    这里写图片描述
    这里写图片描述
    这里写图片描述
    这里写图片描述

    进一步的先进压缩算法

    实际中的图像往往是颜色丰富错综复杂的,仅仅利用空间冗余来进行压缩适应性太低,利用重复性进行游长编码压缩往往不但压缩失败,甚至会使压缩后的图像体积更大,最差的情况如上所说会是原来的两倍。因此为了研究适应性更好的算法就要从更多维度去利用图像本身的重复性(图像的重复性再多维度上是很大的)。

    从另一种程度上图像信息是一种信号信息,图像数据的内在联系不仅仅是相邻像素之间的相似性而已,图像可以向声音信号一样常使用波信号去模拟预测,挖掘图像整体的信息后可以利用已有信息在压缩过程中对未压缩数据进行预测,利用图像的多维度重复性进行进一步的压缩。

    自适应预测熵编码

    。。。

    基于分片的无损压缩方法

    。。。

    展开全文
  • 上节咱们说到影像/栅格数据所占的空间可以通过像元深度和行列数推算出来。...而在绝大多数情况下,影像的数据量都非常大,为了节省磁盘空间就需要把影像数据压缩一下,也就出现了上面所说的大小不等的情况。压缩影像的

          上节咱们说到影像/栅格数据所占的空间可以通过像元深度和行列数推算出来。可是常常遇到的情况是我们在Windows的资源管理器里面看到的影像大小与计算出来的不等,这又是怎么一回事儿呢?

     

          之前我们说到的都叫未压缩大小(Uncompressed Size)。而在绝大多数情况下,影像的数据量都非常大,为了节省磁盘空间就需要把影像数据压缩一下,也就出现了上面所说的大小不等的情况。压缩影像的好处是显而易见的,不仅是节省了磁盘空间,在通过网络传输时也大大节省了带宽,提高了网络服务的性能。但是任何事物都有两面性,影像压缩也不例外。压缩影像是不能够直接在屏幕上显示出来的,都必须经历一个解压缩的过程。一般情况下,影像的压缩比率越大,解压缩的时间也就越长。也就是说,将影像压缩到非常小的时候,虽然节省了空间,但是在使用时会占用非常大的系统资源。要求快速显示的话,对CPU要求是非常高的。

          影像压缩算法分成两种,有损压缩和无损压缩。我们常见的JPEG,JPEG2000都属于有损压缩。而LZ77和Run-Length Encoding(RLE)则是无损压缩。


          这两种压缩有什么区别呢,从有损这个字眼也能够看出来图像会有损失。简单的说就是使用无损压缩的影像能够通过解压缩完全还原到影像压缩前的状态,而有损压缩则会造成影像的失真。

    ArcGIS中支持的压缩类型见下表:


           除了上面列出来的,影像压缩的算法可谓是琳琅满目,层出不穷。在这里一一说明白是不可能的了。所以特找出几个比较典型的压缩类型来简单说说,不涉及算法的代码。内容可能有点枯燥,觉得无聊的可以直接跳到小结部分。

          我们来看看RLE是怎样压缩影像的。

          假使我们有这样一张1bit的黑白影像,B表示1,W表示0。

    WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW

           在使用RLE压缩算法以后,我们得到的就是:

    12W1B12W3B24W1B14W。

           很显然,这种算法并没有改变影像的像元值,也就是进行了无损压缩。但是采用重新编码的方式能够压缩的幅度并不大。

          再来看看最常见的有损压缩JEPG。

          JPEG之所以在日常生活中被广泛的应用,肯定是因为其益处大大的好。好在哪里呢,当然就是其强大的压缩比率。对于一个常见的256色的8bit彩色影像,一般无损压缩能达到的压缩比率为1/2到1/3。但是同样的影像使用jpeg压缩,在保证视觉上无差异的情况下可以达到1/20 至1/40。如果对影像质量要求不高,象是用于缩略图或者索引图,更可以压缩到1/100。举个例子,如果一景影像使用Jpeg压缩,得到的影像大小仅与1/10大小的拇指图所占空间一样,但是这样却不妨碍压缩后的影像显示出比拇指图更多的细节。

          要实现如此大的压缩比率,显然通过编码的方式是行不通的。正如上面提到过的,jepg是保证视觉无差异的情况下进行的压缩。

    先讲个小知识。除了RGB的渲染方式外,颜色也可以通过YCbCr的方式进行渲染,其中Y代表亮度,Cb和Cr则代表色度、饱和度。由于人类的眼睛,至少是绝大多数人的眼睛对亮度的细微变化非常敏感,但是对色彩的改变就没那么在意。所以对一张图片/影像来说,相对Cb和Cr,Y值更重要一些。

    JPEG压缩的原理就是通过余弦变换的方式对Cb和Cr部分取值来增大压缩的程度。具体实现的算法也有很多种,这里就不深入的说了,有兴趣的童鞋可以自行google.


          另外还有一种就是GIS筒子们所喜闻乐见的MrSID格式了。

          这是一种基于离散小波变换的压缩模式,同jpeg2000和ecw格式。原理是将原始图像分割成多个不同分辨率下的小图像,然后再提取其主要信息。为啥专业人员更喜欢它呢,因为即使在1/100的压缩比率下,压缩后的影像仍然能够保证很小的视觉失真。是的,你没有看错,MrSID也会造成数据的损失。即使在较小的(1/20或1/30)的压缩比率下,压缩后的影像看上去完全没有视觉差异,但是像元值与原始数据仍然有差异,所以不建议对MrSID格式的数据进行分析。BUT,对于巨大的卫星影像来说,MrSID的格式仍然被广泛使用。因为MrSID可以实现更高效,压缩比率更大且视觉差异很小的压缩结果(与jpeg的压缩方式相比),而这样是非常方便网络传输的。并且,MrSID压缩与解压缩速度更快一些。

          在ArcGIS的老版本中(9.3和9.3.1),提供了Raster to MrSID的影像压缩功能。在ArcCatalog中一个为压缩大小不超过50M的影像上右键,可以看到这个选项。在ArcGIS 10的版本中,就不再有这个“测试版”的MrSID压缩功能了。但是呢,我们仍然可以借助强大的GDAL来实现大影像的MrSID格式的压缩。

         压缩质量的选择

         在ArcGIS中导出影像成JPEG或者TIFF格式的时候,会发现JPEG压缩还有不同的比例选择,Compression Quality (1-100)。这个值表示了啥呢?首先要说的是,这个数值并不代表压缩大小的比率,也不是保留的信息的比率,只体现了结果数据的质量。简单的说选择的数值越小,压缩的越多,图像质量越差。直观视觉感受见下图。



           另外呢,对于全彩色的影像,建议的最佳的选择是75%。这个值是在看不出差异的标准下能得到的最大的压缩比率。需要注意的一点是,由于jpeg对于亮度的压缩比率很小,和彩色的影像相比较,灰度图的压缩比率就很有限了。在人眼看不出差异的标准下,一般只能压缩10%-25%的大小。

    小结一下

           影像的质量与大小是鱼和熊掌不可兼得矣。如果需要更高的质量,那么就需要更多的磁盘空间。如果需要快速的看到影像,就需要损失一定的影像质量。这两者之间需要有一个取舍。

    经常发生这样一个情况,用作底图的是一个范围很大的数据,但是我们只会查看到某个部分的影像,而不是全图显示。对于这个一框选,就出来的需求我们要如何选择影像的存储格式呢?

          首先,和矢量一样,要通过索引快速定位到要返回的内容,原始影像得有内部分区。这样没有内部分区的JPG格式的就可以pass了。其次,不管是本地还是服务器上的数据,取的数据要小以便传输。这样,我们就需要做压缩。此外,除了影像传输要消耗时间,将压缩后的影像解压缩并显示出来也需要时间。综合上面这两点,建议在单张影像<300M (高程数据<100M)的时候,请一定使用75%jpeg压缩的Tiled Tiff。对于某些单张影像>1G的超大数据,如果只在较大比例尺先预览,可以考虑MrSID。

    最后就是,有损压缩适用于作为矢量背景图的影像,需要快速加载获取的影像。相对的呢,无损压缩适用于需要进行空间分析的影像/栅格,需要推导出新数据的影像/栅格。

     

         如果您对在栅格属性列表中的金字塔,统计值与颜色表(color map)的内容感兴趣,敬请期待在栅格显示与渲染这个部分
    展开全文
  • 写一个对文件进行压缩和解压缩的程序,功能如下: ① 可以对纯英文文档实现压缩和解压; ② 较好的界面程序运行的说明。 介绍哈夫曼: 效率最高的判别树即为哈夫曼树 在计算机数据处理中,霍夫曼编码...

    写一个对文件进行压缩和解压缩的程序,功能如下:

    ① 可以对纯英文文档实现压缩和解压;

    ② 较好的界面程序运行的说明。

     

     

    介绍哈夫曼:

     

    效率最高的判别树即为哈夫曼树

    在计算机数据处理中,霍夫曼编码使用变长编码表对源符号(如文件中的一个字母)进行编码,其中变长编码表是通过一种评估来源符号出现机率的方法得到的,出现机率高的字母使用较短的编码,反之出现机率低的则使用较长的编码,这便使编码之后的字符串的平均长度、期望值降低,从而达到无损压缩数据的目的。

    例如,在英文中,e的出现机率最高,而z的出现概率则最低。当利用霍夫曼编码对一篇英文进行压缩时,e极有可能用一个比特来表示,而z则可能花去25个比特(不是26)。用普通的表示方法时,每个英文字母均占用一个字节,即8个比特。二者相比,e使用了一般编码的1/8的长度,z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算,就可以大幅度提高无损压缩的比例。

    霍夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。树的路径长度是从树根到每一结点的路径长度之和,记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln),N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树,相应的叶结点的路径长度为Li(i=1,2,...n)。可以证明霍夫曼树的WPL是最小的。

     

    文件压缩与解压

    姓名:  范天祚 

    1 程序说明

    1.1数据结构

    哈夫曼树

    1.2函数功能说明

    printfPercent界面

    compress()读取文件内容并加以压缩,将压缩内容写入另一个文档

    uncompress()解压缩文件,并将解压后的内容写入新文件

    1.3 程序编写的思路及流程

    压缩:统计字符出现次数、将节点按出现次数排序、构造哈夫曼树、设置字符编码、读文件字符、按设置好的编码替换字符、写入存储文件

    解压:读取文件各参数、转换成二进制码、按码求对应字符、写入存储文件

    #define _CRT_SECURE_NO_WARNINGS
    #include <stdlib.h>
    #include <stdio.h>
    #include <string.h>
    
    struct head
    {
        int b;						  //字符
        long count;                   //文件中该字符出现的次数
        long parent, lch, rch;        //make a tree
        char bits[256];               //the huffuman code
    };
    
    struct head header[512], tmp;  //节点树
    
    void printfPercent(int per)
    {
    	int i = 0;
    	printf("|");
    	for(i = 0; i < 10; i++)
    	{
    		if(i < per/10)
    			printf(">");
    		else
    			printf("-");
    	}
    	printf("|已完成%d%%\n",per);
    }
    
    //函数:compress()
    //作用:读取文件内容并加以压缩
    //将压缩内容写入另一个文档
    int compress(const char *filename,const char *outputfile)
    {
        char buf[512];
        unsigned char c;
        long i, j, m, n, f;
        long min1, pt1, flength;
        FILE *ifp, *ofp;
    	int per = 10;
        ifp = fopen(filename, "rb");                  //打开原始文件
        if (ifp == NULL)
        {
            printf("打开文件失败:%s\n",filename);
            return 0;                             //如果打开失败,则输出错误信息
        }
        ofp = fopen(outputfile,"wb");                 //打开压缩后存储信息的文件
        if (ofp == NULL)
        {
            printf("打开文件失败:%s\n",outputfile);
            return 0;
        }
        flength = 0;
        while (!feof(ifp))
        {
            fread(&c, 1, 1, ifp);
            header[c].count ++;                       //读文件,统计字符出现次数
            flength ++;                               //记录文件的字符总数
        }
        flength --;
        header[c].count --;
        for (i = 0; i < 512; i ++)                    //HUFFMAN算法中初始节点的设置
        {
            if (header[i].count != 0)
                header[i].b = (unsigned char) i;
            else
                header[i].b = -1;
            header[i].parent = -1;
            header[i].lch = header[i].rch = -1;
        }
    
        for (i = 0; i < 256; i ++)                    //将节点按出现次数排序
        {
            for (j = i + 1; j < 256; j ++)
            {
                if (header[i].count < header[j].count)
                {
                    tmp = header[i];
                    header[i] = header[j];
                    header[j] = tmp;
                }
            }
        }
    
    
        for (i = 0; i < 256; i ++)                    //统计不同字符的数量
    	{
            if (header[i].count == 0)
                break;
    	}
    
        n = i;
        m = 2 * n - 1;
        for (i = n; i < m; i ++)
        {
            min1 = 999999999;
            for (j = 0; j < i; j ++)
            {
                if (header[j].parent != -1) continue;
                if (min1 > header[j].count)
                {
                    pt1 = j;
                    min1 = header[j].count;
                    continue;
                }
            }
            header[i].count = header[pt1].count;
            header[pt1].parent = i;
            header[i].lch = pt1;
            min1 = 999999999;
            for (j = 0; j < i; j ++)
            {
                if (header[j].parent != -1) continue;
                if (min1 > header[j].count)
                {
                    pt1 = j;
                    min1 = header[j].count;
                    continue;
                }
            }
            header[i].count += header[pt1].count;
            header[i].rch = pt1;
            header[pt1].parent = i;
        }
    
        for (i = 0; i < n; i ++)                        //构造HUFFMAN树,设置字符的编码
        {
            f = i;
            header[i].bits[0] = 0;
            while (header[f].parent != -1)
            {
                j = f;
                f = header[f].parent;
                if (header[f].lch == j)
                {
                    j = strlen(header[i].bits);
                    memmove(header[i].bits + 1, header[i].bits, j + 1);
                    header[i].bits[0] = '0';
                }
                else
                {
                    j = strlen(header[i].bits);
                    memmove(header[i].bits + 1, header[i].bits, j + 1);
                    header[i].bits[0] = '1';
                }
            }
        }
    
        //下面的就是读原文件的每一个字符,按照设置好的编码替换文件中的字符
        fseek(ifp, 0, SEEK_SET);                                                //将指针定在文件起始位置
        fseek(ofp, 8, SEEK_SET);                                //以8位二进制数为单位进行读取
        buf[0] = 0;
        f = 0;
        pt1 = 8;
    
    	printf("读取将要压缩的文件:%s\n",filename);
    	printf("当前文件有:%d字符\n",flength);
    	printf("正在压缩\n");
    
        while (!feof(ifp))
        {
            c = fgetc(ifp);
            f ++;
            for (i = 0; i < n; i ++)
            {
                if (c == header[i].b) break;
            }
            strcat(buf, header[i].bits);
            j = strlen(buf);
            c = 0;
            while (j >= 8)                                             //当剩余字符数量不小于8个时
            {
                for (i = 0; i < 8; i ++)                               //按照八位二进制数转化成十进制ASCII码写入文件一次进行压缩
                {
                    if (buf[i] == '1') c = (c << 1) | 1;
                    else c = c << 1;
                }
                fwrite(&c, 1, 1, ofp);
                pt1 ++;
                strcpy(buf, buf + 8);
                j = strlen(buf);
            }
    		if(100 * f/flength > per)
    		{
    			printfPercent(per);
    			per += 10;
    		}
            if (f == flength)
    			break;
        }
    	printfPercent(100);
    
        if (j > 0)                                                      //当剩余字符数量少于8个时
        {
            strcat(buf, "00000000");
            for (i = 0; i < 8; i ++)
            {
                if (buf[i] == '1') c = (c << 1) | 1;
                else c = c << 1;                                        //对不足的位数进行补零
            }
            fwrite(&c, 1, 1, ofp);
            pt1 ++;
        }
        fseek(ofp, 0, SEEK_SET);                                        //将编码信息写入存储文件
    	fwrite(&flength,1,sizeof(flength),ofp);
        fwrite(&pt1, sizeof(long), 1, ofp);
        fseek(ofp, pt1, SEEK_SET);
        fwrite(&n, sizeof(long), 1, ofp);
        for (i = 0; i < n; i ++)
        {
    		tmp = header[i];
    
            fwrite(&(header[i].b), 1, 1, ofp);
    		pt1++;
            c = strlen(header[i].bits);
            fwrite(&c, 1, 1, ofp);
    		pt1++;
            j = strlen(header[i].bits);
    
            if (j % 8 != 0)                                             //当位数不满8时,对该数进行补零操作
            {
                for (f = j % 8; f < 8; f ++)
                    strcat(header[i].bits, "0");
            }
    
            while (header[i].bits[0] != 0)
            {
                c = 0;
                for (j = 0; j < 8; j ++)
                {
                    if (header[i].bits[j] == '1') c = (c << 1) | 1;
                    else c = c << 1;
                }
                strcpy(header[i].bits, header[i].bits + 8);
                fwrite(&c, 1, 1, ofp);                                            //将所得的编码信息写入文件
    			pt1++;
            }
    
    		header[i] = tmp;
        }
        fclose(ifp);
        fclose(ofp);                                                              //关闭文件
    
    	printf("压缩后文件为:%s\n",outputfile);
        printf("压缩后文件有:%d字符\n",pt1 + 4);
    
        return 1;                                       //返回压缩成功信息
    }
    
    
    //函数:uncompress()
    //作用:解压缩文件,并将解压后的内容写入新文件
    int uncompress(const char *filename,const char *outputfile)
    {
        char buf[255], bx[255];
        unsigned char c;
    	char out_filename[512];
        long i, j, m, n, f, p, l;
        long flength;
    	int per = 10;
    	int len = 0;
        FILE *ifp, *ofp;
    	char c_name[512] = {0};
        ifp = fopen(filename, "rb");                                              //打开文件
        if (ifp == NULL)
        {
            return 0;     //若打开失败,则输出错误信息
        }
    
    													  //读取原文件长
    	if(outputfile)
    		strcpy(out_filename,outputfile);
    	else
    		strcpy(out_filename,c_name);
    
        ofp = fopen(out_filename, "wb");                                            //打开文件
        if (ofp == NULL)
        {
            return 0;
        }
    
    	fseek(ifp,0,SEEK_END);
    	len = ftell(ifp);
    	fseek(ifp,0,SEEK_SET);
    
    	printf("将要读取解压的文件:%s\n",filename);
    	printf("当前文件有:%d字符\n",len);
    	printf("正在解压\n");
    
        fread(&flength, sizeof(long), 1, ifp);                                    //读取原文件长
        fread(&f, sizeof(long), 1, ifp);
        fseek(ifp, f, SEEK_SET);
        fread(&n, sizeof(long), 1, ifp);                                          //读取原文件各参数
        for (i = 0; i < n; i ++)                                                  //读取压缩文件内容并转换成二进制码
        {
            fread(&header[i].b, 1, 1, ifp);
            fread(&c, 1, 1, ifp);
            p = (long) c;
            header[i].count = p;
            header[i].bits[0] = 0;
            if (p % 8 > 0) m = p / 8 + 1;
            else m = p / 8;
            for (j = 0; j < m; j ++)
            {
                fread(&c, 1 , 1 , ifp);
                f = c;
                _itoa(f, buf, 2);
                f = strlen(buf);
                for (l = 8; l > f; l --)
                {
                    strcat(header[i].bits, "0");                                  //位数不足,执行补零操作
                }
                strcat(header[i].bits, buf);
            }
            header[i].bits[p] = 0;
        }
    
        for (i = 0; i < n; i ++)
        {
            for (j = i + 1; j < n; j ++)
            {
                if (strlen(header[i].bits) > strlen(header[j].bits))
                {
                    tmp = header[i];
                    header[i] = header[j];
                    header[j] = tmp;
                }
            }
        }
    
        p = strlen(header[n-1].bits);
        fseek(ifp, 8, SEEK_SET);
        m = 0;
        bx[0] = 0;
    
    
        while (1)
        {
            while (strlen(bx) < (unsigned int)p)
            {
                fread(&c, 1, 1, ifp);
                f = c;
                _itoa(f, buf, 2);
                f = strlen(buf);
                for (l = 8; l > f; l --)
                {
                    strcat(bx, "0");
                }
                strcat(bx, buf);
            }
            for (i = 0; i < n; i ++)
            {
                if (memcmp(header[i].bits, bx, header[i].count) == 0) break;
            }
            strcpy(bx, bx + header[i].count);
            c = header[i].b;
            fwrite(&c, 1, 1, ofp);
            m ++;
    
    		if(100 *  m/flength > per)
    		{
    			printfPercent(per);
    			per += 10;
    		}
            if (m == flength) break;
        }
    	printfPercent(100);
    
        fclose(ifp);
        fclose(ofp);
    
    	printf("解压后文件为:%s\n",out_filename);
        printf("解压后文件有:%d字符\n",flength);
    
        return 1;                   //输出成功信息
    }
    
    int main(int argc,const char *argv[])
    {
    	memset(&header,0,sizeof(header));
        memset(&tmp,0,sizeof(tmp));
    
    	compress("测试文档.txt","测试文档.txt.zip");
    	uncompress("测试文档.txt.zip","测试文档.txt 解压后.txt");
    	system("pause");
    
    	return 0;
    }
    

     

    2 功能展示

    2.1 控制台显示

    2.2 文件效果

    开始时只有一个文件《测试文档.txt》:

    打开《测试文档.txt》

    《测试文档.txt》文件大小:

    程序运行结束后多了两个文件:

    以文本形式打开压缩二进制文件《测试文档.txt.zip》:

    《测试文档.txt.zip》文件属性:

    展开全文
  • 无损压缩经典算法

    2019-10-30 11:50:00
    @前言总结经典的文件压缩算法原理,主要包括:哈夫曼压缩算法及其延伸,LZ77算法及其演变算法,LZ78算法及其演变算法,几何编码算法Arithmetic Coding。内容部分摘录翻译自港大‘多媒体技术’硕士课程1.进行文件压缩...

    @前言

    总结经典的文件压缩算法原理,主要包括:哈夫曼压缩算法及其延伸,LZ77算法及其演变算法,LZ78算法及其演变算法,几何编码算法Arithmetic Coding。


    1.进行文件压缩的必要性

    像图片、声音、视频这些类型的多媒体数据要比文本数据占用多得多的内存空间,尤其是视频文件,文件传输时占用带宽大,存储又占用大量的硬盘空间。

    举个例子:一个1080p分辨率格式下90分钟的无压缩视频要多大?

    1帧大小 = 1920 x 1080 x 3 = 6220800 bytes (1920x1080是每一帧的像素数,3指的是每个像素红绿蓝三个通道各占一个字节0~256)

    ***每秒大小 = 6220800 x 25 = 155.52MB!***(假设帧率为每秒25帧,很小了!)

    每分钟大小 = 155.52MB x 60 = 9.3312GB!

    90分钟:大约839.81GB

    存储高清视频的蓝光光碟容量不过只有大约50GB,所以视频如果不压缩根本没法存储,更不用说互相传送了。

    2.简单黑白图像的压缩

    假设黑白图像的数据如下图,黑色像素用1编码,白色图像用0编码:

    这里写图片描述

    黑白图像的尺寸为16x8 = 128,因此需要128bits来表示它。

    如果我们从0开始算起,只保存一些列0和1的个数,那么上面的图像信息可以表示为:

    21 6 9 1 5 2 8 1 3 2 1 1 8 1 2 2 2 1 8 6 21

    其中最大的数字是21,所以可以统一使用5bits(2^5=32)来表示每一个数字,那么现在的存储空间变为5x21=105bits,节省了23bits。

    3.字符串行程编码

    和上面黑白图像压缩一样的道理,这里压缩一段字符串:RRRRRGGGBBBBBRRRRGB

    压缩的结果为:5R3G5B4R1G1B

    这种方法叫做行程编码run-ength encoding(RLE),应用于像BMP,TIFF格式的图像文件中。

    但这种压缩编码方式很有局限性,我们无法继续用相同的方法进一步压缩压缩后的数据,比如上面的压缩结果无法继续用这种方法压缩,这种压缩基于数据的重复性。

    4.信息的可压缩性-信息量和信息熵

    信息量

    数据的压缩水平和数据的信息量有关,信息量越大自然数据量越大越难以压缩。数据的信息量如何来衡量呢?

    例子:假设有一个64位的字符串,64个数字,其中63个0,另一个是1,1可能出现在任意位置,也就是在某个位置的概率为1/64。现在从左往右读取知道找到1。(注意下表是找到1之前的概率,当找到1之后,之后的符号确定不可能再出现1了,因此P(bi=1)变为0,P(bi=0)变为1)

    对于在位置i的符号bi,bi为0或者为1的概率分布如下:
    这里写图片描述

    事实上,一个符号的概率越大,那么它包含的信息就越小,也就是信息量和符号出现的概率成反比,信息量的定义为:
    h(x)=log21p(x)h(x)=log_2\frac{1}{p(x)}

    计算对应的符号信息量表:
    这里写图片描述

    信息量计算:如果1位于第4个位置:000100…0,则总的信息量为:

    Sum = 0.0227 + 0.023 + 0.0235 + 5.9307 = 6

    通用公式:

    n=1ih(bn)=(m=66i64log2mm1+log211/(651))=log2((m=66i64mm1)(65i))=6\sum_{n=1}^ih(b_n)=(\sum_{m=66-i}^{64}log_2\frac{m}{m-1} +log_2\frac{1}{1/(65-1)}) = log_2((\prod_{m=66-i}^{64}\frac{m}{m-1}) (65-i)) = 6

    每个字符信息量的和表示了整个字符串的信息量,这里至少需要6位来表示这个字符串,要保存的是公式中的索引(0~63)。

    信息熵

    数据的压缩实际是用更短的数据来表示反复出现的数据实现压缩,因此数据重复率越高或者可预测性越强可压缩性就越高,不同数据可压缩的程度不一样,信息熵是用来衡量数据可压缩的程度的一个参数,计算信息最短的长度的期望,关于信息熵:http://www.ruanyifeng.com/blog/2014/09/information-entropy.html

    上面能精确计算信息量是因为我们知道了字符串的具体结构,对于未知的信息我们只能根据概率计算其信息量的期望,计算公式为:

    H(X)=iP(xi)h(xi)H(X) = \sum_{i}P(x_i)h(x_i)

    最差的情况是当所有符号的概率都相同,概率均匀分布,此时信息熵为最大值,因为对于一个子串,根本无法预测下一个符号。

    5.对编码算法的要求

    1. 通过编码后的编码必须可以准确解码,编码必须确定地对应一种原码;
    2. 编码算法得到的编码要容易解码,可以很容易的找到信息的末尾,可以在线解码,可以直接对编码进行解码而不用知道完整的编码信息;
    3. 编码必须是压缩的,否则失去了编码的意义;

    6.哈夫曼编码

    哈夫曼编码是David A. Huffman于1952年发明的一种满足上面对编码算法要求的一种编码算法。

    举一个例子:知道一段字符串全部由a,b,c,d,e五个字母组成,已知了每个字母出现的频率:

    a(0.25),b(0.25),c(0.2),d(0.15),e(0.15)

    【如果不考虑编码算法,使用定长的编码来区别五个字母,不利用频率这些信息,那么五个字母每个字母需要用3bits表示(22=4,23=8).】

    哈夫曼算法是利用频率信息构造一棵二叉树,频率高的离根节点近(编码长度短),频率低的离根节点远(编码长度长),手动构造方法是先将字母按照频率从小到大排序,然后不断选择当前还没有父节点的节点中权值最小的两个,构造新的父节点,父节点的值为这两个节点值的和,直到构造成一棵二叉树,上面的例子构造的Y一棵哈弗曼树如下(由于构造过程中叶子节点的值以及新节点的值可能会相同,所以哈弗曼树的结构不唯一):

    这里写图片描述

    对构造的哈弗曼二叉树进行编码,左边为0,右边为1,就得到一个编码的哈弗曼树,从而对字符串进行编码。

    哈夫曼算法C++实现,使用线性数组存储节点的方式实现,输入上面每个字母的权值可以得到哈弗曼树结构:

    #include <iostream>
    using namespace std;
    
    #define n 5         // 字符个数(叶子个数)
    #define m 2*(n)-1   // 总节点数:1+2+4+8+...+n
    
    typedef struct{
        double weight;   // 节点权重
        int lchild;      // 左子树
        int rchild;      // 右子树
        int parent;      // 父节点
    }HTNODE;
    
    typedef HTNODE HuffmanT[m];  // 一棵线性结构存储的哈弗曼树
        
    /**
     * 哈弗曼树初始化
     */
    void InitHT(HuffmanT T)
    {
        for(int i=0; i<m; i++)
        {
            T[i].lchild=-1;
            T[i].rchild=-1;
            T[i].parent=-1;
        }
        // 依次输入每个节点的权重
        for(int i=0; i<n; i++)
            std::cin>>T[i].weight;
    }
    
    /**
     * 找出还没有父节点的节点中权值最小的两个,p1和p2是要选出的权值最小的两个节点的下标,n1是新父节点的下标
     */
    void SelectMin(HuffmanT T, int n1, int &p1, int &p2)
    {
        int i, j;
        // 先任意找两个没有父节点的节点
        for(i=0; i<n1; i++)
            if(T[i].parent==-1)
            {
                p1=i;
                break;
            }
        for(j=i+1; j<n1;j++)
            if(T[j].parent==-1)
            {
                p2=j;
                break;
            }
        // 搜索替换成权值最小的节点
        for(i=0; i<n1; i++)
            if((T[p1].weight>T[i].weight) && (T[i].parent==-1) && (p2!=i))
                p1=i;
        for(i=0; i<n1; i++)
            if((T[p2].weight>T[i].weight) && (T[i].parent==-1) && (p1!=i))
                p2=i;
        
    }
    /**
     * 构造哈弗曼树
     */
    void CreatHT(HuffmanT T)
    {
        int i, p1, p2;
        InitHT(T);
        // 非叶子节点
        for(i=n; i<m; i++)
        {
            // 找出还没有父节点的节点中权值最小的两个
            SelectMin(T, i, p1, p2);
            T[p1].parent=T[p2].parent=i;
            T[i].lchild=p1;
            T[i].rchild=p2;
            T[i].weight=T[p1].weight+T[p2].weight;
        }
    }
    
    /**
     * 打印哈弗曼树
     */
    void printHT(HuffmanT T)
    {
        for(int i=0; i<m; i++)
        {
            std::cout<<T[i].weight<<'\t'<<T[i].parent<<'\t'<<T[i].rchild<<'\t'<<T[i].lchild<<std::endl;
        }
    }
    
    /**
     * 前台测试
     */
    int main(){
        HuffmanT T;
        CreatHT(T);
        printHT(T);
        return 0;
    }
    

    缩减的哈夫曼算法

    哈夫曼编码的缩减实质是对编码字符分组继续进行子分组内编码。先将所有字符按照出现的概率排序,将概率相近的字符作为一个整体参与上一级的编码,这样上一级的编码数量大大减少,分组内继续进行内部哈夫曼编码,同时在上一级中本组的编码作为组内编码的一个固定的前缀。

    这里写图片描述

    Shift Coding

    和缩减的思想类似,将字符按照频率8个一组分块,每到下一块在前面加111进行区分后继续进行3bit的编码。

    这里写图片描述

    7.Lempel-Ziv压缩算法

    LZ算法及其衍生变形算法是压缩算法的一个系列。LZ77和LZ78算法分别在1977年和1978年被创造出来。虽然他们名字差不多,但是算法方法完全不同。这一系列算法主要适用于字母数量有限的信息,比如文字、源码等。流行的GIF和PNG格式的图像,使用颜色数量有限的颜色空间,其压缩就采用了两种算法的灵活变形应用。

    LZ77:

    推荐阅读文章:

    LZ77压缩算法编码原理详解(结合图片和简单代码)

    LZ77算法原理及实现

    LZ77算法的思想是在编码解码过程中,使用之前刚结束编解码的部分数据的位置索引来代替当前要编解码的数据,压缩的实现靠的是之前编解码结束的部分数据和当前数据的重复性。

    算法中几个重要的对象概念:

    LAB(look-ahead-buffer):将要编码的固定长度的数据缓冲;

    SB(search-buffer):刚过去的固定长度的数据缓冲,搜索缓冲区,也就是临时的数据字典,要从这里面搜索重复数据获得压缩索引;

    Cursor:一个指针,指的是SB和LAB缓冲之间的边界处

    **Token(p,l,c)**编码的结果:

    • p: 第一个数字指的是SB中开始匹配的位置,注意是从Cursor往前倒着数,从1开始数
    • l: 第二个数字指的是匹配成功的字符个数;
    • c: 第三个指的是LAB中匹配结束的下一个字符;

    ***注意:***在匹配时是搜索字典中最长的匹配,且当前的LAB区域如果继续匹配也继续搜索(比如匹配到SB的最后一个字符后下一个到LAB的第一个字符仍然匹配则继续,直到不匹配或匹配数达到了LAB的长度限制则停止。如果在SB中一个都不匹配则不继续搜索,排除LAB第一个字符自身无尽循环匹配的情况)。

    示例:

    字符串“aacaacabcabaaac”的一个LZ77编码示例,其中缓冲长度分别为:LAB=4,SB=6

    这里写图片描述

    LZ77的变形

    ***LZR:***就是SB搜索缓冲的长度不固定了,算法输出的token位长度也是可变的。

    ***LZH:***算法的输出结果又进行了哈夫曼编压缩。

    ***DEFLATE:***当前最流行的基于LZ77的压缩算法,是很多通用的Unix压缩项目‘gzip’的一部分。

    LZ78:

    算法是将编码过程中之前编码过的所有字符作为了一个索引字典,之前的每一次编码是一个字典元素,之后的编码如果包含之前字典的元素则用该元素的索引代替实现压缩(注意是从之前的字典元素中找那个匹配最长的字典元素),同时记录不匹配的那个字符。可以想到,不断更新的字典中最长的字典元素很可能会越来越长且每次长一个字符。

    ***示例:***对字符串“abacbabaccbabbaca“进行LZ78编码。
    这里写图片描述

    LZ78的变形算法

    上面说到LZ78的最长的字典元素只会越来越长不受限制,那么就要使用变长的bit空间来保存字典索引,当前字典的需要保存索引的空间大小为$log2 (i)$ bits, $i$为目前字典中最长字典元素的长度。

    LZC

    算法给字典元素的长度设置一个最大值,如果匹配的结果超出最大值时就选择上一个相对较短的匹配的字典元素,防止字典元素变得太长。如果编码压缩率受限制变得太小,就清空之前的字典,比如重新开始压缩算法。

    LZW

    和LZ78不同的是,算法开始不是空的字典,一开始就把可能的所有单一字符作为最开始的字典,另外不是和LZ78那样记录字典索引和不匹配字符,而是只记录匹配的字典索引(不可能出现不匹配的情况,至少匹配一个字符了)。

    ***示例:***对字符串“abacbabaccbabbaca”进行LZW编码:
    这里写图片描述

    算术编码

    算数编码是考虑到解决哈夫曼编码的一个限制:对于信息的编码,要对每一个字符都要使用一个几个二进制的bit数区别表示,收到整体的影响,平均每个字符可能都要用不少的bit数空间来表示。
    算术编码是将编码的消息表示成实数0和1之间的一个间隔,消息越长,编码表示它的间隔就越小,形成结合越来越紧密的编码,同时需要表示的二进制位数就越多,导致算数编码的最大问题就是计算机的精度问题,精度有限,正常情况下无法进行大量数据的编码,事实上只能编码很短的数据。后来有了其他的先进方法才使算术编码得到应用,具体参考算数编码文章链接。

    推荐阅读:算术编码

    展开全文
  • 文件的压缩压缩

    2018-09-10 19:12:15
    背景:看到文件压缩gzip,bzip2。脑子一热,想到能不能再次压缩文件?没有百度到,想要的答案,自己费事来try try。 看不懂的知识:https://blog.csdn.net/xuchuangqi/article/details/52939705 gzip 对于要压缩...
  • ZIP是一种较为常见的压缩形式,在Java中要想实现ZIP的压缩需要导入java.util.zip包,可以使用此包中的ZipFile、ZipOutputStream、ZipInputStream、ZipEntry几个类完成。在JAVA IO中,不仅可以实现ZIP压缩格式的输入...
  • 最近自己实现了一个ZIP压缩数据的解压程序,觉得有必要把ZIP压缩格式进行一下详细总结,数据压缩是一门通信原理和计算机科学都会涉及到的学科,在通信原理中,一般称为信源编码,在计算机科学里,一般称为数据压缩,...
  • 压缩的好处和坏处

    2020-05-29 15:33:23
    1. 压缩的好处和坏处 压缩技术分为有损和无损:大数据场景下我们用到的都是无损;不允许丢失数据 好处 减少存储磁盘空间 降低IO(网络的IO和磁盘的IO) 加快数据在磁盘和网络中的传输速度,从而提高系统的...
  • 几种压缩算法

    2018-01-24 16:37:34
    一、 行程长度压缩  原理是将一扫描行中的颜色值相同的相邻像素用一个计数值和那些像素的颜色值来代替。 例如:aaabccccccddeee,则可用3a1b6c2d3e来代替。对于拥有大面积,相同颜色区域的图像, 用RLE压缩方法...
  • 1,zip压缩工具。 zip的压缩包在windows和linux中都比较常用,它可以压缩目录和文件,压缩时录时,需要指定目录下的文件。zip后面先跟目标文件名,即压缩后得自定义压缩包名,然后跟要压缩的文件或目录。没有该命令...
  • 一、压缩列表概述  压缩列表是一种编码过的“链表”旨在实现高效的内存管理。它可以存储整数和字符串,整数以小端序存储,字符串则以字节数组存储。压缩列表的内存存储结构如下图所示:  其中zlbytes、zltail...
  • 一、gzip压缩技术 gzip(GNU- ZIP)是一种压缩技术。经过gzip压缩后页面大小可以变为原来的30%甚至更小,这样,用户浏览页面的时候速度会快得多。gzip的压缩页面需要浏览器和服务器双方都支持,实际上就是服务器端...
  • 对于我们这种资料特别多,随时都需要跟工作伙伴沟通传递资料的人来说,一款方便的压缩软件真的太重要了,不仅可以节省时间,节省内存,更重要的是提高工作效率,今天废鱼就给大家推荐几款常用压缩软件。 The ...
  • 在网上调查了图片压缩的方法并实装后,大致上可以认为有两类压缩:质量压缩(不改变图片的尺寸)和尺寸压缩(相当于是像素上的压缩);质量压缩一般可用于上传大图前的处理,这样就可以节省一定的流量,毕竟现在的...
  • 打包是指将多个文件或者目录放在一起,形成一个总的包,这样便于保存和传输,但是大小是没有变化的,压缩是指将一个或者多个大文件或者目录通过压缩算法是文件的体积变小以达到压缩的目的,可以节省存储空间,在压缩...
  • 一、打包的概念  打包:指将多个文件(或目录)合并成一个文件,方便在不同节点... Linux系统一般文件的扩展名用途不大,但是压缩或打包文件的扩展名时必须的,因为linux支持的压缩命令较多,不同的压缩技术使...
  • 哈夫曼压缩与解压缩

    2019-06-13 00:24:05
    哈夫曼压缩与解压缩 目录 哈夫曼压缩与解压缩 一:引言 二:主要技术点 三:过程介绍 1、压缩: 2、解压缩 四:详细分析 一:准备过程 二:压缩 三:解压缩 五:结果演示 六:总结 七:源码地址 一:...
  • java高清无损图片压缩

    2019-03-29 22:46:57
    Java高清无损图片压缩 (本文禁止转载,如需转载请联系本人:微信/QQ同号:969987665)简单介绍thumbnailator-0.4.5.jar 官方下载网址语法使用(超级简单的,再也没有比这个再简单的东西)一、保持和原图像一样的宽高...
  • Java解压缩zip - 多个文件(包括文件夹) 对多个文件和文件夹进行压缩,对复杂的文件目录进行解压。 压缩方法使用的是可变参数,可以压缩1到多个文件..可以写数组的方式或者一个个写到参数列表里面... ZipFiles(zip...
1 2 3 4 5 ... 20
收藏数 1,161,528
精华内容 464,611
关键字:

压缩