huffman编码实现数据压缩

#huffman编码压缩

huffman编码压缩的代码如下：

主方法 public static void main(String[] args) { String content = "I like java, do you like java ? We can study it together and make progress."; byte[] contentBytes = content.getBytes(); // 输出需要压缩的字符串 System.out.println("压缩前" + content + "\t长度为" + content.length()); // 获取哈夫曼编码压缩后对应的字节数组 byte[] huffmanBytes = getHuffmanCodesBytes(contentBytes); System.out.println("哈夫曼压缩后字节数组" + Arrays.toString(huffmanBytes) + "\t长度为" + huffmanBytes.length); // 解压哈夫曼编码 byte [] huffmanDecodeBytes = decode(huffmanBytes, huffmanCodes); System.out.println("解压后得到的原始数据为：" + new String(huffmanDecodeBytes)); }

2.统计内容的字符数量，构建List<Node>为哈夫曼树做准备

//将统计字符个数的方法封装 public static List<Node> countCharNum(byte [] bytes){ //统计每个字符出现的次数，保存到map中 Map<Byte,Integer> count = new HashMap<>(); for(byte b :bytes){ Integer num = count.get(b); if(num == null){ //当map中还没有保存响应的字符时，那么就先放进去，数量为1 count.put(b, 1); }else{ //如果有，直接增加数值即可.但是注意不是num++,而是再添加一次，相同的key值在map中会覆盖 count.put(b, count.get(b)+1); } } List<Node> nodes = new ArrayList<>(); //遍历map，创建node对象放在list中 for(Map.Entry<Byte, Integer> entry : count.entrySet()){ nodes.add(new Node(entry.getKey(),entry.getValue())); } return nodes; }

3.构建huffman树

//构建哈夫曼树 public static Node createHuffmanTree(byte [] bytes){ //统计每个字符出现的次数 List<Node> nodes = countCharNum(bytes); // 构建哈夫曼树 while (nodes.size() > 1) { // 排序 Collections.sort(nodes); // 取出最小的两个值，构建最简二叉树 Node left = nodes.get(0); Node right = nodes.get(1); // 辅助节点（非叶子节点）没有自己的data值 Node parent = new Node(null, left.weight + right.weight); parent.left = left; parent.right = right; // 删除使用完的节点 nodes.remove(left); nodes.remove(right); // 添加父节点到list中 nodes.add(parent); } //返回root节点 return nodes.get(0); }

4.根据哈夫曼树，找到每个叶子节点路径，获得huffman编码

static Map<Byte,String> huffmanCodes = new HashMap<>(); //寻找叶子节点并拼接路径--使用StringBuilder类拼接字符串效率高，线程不安全，适用单线程， //重载一下路径编码方法--只需要传哈夫曼树的根节点就行 public static Map<Byte, String> getPathCodes(Node node) { StringBuilder stringBuilder = new StringBuilder(); if (node != null) { // 遍历左子树 if (node.left != null) { getPathCodes(node.left, "0", stringBuilder); } // 遍历右子树 if (node.right != null) { getPathCodes(node.right, "1", stringBuilder); } } else { System.out.println("树为空"); } return huffmanCodes; } /** * @param node 传入的节点，需要判断data，且帮助递归 * @param code 路径编码，左边"0" 右边"1" * @param stringBuilder 递归需要，未找到叶子节点之前，需要保留引用变量拼接串对象一直拼接 */ public static void getPathCodes(Node node,String code,StringBuilder stringBuilder){ //每一个叶子节点都需要自己的一个路径，所以重新建立一个StringBuilder, //并且获取递归前当前的编码--回溯所以不会导致整个拼接一直延长!!!!!!!!!!!!! StringBuilder currentStrBuilder = new StringBuilder(stringBuilder); //拼接当前的编码，传进来左-0，右-1，再向下判断 currentStrBuilder.append(code); //判断当前是否是叶子节点--用过data值 if(node.data==null){ //data=null 说明非叶子节点，还需要继续递归寻找 if(node.left!=null){ getPathCodes(node.left, "0", currentStrBuilder); } //遍历右节点 if(node.right!=null){ getPathCodes(node.right, "1", currentStrBuilder); } }else{ //不是，即data有值，那就是叶子节点，我们带字符的节点 //将其放在map中 huffmanCodes.put(node.data, currentStrBuilder.toString()); } }

5.通过huffman编码压缩成相应的byte数组

// 将压缩过程的方法全部封装 public static byte[] getHuffmanCodesBytes(byte[] bytes) { // 获取哈夫曼树 Node root = createHuffmanTree(bytes); // 获取哈夫曼路径编码--为了简化传的参数，那就重载一下方法 // getHuffmanCodes(root, "",stringBuilder); // 其实返回值就是全局的，这里再接收一下，增加阅读性 Map<Byte, String> pathCodes = getPathCodes(root); //获取哈夫曼编码压缩后的字节数组 byte[] huffmanCodesBytes = huffmanZip(bytes, pathCodes); return huffmanCodesBytes; } // 方便解码的 时候判断解码的正确性--最后一位少位的化补齐0.将拼接的字符串设置成静态变量 static StringBuilder huffmanCodesStr = new StringBuilder(); //通过路编码获得哈夫曼编码 public static byte[] huffmanZip(byte[] bytes, Map<Byte, String> pathCodes) { for (byte b : bytes) { huffmanCodesStr.append(pathCodes.get(b)); } // 输出哈夫曼编码字符串 System.out.println("哈夫曼编码字符串为" + huffmanCodesStr.toString() + "长度为：" + huffmanCodesStr.length()); // 只是转换成字符串传输是不对的，之前长度40 现在133，变长了不合理。所以要每8位保存为一个byte，放到数组中，返回 // 创建byte数组进行接收-每8位算一个 // 计算长度 int len; len = (huffmanCodesStr.length() + 7) / 8; // 很好的算法 // len = huffmanCodesStr.length() % 8 == 0 ? huffmanCodesStr.length()/8:huffmanCodesStr.length()/8+1; byte[] huffmanCodesBytes = new byte[len]; int index = 0; // 遍历字符串，步长为8 // 创建接收子串的变量 String subStr; for (int i = 0; i < huffmanCodesStr.length(); i += 8) { // 注意变量越界 if (i + 8 > huffmanCodesStr.length()) { subStr = huffmanCodesStr.substring(i);// 只写起始索引，就是直接到末尾 } else { subStr = huffmanCodesStr.substring(i, i + 8);// 注意子串切割左闭右开，所以右边界要大1 } // 将截取下来的子串放到byte数组中--注意解析时，radix参数设置成2 表示解析成二进制，默认为10进制 huffmanCodesBytes[index] = (byte) Integer.parseInt(subStr, 2); index++; } return huffmanCodesBytes; }