[数据结构与算法]赫夫曼编码[ 无损压缩 ]

赫夫曼编码及解码

package com.example.dataalgorithm.tree;

import org.jetbrains.annotations.NotNull;

import java.util.*;

/**
 * 哈夫曼编码
 *
 * @author qb
 * @version 1.0
 * @since 2022/3/3 14:50
 */
public class huffmanCode {

    public static void main(String[] args) {

        String str = "i like like like java do you like a java";
        byte[] contentBytes = str.getBytes();
        //40
        byte[] bytes = huffmanZip(contentBytes);
        System.out.println(Arrays.toString(bytes));
        byte[] decode = decode(huffmanCodes, bytes);
        System.out.println("原来的字符串："+ new String(decode));
    }

    /**
     * 数据解压
     * 1. 先将压缩后的数组转成赫夫曼编码对应的二进制的字符串
     * 2. 将二进制对照赫夫曼编码转成 原始字符串
     */

    /**
     *
     * @param huffmanCodes 哈夫曼编码
     * @param huffmanBytes 赫夫曼编码得到的字节数组
     * @return 原来的字符串对应的数组
     */
    private static byte[] decode(Map<Byte,String> huffmanCodes,byte[] huffmanBytes){
        //1.先得到huffmanBytes 对应的二进制字符串
        StringBuilder stringBuilder = new StringBuilder();
        //将byte数组转成二进制的字符串
        for (int i=0;i< huffmanBytes.length; i++){
            //判断是不是最后一个字节
            boolean flag = (i == huffmanBytes.length -1);
            stringBuilder.append(byteToBitString(!flag,huffmanBytes[i]));
        }
        //把字符串按照指定的赫夫曼编码进行解码
        //把赫夫曼编码表进行调换，因为反向查询 a-100  => 100-a
        Map<String,Byte> map = new HashMap<>();
        for (Map.Entry<Byte,String> entry : huffmanCodes.entrySet()){
            map.put(entry.getValue(),entry.getKey());
        }
        //创建一个集合存放byte
        List<Byte> list = new ArrayList<>();
        // i 可以理解成一个索引，不停扫秒 StringBuilder
        for (int i=0;i<stringBuilder.length();){
            int count =1;
            boolean flag = true;
            Byte b = null;
            while (flag){
                //取出一个'1'/'0'
                String key = stringBuilder.substring(i, i + count);
                b = map.get(key);
                if(null == b){
                    //说明没有匹配到
                    count ++;
                }else{
                    flag = false;
                }
            }
            list.add(b);
            //让i 直接移动到count
            i += count;
        }
        //当for循环结束后 list中就存放了所有的字符
        //把list中的数据放入到 byte[] 并返回
        byte[] b = new byte[list.size()];
        for (int i=0;i<b.length;i++){
            b[i] = list.get(i);
        }
        return b;
    }


    /**
     * 将一个byte 转成二进制的字符串
     * @param flag 标识 是否补高位，如果是true表示需要补高位
     * @param b byte字节
     * @return 对应字符串 (是按补码返回的，编码的时候也是按补码编码的)
     */
    private static String byteToBitString(boolean flag,byte b){
        //使用变量保存b
        int temp = b;
        //如果是正数，还需要补充高位
        // temp |= 256; 按位与 （256 = 1 0000 00000 | 1= 0000 0001） = 1 0000 0001
        // 最后一个字节不需要补高位
        if(flag){
            temp |= 256;
        }
        //返回的是int的二进制的补码
        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,"",stringBuilder);
        //根据赫夫曼编码 获取压缩后的赫夫曼编码字节数组
        return zip(bytes, huffmanCodes);
    }

    /**
     * 生成赫夫曼树对应的赫夫曼编码
     * 1. 将赫夫曼编码表存放在 Map<Byte,String>，形式如32-01 97-100  100-11000 等等
     * 2. 在生成赫夫曼编码时，需要去拼接路径  定义一个StringBuilder 存储叶子节点
     * */
    public static Map<Byte,String> huffmanCodes = new HashMap<>();
    public static StringBuilder stringBuilder = new StringBuilder();


    /**
     * 编写一个方法，将字符串对应的byte[] 数组，通过生成的赫夫曼编码表，返回一个赫夫曼编码 压缩后的byte[]
     * @param bytes 原始的字符串对应的byte[]
     * @param huffmanCodes 生成的赫夫曼编码
     * @return byte[] 赫夫曼编码处理后的byte[] 数组
     * huffmanCodeBytes[0] = 10101000(补码) => byte [ 推导 10101000 => 10101000 - 1 => 10100111(反码)
     * => 11011000 = -88]
     * huffmanCodeBytes[0] = -88
     */
    private static byte[] zip(byte[] bytes,Map<Byte,String> huffmanCodes){

        //1.先利用 huffmanCodes 将bytes转成 赫夫曼编码后的字符串
        StringBuilder stringBuilder = new StringBuilder();
        //遍历byte数组
        for (byte b : bytes){
            stringBuilder.append(huffmanCodes.get(b));
        }
        System.out.println(stringBuilder);
        //将 字符串转成byte数组

        //统计返回的 huffmanCodes 的长度
        int len;
        if(stringBuilder.length() % 8 == 0){
            len = stringBuilder.length() / 8;
        }else{
            len = stringBuilder.length() / 8 + 1;
        }
        //创建存储压缩后的byte数组
        byte[] huffmanCodeBytes = new byte[len];
        //记录第几个byte
        int index = 0;
        //因为8位对应一个byte 所以步长就是8
        for (int i=0;i<stringBuilder.length();i+=8){
            String strByte;
            if(i+8>stringBuilder.length()){
                strByte = stringBuilder.substring(i);
            }else{
                strByte = stringBuilder.substring(i,i+8);
            }
            //将strByte 转成byte数组，放入到by
            huffmanCodeBytes[index] = (byte) Integer.parseInt(strByte,2);
            index++;
        }
        return huffmanCodeBytes;
    }


    /**
     * 功能 将传入的node节点的所有叶子结点的和夫曼编码得到并放入到  huffmanCodes 中
     * @param node 传入的节点
     * @param code 路径：左子节点是0，右子节点是1
     * @param stringBuilder 是用于拼接路径
     */
    private static void getCodes(Node node,String code,StringBuilder stringBuilder){

        StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
        //将code加入到StringBuilder2
        stringBuilder2.append(code);
        if (null != node){
            //判断当前node是叶子结点还是非叶子结点
            if(null == node.data){
                //非叶子结点 递归
                getCodes(node.left,"0",stringBuilder2);
                //向右递归
                getCodes(node.right,"1",stringBuilder2);
            }
            else {
                //说明是叶子节点
                //就表示找到了某个叶子结点的最后
                huffmanCodes.put(node.data,stringBuilder2.toString());
            }
        }


    }

    /**
     *
     * @param bytes 接收字节数组
     * @return 返回list集合
     */
    private static @NotNull List<Node> getNodes(byte @NotNull [] bytes){

        //1.创建一个list
        List<Node> nodes = new ArrayList<>();
        Map<Byte,Integer> counts = new HashMap<>();
        //存储每个byte出现的次数 -> map
        for (byte b : bytes) {
            counts.merge(b, 1, Integer::sum);
        }
        //把每个键值对转成node对象 加到nodes
        for (Map.Entry<Byte,Integer> entry : counts.entrySet()){
            nodes.add(new Node(entry.getKey(),entry.getValue()));
        }

        return nodes;
    }


    /**
     * 通过list 创建赫夫曼树
     * @param nodes node集合
     * @return Node
     */
    private static Node createHuffmanTree(@NotNull 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);
    }


}
class Node implements Comparable<Node>{

    /**
     * 存放数据本身，比如:'a' => 97 ' ' =>32
     */
    Byte data;

    /**
     * 数据出现的次数   -- 权重
     */
    int weight;

    Node left;

    Node right;

    public Node(Byte data, int weight) {
        this.data = data;
        this.weight = weight;
    }

    @Override
    public int compareTo(Node o) {
        return this.weight - o.weight;
    }

    @Override
    public String toString() {
        return "Node[ data="+data+",weight="+weight+"]";
    }

    /**
     * 前续遍历
     */
    public void preOrder(){
        System.out.println(this);
        if(null != this.left){
            this.left.preOrder();
        }
        if(null != this.right){
            this.right.preOrder();
        }
    }

}

赫夫曼解压及压缩案例

package com.example.dataalgorithm.tree;

import org.jetbrains.annotations.NotNull;

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

/**
 * 哈夫曼编码
 *
 * @author qb
 * @version 1.0
 * @since 2022/3/3 14:50
 */
public class huffmanCode {

    public static void main(String[] args) {

//        String str = "i like like like java do you like a java";
//        byte[] contentBytes = str.getBytes();
//        //40
//        byte[] bytes = huffmanZip(contentBytes);
//        System.out.println(Arrays.toString(bytes));
//        System.out.println("压缩后的长度:"+bytes.length);
//        byte[] decode = decode(huffmanCodes, bytes);
//        System.out.println("原来的字符串字节长度:"+decode.length);
//        System.out.println("原来的字符串："+ new String(decode));

        //String zipFile = "D://stu-git//数据结构与算法//cs//ddd.png";
//        String dstFile = "D://stu-git//数据结构与算法//cs//ddd.zip";
//        String zipFile = "D://stu-git//数据结构与算法//cs//src.bmp";
//        String dstFile = "D://stu-git//数据结构与算法//cs//src.zip";
        String dstFile = "D://stu-git//数据结构与算法//cs//ddd01.png";
        String zipFile = "D://stu-git//数据结构与算法//cs//ddd.zip";
        //zipFile(zipFile,dstFile);
        unZipFile(zipFile,dstFile);

    }


    /**
     * 解压
     */
    public static void unZipFile(String zipFileName,String distFile){

        //定义文件的输入流
        InputStream is = null;
        //定义一个对象输入流
        ObjectInputStream ois = null;
        //文件输出流
        OutputStream os = null;
        try {
            is = new FileInputStream(zipFileName);
            ois = new ObjectInputStream(is);
            //读取byte数组
            byte[] huffmanBytes = (byte[]) ois.readObject();
            //读取赫夫曼编码表
            Map<Byte,String> codes = (Map<Byte, String>) ois.readObject();
            byte[] decode = decode(codes, huffmanBytes);
            os = new FileOutputStream(distFile);
            os.write(decode);
        }catch (Exception e){
            e.printStackTrace();
        }finally {
            try {
                if(null != os){
                    os.close();
                }
                if(null != is){
                    is.close();
                }
                if(null != ois){
                    ois.close();
                }
            } catch (IOException e) {
                e.printStackTrace();
            }
        }




    }

    /**
     * 编写方法 将一个文件进行压缩
     * @param srcFile 你传入的希望压缩的文件的全路径
     * @param dstFile 我们压缩后将文件放在哪儿个目录下
     */
    public static void zipFile(String srcFile,String dstFile){
        //创建输出流
        OutputStream os = null;
        ObjectOutputStream oos = null;
        //创建文件的输入流
        FileInputStream is = null;
        try {
            is = new FileInputStream(srcFile);
            new ObjectInputStream(is);
            //创建一个和源文件大小一样的byte数组
            byte[] b = new byte[is.available()];
            //读取文件
            is.read(b);
            //使用赫夫曼编码进行编码
            System.out.println(b.length);
            byte[] huffmanBytes = huffmanZip(b);
            System.out.println(huffmanBytes.length);
            os = new FileOutputStream(dstFile);
            //创建一个和文件输出关联的ObjectOutputStream
            oos = new ObjectOutputStream(os);
            //把赫夫曼的字节数组写入压缩文件
            oos.writeObject(huffmanBytes);
            //我们以对象流的方式写入赫夫曼编码 ，是为了以后我们恢复源文件时使用
            oos.writeObject(huffmanCodes);
            System.out.println("文件压缩完成~~");
        }catch (Exception e){
            e.printStackTrace();
        }finally {
                try {
                    if(null != is){
                        is.close();
                    }
                    if(null != os){
                        os.close();
                    }
                    if(null != oos){
                        oos.close();
                    }
                } catch (IOException e) {
                    e.printStackTrace();
                }

        }

    }

    /**
     * 数据解压
     * 1. 先将压缩后的数组转成赫夫曼编码对应的二进制的字符串
     * 2. 将二进制对照赫夫曼编码转成 原始字符串
     */

    /**
     *
     * @param huffmanCodes 赫夫曼编码
     * @param huffmanBytes 赫夫曼编码得到的字节数组
     * @return 原来的字符串对应的数组
     */
    private static byte[] decode(Map<Byte,String> huffmanCodes,byte[] huffmanBytes){
        //1.先得到huffmanBytes 对应的二进制字符串
        StringBuilder stringBuilder = new StringBuilder();
        //将byte数组转成二进制的字符串
        for (int i=0;i< huffmanBytes.length; i++){
            //判断是不是最后一个字节
            boolean flag = (i == huffmanBytes.length -1);
            stringBuilder.append(byteToBitString(!flag,huffmanBytes[i]));
        }
        //把字符串按照指定的赫夫曼编码进行解码
        //把赫夫曼编码表进行调换，因为反向查询 a-100  => 100-a
        Map<String,Byte> map = new HashMap<>();
        for (Map.Entry<Byte,String> entry : huffmanCodes.entrySet()){
            map.put(entry.getValue(),entry.getKey());
        }
        //创建一个集合存放byte
        List<Byte> list = new ArrayList<>();
        // i 可以理解成一个索引，不停扫秒 StringBuilder
        for (int i=0;i<stringBuilder.length();){
            int count =1;
            boolean flag = false;
            Byte b ;
            while (true){
                String key = "";
                if(stringBuilder.length()- i > 8){
                     key = stringBuilder.substring(i, i + count);
                }else {
                    //从后往前找，不确定最后这个不满8位的字节到底是几位
                    key = stringBuilder.substring(stringBuilder.length() - count);
                    flag = true;
                }
                //取出一个'1'/'0'

                b = map.get(key);
                if(null == b){
                    //说明没有匹配到
                    count ++;
                }else {
                    list.add(b);
                    break;
                }
            }
            //让i 直接移动到count
            i += count;
            if(flag){
                break;
            }
        }
        //当for循环结束后 list中就存放了所有的字符
        //把list中的数据放入到 byte[] 并返回
        byte[] b = new byte[list.size()];
        for (int i=0;i<b.length;i++){
            b[i] = list.get(i);
        }
        return b;
    }


    /**
     * 将一个byte 转成二进制的字符串
     * @param flag 标识 是否补高位，如果是true表示需要补高位
     * @param b byte字节
     * @return 对应字符串 (是按补码返回的，编码的时候也是按补码编码的)
     */
    private static String byteToBitString(boolean flag,byte b){
        //使用变量保存b
        int temp = b;
        //如果是正数，还需要补充高位
        // temp |= 256; 按位与 （256 = 1 0000 00000 | 1= 0000 0001） = 1 0000 0001
        // 最后一个字节不需要补高位
        if(flag){
            temp |= 256;
        }
        //返回的是int的二进制的补码
        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,"",stringBuilder);
        //根据赫夫曼编码 获取压缩后的赫夫曼编码字节数组
        return zip(bytes, huffmanCodes);
    }

    /**
     * 生成赫夫曼树对应的赫夫曼编码
     * 1. 将赫夫曼编码表存放在 Map<Byte,String>，形式如32-01 97-100  100-11000 等等
     * 2. 在生成赫夫曼编码时，需要去拼接路径  定义一个StringBuilder 存储叶子节点
     * */
    public static Map<Byte,String> huffmanCodes = new HashMap<>();
    public static StringBuilder stringBuilder = new StringBuilder();


    /**
     * 编写一个方法，将字符串对应的byte[] 数组，通过生成的赫夫曼编码表，返回一个赫夫曼编码 压缩后的byte[]
     * @param bytes 原始的字符串对应的byte[]
     * @param huffmanCodes 生成的赫夫曼编码
     * @return byte[] 赫夫曼编码处理后的byte[] 数组
     * huffmanCodeBytes[0] = 10101000(补码) => byte [ 推导 10101000 => 10101000 - 1 => 10100111(反码)
     * => 11011000 = -88]
     * huffmanCodeBytes[0] = -88
     */
    private static byte[] zip(byte[] bytes,Map<Byte,String> huffmanCodes){

        //1.先利用 huffmanCodes 将bytes转成 赫夫曼编码后的字符串
        StringBuilder stringBuilder = new StringBuilder();
        //遍历byte数组
        for (byte b : bytes){
            stringBuilder.append(huffmanCodes.get(b));
        }
        //System.out.println(stringBuilder);
        //将 字符串转成byte数组

        //统计返回的 huffmanCodes 的长度
        int len;
        if(stringBuilder.length() % 8 == 0){
            len = stringBuilder.length() / 8;
        }else{
            len = stringBuilder.length() / 8 + 1;
        }
        //创建存储压缩后的byte数组
        byte[] huffmanCodeBytes = new byte[len];
        //记录第几个byte
        int index = 0;
        //因为8位对应一个byte 所以步长就是8
        for (int i=0;i<stringBuilder.length();i+=8){
            String strByte;
            if(i+8>stringBuilder.length()){
                strByte = stringBuilder.substring(i);
            }else{
                strByte = stringBuilder.substring(i,i+8);
            }
            //将strByte 转成byte数组，放入到by
            huffmanCodeBytes[index] = (byte) Integer.parseInt(strByte,2);
            index++;
        }
        return huffmanCodeBytes;
    }


    /**
     * 功能 将传入的node节点的所有叶子结点的和夫曼编码得到并放入到  huffmanCodes 中
     * @param node 传入的节点
     * @param code 路径：左子节点是0，右子节点是1
     * @param stringBuilder 是用于拼接路径
     */
    private static void getCodes(Node node,String code,StringBuilder stringBuilder){

        StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
        //将code加入到StringBuilder2
        stringBuilder2.append(code);
        if (null != node){
            //判断当前node是叶子结点还是非叶子结点
            if(null == node.data){
                //非叶子结点 递归
                getCodes(node.left,"0",stringBuilder2);
                //向右递归
                getCodes(node.right,"1",stringBuilder2);
            }
            else {
                //说明是叶子节点
                //就表示找到了某个叶子结点的最后
                huffmanCodes.put(node.data,stringBuilder2.toString());
            }
        }


    }

    /**
     *
     * @param bytes 接收字节数组
     * @return 返回list集合
     */
    private static @NotNull List<Node> getNodes(byte @NotNull [] bytes){

        //1.创建一个list
        List<Node> nodes = new ArrayList<>();
        Map<Byte,Integer> counts = new HashMap<>();
        //存储每个byte出现的次数 -> map
        for (byte b : bytes) {
            counts.merge(b, 1, Integer::sum);
        }
        //把每个键值对转成node对象 加到nodes
        for (Map.Entry<Byte,Integer> entry : counts.entrySet()){
            nodes.add(new Node(entry.getKey(),entry.getValue()));
        }

        return nodes;
    }


    /**
     * 通过list 创建赫夫曼树
     * @param nodes node集合
     * @return Node
     */
    private static Node createHuffmanTree(@NotNull 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);
    }


}
class Node implements Comparable<Node>{

    /**
     * 存放数据本身，比如:'a' => 97 ' ' =>32
     */
    Byte data;

    /**
     * 数据出现的次数   -- 权重
     */
    int weight;

    Node left;

    Node right;

    public Node(Byte data, int weight) {
        this.data = data;
        this.weight = weight;
    }

    @Override
    public int compareTo(Node o) {
        return this.weight - o.weight;
    }

    @Override
    public String toString() {
        return "Node[ data="+data+",weight="+weight+"]";
    }

    /**
     * 前续遍历
     */
    public void preOrder(){
        System.out.println(this);
        if(null != this.left){
            this.left.preOrder();
        }
        if(null != this.right){
            this.right.preOrder();
        }
    }

}