赫夫曼压缩解压(java)

/**
 * 创建Node,包含数据和权值
 */
public class Node implements Comparable<Node> {
    //存放字符串本身
    Byte data;
    //存放权值 字符出现的次数
    int weight;
    Node left;
    Node right;
 
    public Node(int weight) {
        this.weight = weight;
    }
 
    public Node(Byte data, int weight) {
        this.data = data;
        this.weight = weight;
    }
 
 
    /**
     * 前序遍历
     */
    public void preOrder() {
        System.out.println(this);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }
 
    @Override
    public int compareTo(Node o) {
        return this.weight - o.weight;
    }
 
    @Override
    public String toString() {
        return "Node{" +
                "date=" + data +
                ", weight=" + weight +
                '}';
    }
}

import java.io.*;
import java.util.*;
 
public class HuffmanCode {
    //    赫夫曼编码 32=01, 97=100, 100=11000, 117=11001, 101=1110, 118=11011, 105=101, 121=11010, 106=0010, 107=1111, 108=000, 111=0011
    static Map<Byte, String> huffmanCodes = new HashMap<>();
 
    public static void main(String[] args) {
        String content = "i like like like java do you like a java";
        byte[] strByte = content.getBytes();
        System.out.println("压缩前数组" + Arrays.toString(strByte));
        System.out.println("压缩前数组长度" + strByte.length);
        //压缩
        byte[] huffmanCodeBytes = huffmanZip(strByte);
        System.out.println("压缩后数组" + Arrays.toString(huffmanCodeBytes));
        System.out.println("压缩后数组长度" + huffmanCodeBytes.length);
        //解压
        byte[] sourceByte = decode(huffmanCodes, huffmanCodeBytes);
        System.out.println("解压后数组" + Arrays.toString(sourceByte));
        System.out.println("解压后数组长度" + sourceByte.length);
        //解压后数据
        System.out.println(new String(sourceByte));
 
        //String srcFile = "D:\\demo.png";
        //String zipFile = "D:\\demo.zip";
        //zipFile(srcFile, zipFile);
        //System.out.println("压缩文件成功");
 
        String zipFile = "D:\\demo.zip";
        String dstFile = "D:\\demo2.png";
        unZipFile(zipFile,dstFile);
 
 
    }
 
    /**
     * 赫夫曼解压
     *
     * @param zipFile 准备解压的文件
     * @param dstFile 解压后的文件存放目录
     */
    public static void unZipFile(String zipFile, String dstFile) {
        //定义文件输入流
        InputStream is = null;
        //定义一个对象输入流
        ObjectInputStream ois = null;
        //定义文件输出流
        OutputStream os = null;
        try {
            //创建文件输入流
            is = new FileInputStream(zipFile);
            //创建一个和is关联的对象输入流
            ois = new ObjectInputStream(is);
            //读取byte数组，huffmanBytes
            byte[] huffmanBytes = (byte[]) ois.readObject();
            //读取赫夫曼编码表
            Map<Byte, String> huffmanCode = (Map<Byte, String>) ois.readObject();
            //    解码
            byte[] bytes = decode(huffmanCode, huffmanBytes);
            //    将解码后字节流写入目标文件
            os = new FileOutputStream(dstFile);
            os.write(bytes);
 
        } catch (Exception e) {
            throw new RuntimeException(e);
        } finally {
            try {
                os.close();
                ois.close();
                is.close();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
    }
 
    /**
     * 编写方法，将文件进行压缩
     *
     * @param srcFile 压缩文件全路径
     * @param dstFile 压缩后文件输出路径
     */
    public static void zipFile(String srcFile, String dstFile) {
        //创建输入流
        FileInputStream inputStream = null;
        //创建输出流
        FileOutputStream outputStream = null;
        ObjectOutputStream oos = null;
        try {
            //创建文件输出流
            inputStream = new FileInputStream(srcFile);
            //     创建一个和源文件大小一样的byte[]
            int inputSize = inputStream.available();
            byte[] bytes = new byte[inputSize];
            //读取文件
            inputStream.read(bytes);
            //压缩文件
            byte[] zipBytes = huffmanZip(bytes);
            //创建文件输出流，存放压缩文件
            outputStream = new FileOutputStream(dstFile);
            //创建一个和文件输出流相关的ObjectOutputStream
            oos = new ObjectOutputStream(outputStream);
            //   将赫夫曼编码后的字节数组写入压缩文件
            oos.writeObject(zipBytes);
            // 以对象流写入赫夫曼编码，
            oos.writeObject(huffmanCodes);
        } catch (IOException e) {
            throw new RuntimeException(e);
        } finally {
            try {
                inputStream.close();
                outputStream.close();
                oos.close();
            } catch (IOException e) {
                System.out.println(e.getMessage());
            }
        }
    }
 
    /**
     * 对压缩数据的解码
     *
     * @param huffmanCodes
     * @param huffmanByte
     * @return
     */
    private static byte[] decode(Map<Byte, String> huffmanCodes, byte[] huffmanByte) {
        //将赫夫曼编码数组转换为二进制字符串
        StringBuffer stringBuffer = new StringBuffer();
        for (int i = 0; i < huffmanByte.length; i++) {
            //最后一位不需要补高位
            if (i != huffmanByte.length - 1) {
                stringBuffer.append(byteToBitString(true, huffmanByte[i]));
            } else {
                stringBuffer.append(byteToBitString(false, huffmanByte[i]));
            }
        }
        //根据赫夫曼编码表，反写解码表
        Map<String, Byte> decodeMap = new HashMap<>();
        for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) {
            decodeMap.put(entry.getValue(), entry.getKey());
        }
        //创建要给的集合，存放byte
        List<Byte> list = new ArrayList<>();
        StringBuffer key = new StringBuffer();
        for (int i = 0; i < stringBuffer.length(); i++) {
            key.append(stringBuffer.substring(i, i + 1));
            Byte aByte = decodeMap.get(key.toString());
            if (aByte != null) {
                list.add(aByte);
                key = new StringBuffer();
            }
        }
        //构造返回数据
        byte[] res = new byte[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }
 
    /**
     * 将一个byte转成一个二进制的字符串
     *
     * @param b    传入的byte
     * @param flag 标志是否需要补高位，如果为true,表示需要补高位
     * @return byte对应的二进制字符串（按照补码返回）
     */
    private static String byteToBitString(boolean flag, byte b) {
        //  使用变量保存b 将b转换为int
        int temp = b;
        //如果是正数，需要补高位 1 0000 0000 | 0000 0001= 10000 0001
        if (flag) {
            temp |= 256;
        }
        //返回对应二进制的补码
        String str = Integer.toBinaryString(temp);
        if (flag) {
            return str.substring(str.length() - 8);
        } else {
            return str;
        }
    }
 
    /**
     * 将字节数组压缩为赫夫曼数组
     *
     * @param bytes
     * @return
     */
    private static byte[] huffmanZip(byte[] bytes) {
        //获取赫夫曼树节点
        List<Node> nodes = getNodes(bytes);
        //创建霍夫曼树
        Node huffmanTree = createHuffmanTree(nodes);
        //生成霍夫曼编码
        getCodes(huffmanTree);
        //压缩数据
        return zip(bytes, huffmanCodes);
 
    }
 
    /**
     * 将字符串对应的byte[]数组，通过生成的赫夫曼编码表，返回一个赫夫曼编码压缩后的byte[]
     *
     * @param bytes        这是原始的字符串对应的byte[]
     * @param huffmanCodes 生成的赫夫曼编码map
     * @return 返回赫夫曼处理后的byte
     * 10101000补码  反码10101000-1=10100111 原码11011000 -（24+64）
     */
    private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
        StringBuffer temp = new StringBuffer();
        for (byte b : bytes) {
            temp.append(huffmanCodes.get(b));
        }
        //计算新数组长度 int len=(tem.length()+7)/8
        int len;
        if (temp.length() % 8 == 0) {
            len = temp.length() / 8;
        } else {
            len = temp.length() / 8 + 1;
        }
        //创建存储压缩后的byte数组；
        byte[] huffmanCodeBytes = new byte[len];
        //记录第几个byte
        int index = 0;
        for (int i = 0; i < temp.length(); i += 8) {
            String strByte;
            if (i + 8 > temp.length()) {
                strByte = temp.substring(i);
            } else {
                strByte = temp.substring(i, i + 8);
            }
            //将字符串二进制转换为byte
            huffmanCodeBytes[index] = (byte) Integer.parseInt(strByte, 2);
            index++;
        }
 
        return huffmanCodeBytes;
    }
 
    /**
     * 重载
     *
     * @param root
     */
    private static void getCodes(Node root) {
        if (root != null) {
            getCodes(root.left, "0", new StringBuffer());
            getCodes(root.right, "1", new StringBuffer());
        }
    }
 
    /**
     * 将传入的node节点的所有叶子节点的赫夫曼编码得到，放到huffmanCodes集合
     *
     * @param node         传入节点
     * @param code         路径：左子节点0，右子节点1
     * @param stringBuffer 用于路径拼接
     */
    private static void getCodes(Node node, String code, StringBuffer stringBuffer) {
        StringBuffer temp = new StringBuffer(stringBuffer);
        temp.append(code);
        if (code != null) {
            //飞叶子结点
            if (node.data == null) {
                //左递归
                getCodes(node.left, "0", temp);
                //右递归
                getCodes(node.right, "1", temp);
            } else {
                //处理叶子节点
                huffmanCodes.put(node.data, temp.toString());
            }
        }
    }
 
    /**
     * 前序打印
     *
     * @param root
     */
    private static void preOrder(Node root) {
        if (root != null) {
            root.preOrder();
        } else {
            System.out.println("赫夫曼树为空");
        }
    }
 
    /**
     * 接受数组返回节点集合
     *
     * @param bytes
     * @return
     */
    private static List<Node> getNodes(byte[] bytes) {
        //    创建一个ArrayList
        ArrayList<Node> nodes = new ArrayList<>();
        //创建一个map保存byte出现的次数
        HashMap<Byte, Integer> counts = new HashMap<>();
        for (byte b : bytes) {
            Integer num = counts.get(b);
            if (num == null) {
                counts.put(b, 1);
            } else {
                counts.put(b, ++num);
            }
        }
        //构建集合
        for (Map.Entry<Byte, Integer> entry : counts.entrySet()) {
            nodes.add(new Node(entry.getKey(), entry.getValue()));
        }
        return nodes;
    }
 
    /**
     * 创建赫夫曼树
     *
     * @param nodes
     * @return
     */
    private static Node createHuffmanTree(List<Node> nodes) {
        while (nodes.size() > 1) {
            //排序从小到大
            Collections.sort(nodes);
            //    取出前两个
            Node leftNode = nodes.get(0);
            Node rightNode = nodes.get(1);
            //    创建父节点
            Node parent = new Node(null, leftNode.weight + rightNode.weight);
            parent.left = leftNode;
            parent.right = rightNode;
            //删除已使用节点，增加新创建的节点
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            nodes.add(parent);
        }
        return nodes.get(0);
    }
}

压缩前数组[105, 32, 108, 105, 107, 101, 32, 108, 105, 107, 101, 32, 108, 105, 107, 101, 32, 106, 97, 118, 97, 32, 100, 111, 32, 121, 111, 117, 32, 108, 105, 107, 101, 32, 97, 32, 106, 97, 118, 97]
压缩前数组长度40
压缩后数组[-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]
压缩后数组长度17
解压后数组[105, 32, 108, 105, 107, 101, 32, 108, 105, 107, 101, 32, 108, 105, 107, 101, 32, 106, 97, 118, 97, 32, 100, 111, 32, 121, 111, 117, 32, 108, 105, 107, 101, 32, 97, 32, 106, 97, 118, 97]
解压后数组长度40
i like like like java do you like a java