Java利用哈夫曼编码实现字符串压缩

赫夫曼编码基本介绍

1) 赫夫曼编码也翻译为 哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式, 属于一种程序算法

2) 赫夫曼编码是赫哈夫曼树在电讯通信中的经典的应用之一。

3) 赫夫曼编码广泛地用于数据文件压缩。其压缩率通常在 20%～90%之间

4) 赫夫曼码是可变字长编码(VLC)的一种。Huffman 于 1952 年提出一种编码方法，称之为最佳编码

在通信领域中几种信息处理方式的区别（以字符串" i like like like java do you like a java"举例）:

第一种-定长编码:

第二种-变长编码:

第三种-赫夫曼编码:

传输的字符串:

1、 i like like like java do you like a java

2、 d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9 // 各个字符对应的个数

3、 按照上面字符出现的次数构建一颗赫夫曼树, 次数作为权值

构成赫夫曼树的步骤：

1) 从小到大进行排序, 将每一个数据，每个数据都是一个节点 ， 每个节点可以看成是一颗最简单的二叉树

2) 取出根节点权值最小的两颗二叉树

3) 组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和

4) 再将这颗新的二叉树，以根节点的权值大小 再次排序， 不断重复 1-2-3-4 的步骤，直到数列中，所有的数据都被处理，就得到一颗赫夫曼树

4、 根据赫夫曼树，给各个字符,规定编码 (前缀编码)， 向左的路径为 0 向右的路径为 1 ，编码

如下:

o: 1000 u: 10010 d: 100110 y: 100111 i: 101

a : 110 k: 1110 e: 1111 j: 0000 v: 0001  l: 001 : 01

5、 按照上面的赫夫曼编码，我们的"i like like like java do you like a java" 字符串对应的编码为 (注意这里我们使用的无损压缩)1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110 通过赫夫曼编码处理 长度为：133

通过以上三种信息处理方式可以对比看出赫夫曼编码的优越性。

以下给出实现哈夫曼编码需要的各个方法:

1、先创建节点对象:

// 为了排序，必须实现Comprable<>接口

public class Node implements Comparable<Node>{
    Byte data;
    int weight;
    Node left;
    Node right;

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

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

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

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

2、需要先实现统计输入的字符串中各个字符的个数: 

/**
     * //统计字符串中每个字符出现的次数和空格出现次数
     *
     * @param str 字符串
     * @return 返回一个排好序的Node集合
     */
    public static List<Node> totalCharCounts(String str) {

        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            Integer count = map.get(ch);
            if (count == null) {
                count = 0;
            }
            map.put(ch, count + 1);
        }
        //遍历map，将map中的数据存入Node节点中
        //先将map转为set集合
        Set<Map.Entry<Character, Integer>> mapSet = map.entrySet();
        //观察测试输出
        //System.out.println(mapSet);
        List<Node> nodeList = new ArrayList<>();
        //遍历set
        for (Map.Entry<Character, Integer> set : mapSet) {
            // 将map中的数据存入Node节点中
            Node node = new Node((byte) set.getKey().charValue(), set.getValue());
            // 将node存入集合中
            nodeList.add(node);
            //System.out.println(set.getKey() + " = " + set.getValue());
        }
        //排序
        Collections.sort(nodeList);
        //测试
        //System.out.println(nodeList);
        return nodeList;
    }

3、创建赫夫曼树:

/**
     * 创建huffman树
     *
     * @param nodeList 排好序的集合
     * @return 返回huffman树的根节点
     */
    public static Node createHuffmanTree(List<Node> nodeList) {
        //循环创建huffman树
        while (nodeList.size() > 1) {
            //1、每次取出集合中的前两个节点
            Node left = nodeList.get(0);
            Node right = nodeList.get(1);
            //2、将他们的权值相加构成一个新的节点并作为他们的父节点
            Node parent = new Node(null, left.weight + right.weight);
            parent.left = left;
            parent.right = right;
            //3、删除已经处理过的节点
            nodeList.remove(left);
            nodeList.remove(right);
            //4、将新的节点存入集合中
            nodeList.add(parent);
            //5、重新给集合排序,循环这5步即可，直到集合中只有一个节点，这就是huffman树的根节点
            Collections.sort(nodeList);
            //观察测试输出
            //System.out.println(nodeList);
        }
        //返回huffman树的根节点
        return nodeList.get(0);
    }

4、根据创建的赫夫曼树进行字符串编码压缩:

/**
     * 根据huffman树来进行数据编码压缩
     * 思路:
     * 1、只要向左子树走就代表0，向右子树走就代表1
     * 2、从头节点走到对于字符在的节点位置的路径对于的0和1组成的二进制编码就是压缩后该字符对于的编码
     * 3、需要定义一个StringBuffer来存储某个节点的路径对于的编码
     * 4、将赫夫曼编码表存放在Map<Byte,String>中
     *
     * @param node         huffman树的根节点
     * @param stringBuffer 用于拼接路径
     * @param code         路径：左子节点是0，右子节点是1
     * @return
     */
    private static void getHuffmanCompressionCode(Node node, String code, StringBuffer stringBuffer) {
        StringBuffer stringBuffer1 = new StringBuffer(stringBuffer);
        stringBuffer1.append(code);
        //如果为空，不进行处理
        if (node != null) {
            //判断node是叶子节点还是非叶子节点
            if (node.data == null) {
                //非叶子节点
                //向左递归
                getHuffmanCompressionCode(node.left, "0", stringBuffer1);
                //向右递归
                getHuffmanCompressionCode(node.right, "1", stringBuffer1);
            } else {
                //叶子节点
                //说明这条路走到尾了，将路径编码存入map中
                huffmanCodes.put(node.data, stringBuffer1.toString());
            }
        }
    }

5、得到压缩后的赫夫曼编码长度(二进制位数):

/**
     * @return 得到压缩后的赫夫曼编码大小
     */
    public static int getStrCodeSize() {
        int size = 0;
        //将两个map集合都转为set集合
        Set<Map.Entry<Character, Integer>> mapSet = map.entrySet();
        Set<Map.Entry<Byte, String>> huffmanMapSet = huffmanCodes.entrySet();
        //循环两个set集合
        for (Map.Entry<Character, Integer> set1 : mapSet) {
            for (Map.Entry<Byte, String> set2 : huffmanMapSet) {
                //如果两个set的key相同就将他们的value相乘,只是需要注意存储huffman编码中的是字符串，需要乘字符串的长度
                if ((byte) set1.getKey().charValue() == set2.getKey()) {
                    size = size + set1.getValue() * (set2.getValue().length());
                    //节约时间，之间退出内循环。因为不可能有一对多的关系。
                    break;
                }
            }
        }
        return size;
    }

6、编写一个方法，将字符串对应的byte[]数组，通过生成的赫夫曼编码表，返回一个赫夫曼编码压缩后的byte[]

/**
     * 编写一个方法，将字符串对应的 byte[] 数组，通过生成的赫夫曼编码表，返回一个赫夫曼编码 压缩后的byte[]
     *
     * @param bytes        这时原始的字符串对应的 byte[]
     * @param huffmanCodes 生成的赫夫曼编码 map
     * @return 返回赫夫曼编码处理后的 byte[]
     * 举例： String content = "i like like like java do you like a java"; =》 byte[] contentBytes = content.getBytes();
     * 返 回 的 是 字 符 串:
     * "1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000
     * 101111111100110001001010011011100"
     * => 对应的 byte[] huffmanCodeBytes ，即 8 位对应一个 byte,放入到 huffmanCodeBytes
     * huffmanCodeBytes[0] = 10101000(补码) => byte [推导 10101000=> 10101000 - 1 => 10100111(反
     * 码)=> 11011000(源码) = -88 ]
     */
    public static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
        //1、先利用赫夫曼编码表将传进来的bytes数组转为压缩后的编码
        StringBuffer stringBuffer1 = new StringBuffer();
        for (byte b : bytes) {
            stringBuffer1.append(huffmanCodes.get(b));
        }
        //输出字符串压缩成赫夫曼编码后对应的二进制编码
        //System.out.println("输出字符串压缩成赫夫曼编码后对应的二进制编码:" + stringBuffer1 + "长度为:" + stringBuffer1.length());

        //获取byte数组的长度，Math.ceil()表示向上取整
        int len = (int) Math.ceil(stringBuffer1.length()*1.0 / 8);
        //也可以用下面的方法获取长度
        /*if(stringBuffer1.length() % 8 == 0) {
            len = stringBuffer1.length() / 8;
        } else {
            len = stringBuffer1.length() / 8 + 1;
        }*/
        //测试
        //System.out.println(stringBuffer1.length());
        //System.out.println(len);
        byte[] huffmanBytes = new byte[len];
        int index = 0;
        for (int i = 0; i < stringBuffer1.length(); i = i + 8) {
            String strByte;
            if (i + 8 > stringBuffer1.length()) {
                //从i取到字符串最后一个字符
                strByte = stringBuffer1.substring(i);
            } else {
                //一次截取8个
                strByte = stringBuffer1.substring(i, i + 8);
            }
            //将 strByte 转成一个 byte,放入到 huffmanBytes中
            //该方法是将strByte对应的01字符串传换为十进制
            //第二个参数表示基数（radix）,表示转换为radix进制
            huffmanBytes[index] = (byte) Integer.parseInt(strByte, 2);
            index++;
        }
        return huffmanBytes;
    }

其实也可以不用写5中的方法，可以直接在6中输出stringBuffer1.length()就可以得到压缩后的二进制位数。不过也可以把5当作一种解决的算法。

以下给出完整的代码:

import java.util.*;

/**
 * 实现huffman编码
 */

public class HuffmanCode {

    //将赫夫曼编码表存放在Map<Byte,String>中
    public static Map<Byte, String> huffmanCodes = new HashMap<>();

    //需要定义一个StringBuffer来存储某个节点的路径对于的编码
    public static StringBuffer stringBuffer = new StringBuffer();

    //创建一个map，来保存每个字符以及他对应出现的次数
    public static Map<Character, Integer> map = new HashMap<>();

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        System.out.println("输入字符串:");
        //scanner.next()方法不能输入空格，例如输入: aaa bbb实际上只能接收到aaa,空格后面的字符串都接收不到
        //所以需要用scanner,nextLine()方法来接收字符串

        String str = scanner.nextLine();

        // 把输入的字符串转为byte数组，在byte数组中存储的是字符对应的ASCII码值
        byte[] strBytes = str.getBytes();
        System.out.println(str + ",压缩成赫夫曼编码前对应的byte数组:" + Arrays.toString(strBytes));

        //计算压缩前的字符串有多少位二进制数
        int compressionBeforeCodeSize = str.length() * 8 + str.length() - 1;
        System.out.println(str + ",压缩前的字符串大小:" + compressionBeforeCodeSize);

        //统计字符串中每个字符出现的次数和空格出现次数并存入Node节点中
        List<Node> nodeList = totalCharCounts(str);

        //创建huffman树
        Node root = createHuffmanTree(nodeList);

        //得到压缩后的编码
        getHuffmanCompressionCode(root, "", stringBuffer);

        //输出赫夫曼编码表
        System.out.println(str + ",对应的赫夫曼编码表:");
        System.out.println(huffmanCodes);

        //得到压缩后的字符串大小
        int compressionAfterCodeSize = getStrCodeSize();
        System.out.println(str + ",压缩后的字符串大小:" + compressionAfterCodeSize);

        //可以算出压缩率是多少
        double compressionRadio = (compressionBeforeCodeSize - compressionAfterCodeSize) * 1.0 / compressionBeforeCodeSize;
        System.out.println(str + ",压缩成赫夫曼编码的压缩率为:" + compressionRadio);

        byte[] bytes = zip(strBytes, huffmanCodes);
        System.out.println(str + ",压缩成赫夫曼编码后对应的byte数组:" + Arrays.toString(bytes));

    }

    /**
     * @return 得到压缩后的赫夫曼编码大小
     */
    public static int getStrCodeSize() {
        int size = 0;
        //将两个map集合都转为set集合
        Set<Map.Entry<Character, Integer>> mapSet = map.entrySet();
        Set<Map.Entry<Byte, String>> huffmanMapSet = huffmanCodes.entrySet();
        //循环两个set集合
        for (Map.Entry<Character, Integer> set1 : mapSet) {
            for (Map.Entry<Byte, String> set2 : huffmanMapSet) {
                //如果两个set的key相同就将他们的value相乘,只是需要注意存储huffman编码中的是字符串，需要乘字符串的长度
                if ((byte) set1.getKey().charValue() == set2.getKey()) {
                    size = size + set1.getValue() * (set2.getValue().length());
                    //节约时间，之间退出内循环。因为不可能有一对多的关系。
                    break;
                }
            }
        }
        return size;
    }

    /**
     * 根据huffman树来进行数据编码压缩
     * 思路:
     * 1、只要向左子树走就代表0，向右子树走就代表1
     * 2、从头节点走到对于字符在的节点位置的路径对于的0和1组成的二进制编码就是压缩后该字符对于的编码
     * 3、需要定义一个StringBuffer来存储某个节点的路径对于的编码
     * 4、将赫夫曼编码表存放在Map<Byte,String>中
     *
     * @param node         huffman树的根节点
     * @param stringBuffer 用于拼接路径
     * @param code         路径：左子节点是0，右子节点是1
     * @return
     */
    private static void getHuffmanCompressionCode(Node node, String code, StringBuffer stringBuffer) {
        StringBuffer stringBuffer1 = new StringBuffer(stringBuffer);
        stringBuffer1.append(code);
        //如果为空，不进行处理
        if (node != null) {
            //判断node是叶子节点还是非叶子节点
            if (node.data == null) {
                //非叶子节点
                //向左递归
                getHuffmanCompressionCode(node.left, "0", stringBuffer1);
                //向右递归
                getHuffmanCompressionCode(node.right, "1", stringBuffer1);
            } else {
                //叶子节点
                //说明这条路走到尾了，将路径编码存入map中
                huffmanCodes.put(node.data, stringBuffer1.toString());
            }
        }
    }

    /**
     * //统计字符串中每个字符出现的次数和空格出现次数
     *
     * @param str 字符串
     * @return 返回一个排好序的Node集合
     */
    public static List<Node> totalCharCounts(String str) {

        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            Integer count = map.get(ch);
            if (count == null) {
                count = 0;
            }
            map.put(ch, count + 1);
        }
        //遍历map，将map中的数据存入Node节点中
        //先将map转为set集合
        Set<Map.Entry<Character, Integer>> mapSet = map.entrySet();
        //观察测试输出
        //System.out.println(mapSet);
        List<Node> nodeList = new ArrayList<>();
        //遍历set
        for (Map.Entry<Character, Integer> set : mapSet) {
            // 将map中的数据存入Node节点中
            Node node = new Node((byte) set.getKey().charValue(), set.getValue());
            // 将node存入集合中
            nodeList.add(node);
            //System.out.println(set.getKey() + " = " + set.getValue());
        }
        //排序
        Collections.sort(nodeList);
        //测试
        //System.out.println(nodeList);
        return nodeList;
    }

    /**
     * 创建huffman树
     *
     * @param nodeList 排好序的集合
     * @return 返回huffman树的根节点
     */
    public static Node createHuffmanTree(List<Node> nodeList) {
        //循环创建huffman树
        while (nodeList.size() > 1) {
            //1、每次取出集合中的前两个节点
            Node left = nodeList.get(0);
            Node right = nodeList.get(1);
            //2、将他们的权值相加构成一个新的节点并作为他们的父节点
            Node parent = new Node(null, left.weight + right.weight);
            parent.left = left;
            parent.right = right;
            //3、删除已经处理过的节点
            nodeList.remove(left);
            nodeList.remove(right);
            //4、将新的节点存入集合中
            nodeList.add(parent);
            //5、重新给集合排序,循环这5步即可，直到集合中只有一个节点，这就是huffman树的根节点
            Collections.sort(nodeList);
            //观察测试输出
            //System.out.println(nodeList);
        }
        //返回huffman树的根节点
        return nodeList.get(0);
    }

    /**
     * 编写一个方法，将字符串对应的byte[]数组，通过生成的赫夫曼编码表，返回一个赫夫曼编码压缩后的byte[]
     *
     * @param bytes        这时原始的字符串对应的 byte[]
     * @param huffmanCodes 生成的赫夫曼编码 map
     * @return 返回赫夫曼编码处理后的 byte[]
     * 举例： String content = "i like like like java do you like a java"; =》 byte[] contentBytes = content.getBytes();
     * 返 回 的 是 字 符 串:
     * "1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000
     * 101111111100110001001010011011100"
     * => 对应的 byte[] huffmanCodeBytes ，即 8 位对应一个 byte,放入到 huffmanCodeBytes
     * huffmanCodeBytes[0] = 10101000(补码) => byte [推导 10101000=> 10101000 - 1 => 10100111(反
     * 码)=> 11011000(源码) = -88 ]
     */
    public static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
        //1、先利用赫夫曼编码表将传进来的bytes数组转为压缩后的编码
        StringBuffer stringBuffer1 = new StringBuffer();
        for (byte b : bytes) {
            stringBuffer1.append(huffmanCodes.get(b));
        }
        //输出字符串压缩成赫夫曼编码后对应的二进制编码
        //System.out.println("输出字符串压缩成赫夫曼编码后对应的二进制编码:" + stringBuffer1 + "长度为:" + stringBuffer1.length());

        //获取byte数组的长度，Math.ceil()表示向上取整
        int len = (int) Math.ceil(stringBuffer1.length()*1.0 / 8);
        //也可以用下面的方法获取长度
        /*if(stringBuffer1.length() % 8 == 0) {
            len = stringBuffer1.length() / 8;
        } else {
            len = stringBuffer1.length() / 8 + 1;
        }*/
        //测试
        //System.out.println(stringBuffer1.length());
        //System.out.println(len);
        byte[] huffmanBytes = new byte[len];
        int index = 0;
        for (int i = 0; i < stringBuffer1.length(); i = i + 8) {
            String strByte;
            if (i + 8 > stringBuffer1.length()) {
                //从i取到字符串最后一个字符
                strByte = stringBuffer1.substring(i);
            } else {
                //一次截取8个
                strByte = stringBuffer1.substring(i, i + 8);
            }
            //将 strByte 转成一个 byte,放入到 huffmanBytes中
            //该方法是将strByte对应的01字符串传换为十进制
            //第二个参数表示基数（radix）,表示转换为radix进制
            huffmanBytes[index] = (byte) Integer.parseInt(strByte, 2);
            index++;
        }
        return huffmanBytes;
    }

}

以下是我的测试结果输出:

输入的字符串: i like like like java do you like a java

输入的字符串: asdjkj ;lkjsadlkj kj ()dasd

到此这篇关于Java利用哈夫曼编码实现字符串压缩的文章就介绍到这了,更多相关Java字符串压缩内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！