java的第四个程序—漏洞百出的压缩
在过年之前，先总结一下，自己第一次写的，漏洞百出的压缩。相对来说，Huffman压缩的流程比较多。
压缩步骤：
1．读取原文件。
2．统计文件中每个字节出现的次数，存于Map<Byte, Integer>中。
3．根据每个字节的次数，构建Huffman树，得到每个字节对应的编码，存于Map<Byte,String>中。
4．根据Map<Byte, String>，将原文件的字节转化成0、1码。
5．将步骤4中得到的0、1码，每8位转换成一位十进制字节。最后0、1剩余不足8位时，则通过补0补满8位。在末尾添加一位，说明最后一位十进制对应的0、1二进制，实际有几位。
6．将Map<Byte, String>和步骤5得到的字节，写入文件中，得到压缩文件。
解压缩：
1.读压缩文件，先读取Map< String, Byte >，再读取压缩的源文件。
2.将压缩的源文件转换为0、1二进制。
3.根据Map< String, Byte >，将0、1二进制转换为对应的字节。
4.将步骤4得到的字节写入文件，即解压后的文件。
解压缩等同于顺序相反地执行压缩。
本程序的缺陷（只能压缩100k以内的文件，否则速度特别慢）：
1.处理字节数组，这对大容量文件来说，肯定会数组越界。
解决方法：避免将内容全部存于数组来处理。
压缩：
1.1读文件时，读两遍。第一遍，得到Map<字节，出现的次数>。
1.2第二遍读原文件，读一个字节，根据Huffman得到的Map<字节，对应编码>，转换成0、1编码，满8位0、1码就转换为一个字节，写入压缩文件。
解压缩：
1.3读压缩文件的一个字节，转换为8位0、1码，根据Map<对应编码, 字节>,查找是否有对应的字节，若有，则写入解压的目标文件。再继续读压缩文件的一个字节，转换为8位0、1码，重复，直至读完压缩文件,并全部转化为字节，写入解压的文件。
2.未优化其中的函数模块，所以压缩速度比较慢。
如String可以用StringBuffer代替。虽然String的’+’用起来很方便，但是每’+’一个字符，虚拟机都new了一个String对象，释放原来的String对象，所以，’+’操作频繁，则效率很低。
有以下几点体会：
1.由于流程较多，所以，保证每个函数模块正确后，再将他们拼接起来，否则，找错误会很困难，不知道错在哪一部分。
函数可分为3部分：
(1).输入的参数
(2).函数实现
(3).输出结果
2.函数的参数，不要轻易地定义为类的属性。
虽然函数不需要传参，似乎方便了。但是，当类的属性名很多的时候，局部变量名易与类的属性同名，两者混淆；属性多了，容易忘记属性的具体意义。并且，函数的参数定义为类的属性，则一直占用空间。
所以，尽量作为函数参数传入，而不是简单地定义为类的属性。
3.byte类型的范围为：-128~127
而无符号的byte范围为：0~255，最大值为255。
当值大于127时，byte会从-128 ~ 127 ~ -128 ~ 127……在这256个数内循环。即128对应的byte为-128；129对应byte为-127。
所以，读文件时，可用readUnsignedByte();，当数字大于255时，则不能用byte了。否则结果错误。比如表示字节个数，就不能用byte类型表示，因为有256种字节。
5.文件的保存形式。
此处用的是字节流。若写入文件的内容由多个不同长度的部分组成，则可以在每个部分之前，用一个长度来表示这个部分的结束，来区分标志各个部分。
还有一种加分隔符，XML应该也是一种加入分隔符的形式。
6.测试函数执行所用的时间，来比较多种方案的效率
long t1 = System.currentTimeMillis();rd.mainly();long t2 = System.currentTimeMillis();long a = t2-t1;//计算rd.mainly();运行的时间System.out.println("共用时"+a+"m秒");
以下是代码，没有界面：
package treeV2;//实现压缩、解压public class Reduction {public static void main(String args[]){Reduction rd=new Reduction();long t1 = System.currentTimeMillis();rd.mainly();long t2 = System.currentTimeMillis();long a = t2-t1;//计算rd.mainly();运行的时间System.out.println("共用时"+a+"m秒");} //总函数public void mainly(){//1.读源文件FileTest file=new FileTest();String sourcePath = "E:\\test.doc";byte[] bytFile=file.readFile(sourcePath);//读原文件，得到的文件字节数组System.out.print("读源文件的字节为：");for(int i=0;i<bytFile.length;i++) System.out.print(bytFile);System.out.println();// 2.根据传入的字节，统计每个字节出现的次数MapTest mt = new MapTest();java.util.Map<Byte, Integer> mapBI = mt.createMap(bytFile);mt.mapToArraylist(mapBI);//取出map中数据，并存入 mapV //3.通过map<字节，次数>，建造Huffman树Tree tree=new Tree();tree.codeTree(tree.Array2Tree(MapTest.mapV));//3.1转化成<字节、对应编码>的mapjava.util.Map<Byte, String> mapBS=mapOfCode(); System.out.println("写入压缩文件前的map<字节、对应编码>：");// printMap(mapBS);//测试 //4.将原文件的字节转化成01码 String strBinary=byte2binary(bytFile,mapBS); System.out.println("将原文件的字节转化成01码：成功"); byte[] byt1=binary2byte(strBinary);//4.1 将01码转化成写入压缩文件的字节System.out.println("压缩后的字节数组：");for(int i=0;i<byt1.length;i++)//测试最后压缩后的原文件System.out.print(byt1+" ");System.out.println();//System.out.println("map字节的总个数="+MapTest.mapV.size());//测试map字节的总个数//5.将压缩文件的字节 写入压缩文件String yasuoPath="E:\\aa.s";//压缩文件的路径file.reduceWrite(yasuoPath, mapBS, byt1);System.out.println("----------------------读压缩文件后--------------------------：");//6.读压缩文件，存入字节数组，得到map<01编码,字节>byte[] bytLast=file.reduceRead(yasuoPath);//解压缩后的文件字节System.out.println("读压缩文件的map<编码、对应字节>：");printMap1(file.mapLast);//测试读压缩后的mapSystem.out.println("读压缩文件的原文件字节：");//测试读压缩后的原文件字节for(int i=0;i<bytLast.length;i++){System.out.print(bytLast+" ");}System.out.println();//7.转换成解压缩后的01文件String strLast=recovery2binary(file.mapLast,bytLast);//解压缩后的01文件System.out.print("读压缩文件的原文件01码："+strLast);System.out.println("读压缩文件的原文件01码");//8.通过map将01转成原文件字节,并写成原文件recovery2file(file.mapLast,strLast, "E:\\test1.doc");}//----------------------------文件压缩函数--------------------/** *1.将读文件的字节转为二进制0、1 * @param byt:读文件的字节 * @param map1：存<字节，编码> * @return:byte转化成string */public String byte2binary(byte[] byt,java.util.Map<Byte, String> map1){String str="";for(int i=0;i<byt.length;i++){str+=map1.get(byt); //可再用二分搜索写一下}System.out.println(" byte2binary转换后的01串为"+str+"长度为"+str.length());return str;}//1.1转化 为map<字节、对应编码>//为了文件中字节转换为01编码方便，用到map的get方法public java.util.Map<Byte, String> mapOfCode(){java.util.Map<Byte, String> map=new java.util.HashMap<Byte, String>();for(int i=0;i<MapTest.mapV.size();i++){map.put(MapTest.mapV.get(i).keyB, MapTest.mapV.get(i).code);//存入字节，对应的编码}return map;}/** * 2.将二进制0、1转换为十进制字节 * @param str：需要转换成字节的01码 * @return:压缩文件byte数组 */public byte[] binary2byte(String str){char[] str1=str.toCharArray();int result=str1.length%8;byte[] byt1=new byte;//若所有字节正好8位，则最后两位都为0int k=0,i=0;//System.out.println(str1.length/8);for(;i<str1.length/8;i++){//有i个8k=k+8;byte sum=0;for(int j=0;j<8;j++){if(str1!='0'){//字符直接乘错误sum+=java.lang.Math.pow(2,j);}}byt1=sum;}if(result!=0){//剩余位byte sum=0;for(int j=0;j<result;j++){if(str1!='0'){sum+=java.lang.Math.pow(2,8-result+j);}}byt1=sum;byt1[++i]=(byte)(result);//有result个0（result<8）//System.out.println("<<<<"+sum);}else{//无剩余位，则补两位0byt1=0;byt1[++i]=0;}return byt1;}//----------------------------文件解压缩的函数--------------------/** * 1.1将字节转为对应0、1编码，1位十进制转为8位二进制， * @param b:需要转换的字节 * @return 字符串 */public String dec2binary(byte b){//可直接转成整型，若为字节，则范围-128~127.无法表示128~255,所以用整型运算int a;if(b<0)//计算成为正确的整型a=b+256;elsea=b;String str="";int i=0;int d=128;//除数while(i<8){int ay=a/d;//当不足8位时，此处可改为：不需计算直接剩余赋为0//System.out.print(" "+ay);if(ay==0)str+='0';else{a=a-d;str+='1';}d=d/2;i++;}return str;}/** * 1.2将文件字节数组转为01编码 * @param map:<编码，字节> * @param b: 需要转换的字节数组 * @return */public String recovery2binary(java.util.Map<String, Byte> map,byte[] b){String str="";for(int i=0;i<b.length-2;i++){str+=dec2binary(b);//将字节转换为01}//最后两位处理 if(b!=0){//有不足8位的 String str1=dec2binary(b);//将最后第二位译成01码 //取str1前b位str+=str1.substring(0, b); }return str;}/** * 2.将解压的01编码翻译成原文件,写入指定目录 * @param map:读压缩文件的map * @param str：要转换的01码 * @param filePath：解压的文件路径 */public void recovery2file(java.util.Map<String, Byte>map,String str,String filePath){String strtest="";//测试转换后的文件字节java.util.Set<String> keys=map.keySet();//建立 Map的Set集合//得到Set的迭代器,遍历Setjava.util.Iterator<String> iterator=keys.iterator();int n=MapTest.mapV.size();//总字节个数String[] s=new String;int i=0;//将iterator中编码存于数组String[]中while(iterator.hasNext()){//iterator仍有元素迭代s=iterator.next();i++;}//创建指定路径的文件对象java.io.File file=new java.io.File(filePath);try{//创建这个文件的输出流java.io.FileOutputStream fos=new java.io.FileOutputStream(file);while(!str.isEmpty()){//str为空for(int j=0;j<s.length;j++){//从第一个开始找，所以不能用containsi=0;while(i<s.length() && str.charAt(i)==s.charAt(i) ){//包含si++;}if(i==s.length()){//System.out.println("recovery2files为："+s);byte b=map.get(s); //得到相应字节//将字节b写入制定文件fos.write(b);str=str.substring(s.length(), str.length());//不考虑效率，每次new一个stringstrtest+=b;break;}}}//强制输出fos.flush();fos.close();}catch(Exception ef){ef.printStackTrace();}System.out.println("recovery2file测试后结果为："+strtest);}//测试打印java.util.Map<Byte, String>public void printMap(java.util.Map<Byte, String> map){//建立 Map的Set集合java.util.Set<Byte> keys=map.keySet();//得到Set的迭代器,遍历Setjava.util.Iterator<Byte> iterator=keys.iterator();while(iterator.hasNext()){//仍有元素迭代byte b=iterator.next();//根据key得到相应的valueString code=map.get(b);System.out.println(code+"<<---"+b);//输出map中的key和value}}//测试打印java.util.Map<String, Byte>public void printMap1(java.util.Map<String, Byte> map){//建立 Map的Set集合java.util.Set<String> keys=map.keySet();//得到Set的迭代器,遍历Setjava.util.Iterator<String> iterator=keys.iterator();while(iterator.hasNext()){//仍有元素迭代String code=iterator.next();//根据key得到相应的valuebyte b=map.get(code);System.out.println(code+"--->>"+b);//输出map中的key和value}}}
package treeV2;//1.读取原文件//2.编码01二进制转换成十进制，由字节形式写入文件，//3.读取文件，将字节转换为二进制，再解码public class FileTest {java.util.Map<String, Byte> mapLast=new java.util.HashMap<String, Byte>();//存读入的map//首先，读取将要压缩的文件public byte[] readFile(String str){//创建对应路径的文件,由于有try｛｝catch，所以不判断文件是否存在也可以java.io.File file=new java.io.File(str);//如果文件存在if(file.exists()){try{//创建文件对象的输入流java.io.FileInputStream fis=new java.io.FileInputStream(file);//得到输入流的字节int len=fis.available();//创建字节数组，存放读入的字节byte by[]=new byte;int t=fis.read();//读完文件，t=-1int i=0;while(t!=-1){by=(byte)t;//int 转为 bytet=fis.read();i++;}fis.close();//关闭文件return by;}catch(Exception ef){ef.printStackTrace();}}return null;}/** * 读取指定路径，并解压 * @param path:读取压缩文件的路径 * @return:压缩文件的字节数组 */public byte[] reduceRead(String path){byte[] bytt = null;//存放文件压缩的字节数组//创建文件对象java.io.File file=new java.io.File(path);//如果文件存在if(file.exists()){try{//创建这个文件的输入流java.io.FileInputStream fis=new java.io.FileInputStream(file);//将问件输入流包装成课读基本类型的数据流java.io.DataInputStream dis=new java.io.DataInputStream(fis);//1.先读取map中字节个数int num=dis.readShort();//可能有256个字节，所以用int写，不能用byteSystem.out.println("读文件map中字节个数为"+num);//2.读取mapfor(int i=0;i<num;i++){byte byt=dis.readByte();//（1）读字节//（2）读对应编码长度,转换成Stringint codeLen=dis.readUnsignedByte();//次数>127，无符号byteString str="";for(int j=0;j<codeLen;j++){//（3）读编码int t=fis.read(); str+=(char)t;//直接将int转为01字符 ///int转为char：转换成int值对应的ASCII码}mapLast.put(str,byt ); //装入<01编码、字节>}//3.读存入的文件压缩字节int len=fis.available();//剩余字节长度//给bytt定义空间，存放文件压缩的字节bytt=new byte;int t=fis.read();int i=0;while(t!=-1){bytt=(byte)t;t=fis.read();i++;}System.out.println("读的原压缩文件为");//测试输出所读文件的压缩字码段for(int j=0;j<bytt.length;j++)System.out.print(bytt+" ");System.out.println();}catch(Exception ef){ef.printStackTrace();}}return bytt;}/** * 将map和转换后的字节数组写入指定的地址 * @param path压缩文件地址 * @param map<字节,对应01编码> * @param bytt转换后的文件字节 */public void reduceWrite(String path,java.util.Map<Byte, String> map,byte[] bytt){try{//文件输出流java.io.FileOutputStream fos=new java.io.FileOutputStream(path);//将文件流包装成数据输出流java.io.DataOutputStream dos=new java.io.DataOutputStream(fos);//1.写入map中字节的个数dos.writeShort(MapTest.mapV.size());//可能有256个字节，所以用int写，不能用byteSystem.out.println("写文件map中字节个数为"+MapTest.mapV.size());//2.写入map中数据for(int i=0;i<MapTest.mapV.size();i++){dos.writeByte(MapTest.mapV.get(i).keyB);// （1）写字节//（2）写字节对应编码长度dos.writeByte(MapTest.mapV.get(i).code.length());//（3）写编码 byte by[]=MapTest.mapV.get(i).code.getBytes();fos.write(by);//将字节数组写到文件 //char 转为 byte：得到对应ASCII的int值}//3.写入转换后的原文件压缩字节fos.write(bytt);//强制输出fos.flush();fos.close();}catch(Exception ef){ef.printStackTrace();}}}
package treeV2;public class MapValue {public byte keyB;// 存读取文件的字符public int times;// 次数String code; //对应的二进制编码}
package treeV2;public class Tree {private int n=0;//outArray(TreeNode a[])中限制大小/** * 将指定的数组转化成哈夫曼树 * @param arr：要转化的数组 * @return：将转化后的树的根节点返回 */public TreeNode Array2Tree(java.util.ArrayList<MapValue> mapVL){bubbleOrder(mapVL);//先按次数排序n=mapVL.size();//比较大小的数组的长度 //另外写一个方法求得数组内的实际元素个数int m=2*mapVL.size()-1;//共2n-1个节点TreeNode nodes[]=new TreeNode;//创建节点数组，其中只存比较大小的节点for(int i=0;i<mapVL.size();i++){//创建n个叶子节点,并初始化TreeNode node=new TreeNode(mapVL.get(i).times,mapVL.get(i).keyB);nodes=node;}for(int i=mapVL.size();i<m;i++){//比较节点内的数据TreeNode node=new TreeNode(0,(byte)0);//其余节点赋值为0 node.setLeft(nodes); node.setRight(nodes); nodes.setParent(node); nodes.setParent(node); node.times=nodes.times+nodes.times;//将次数存入节点 outArray(nodes);//移出头两个元素 insertOrder(nodes,node);//插入新节点}return nodes;//最后一个点为根节点，值最大}// 遍历树,左边标1，右边标0private String strcode="";public void codeTree(TreeNode root){//由下往上打印byte keyB = root.keyB;//字节if(root.getLeft()==null&&root.getRight()==null){//为叶子的时候,存入编码//找到mapV中对应的keyB，加上HF编码int pos=findPos(MapTest.mapV,keyB);//System.out.println("pos="+pos);if(pos!=-1){MapTest.mapV.get(pos).code=strcode; //0,1编码存入队列}else{System.out.println("HF编码出错");}}TreeNode left = root.getLeft();if(left!=null){//标1strcode=strcode+"1";codeTree(left);}TreeNode right = root.getRight();if(right!=null){//只改变右子树，y的间距是不变的//标0strcode=strcode+"0";codeTree(right);}//此时左右子树都为空，往上回一层if(strcode.length()>0){strcode=strcode.substring(0,strcode.length()-1);//不包括原来的第length()-1个}}//找到mapVL中对应的keyB,并返回位置public int findPos(java.util.ArrayList<MapValue> mapVL,byte key){int pos=-1;for(int i=0;i<mapVL.size();i++){//只能根据字节找，因为出现次数不唯一if(mapVL.get(i).keyB==key){pos=i;break;}}return pos;}//冒泡排序,升序，大的往后; 最好适用于所有类型或数据结构public void bubbleOrder(java.util.ArrayList<MapValue> mapVL){for(int i=0;i<mapVL.size()-1;i++){//n-1次比较for(int j=0;j<(mapVL.size()-1)-i;j++){if(mapVL.get(j).times>mapVL.get(j+1).times){//交换顺序MapValue tmp=new MapValue(); //交换整个对象tmp=mapVL.get(j);mapVL.set(j, mapVL.get(j+1));//j变为j+1的对象mapVL.set(j+1, tmp);//j+1变为原来j的对象}}}//printArrayList(mapVL);}//插入排序public void insertOrder(TreeNode a[],TreeNode node){int i=0;while( node.times>a.times && i<n){ //大于再往后插入i++;}n++;for(int j=n-1;j>i;j--){//往后移,node放在i位置a=a;}a=node;}//出数组,一次出两个public void outArray(TreeNode a[]){for(int i=2;i<n;i++){a=a;}n=n-2;//记录比较大小数组的长度，每次少2个//数组内后最后两个数字仍存在}//输出队列mapVLpublic void printArrayList(java.util.ArrayList<MapValue> mapVL){for(int i=0;i<mapVL.size();i++){System.out.println("字节为"+mapVL.get(i).keyB);System.out.println("出现次数为"+mapVL.get(i).times);System.out.println("编码为"+mapVL.get(i).code);}}}
package treeV2;/** * 树的节点类 *包含了MapValue中的字节和次数属性 * @author Administrator * */public class TreeNode {int times;// 节点中的数据对象byte keyB;// 存读取文件的字节，若为字符会超出private TreeNode parent;// 父节点private TreeNode left;// 左子节点private TreeNode right;// 右子节点//构造函数，初始化节点数据,不要漏了数据public TreeNode(int times,byte keyB){this.times = times;this.keyB=keyB;}public byte getKeyB() {return keyB;}public void setKeyB(byte keyB) {this.keyB = keyB;}public int getObj() {return times;}public void setObj(int obj) {this.times = obj;}public TreeNode getParent() {return parent;}public void setParent(TreeNode parent) {this.parent = parent;}public TreeNode getLeft() {return left;}public void setLeft(TreeNode left) {this.left = left;}public TreeNode getRight() {return right;}public void setRight(TreeNode right) {this.right = right;}}
package treeV2; //统计字节数组中每个字节出现的次数，并放在一个Map映射中public class MapTest {static java.util.ArrayList<MapValue> mapV = new java.util.ArrayList<MapValue>();/** * 根据传入的字节数组，统计每个字节出现的次数 * @param byt：字节数组 */public java.util.Map<Byte, Integer> createMap(byte[] byt) {// 创建一个Map对象java.util.Map<Byte, Integer> map = new java.util.HashMap<Byte, Integer>();for(int i=0;i<byt.length;i++){if(map.get(byt) != null){int sum=map.get(byt)+1;map.put(byt,sum ); //装入数据}else {//数据在map中没有map.put(byt,1);}}return map;}//取出map中数据，打印map，并存入java.util.ArrayList<MapValue> mapV public void mapToArraylist(java.util.Map<Byte, Integer> map){//得到Map的Set集合java.util.Set<Byte> keys = map.keySet();//返回此映射中包含的键的 Set 视图//遍历Set//得到Set的迭代器java.util.Iterator<Byte> iter = keys.iterator();int i=0;while(iter.hasNext()){//是否有下一个,如果仍有元素可以迭代，则返回 true。MapValue mapv=new MapValue();//如果有就取一个mapv.keyB = iter.next();//返回迭代的下一个元素。//根据键取得对应的Valuemapv.times= map.get(mapv.keyB);mapV.add(mapv);//加入队列i++;}}//输出队列mapVLpublic void printArrayList(java.util.ArrayList<MapValue> mapVL){for(int i=0;i<mapVL.size();i++){System.out.println("字节为"+mapVL.get(i).keyB);System.out.println("出现次数为"+mapVL.get(i).times);System.out.println("编码为"+mapVL.get(i).code);}}}
页:
[1]