java基于哈夫曼树的压缩和解压控制台小程序

基于哈夫曼树的原理用java写的一个用来压缩解压图片的控制台小程序。
程序压缩思路大致如下:
1.读取文件字节,转换成int类型数据就是0-255范围内的整型,然后统计出现次数即权重
2.根据权重构造出哈夫曼树,然后生成哈夫曼编码
3.将主要的编码长度,哈夫曼编码表和文件转译成的哈夫曼编码串写入文件即压缩文件。
解压的思路大致如下:
1.读取压缩文件,先读出各编码长度,计算出总长度,然后根据总长度读出哈夫曼编码表。
2.哈夫曼编码的特性编码前缀不重复,然后循环遍历查找哈夫曼编码表转译成字节然后写入文件即解压文件

源代码:

一、节点类:

public class HuffNode {
    private long weight;  //权值
    private int index;    //序号
    private HuffNode left;    //左子节点
    private HuffNode right;    //右子节点
      
    //哈夫曼节点的构造函数  
    public HuffNode(long l,int index){  
        this.weight=l;  
        this.index=index;  
    }  
      
    //私有属性的封装  
    public long getWeight() {  
        return weight;  
    }  
    public void setWeight(int weight) {  
        this.weight = weight;  
    }  
    public int getIndex() {  
        return index;  
    }  
    public void setIndex(int index) {  
        this.index = index;  
    }  
    public HuffNode getLeft() {  
        return left;  
    }  
    public void setLeft(HuffNode left) {  
        this.left = left;  
    }  
    public HuffNode getRight() {  
        return right;  
    }  
    public void setRight(HuffNode right) {  
        this.right = right;  
    }
}

二、压缩类

import java.io.File;
import java.io.FileInputStream;  
import java.io.FileOutputStream;  
import java.text.DecimalFormat;
import java.util.LinkedList;

public class Compress {  
    public int [] weight = new int[256]; //统计字符出现的次数  即权值 
    public static String [] HuffmCodes=new String[256];  //哈夫曼编码
    public LinkedList<HuffNode> list = new LinkedList<HuffNode>(); //基于链表的哈夫曼节点链

    public Compress(){  
        for (int i = 0; i < HuffmCodes.length; i++)    {
            HuffmCodes[i]="";    //初始化  
        }
    }  

    public void calcuWeight(String path) throws Exception{
        FileInputStream fis = new FileInputStream(path);
        int value;
        while((value = fis.read()) != -1){  //读取一个数据字节
            weight[value]++;  
            value=fis.read();  
        }
        fis.close();  
    }  

    //构造哈夫曼树  
    public HuffNode createHuffTree(){
        //将次数作为权值构造森林  
        for (int i = 0; i < weight.length; i++) {  
            if(weight[i]!=0){  
                HuffNode node = new HuffNode(weight[i],i);//数据i出现了weight[i]次
                //将构造好的节点加入到容器中的正确位置  
                list.add(getIndex(node), node); //利用getIndex使list保持从小到大排序
            }  
        }
        //构造哈夫曼树  
        while(list.size()>1) {//容器list从小到大排序
            HuffNode firstNode =list.removeFirst();//获取权值最小的节点
            HuffNode secondNode =list.removeFirst(); //获取权值第二小的节点
            HuffNode fatherNode = new HuffNode(firstNode.getWeight()+secondNode.getWeight(),-1);//组成新子树,新父节点  
            fatherNode.setLeft(firstNode);//设置左子节点  
            fatherNode.setRight(secondNode);//设置右子节点  
            list.add(getIndex(fatherNode),fatherNode);//根据权值放入容器中正确的位置
        }
        //while循环完成之后容器里只有一个根节点,然后整颗哈夫曼树就靠各节点保存的左右子节点建立起来
        return list.getFirst(); //返回哈夫曼树的根节点
    }  
    //利用前序遍历获取编码表  
    public void getHuffCode(HuffNode root,String code){  
        //往左走,哈夫曼编码加0  
        if(root.getLeft()!=null){  
            getHuffCode(root.getLeft(),code+"0");  
        }  
        //往右走,哈夫曼编码加1  
        if(root.getRight()!=null){  
            getHuffCode(root.getRight(),code+"1");
        }  
        //如果是叶子节点,返回该叶子节点的哈夫曼编码  
        if(root.getLeft()==null && root.getRight()==null){
            HuffmCodes[root.getIndex()]=code;
        }  
    }  

    //压缩文件  
    public void compress(String filePath,String putPath) throws Exception{  
        //filePath 需要压缩的文件路径
        //putPath  压缩文件输出路径
        FileOutputStream fos = new FileOutputStream(putPath);
        FileInputStream fis = new FileInputStream(filePath);  
        StringBuilder sb = new StringBuilder();
        //将整个哈夫曼编码以及每个编码的长度写入文件  
        String code ="";  
        for (int i = 0; i < 256; i++) {  
        fos.write(Compress.HuffmCodes[i].length());  
        sb.append(Compress.HuffmCodes[i]);  
        fos.flush();  
        }  
        code = sb.toString();
        sb.delete(0, sb.length());
        //Scanner sc = new Scanner(System.in);
        //sc.next();
        //System.out.println("code="+code);
        String str1="";  
        while(code.length()>=8){
            str1=code.substring(0, 8);
            int c=Integer.valueOf(str1,2);//二进制字符串转十进制整数
            //System.out.println(c+"\t"+temp);
            //Thread.sleep(1000);
            fos.write(c);//写入int
            fos.flush();
            code=code.substring(8);
        }  
        
        //理最后长度不够处8的二进制组
        int last=8-code.length(); 
        for (int i = 0; i <last; i++)    code+='0';
        str1=code.substring(0, 8);  
        int c = Integer.valueOf(str1,2);  
        fos.write(c);  
        fos.flush();  
        
        /*-------------写入码表end------------*/
        /*-------------写入文件内容的哈夫曼编码start------------*/
        int value=fis.read();
        while(value!=-1){
            sb.append(Compress.HuffmCodes[value]);
            //System.out.println((char)value+":"+str);  
            value=fis.read();  
        }
        String str=sb.toString();  
        sb.delete(0, sb.length());
        fis.close();
        String s="";  
        //将字符8位分割
        while(str.length()>=8){  
            s=str.substring(0, 8);  
            int b=Integer.valueOf(s,2); 
            //System.out.println(c);  
            fos.write(b);  
            fos.flush();  
            str=str.substring(8);  
        }
        //最后不够8位添0  
        int last1=8-str.length();  
        for (int i = 0; i <last1; i++) {  
            str+="0";  
        }  
        s=str.substring(0, 8);  
        //System.out.println(s);  
        int d=Integer.valueOf(s,2);  
        fos.write(d);  

        //压缩后不够补0的个数暂  
        fos.write(last1);  
        fos.flush();  
        fos.close();
        /*-------------写入文件内容的哈夫曼编码end------------*/
    }  

    //插入元素位置的索引  
    public int getIndex(HuffNode node) {  
        for (int i = 0; i < list.size(); i++) {  
            if(node.getWeight()<=list.get(i).getWeight()){  
                return i;  
            }
        }  
        return list.size();  
    }  
    
    //计算压缩率
    public void compressRadio(String filePath, String putPath) {
        double oldFileSize = 0.0,newFileSize=0.0,result;
        File f= new File(filePath);  
        oldFileSize = f.length();
        f = new File(putPath);
        newFileSize = f.length();
        result = ((oldFileSize-newFileSize)/oldFileSize)*100;
        DecimalFormat df=new DecimalFormat(".##");
        if(result<0){
            System.out.println("压缩率:你还是别知道了!");
        }
        else{
            String re=df.format(result);
            System.out.println("压缩率:"+re+"%");
        }
    }  
    //public static int test=0;
    public void showHuffTree(HuffNode huffnode){
        System.out.print(huffnode.getIndex()+"\t"+huffnode.getWeight()+"\t");
        if(huffnode.getLeft()==null){
            System.out.print("-1\t");
        }else{
            System.out.print(huffnode.getLeft().getIndex()+"\t");
        }
        if(huffnode.getRight()==null){
            System.out.println("-1\t");
        }else{
            System.out.println(huffnode.getRight().getIndex());
        }
        //System.out.println(test++);
        if(huffnode.getLeft()!=null){
            showHuffTree(huffnode.getLeft());
        }
        if(huffnode.getRight()!=null){  
            showHuffTree(huffnode.getRight());
        }
        if(huffnode.getLeft()==null && huffnode.getRight()==null){
            return ;
        } 
    }
}  

三、解压类

import java.io.FileInputStream;  
import java.io.FileOutputStream;  
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Decompress {  

    //每个编码的长度  
    public int [] codelengths = new int [256];  
    //对应的哈夫曼编码值  
    //public String [] codeMap=new String[256];  
    public Set<String> huffCode = new HashSet<String>(256);  
    public Map<String,String> codeMap = new HashMap<String, String>();
    //public LinkedList<String> deCode = new LinkedList<String>();

    public void decompress(String path,String putPath) {  

        try {  
            FileInputStream fis = new FileInputStream(path);  
            FileOutputStream fos = new FileOutputStream(putPath);  
            StringBuilder sb = new StringBuilder();
            Caltime ct;
            int value;  
            int codeLength=0;  
            ct = new Caltime("读取编码长度");
            String code="";
            for (int i = 0; i < codelengths.length; i++) {  
                value=fis.read();  
                codelengths[i]=value;  
                //System.out.println(times[i]);  
                codeLength+=codelengths[i];  
            }  
            ct.End();
            ct = new Caltime("读取哈夫曼码表");
            //得到总长度  codeLength
            //将总长度除以8的到字节个数  
            int len=codeLength/8;  
            //如果不是8的倍数,则字节个数加1(对应压缩补0的情况)  
            if((codeLength)%8!=0){  
                len++;  
            }  
            //读取哈夫曼编码  
            //System.out.println("codeLength:"+len);
            for (int i = 0; i < len; i++) {  
                //把读到的整数转换成二进制  
                //System.out.println(changeIntToString(temp1)+"\t"+Integer.toBinaryString(temp1));
                //Thread.sleep(1000);
                sb.append(changeIntToString(fis.read()));
            }  
            code = sb.toString();
            //System.out.println("哈夫曼编码:"+code);  
            ct.End();
            ct = new Caltime("分割码表");
            /*for (int i = 0; i < codeMap.length; i++) {  
                //如果第i个位置不为0 ,则说明第i个位置存储有哈夫曼编码  
                if(codelengths[i]!=0){  
                    //将得到的一串哈夫曼编码按照长度分割分割  
                    String ss=code.substring(0, codelengths[i]);  
                    codeMap[i]=ss;  
                    code=code.substring(codelengths[i]);  
                }else{  
                    //为0则没有对应的哈夫曼编码  
                    codeMap[i]="";  
                }  
            }  */
            for (int i = 0; i < 256; i++) {  
                //如果第i个位置不为0 ,则说明第i个位置存储有哈夫曼编码  
                if(codelengths[i]!=0){  
                    //将得到的一串哈夫曼编码按照长度分割分割  
                    String ss=code.substring(0, codelengths[i]);  
                    huffCode.add(ss);
                    codeMap.put(ss, String.valueOf(i));
                    code=code.substring(codelengths[i]);  
                }
            } 
            ct.End();
            ct = new Caltime("读取压缩正文编码");
            //读取压缩的文件内容  
            String codeContent="";  
            sb.delete(0, sb.length());
            while(fis.available()>1){  
                sb.append(changeIntToString(fis.read()));
            }
            codeContent = sb.toString();
            sb.delete(0, sb.length());
            //读取最后一个  
            value=fis.read();  
            //把最后补的0给去掉  
            codeContent=codeContent.substring(0, codeContent.length()-value);  
            ct.End();
            //sb.replace(0, sb.length(), sb.substring(0, sb.length()-value));

            /*for (int i = 0; i < codeContent.length(); i++) {  
                String codecontent=codeContent.substring(0, i+1);  
                for (int j = 0; j < codeMap.length; j++) {  
                    ct = new Caltime("开始翻译解码输出");
                    if(codeMap[j].equals(codecontent)){  
                        
                        fos.write(j);  
                        fos.flush();   
                        codeContent=codeContent.substring(i+1);  
                        i=-1;
                        break;  
                    } 
                    ct.End();
                }  
            }*/
            ct = new Caltime("翻译解码");
            String temp = "";  
            int count = 1; 
            while (codeContent.length() > 0) {  
                temp = codeContent.substring(0, count);  
                if (huffCode.contains(temp)) {  
                    fos.write(Integer.parseInt(codeMap.get(temp)));
                    fos.flush();
                    codeContent = codeContent.substring(count);  
                    count = 1;  
                } else {
                    count++;  
                }  
            } 
            ct.End();
//            ct = new Caltime("编码输出");
//            for(int i=0;i<deCode.size();i++){
//                int sj = Integer.parseInt(deCode.get(i));
//                fos.write(sj);
//                fos.flush();
//            }
//            ct.End();
            fos.close();  
            fis.close();  
        } catch (Exception e) {  
            e.printStackTrace();  
        }  
    }  
     
    
    //十进制转二进制字符串  
    public String changeIntToString(int value) {  
        String s="";  
        for (int i = 0; i < 8; i++) {  
            s=value%2+s;
            value=value/2;
        } 
        return s;  
    }  
}  

四、总结

花了差不多6天的时间吧。程序效率比较低,300k的图片压缩解压差不多一分钟左右。后期尝试使用多线程,尝试在最后解压的时候换成遍历哈夫曼树然后直接输出字节文件的思路,解压的速度应该会提升一些。源代码下载:https://www.hongxuelin.com/usr/uploads/src/Hzip.rar

添加新评论