赫夫曼树编码思路分析:(以一串字母举例)
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; } }