投稿
  1. 首页
  2. 随笔

哈夫曼编码与解码（文件编码与解码）

滑稽壁纸•2022-12-12•随笔•阅读16

哈夫曼编码与解码（文件编码与解码）,第1张

哈夫曼编码与解码（文件编码与解码）


数据结构实验
实现哈夫曼树的编码与译码
主功能函数
//具体细节已经写在注释里面了

Java实现

package Haffman;

import java.io.*;
import java.util.*;

public class HuffMain {

    public static void main(String[] args) {
        
        String srcFile="D:\test\srcfile.txt";//要压缩的文件

        String zipFile1="D:\test\b.txt";//压缩后的文件

        zipFile(srcFile,zipFile1);//压缩函数

        String dstFile="D:\test\dstfile.txt";//将压缩后的文件解压缩到新文件中
//        String srcFile="D:\test\beautiful.jpg";
//
//        String zipFile1="D:\test\d.zip";
//        zipFile(srcFile,zipFile1);
//        String dstFile="D:\test\x.jpg";

        unZipFile(zipFile1,dstFile);
    }

    
    public static byte[] huffmanzip(byte[] bytes) {
        List nodes = getNodes(bytes);//计算权重，创建每个结点，放在list集合里面.
        HTreeNode tree = HuffmanTree.creatHuffTree(nodes);//根据每个结合的每个结点，创建哈夫曼树
        Map HuffmanCodes = getCode(tree);//获取哈夫曼树的叶子结点的编码，键为data,值为编码。
        byte[] zip = zip(bytes, huffmanCodes);//参数为data转换为字节后的data，huffmanCodes为哈夫曼树叶子结点的编码，返回值是一个压缩后的编码(byte数组)
        return zip;
    }



    
    
    private static List getNodes(byte[] bytes) {
        ArrayList nodes = new ArrayList<>();

        HashMap Ma = new HashMap<>();

//        用map集合统计次数

        for (byte a : bytes) {
            Integer integer = Ma.get(a);//map集合的值是字节数组每个字节出现的频率，键就是每个字节
            if (integer == null) {
                Ma.put(a, 1);
            } else {
                Ma.put(a, integer + 1);
            }
        }
        for (Map.Entry entry : Ma.entrySet()) {
            nodes.add(new HTreeNode(entry.getKey(), entry.getValue()));
        }
        return nodes;
    }


    

    private static Map huffmanCodes = new HashMap<>();


    public static Map getCode(HTreeNode node) {
        if (node == null) {
            return null;
        }
        getCode(node.getLeft(),"0",new StringBuilder());
        getCode(node.getRight(),"1",new StringBuilder());
        return huffmanCodes;
    }

        
    public static void getCode(HTreeNode node, String code, StringBuilder stringBuilder) {
        StringBuilder stringBuilder1 = new StringBuilder(stringBuilder);
        stringBuilder1.append(code);
        if (node != null) {
            if (node.getLeft() == null && node.getRight() == null) {
                huffmanCodes.put(node.getData(), stringBuilder1.toString());
               return;
            }

            getCode(node.getLeft(), "0", stringBuilder1);
            getCode(node.getRight(), "1", stringBuilder1);

        }
    }

        

     private static int lastcount=0;


     private static byte[] zip(byte[] bytes,Map huffmanCodes){

         StringBuilder stringBuilder = new StringBuilder();

         for (byte aByte : bytes) {
             String s=huffmanCodes.get(aByte);
             stringBuilder.append(s);
         }


//         此时的stringBuilder是一长串01字符串


//         for (Map.Entry entry : huffmanCodes.entrySet()) {
//             stringBuilder.append(entry.getValue(entry.getKey()));
//
//         }

        int length=(stringBuilder.length()+7)/8;//按每8位压缩，防止出现哈夫曼码后面有不够的，主要是存byte数组时，准确的知道要存多少个字节

        lastcount=stringBuilder.length()%8;//看看剩余编码最后剩下几位
         byte[] huffmanCodeBytes=new byte[length];
        int index=0;
        for (int i=0;istringBuilder.length()){
                strByte =stringBuilder.substring(i);
            }else {
                strByte =stringBuilder.substring(i,i+8);
            }
//            将截取的字符串转换为

            huffmanCodeBytes[index]= (byte) Integer.parseInt(strByte,2);//将字符串strByte转换为二进制
             index++;

        }

            return huffmanCodeBytes;
     }






    
    private static String byteToBitString(boolean flag,byte b){
        int temp=b;
        temp|=256;//或运算是为了防止下面转换时去掉八位二进制前面的0导致数据不完整
        String s = Integer.toBinaryString(temp);
        if(flag){
            return s.substring(s.length()-8);
        }else {
            return s.substring(s.length()-lastcount);
        }
    }




     
    private static byte[] decode(Map huffmanCodes,byte[] huffmanBytes){
        StringBuilder stringBuilder = new StringBuilder();
        for(int i=0;i map = new HashMap<>();

        for (Map.Entry entry : huffmanCodes.entrySet()) {
            map.put(entry.getValue(),entry.getKey());
        }

        ArrayList list = new ArrayList<>();

        for (int i=0;i map= (Map) oiss.readObject();

            byte[] decode = decode(map, o);

            os=new FileOutputStream(dstFile);

            os.write(decode);
        } catch (IOException | ClassNotFoundException e) {
            e.printStackTrace();
        }finally {

        }
    }
}
 

哈夫曼建树
 

public class HuffmanTree {
    public static  HTreeNode creatHuffTree(List nodes) {
        while (nodes.size() > 1) {
            Collections.sort(nodes);
            HTreeNode left = nodes.get(nodes.size() - 1);
            HTreeNode right = nodes.get(nodes.size() - 2);

            HTreeNode parent = new HTreeNode<>(null, left.getWeight() + right.getWeight());

            parent.setLeft(left);
            parent.setRight(right);
            nodes.remove(left);
            nodes.remove(right);
            nodes.add(parent);
        }
        return nodes.get(0);
    }
//    Map map = new linkedHashMap<>();
//
//    public  Map getHfmCode(HTreeNode root) {
//
//        return (Map) map;
//    }
}

 

结点类
 

public class HTreeNode implements Comparable> {

    private T data;
    private int weight;
    private HTreeNode left;
    private HTreeNode right;

    public HTreeNode(T data, int weight) {
        this.data = data;
        this.weight = weight;
    }

    public HTreeNode() {
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public int getWeight() {
        return weight;
    }

    public void setWeight(int weight) {
        this.weight = weight;
    }

    public HTreeNode getLeft() {
        return left;
    }

    public void setLeft(HTreeNode left) {
        this.left = left;
    }

    public HTreeNode getRight() {
        return right;
    }

    public void setRight(HTreeNode right) {
        this.right = right;
    }

    @Override
    public int compareTo(HTreeNode o) {
        //        从大到小排
        if (o.getWeight() > this.getWeight()) {
            return 1;
        } else if (o.getWeight() < this.getWeight()) {
            return -1;
        } else {
            return 0;
        }
    }

    @Override
    public String toString() {
        return "HTreeNode{" +
                "data=" + data +
                ", weight=" + weight +
                ", left=" + left +
                ", right=" + right +
                '}';
    }


    public static void preOrder(HTreeNode node) {
        if (node != null) {
            System.out.println(node);
            preOrder(node.left);
            preOrder(node.right);
        }
    }


    public static Integer cacluateWeight(HTreeNode node, int deep) {
        if (node != null) {
            if (node.left == null && node.right == null) {
                return node.weight * deep;
            }
            return cacluateWeight(node.left, deep + 1) + cacluateWeight(node.right, deep + 1);
        }

        return 0;
    }
}


欢迎分享，转载请注明来源：内存溢出
原文地址:https://54852.com/zaji/5481123.html
赞
(0)
打赏
微信扫一扫微信扫一扫
支付宝扫一扫支付宝扫一扫

滑稽壁纸滑稽壁纸一级用户组
00
上一篇
2022-12-12

下一篇2022-12-12

发表评论

登录后才能评论

评论列表（0条）
    
	

    
	
    
		
    
			

			
    
				
				
    
					
    
						Copyright © 2022 内存溢出 版权所有
						
							蜀ICP备2023005044号						
						Powered by
						
							outofmemory.cn
						
					
					
    
				
    
			
    
			
    
				
    
					
					
						
						
					
					
						
					
				
    
			
    
		
    
	
    

    



















    保存