2021-09-07

本文主要是介绍2021-09-07，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

赫夫曼树编码思路分析:(以一串字母举例)
1) 分析每个字母出现的次数, 空格等也算. 以出现的次数作为权值, 建立赫夫曼树
2) 定义向左路径为0, 向右路径为1(由于编码的字符都是叶子节点, 所以不会出现二义性)
赫夫曼压缩后的数据解思路:
1) 将 huffmanCodeByte数组, 重新先转成字符串, 1010100110111101111010…这样的形式
即,压缩文件对应的二进制的字符串
2) 创建个新的map表, 将赫夫曼编码表反转, 再通过get()方法, 找到对应的value值, 将value值放入数组中返回即可得到需要的源文件
编码代码实现:
在这里调用了count, 在后面的解码程序中用到

public class HuffmanCode {
    static int count = 0;// 用于判断最后一位的编码省略了几个0!!!(解压时用)
    /**
     * 生成赫夫曼树对应的赫夫曼编码!!!
     * 思路:
     * 1) 将赫夫曼编码表存放在Map<Byte,String> 形式如下
     * 32->01,97->100,100->11000.....等等
     * 2) 在生成赫夫曼编码表时候, 需要去拼接路径, 所以需要创建一个StringBuilder,
     * 存储某个叶子结点的路径
     */
    static Map<Byte, String> huffmanCodes = new HashMap<>();
    static StringBuilder stringBuilder = new StringBuilder();

    // 使用一个方法, 将压缩的方法封装起来, 便于调用
    public static byte[] huffmanZip(String data) {
        // 1.将原始数据转为byte数据
        byte[] bytes = data.getBytes();
        // 2.获取出现过的字节, 以及字节出现过的次数
        List<Node1> list = getList(bytes);// 其中list存储的都是node1节点类的对象
        // 3.根据list创建赫夫曼树
        Node1 huffmanTree = createHuffmanTree(list);
        // 4.生成此赫夫曼树对应的赫夫曼编码
        Map<Byte, String> huffmanCodes = getCodes(huffmanTree);
        // 5.调用最后的压缩方法, 将字符串按照生成的赫夫曼编码对应的数值封装在一个byte[]中
        byte[] huffmanCodeBytes = zip(bytes, huffmanCodes);
        return huffmanCodeBytes;
    }

    /**
     * 编写一个方法, 将一个字符串对应的byte数组, 通过生成的 赫夫曼编码表,
     * 返回一个赫夫曼编码压缩后的byte数组
     *
     * @param bytes        此时原始字符串对应的byte数组
     * @param huffmanCodes 生成的赫夫曼编码表
     * @return 赫夫曼处理后的byte[]
     * (重要)举例:
     * 按照上面的赫夫曼编码，我们的"i like like like java do you like a java"
     * 字符串对应的编码为 (注意这里我们使用的无损压缩):
     * 10101001101111011110100110111101111010011011110111101000011
     * 00001110011001111000011001111000100100100110111101111011100100001100001110
     * =>对应的byte[] huffmanCodeBytes,即8位对应一个byte放入byte[]中
     * huffmanCodeBytes[0] = 10101001(由首位对应负数,且是补码)=>[推导 10101000 -1=>10100111(反码)=>11011000=>-88]
     */
    private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
        // 1.利用huffmanCodes将 bytes转变成赫夫曼编码对应的字符串
        StringBuilder sb = new StringBuilder();
        for (byte b : bytes) {
            sb.append(huffmanCodes.get(b));
        }
        System.out.println(sb);
        // 2.将sb对应的字符串转化成byte数组
        // 统计返回的byte[] huffmanCodeBytes的长度
//        int len;
//        if (sb.length()%8==0)
//            len = sb.length()/8;
//        else
//            len = sb.length()/8+1;
        int len = (sb.length() + 7) / 8;
        // 3.创建个存储压缩后的byte数组
        byte[] huffmanCodeBytes = new byte[len];
        // 因为是每八位对应一个byte, 所以步长为8
        for (int i = 0, j = 0; i < sb.length(); i += 8, j++) {
            String strByte;
            if (i + 8 > sb.length()) {// 到最后且不够8位
                strByte = sb.substring(i);
                /*
                 * 此时需要判断最后一位省略了几个0(解码时用到)
                 * 不然以0111举例, 转成十进制后是7
                 * 在解码时7转成2进制就变为了111,导致出现异常之类的情况
                 */
                while (Integer.parseInt(strByte.substring(count, count + 1)) == 0) {
                    // 当一个字母权值较大时, 且出现在最后一位时, 对应的路径可能都是0
                    // 所以要加个break语句
                    if (count + 1 == strByte.length()) {
                        count++;
                        break;
                    }
                    count++;
                }
            } else
                strByte = sb.substring(i, i + 8);
            huffmanCodeBytes[j] = (byte) Integer.parseInt(strByte, 2);
        }

        return huffmanCodeBytes;
    }

    // 包装getCodes()
    private static Map<Byte, String> getCodes(Node1 root) {
        if (root == null)
            return null;
        getCodes(root, "", stringBuilder);
        return huffmanCodes;
    }

    /**
     * 将传入的node节点的所有叶子节点的赫夫曼编码得到, 并放入到HuffmanCodes中
     *
     * @param node          传入结点, 默认从根结点
     * @param code          路径: 左子结点是0, 右子结点是1
     * @param stringBuilder 用于拼接路径
     */
    private static void getCodes(Node1 node, String code, StringBuilder stringBuilder) {
        StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
        // 将code传入stringBuilder2中
        stringBuilder2.append(code);
        if (node != null) {
            if (node.data == null) {// 非叶子结点
                getCodes(node.left, "0", stringBuilder2);
                getCodes(node.right, "1", stringBuilder2);
            } else {// 说明是叶子结点, 表示找到了某个叶子结点的最后
                huffmanCodes.put(node.data, stringBuilder2.toString());
            }
        }
    }

    /**
     * 接收一个字节数组, 返回一个list, 其中存放出现过的字节, 以及出现过的子节的个数
     */
    private static List<Node1> getList(byte[] bytes) {
        // 1.创建一个ArrayList
        ArrayList<Node1> node1s = new ArrayList<>();
        // 2.遍历bytes, 统计并存储每一个bytes出现的次数
        HashMap<Byte, Integer> map = new HashMap<>();
        for (byte aByte : bytes) {
            // 说明之前没存储过
            map.merge(aByte, 1, Integer::sum);
        }
        // 3.把每个键值对转成node对象, 并假如集合中
        for (Map.Entry<Byte, Integer> entry : map.entrySet()) {
            node1s.add(new Node1(entry.getKey(), entry.getValue()));
        }
        return node1s;
    }

    // 创建约瑟夫树
    private static Node1 createHuffmanTree(List<Node1> nodes) {
        while (nodes.size() > 1) {
            Collections.sort(nodes);
            Node1 leftNode = nodes.get(0);
            Node1 rightNode = nodes.get(1);
            Node1 node = new Node1(null, leftNode.weight + rightNode.weight);
            node.left = leftNode;
            node.right = rightNode;
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            nodes.add(node);
        }
        return nodes.get(0);
    }
}

解码代码实现:

public class HuffmanUncompress {
    public static void main(String[] args) {
        byte[] decode = decode();
        System.out.println(new String(decode));
    }
    // 赫夫曼压缩文件对应的编码表
    static Map<Byte, String> huffmanCodes = HuffmanCode.huffmanCodes;

    // 将方法封装在一起, 传入压缩后的数据就可以直接解压
    public static byte[] decode() {
        // 1.因为没有压缩后的文件, 创建一个压缩后的文件
        String content = "i lssssss";
        byte[] codes = HuffmanCode.huffmanZip(content);
        // 2.将压缩后的文件转为String字符串
        // 即还原到1010101000这样的二进制形式
        String code = bytesToString(codes);
        // 3.通过这个二进制String字符串
        byte[] decode = decode(huffmanCodes, code);
        return decode;
    }

    /**
     * 将一个二进制转变为string字符串
     * @param bytes 赫夫曼编码得到的数组
     * @return 原来的字符串对应的数组
     */
    private static String bytesToString(byte[] bytes) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < bytes.length; i++) {
            int temp = bytes[i];
            boolean flag = (i + 1) < bytes.length || temp < 0;
            if (flag) {
                temp |= 256;
                String str = Integer.toBinaryString(temp);
                sb.append(str.substring(str.length() - 8));
            } else {
                String str = Integer.toBinaryString(temp);
                // 此处是重点, 由于太笨之前被这里卡了半天才想明白-.-
                for (int j = 0; j < HuffmanCode.count; j++) {
                    sb.append(0);
                }
                sb.append(str);
            }
        }
        return new String(sb);
    }

    /**
     * 先创建一个map, 倒序存放赫夫曼编码表,
     * 再通过新的map将字符串中的数值循环匹配
     * 直到匹配成功添加到StringBuilder对象中
     * 返回StringBuilder对象
     */
    private static byte[] decode(Map<Byte, String> huffmanCodes, String codes) {
        Map<String, Byte> reverseHuffmanCodes = new HashMap<>();
        for (Map.Entry<Byte, String> byteStringEntry : huffmanCodes.entrySet()) {
            reverseHuffmanCodes.put(byteStringEntry.getValue(), byteStringEntry.getKey());
        }
        // 创建一个list用于存放数据
        List<Byte> list = new ArrayList<>();
        for (int i = 0; i < codes.length(); ) {
            int count = 1;// 计数器
            boolean flag = true;
            Byte b = null;
            while (flag) {
                String key = codes.substring(i, i + count);
                b = reverseHuffmanCodes.get(key);
                if (b == null) {
                    count++;
                } else {
                    flag = false;
                }
            }
            i += count;// i移动到count
            list.add(b);
        }
        byte[] code = new byte[list.size()];
        for (int i = 0; i < code.length; i++) {
            code[i] = list.get(i);
        }
        return code;
    }
}

这篇关于2021-09-07的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！