本站原创【摘 要】现有通用压缩软件对JPEG文件压缩效果均不佳,本文分析了其原因,提出了应用一种新颖的洗牌算法来对JPEG文件进行预编码,再运用无损压缩工具对文件进行无损压缩,结果表明,这种方法能进一步去除文件内部冗余,减小文件体积.
【关 键 词 】压缩,解压,编码,同父洗牌算法,洗牌算法
0.前言
对于通用无损压缩而言,代表算法是哈夫曼算法、LZ及其衍生算法（LZW, deflate等）,衍生的软件为WinRAR、WinZip,7-zip等,它们的运行流程基本上是一致的,即直接对源文件进行压缩.因源文件中排放的序列的不同而存在一定的冗余度,这种冗余度在不对源文件作规整的前提下是不能去除的.对源文件做出更有效的规整已成为提高压缩比的又一手段.
为了解决以上问题,本文应用一种新颖的洗牌（shuffle）算法-同父洗牌算法（专利号为200810073769.0）,先对JPEG图像文件进行有效规整,再运用无损压缩工具对文件进行无损压缩,达到进一步去除文件内部信息冗余的目的.大量实验表明,这种方法可以在原有压缩比的基础上有效去除1-3%的冗余,且算法简单,易于实现.
1.基于同父洗牌算法的编解码介绍
洗牌( Shuffle)算法的作用是对数据的比特位进行重排, 把比特位的排列变成另一个排列,有多种洗牌函数, 如均匀洗牌、 第 k 个子洗牌、 第 k 个超洗牌等等, 逆洗牌函数将排列变换成原来的排列顺序.
本文应用了一种新颖洗牌算法--同父洗牌算法（专利号为200810073769.0）,顾名思义,如果位于A牌前面一张牌是C牌,位于B牌前面一张牌也是C牌,则定义C牌为A和B牌的父牌.洗牌时,将A牌和B牌按先后出现顺序排列在一起.
这种基于洗牌( Shuffle)算法的编解码我们把它命名为XCS编解码,它基于VC++6.0实现的源代码存于附件中.
下面是结合JPEG文件和同父洗牌算法具体描述.
1.1 洗牌算法原理
对JPEG图像文件进行同父洗牌的规则规整,包括以下步骤：
①以二进制方式读取JPEG图像文件,并对其进行分组；所述分组是从二进制数的第一个比特位开始,一般按每8个比特位为一组,如果不够8位的,则在不够的这组二进制数的前面补0并补够8位.
②将每组二进制代码转换成无符号十进制数,并将第一组二进制代码转换成的无符号十进制数保存于新建数组H中.
由于第一个分组数据转换成的无符号十进制数在0-255之间,为了节省空间,可将该无符号十进制数设定为占用1个字节的空间.
③顺序建立256个数组Ei , i等于0-255；用于存放与i对应的父数据之后的子数据；对于任意两个相邻分组而言,位于前面的分组数据设为父数据,位于后面的分组数据设为子数据.
④按由小到大的顺序遍历转换成的无符号十进制数,将每个父数据后面出现的子数据,存放在步骤③所建立的第i个数组E[i]中,其中i等于父数据,若不存在与i相同的父数据,则该数组E[i]为空.
⑤判断遍历是否结束,若是则统计完成遍历后每个数组的长度,并存放于新建数组G中；若否则继续步骤④.
所述数组G中记录每个数组的长度的元素一般占用4个字节的空间.
⑥将256个Ei数组中的内容依次首尾相连保存于新建数组I中.
⑦将数组H、数组G和数组I中的内容依次首尾相连合并,保存于新建数组J中,数组J即为变换后的JPEG图像文件.
可以看出,变换后的文件比原文件体积大1001字节.
1.2 反洗牌算法
对变换后的JPEG图像文件进行反洗牌,步骤为：
①以二进制方式读取该可逆变换后的JPEG图像文件到新建数组J中,并对其进行数据分组.
所述分组是从第一个比特位开始,一般以每8个比特位为一组.
②将每组数据转换成无符号十进制数,并读取出第一个无符号十进制数存放于新建数组H中；读取出用于存放子数据的数组的长度元素,并将该长度元素依次存放于新建数组G中.
上述读取的规则按压缩时存入数据所占用的空间来顺序读取,即读取数组J中占用1个字节空间的无符号十进制数放入数组H中；读取该无符号十进制数之后的每4个字节为一个元素的数组长度于数组G中.
③顺序建立256个数组Ei , i等于0-255；用于存放与i对应的父数据之后的子数据.
④将数组J中剩余的数据,按数组G中子数据数组的长度分别依次存放于步骤3）建立的数组E[i]中.
⑤建立A数组,将H数组中数据存放于A数组第一个位置.
⑥顺序读取A数组的数据作为父数据,在256个数组群Ei中寻找i等于父数据的数组E[i]中第一个没有已读标志的数据作为子数据,并将该子数据存于A数组中继该父数据之后的下一个空位置,同时将对应数组E[i]中的该子数据的标志位置为已读.
⑦扫描256个数组Ei,并检查其中所有数据的标志位是否全部为已读,若否则继续步骤⑥；若是则停止扫描,将数组A保存为文件,该文件即为原始JPEG图像文件.
1.3流程图如下：
压缩/解压流程图如图1、图2所示
图1 对JPEG图像文件进行洗牌处理的流程图
图2 对解压后的JPEG图像文件进行还原处理的流程图
1.4基于同父洗牌算法的编解码的应用方向
基于同父洗牌算法的编解码能有效地去除文件的冗余,将无损压缩率提升1%~3%,它可以作为其他压缩算法的补充,提升压缩性能.
2.压缩工具简介
为能更好展现XCS编解码对提升压缩效果的作用,此软件采用了DOS系统中的gzip.exe作为压缩程序,tar.exe作为文件夹打包程序.
压缩程序是tar.exe,使用tar.exe程序压缩出来的文件称为gz文件,gz文件的命令通常都是以.gz结尾的.
语法：gzip [选项] 压缩（解压缩）的文件名
命令：
- * 将文件压缩.
- d 将压缩文件解压.
打包程序是tar.exe,使用tar程序打出来的包称为tar包,tar包文件的命令通常都是以.tar结尾的.
语法：tar [主选项+辅选项][文件或者目录]
命令：
- cvf 将文件夹打包.
- xvf 将tar文件解压.
3.发工具简介及系统运行环境
VC++是微软公司开发的一个IDE(集成开发环境),是Windows平台上的C++编程环境,VC++应用程序的开发主要有两种模式,一种是WIN API方式,另一种则是MFC方式,传统的WIN API开发方式比较繁琐,而MFC则是对WIN API再次封装,所以MFC相对于WIN API开发更具备效率优势.由于MFC在软件的开发过程中更为直观,所见即所得,所以我们是使用MFC来编写程序的.
本软件是基于微软的vc++6.0开发的,所以只能在window操作系统下运行.
4.程序设计
我们虽然研究的是JPEG无损压缩,但为提高软件的易用性,软件设计成通用压缩软件,它不但可以压缩JPEG图片,也可以压缩其它文件和文件夹,软件基于VC++6.0的MFC来开发,界面简介,软件功能可以分为两个部分：一、压缩,它可以将文件压出xcs.gz格式的文件,将文件夹打包成tar文件后压出gz格式的文件；二、解压,它可以解压xcs.gz格式、rar格式、zip格式、7z格式.我们把该软件命名为winxcs.exe.
4.1压缩设计
①选取文件或者文件夹.
②判断,文件则进行xcs编码,文件夹则调用tar.exe来打包.
③调用gzip.exe来进行压缩.
4.2解压设计
①选取文件.
②分析文件类型.
③调用相应的解压工具来进行解压.
5.测试数据
样本来源：三星S850分辨率为3264×2448的数码照片
样本数量：10个
对三星S850分辨率为3264×2448的数码照片压缩后的对比：
平均压缩率对比：
6.设计总结
在基于哈夫曼算法、LZ及其衍生算法（LZW, deflate等）来对文件直接进行压缩的方式越来越接近于极限的时候,也就到了去探索数据压缩新道路的时候.对源文件先进行有效的规整再压缩或许会成为提高压缩比的一种尝试,在这次的软件开发中使用了同父洗牌专利算法来对文件进行先规整后压缩,的确可以在压缩率提升一点点,更有效去除冗余.如果规整的算法能得到发展,能更有效、快速的对文件进行规整,那么压缩将能得到很大的发展.也正是基于这种情况,这个项目被列为了教育厅立项项目（NO.200808LX019）.
由于还没有开发出自己的压缩工具,所以只能借用Linux中的压缩工具Gzip.exe和Tar.exe来完成最后的压缩操作,致使软件的功能不是很强大,但也能满足用户的日常解压缩应用.鉴于软件处于内测阶段,未知情况下的应该应该很多,下一步的工作是开发自己的压缩工具,完善软件,但其免费政策永不改变,以使其成为广大电脑用户的福音.
【参考文献】
［１］肖宏伟.门诊 Visual C++开发答疑300问.北京：人民邮电出版社,2003.
［２］周鸣扬.Visual C++界面编程技术.北京:北京希望电子出版社,2003.
［３］吴金平等.Visual C++ 6.0编程与实战.北京:中国水利水电出版社,2004,6.
［４］新浪博客.压缩历史.l.
［５］中国软件.在VC中做一个选择文件夹的对话框.blog.省略/NeptuneX/.