利用赫夫曼编码来压缩数据

利用赫夫曼算法来压缩数据

压缩文件是我们经常碰到的文件类型，一般在windows上 rar zip 7z这几种格式是最常见的。因为格式的不同他们的原理也同样不同。这里介绍的是使用赫夫曼算法进行简单的压缩数据。

首先要来了解一下赫夫曼树是什么。

赫夫曼树

给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

简单的来说赫夫曼树就是WPL最小的树。

WPL

计算WPL首先要知道这个树的权值，然后还要知道这个树的高度(所谓高度就是到根节点的经过的节点的个数)。

想要一个树是最优二叉树(WPL最小的树)，我们就要尽量把权值较大的数据放在靠近跟节点的地方，把权值较小的数据放在远离根节点的地方。

如何构造赫夫曼树

首先我们要新建一个节点，因为赫夫曼树要比较权值的大小，所以这个节点类还要实现Comparable接口.

// ：让Node是实现Comparable接口，使之可以排序
class Node implements Comparable<Node>{
    private int value;
    private Node left;
    private Node right;

    public Node(int value) {
        this.value = value;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public Node getLeft() {
        return left;
    }

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

    public Node getRight() {
        return right;
    }

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

    @Override
    public String toString() {
        return "[value=" + value + "]";
    }

    //：返回 -1 0 1
    @Override
    public int compareTo(Node o) {
        //： 表示从小到大排序
        return this.value - o.value;
        //： 表示从大到小的排序是 return o.value - this.value
    }
}

这样一个节点就创建好了。

接下来就可以来生成一个赫夫曼树了

class HuffmanTree {
    public static Node createHuffmanTree(int[] arr) {
        List<Node> nodes = new ArrayList<Node>();
        for (int val : arr) {
            nodes.add(new Node(val));
        }
        while(nodes.size() > 1) {
            Collections.sort(nodes);

            Node leftNode = nodes.get(0); // ：最小的那个节点
            Node rightNode = nodes.get(1); //：第二小的那个节点

            Node parentNode = new Node(leftNode.getValue() + rightNode.getValue());

            parentNode.setLeft(leftNode);
            parentNode.setRight(rightNode);

            nodes.remove(leftNode);
            nodes.remove(rightNode);
            nodes.add(parentNode);
        }
        //：实现了Comparable，可以进行排序
        return nodes.get(0);    
    }
}

由代码可见，上面的算法的步骤是：

1. 先将所有的节点放入到一个ArrayList中。
2. 先将这个ArrayList排序，找到最小两个节点，同时new一个新的节点，使其左节点指向稍微小的那个节点，右节点指向稍微大的那个节点。
3. 从ArrayList中去除刚才取出的两个节点，放入新的节点。
4. 循环第二步和第三步，知道ArrayList中就剩下最后一个节点。这个节点就是赫夫曼树的根节点

这个算法还是蛮容易理解的，刚才所有的节点都是赫夫曼树的叶子节点，所有的非叶子节点都是我们新生成的。通过上面的这个算法，我们就能轻松的得到一个赫夫曼树。

赫夫曼编码

计算机中的文件都是以二进制的格式存放的。我们先以字符串来举例。

java java java is good good but cpp cpp is best best

上面的这段话，在计算机中储存也是以二进制的文件进行储存的。我们知道一个字符对应了一个八位的byte，也就是一个ascii。那上面的数据在计算机中储存就是n*8bit。

这就是最直接的编码，每8位对应一个字符。

但是不难发现上面的字符串中存在不少的重复的字符。

j出现了3次，a出现了六次，空格出现了11次。

如果我们按照这些字符出现的顺序对其重新进行编码，不是就节省了不少的内存了吗？

空格编为0，a编为1， o编为10， p编为11.。。。

但是这样也带来了更大的问题，比如说计算机中的11解码成aa还是p呢？？也就是说这样的编码会代码混乱，这样的编码不是一个前缀编码。前缀编码需要满足这样的条件，任何一个码不能是另外的码的前缀。

这些字符出现的顺序对其重新进行编码这种思路是对的，但是如何采取最优的措施呢？

这不难想到上面说的赫夫曼树，字符出现的顺序就是字符的权重，构造一颗赫夫曼树或许能够解决我们的问题。

利用字符串来构造赫夫曼树

首先我们要构造一个新的节点

class NewNode implements Comparable<NewNode>{
    private Byte data;// 字母
    private int weight;// 出现了多少次

    private NewNode left;
    private NewNode right;

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

    public Byte getData() {
        return data;
    }

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

    public int getWeight() {
        return weight;
    }

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

    public NewNode getLeft() {
        return left;
    }

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

    public NewNode getRight() {
        return right;
    }

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

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

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

    public void preOrder() {
        System.out.println(this);
        if (this.left != null) {
            this.left.preOrder();
        }

        if (this.right != null) {
            this.right.preOrder();
        }
    }
}

然后我们还需要统计每个字符出现的次数，将结果放入一个ArrayList中

    /**
     * 由原始字节数组生成对应的集合
     * @param bytes 原始字节数组
     * @return 数值加权重的对应集合
     */
    public static ArrayList<NewNode> getNodes(byte[] bytes){
        ArrayList<NewNode> nodes = new ArrayList<NewNode>();

        //：使用map[key, value]遍历统计每个字符出现的次数
        HashMap<Byte, Integer> counts = new HashMap<Byte, Integer>();
        for (byte b : bytes) {
            Integer count = counts.get(b);
            if (count == null) {
                counts.put(b, 1);
            }else {
                counts.put(b, count+1);
            }
        }

        //：把键值对转为NewNode对象，并放入ArrayList中
        for (Map.Entry<Byte, Integer> entry : counts.entrySet()) {
            nodes.add(new NewNode(entry.getKey(), entry.getValue()));
        }

        return nodes;
    }

这样这个ArrayList中就存放了字符和他的权重了。

然后我们可以利用上面的方法来构造一颗胡夫曼树。

/**
     * 生成一个赫夫曼树
     * @param nodes 由原始字节数组形成的集合
     * @return 赫夫曼数的根节点
     */
    public static NewNode createHuffmanTree(ArrayList<NewNode> nodes) {

        while (nodes.size() > 1) {
            Collections.sort(nodes);

            NewNode leftNode = nodes.get(0);
            NewNode rightNode = nodes.get(1);

            NewNode parentNode = new NewNode(null, leftNode.getWeight() + rightNode.getWeight());
            parentNode.setLeft(leftNode);
            parentNode.setRight(rightNode);

            nodes.remove(leftNode);
            nodes.remove(rightNode);
            nodes.add(parentNode);
        }

        return nodes.get(0);
    }

这样一颗赫夫曼树就构建好了，但是如何得到我们之前说的那个最优的前缀编码呢？？？

很简单当我们从一个节点走向他的左节点的时候，我们为编码加上0，向右走的时候加上1，因为赫夫曼树中的所有的非叶子节点都是null，有意义的仅仅是叶子节点。叶子节点是没有子节点的，所有这样生成的赫夫曼编码就是一种前缀编码。而且他也是最优的前缀编码。

获取赫夫曼编码

/**
     * 获取赫夫曼编码表
     * @param node 赫夫曼树的根节点
     * @param huffmanCodes 用来储存赫夫曼编码的map
     * @param code 左走是0 右走是1
     * @param stringBuilder 用来连接0和1
     */
    public static void getCodes(NewNode node, HashMap<Byte, String> huffmanCodes,
                                String code, StringBuilder stringBuilder) {
        StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
        stringBuilder2.append(code);
        if (node != null) {
            if (node.getData() == null) {
                getCodes(node.getLeft(), huffmanCodes, "0", stringBuilder2);
                getCodes(node.getRight(), huffmanCodes, "1", stringBuilder2);
            }else {
                huffmanCodes.put(node.getData(), stringBuilder2.toString());
            }
        }
    }

可以给这个方法一些默认的参数

public static void getCodes(NewNode node, HashMap<Byte, String> huffmanCodes){
        getCodes(node, huffmanCodes, "", new StringBuilder());
    }

这样我们就得到了赫夫曼编码表。得到了赫夫曼编码我们就可以对数据进行压缩了。

压缩字符串

/**
       *  使用赫夫曼编码压缩字符数组的长度
     * @param contentBytes 要进行压缩的字符数组
     * @param huffmanCodes 传入一个哈希Map，传出的就是 对应的赫夫曼表Map。可用于之后的解压！
     * @return 返回压缩后的字节数组
     */
    public static byte[] zip(byte[] contentBytes, HashMap<Byte, String> huffmanCodes) {
        ArrayList<NewNode> nodes = HuffmanTree.getNodes(contentBytes);
        NewNode root = HuffmanTree.createHuffmanTree(nodes);

        HuffmanTree.getCodes(root, huffmanCodes);

        String codes = HuffmanTree.huffmanCodes(contentBytes, huffmanCodes);
//        System.out.println(codes);

        int len = (codes.length() + 7)/8;
        byte[] by = new byte[len];


        for (int i = 0, index=0; i < codes.length(); i+=8) {
            String strBytes;
            if (i+8 > codes.length()) {
                strBytes = codes.substring(i);
            }else {
                strBytes = codes.substring(i, i+8);
            }
            by[index] = (byte) Integer.parseInt(strBytes, 2);
            index++;
        }
        return by;
    }

上面的代码需要注意的是code（10100010011….)的长度不一定是8的倍数，最后的一个字符串可能是没有8位的，所以我们要进行一次判断。

至此，我们已经完成了压缩的所有的工作。进入主方法进行一次测试。

压缩前的长度：52
压缩后的长度：24
压缩率：53.84615384615385%
解压数据： java java java is good good but cpp cpp is best best
是否解压成功：true

赫夫曼编码表如下所示，可见确实是前缀编码。

{32=00, 97=010, 98=0110, 99=10101, 100=11100, 101=11101, 103=11110, 105=11111, 106=0111, 111=1011, 112=1100, 115=1101, 116=1000, 117=10100, 118=1001}

生成的二进制补码如下所示，这个一看就比原来的少多了，毕竟这个字符中我估计加入了不少重复的字符。

01110101001010000111010100101000011101010010100011111110100111101011101111100001111010111011111000001101010010000010101110011000010101110011000011111110100011011101110110000001101110111011000

解压字符串

首先我们需要将一个byte转为一个二进制补码类型的字符串

/**
     * 将一个byte转为一个二进制的字符串
     * @param flag 是不是最后一个不满8位的byte 看是否需要按位与来补位 true代表需要补高位， false代表不需要补高位
     * @param b
     * @return 按补码返回的 正数的补码就是原码，负数的补码是反码+1
     */
    private static String byteToBitString(boolean flag, byte b) {
        int temp = b;
        if (flag) {
            temp |= 256;// 256: 1 0000 0000
        }

        String str = Integer.toBinaryString(temp);//:返回二进制的补码

        if(flag) {
            return str.substring(str.length()-8);//：只是取得后面的八位
        }else {
            return str;
        }
    }

同样的，我们要考虑到最后几位的问题。还有补码的有关的操作我也在上面注释清楚了。

下面就可以来解压了

    /**
     * 解压之前使用赫夫曼编码的数据
     * @param contentBytes 压缩之后的字节流
     * @param huffmanCodes 之前压缩的时候使用的赫夫曼编码map
     * @return 解压之后的字节数组
     */
    public static byte[] unzip(byte[] contentBytes, HashMap<Byte, String> huffmanCodes) {
        StringBuilder stringBuilder = new StringBuilder();

        for (int i = 0; i < contentBytes.length; i++) {
            byte b = contentBytes[i];
            boolean flag = (i != contentBytes.length-1);
            stringBuilder.append(byteToBitString(flag, b));
        }

//        System.out.println(stringBuilder.toString());

        HashMap<String, Byte> reverseMap = new HashMap<String, Byte>();
        for (Map.Entry<Byte, String> val : huffmanCodes.entrySet()) {
            reverseMap.put(val.getValue(), val.getKey());
        }

        int i=0;
        int count = 1;
        ArrayList<Byte> arrayList = new ArrayList<Byte>();
        while (i < stringBuilder.length() && i+count<=stringBuilder.length()) {
            Byte b = null ;
            while (i+count <= stringBuilder.length()) {
                String str = stringBuilder.substring(i, i+count);
                b = reverseMap.get(str);
                if (b == null) {
                    count++;
                }else {
                    i += count;
                    count = 1;
                    break;
                }
            }
            arrayList.add(b);
        }
        byte[] resultBytes = new byte[arrayList.size()];

        for (int j = 0; j < resultBytes.length; j++) {
            if (arrayList.get(j) == null) {
                break;
            }
            resultBytes[j] = arrayList.get(j);
        }

        return resultBytes;
    }

上面将赫夫曼编码进行了对调键值，这样更有利于后面的解压。通过扫描的方式逐个进行配对。

至此，压缩和解压字符串的操作就都已经完成了。。。

等等，，不是将压缩和解压文件的吗，怎么只讲了字符串？？？

其实刚才我们处理时并不是字符串，而是一个byte[]数组，我们只是把字符串转为了一个byte[]数组进行处理了。而任何文件都是以字节进行储存的，所以说这个解压和压缩的方法不仅适用于这个字符串还适用于各种各样的文件。如文本文件，视频，图片等，不过压缩的效率怎么样就不能保证了。只能说重复的越多，压缩的效率越高。对于文件的处理就是简单的加上Java当中IO流罢了。

直接上代码吧。

    /**
     * 使用赫夫曼编码来压缩文件
     * @param srcFile 要压缩的文件的原地址
     * @param dstFile 压缩后的文件的地址
     */
    public static void zipFile(String srcFile, String dstFile) {
        FileInputStream is = null;
        FileOutputStream os = null;
        ObjectOutputStream oos = null;

        try {
            is = new FileInputStream(srcFile);
            byte[] b = new byte[is.available()];
            is.read(b);
            HashMap<Byte, String> huffmanCodes = new HashMap<Byte, String>();
            byte[] zipcontent = zip(b, huffmanCodes);
//            System.out.println(huffmanCodes);
//            System.out.println(new String(zipcontent).substring(1,10));
            os = new FileOutputStream(dstFile);
            oos = new ObjectOutputStream(os);
            //：以对象流的形式写入， 方便之后的解码
            oos.writeObject(zipcontent);
            oos.writeObject(huffmanCodes);

        } catch (Exception e) {
            System.out.println(e.getMessage());
        } finally {
            try {
                is.close();
                os.close();
                oos.close();
            } catch (IOException e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }

        }
    }

需要注意的是：使用ObjecOutpuStream使用对象流的方式将对象写入文件中,利于后面解压的时候提取数据。注意：赫夫曼编码表需要写入到文件中,不然就没办法解压了！

/**
     * 使用赫夫曼编码来解压文件
     * @param srcFile 需要解压的文件地址
     * @param dstFile 解压后的文件地址
     */
    @SuppressWarnings("unchecked")
    public static void unzipFile(String srcFile, String dstFile) {
        FileInputStream is = null;
        ObjectInputStream ois = null;
        FileOutputStream os = null;
        try {
            is = new FileInputStream(srcFile);
            ois = new ObjectInputStream(is);
            byte[] zipBytes = (byte[]) ois.readObject();
            HashMap<Byte, String> huffmanCodes = (HashMap<Byte, String>) ois.readObject();
//            System.out.println(huffmanCodes);
//            System.out.println(new String(zipBytes).substring(1,10));
            byte[] unzipBytes = unzip(zipBytes, huffmanCodes);
            os = new FileOutputStream(dstFile);
            os.write(unzipBytes);
        } catch (Exception e) {
            System.out.println(e.getMessage());
            e.printStackTrace();
//            System.out.println(e.getStackTrace());
        } finally {
            try {
                if (is!=null) {
                    is.close();
                }
                if (ois!=null) {
                    ois.close();
                }
                if (os!=null) {
                    os.close();
                }
            } catch (IOException e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }

        }
    }

小结

总的来说，上面所提供的压缩和解压文件的方式还是非常简陋的，不过还是足以让我们来了解压缩文件的本质是什么。所谓的zip 7z rar无损压缩都是采用的这个思路，利用重复！如果没用大量的重复，而是杂乱无规则的话，就是神仙来了都压缩不了1kb…

​ ———— Hony Sher 7/17/2019