赫夫曼树及其编码压缩与解码的实现

1. 从小到大对所有数据进行排序，
2. 取出权值最小的两颗二叉树并组成一颗新二叉树，新的二叉树的权值为这两颗二叉树的和
3. 对新二叉树以根节点的权值大小重新进行排序。
4. 重复上述步骤直到所有节点都经过处理。

public class HuffmanTree { public static void main(String[] args) { int[] arr = {13, 7, 8, 3, 29, 6, 1}; Node root = createHuffmanTree(arr); root.preOrder(); } public static Node createHuffmanTree(int[] arr){ List<Node> nodes = new ArrayList<>(); for (int value : arr) { nodes.add(new Node(value)); } while (nodes.size() > 1) { //对二叉树进行排序 Collections.sort(nodes); //取出两个最小的节点（一个节点也可以看为最小的二叉树） Node left = nodes.get(0); Node right = nodes.get(1); //构建新二叉树 Node parent = new Node(left.value + right.value); parent.left = left; parent.right = right; nodes.remove(left); nodes.remove(right); //将最新构建的二叉树加入其中 nodes.add(parent); } return nodes.get(0); } } /** * 实现Comparable接口是为了方便节点的排序 */ class Node implements Comparable<Node>{ public Node left; public Node right; public int value; public Node(int value){ this.value = value; } @Override public String toString() { return "Node{" + "value=" + value + '}'; } @Override public int compareTo(Node o) { //当前节点小于 return this.value - o.value; } public void preOrder(){ System.out.println(this); if (this.left != null){ System.out.print("左子树:"); this.left.preOrder(); } if (this.right != null){ System.out.print("右子树:"); this.right.preOrder(); } } }

public class Huffman { public static void main(String[] args) { String str = "i like like like java do you like a java"; byte[] bytes = str.getBytes(); List<Node> codes = getCodes(bytes); Node huffmanTree = createHuffmanTree(codes); // huffmanTree.preOrder(); System.out.println("赫夫曼编码表："); getHuffmanCodes(huffmanTree, "", stringBuilder); System.out.println(huffmanCodes); byte[] zip = zip(bytes, huffmanCodes); System.out.println("压缩结果" + Arrays.toString(zip)); } //将赫夫曼编码表存入map中 private static Map<Byte,String> huffmanCodes = new HashMap<>(); //使用StringBuilder是为了方便获取这个字符的详细编码 private static StringBuilder stringBuilder = new StringBuilder(); /** * 获取赫夫曼编码表 * 向左值为0，向右值为1 * @param node * @param code * @param stringBuilder */ public static void getHuffmanCodes(Node node,String code,StringBuilder stringBuilder){ //在原基础上获取 StringBuilder st = new StringBuilder(stringBuilder); st.append(code); if (node.data == null){ if (node.left != null){ getHuffmanCodes(node.left, "0", st); } if (node.right != null) getHuffmanCodes(node.right, "1", st); }else { huffmanCodes.put(node.data, st.toString()); } } //对内容进行压缩 public static byte[] zip(byte[] bytes, Map<Byte,String> huffmanCodes){ StringBuilder builder = new StringBuilder(); for (byte b : bytes) { builder.append(huffmanCodes.get(b)); } int len = builder.length() % 8 ==0 ? builder.length()/8 : builder.length()/8 + 1; int index = 0;//index用于记录byte的下标 byte[] fileZip = new byte[len]; for (int i = 0;i < builder.length();i += 8){ int end = Math.min((i + 8), builder.length()); //将builder.substring(i, end)转换为byte，二进制转换为十进制 fileZip[index++] = (byte) Integer.parseInt(builder.substring(i, end), 2); } return fileZip; } //将文本内容转换为节点 public static List<Node> getCodes(byte[] bytes) { List<Node> nodes = new ArrayList<>(); //查询并保存每个字节出现的次数 Map<Byte, Integer> huffmanCodes = new HashMap<>(); for (byte b : bytes) { Integer i = huffmanCodes.get(b); if(i == null){ huffmanCodes.put(b, 1); }else{ huffmanCodes.put(b, i+1); } } //转换为Node集合 for (Map.Entry<Byte, Integer> entry : huffmanCodes.entrySet()) { nodes.add(new Node(entry.getKey(), entry.getValue())); } return nodes; } //通过转换的节点集合转换为赫夫曼树 public static Node createHuffmanTree(List<Node> nodes) { while(nodes.size() > 1){ //进行排序 Collections.sort(nodes); //取出最小的两颗树 Node left = nodes.get(0); Node right = nodes.get(1); //进行构建最新的树 Node parent = new Node(null, left.weight + right.weight); parent.left = left; parent.right = right; //删掉原最小的两棵树 nodes.remove(left); nodes.remove(right); //将最新的树添加进去 nodes.add(parent); } return nodes.get(0); } } class Node implements Comparable<Node>{ public Byte data; public int weight; public Node left; public Node right; public Node(Byte data, int weight) { this.data = data; this.weight = weight; } public void preOrder(){ System.out.println(this); if (this.left != null){ System.out.println("左："); this.left.preOrder(); } if (this.right != null) { System.out.println("右："); this.right.preOrder(); } } @Override public int compareTo(Node o) { return this.weight - o.weight; } @Override public String toString() { return "Node{" + "data=" + data + ", weight=" + weight + '}'; } }

1. 将byte十进制数组还原为原二进制所对应的字符串
2. 根据二进制字符串通过创建的赫夫曼编码表，进行还原。

//这里的byte值为压缩过的值 public static byte[] decode(byte[] bytes, Map<Byte,String> huffmanCodes){ // 添加空值检查 if (bytes == null || huffmanCodes == null || huffmanCodes.isEmpty()) { return new byte[0]; } // 构建二进制字符串 StringBuilder binaryStr = new StringBuilder(); for (int i = 0; i < bytes.length; i++) { boolean isLast = (i == bytes.length - 1); binaryStr.append(BinToString(!isLast, bytes[i])); } // 反转编码表 Map<String, Byte> reverseMap = new HashMap<>(); for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) { reverseMap.put(entry.getValue(), entry.getKey()); } // 解码 List<Byte> result = new ArrayList<>(); StringBuilder currentCode = new StringBuilder(); for (int i = 0; i < binaryStr.length(); i++) { currentCode.append(binaryStr.charAt(i)); Byte decodedByte = reverseMap.get(currentCode.toString()); if (decodedByte != null) { result.add(decodedByte); currentCode.setLength(0); } } // 转换为字节数组 byte[] source = new byte[result.size()]; for (int i = 0; i < result.size(); i++) { source[i] = result.get(i); } return source; } //将压缩的byte转换为原字符串的byte //flag的作用是：首先执行 bytes |= 256，将第9位设为1（256的二进制是100000000） public static String BinToString(boolean flag,int bytes){ if(flag){ bytes |= 256; } String binaryString = Integer.toBinaryString(bytes); if(flag){ return binaryString.substring(binaryString.length() - 8); }else { return binaryString; } }