位置：首页-资讯-后端开发

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

2024-04-02 19:55

短信预约 -IT技能 免费直播动态提醒

赫夫曼编码基本介绍

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、需要先实现统计输入的字符串中各个字符的个数:


    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、创建赫夫曼树:


    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、根据创建的赫夫曼树进行字符串编码压缩:


    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、得到压缩后的赫夫曼编码长度(二进制位数):


    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[]


    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);
        //也可以用下面的方法获取长度
        
        //测试
        //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.*;
 

 
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));
 
    }
 
    
    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;
    }
 
    
    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());
            }
        }
    }
 
    
    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;
    }
 
    
    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);
    }
 
    
    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);
        //也可以用下面的方法获取长度
        
        //测试
        //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