package cn.guizimo.huffmancode; import java.io.*; import java.util.*; /** * @author guizimo * @date 2020/8/8 11:55 上午 */ public class HuffmanCode { public static void main(String[] args) { String zipFile = "d://123.png"; String dstFile = "d://123.zip"; zipFile(zipFile, dstFile);; System.out.println("压缩成功!"); } public static void unZipFile(String zipFile, String dstFile) { InputStream is = null; ObjectInputStream ois = null; OutputStream os = null; try { is = new FileInputStream(zipFile); ois = new ObjectInputStream(is); byte[] huffmanBytes = (byte[]) ois.readObject(); Map<Byte, String> huffmanCodes = (Map<Byte, String>) ois.readObject(); byte[] bytes = huffmanUnzip(huffmanCodes, huffmanBytes); os = new FileOutputStream(dstFile); os.write(bytes); } catch (Exception e) { System.out.println(e.getMessage()); } finally { try { os.close(); ois.close(); is.close(); } catch (Exception e2) { System.out.println(e2.getMessage()); } } } public static void zipFile(String srcFile, String dstFile) { OutputStream os = null; ObjectOutputStream oos = null; FileInputStream is = null; try { is = new FileInputStream(srcFile); byte[] b = new byte[is.available()]; is.read(b); byte[] huffmanBytes = huffmanZip(b); os = new FileOutputStream(dstFile); oos = new ObjectOutputStream(os); oos.writeObject(huffmanBytes); oos.writeObject(huffmanCodes); } catch (Exception e) { System.out.println(e.getMessage()); } finally { try { is.close(); oos.close(); os.close(); } catch (Exception e) { System.out.println(e.getMessage()); } } } //哈夫曼解压 private static byte[] huffmanUnzip(Map<Byte, String> huffmanCodes, byte[] huffmanBytes) { StringBuilder stringBuilder = new StringBuilder(); for (int i = 0; i < huffmanBytes.length; i++) { byte b = huffmanBytes[i]; boolean flag = (i == huffmanBytes.length - 1); stringBuilder.append(byteToBitString(!flag, b)); } //解码,反向编码表 HashMap<String, Byte> map = new HashMap<>(); for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) { map.put(entry.getValue(), entry.getKey()); } //根据编码扫描到对应的ASCLL码对应的字符 List<Byte> list = new ArrayList<>(); for (int i = 0; i < stringBuilder.length(); ) { int count = 1; boolean flag = true; Byte b = null; while (flag) { String key = stringBuilder.substring(i, i + count); b = map.get(key); if (b == null) { count++; } else { flag = false; } } list.add(b); i += count; } byte b[] = new byte[list.size()]; for (int i = 0; i < b.length; i++) { b[i] = list.get(i); } return b; } //转化二进制 private static String byteToBitString(boolean flag, byte b) { int temp = b; if (flag) { temp |= 256; } String str = Integer.toBinaryString(temp); if (flag) { return str.substring(str.length() - 8); } else { return str; } } //哈夫曼编码压缩 private static byte[] huffmanZip(byte[] bytes) { List<Node> nodes = getNodes(bytes); //哈夫曼树 Node huffmanTree = createHuffmanTree(nodes); //哈夫曼编码表 Map<Byte, String> huffmanCodes = getCodes(huffmanTree); //哈夫曼编码 byte[] zip = zip(bytes, huffmanCodes); return zip; } //压缩 private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) { StringBuilder stringBuilder = new StringBuilder(); for (byte b : bytes) { stringBuilder.append(huffmanCodes.get(b)); } int len; if (stringBuilder.length() % 8 == 0) { len = stringBuilder.length() / 8; } else { len = stringBuilder.length() / 8 + 1; } byte[] by = new byte[len]; int index = 0; for (int i = 0; i < stringBuilder.length(); i += 8) { String strByte; if (i + 8 > stringBuilder.length()) { strByte = stringBuilder.substring(i); by[index] = (byte) Integer.parseInt(strByte, 2); index++; } else { strByte = stringBuilder.substring(i, i + 8); by[index] = (byte) Integer.parseInt(strByte, 2); index++; } } return by; } static Map<Byte, String> huffmanCodes = new HashMap<Byte, String>(); static StringBuilder stringBuilder = new StringBuilder(); //重载 private static Map<Byte, String> getCodes(Node root) { if (root == null) { return null; } getCodes(root.left, "0", stringBuilder); getCodes(root.right, "1", stringBuilder); return huffmanCodes; } //获取哈夫曼编码 private static void getCodes(Node node, String code, StringBuilder stringBuilder) { StringBuilder builder = new StringBuilder(stringBuilder); builder.append(code); if (node != null) { if (node.data == null) { //递归 getCodes(node.left, "0", builder); getCodes(node.right, "1", builder); } else { huffmanCodes.put(node.data, builder.toString()); } } } //前序遍历 private static void preOrder(Node root) { if (root != null) { root.preOrder(); } else { System.out.println("哈夫曼树为空"); } } //生成哈夫曼树 private static Node createHuffmanTree(List<Node> nodes) { while (nodes.size() > 1) { Collections.sort(nodes); Node leftNode = nodes.get(0); Node rightNode = nodes.get(1); Node parent = new Node(null, leftNode.weight + rightNode.weight); parent.left = leftNode; parent.right = rightNode; nodes.remove(leftNode); nodes.remove(rightNode); nodes.add(parent); } return nodes.get(0); } //接收字节数组 private static List<Node> getNodes(byte[] bytes) { List<Node> nodes = new ArrayList<>(); Map<Byte, Integer> counts = new HashMap<>(); for (byte b : bytes) { Integer count = counts.get(b); if (count == null) { counts.put(b, 1); } else { counts.put(b, count + 1); } } //遍历map for (Map.Entry<Byte, Integer> entry : counts.entrySet()) { nodes.add(new Node(entry.getKey(), entry.getValue())); } return nodes; } } class Node implements Comparable<Node> { Byte data; int weight; //字符出现的次数 Node left; Node right; //前序遍历 public void preOrder() { System.out.println(this); if (this.left != null) { this.left.preOrder(); } if (this.right != null) { this.right.preOrder(); } } public Node(Byte data, int weight) { this.data = data; this.weight = weight; } @Override public int compareTo(Node o) { //从小到大排序 return this.weight - o.weight; } @Override public String toString() { return "Node{" + "data=" + data + ", weight=" + weight + '}'; } }
package cn.guizimo.huffmancode; import java.io.*; import java.util.*; /** * @author guizimo * @date 2020/8/8 11:55 上午 */ public class HuffmanCode { public static void main(String[] args) { String zipFile = "d://Uninstall.zip"; String dstFile = "d://Uninstall2.xml"; unZipFile(zipFile, dstFile); System.out.println("解压成功!"); } public static void unZipFile(String zipFile, String dstFile) { InputStream is = null; ObjectInputStream ois = null; OutputStream os = null; try { is = new FileInputStream(zipFile); ois = new ObjectInputStream(is); byte[] huffmanBytes = (byte[]) ois.readObject(); Map<Byte, String> huffmanCodes = (Map<Byte, String>) ois.readObject(); byte[] bytes = huffmanUnzip(huffmanCodes, huffmanBytes); os = new FileOutputStream(dstFile); os.write(bytes); } catch (Exception e) { System.out.println(e.getMessage()); } finally { try { os.close(); ois.close(); is.close(); } catch (Exception e2) { System.out.println(e2.getMessage()); } } } public static void zipFile(String srcFile, String dstFile) { OutputStream os = null; ObjectOutputStream oos = null; FileInputStream is = null; try { is = new FileInputStream(srcFile); byte[] b = new byte[is.available()]; is.read(b); byte[] huffmanBytes = huffmanZip(b); os = new FileOutputStream(dstFile); oos = new ObjectOutputStream(os); oos.writeObject(huffmanBytes); oos.writeObject(huffmanCodes); } catch (Exception e) { System.out.println(e.getMessage()); } finally { try { is.close(); oos.close(); os.close(); } catch (Exception e) { System.out.println(e.getMessage()); } } } //哈夫曼解压 private static byte[] huffmanUnzip(Map<Byte, String> huffmanCodes, byte[] huffmanBytes) { StringBuilder stringBuilder = new StringBuilder(); for (int i = 0; i < huffmanBytes.length; i++) { byte b = huffmanBytes[i]; boolean flag = (i == huffmanBytes.length - 1); stringBuilder.append(byteToBitString(!flag, b)); } //解码,反向编码表 HashMap<String, Byte> map = new HashMap<>(); for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) { map.put(entry.getValue(), entry.getKey()); } //根据编码扫描到对应的ASCLL码对应的字符 List<Byte> list = new ArrayList<>(); for (int i = 0; i < stringBuilder.length(); ) { int count = 1; boolean flag = true; Byte b = null; while (flag) { String key = stringBuilder.substring(i, i + count); b = map.get(key); if (b == null) { count++; } else { flag = false; } } list.add(b); i += count; } byte b[] = new byte[list.size()]; for (int i = 0; i < b.length; i++) { b[i] = list.get(i); } return b; } //转化二进制 private static String byteToBitString(boolean flag, byte b) { int temp = b; if (flag) { temp |= 256; } String str = Integer.toBinaryString(temp); if (flag) { return str.substring(str.length() - 8); } else { return str; } } //哈夫曼编码压缩 private static byte[] huffmanZip(byte[] bytes) { List<Node> nodes = getNodes(bytes); //哈夫曼树 Node huffmanTree = createHuffmanTree(nodes); //哈夫曼编码表 Map<Byte, String> huffmanCodes = getCodes(huffmanTree); //哈夫曼编码 byte[] zip = zip(bytes, huffmanCodes); return zip; } //压缩 private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) { StringBuilder stringBuilder = new StringBuilder(); for (byte b : bytes) { stringBuilder.append(huffmanCodes.get(b)); } int len; if (stringBuilder.length() % 8 == 0) { len = stringBuilder.length() / 8; } else { len = stringBuilder.length() / 8 + 1; } byte[] by = new byte[len]; int index = 0; for (int i = 0; i < stringBuilder.length(); i += 8) { String strByte; if (i + 8 > stringBuilder.length()) { strByte = stringBuilder.substring(i); by[index] = (byte) Integer.parseInt(strByte, 2); index++; } else { strByte = stringBuilder.substring(i, i + 8); by[index] = (byte) Integer.parseInt(strByte, 2); index++; } } return by; } static Map<Byte, String> huffmanCodes = new HashMap<Byte, String>(); static StringBuilder stringBuilder = new StringBuilder(); //重载 private static Map<Byte, String> getCodes(Node root) { if (root == null) { return null; } getCodes(root.left, "0", stringBuilder); getCodes(root.right, "1", stringBuilder); return huffmanCodes; } //获取哈夫曼编码 private static void getCodes(Node node, String code, StringBuilder stringBuilder) { StringBuilder builder = new StringBuilder(stringBuilder); builder.append(code); if (node != null) { if (node.data == null) { //递归 getCodes(node.left, "0", builder); getCodes(node.right, "1", builder); } else { huffmanCodes.put(node.data, builder.toString()); } } } //前序遍历 private static void preOrder(Node root) { if (root != null) { root.preOrder(); } else { System.out.println("哈夫曼树为空"); } } //生成哈夫曼树 private static Node createHuffmanTree(List<Node> nodes) { while (nodes.size() > 1) { Collections.sort(nodes); Node leftNode = nodes.get(0); Node rightNode = nodes.get(1); Node parent = new Node(null, leftNode.weight + rightNode.weight); parent.left = leftNode; parent.right = rightNode; nodes.remove(leftNode); nodes.remove(rightNode); nodes.add(parent); } return nodes.get(0); } //接收字节数组 private static List<Node> getNodes(byte[] bytes) { List<Node> nodes = new ArrayList<>(); Map<Byte, Integer> counts = new HashMap<>(); for (byte b : bytes) { Integer count = counts.get(b); if (count == null) { counts.put(b, 1); } else { counts.put(b, count + 1); } } //遍历map for (Map.Entry<Byte, Integer> entry : counts.entrySet()) { nodes.add(new Node(entry.getKey(), entry.getValue())); } return nodes; } } class Node implements Comparable<Node> { Byte data; int weight; //字符出现的次数 Node left; Node right; //前序遍历 public void preOrder() { System.out.println(this); if (this.left != null) { this.left.preOrder(); } if (this.right != null) { this.right.preOrder(); } } public Node(Byte data, int weight) { this.data = data; this.weight = weight; } @Override public int compareTo(Node o) { //从小到大排序 return this.weight - o.weight; } @Override public String toString() { return "Node{" + "data=" + data + ", weight=" + weight + '}'; } }
原文链接:https://www.cnblogs.com/guizimo/p/13457996.html