package com.haiyang.datastructure.huffmancode; import com.sun.org.apache.bcel.internal.generic.NEW; import java.io.*; import java.util.*; public class HuffmanCode { //标记最后一个数的位数 static int lastCode = 8; //用于存储哈夫曼编码 static MaphuffmanCodes = new HashMap (); //用于拼接哈夫曼编码 static StringBuilder stringBuilder = new StringBuilder(); public static void main(String[] args) { zipFile("C:\Users\haiyang\Pictures\草纸\3.jpg", "C:\Users\haiyang\Pictures\草纸\3.zip"); unZipFile("C:\Users\haiyang\Pictures\草纸\3.zip", "C:\Users\haiyang\Pictures\草纸\6.jpg"); } public static void unZipFile(String zipFile, String dstFile) { InputStream is = null; OutputStream os = null; ObjectInputStream ois = null; try { is = new FileInputStream(zipFile);//通过输入流读取压缩后文件 ois = new ObjectInputStream(is);//通过对象流读取压缩后文件和哈夫曼编码两部分 byte[] huffmanBytes = (byte[]) ois.readObject(); Map huffmanCodes = (Map ) ois.readObject(); byte[] decode = decode(huffmanCodes, huffmanBytes);//进行解压 os = new FileOutputStream(dstFile);//通过输出流保存解压后文件 os.write(decode);//写入解压后文件 } catch (Exception e) { e.printStackTrace(); } finally { try { os.close(); ois.close(); is.close(); } catch (IOException e) { System.out.println(e.getMessage()); } } } public static void zipFile(String srcFile, String dstFile) { FileInputStream is = null; FileOutputStream os = null; ObjectOutputStream oos = null; try { is = new FileInputStream(srcFile);//通过输入流读取文件 byte[] b = new byte[is.available()];//用于读取文件 is.read(b);//读取文件到byte[] 中 byte[] huffmanZip = huffmanZip(b);//进行压缩 os = new FileOutputStream(dstFile);//输出流保存压缩后文件 oos = new ObjectOutputStream(os);//因为需保存压缩后文件和哈夫曼编码两部分,使用对象流方便 *** 作 oos.writeObject(huffmanZip);//写入压缩后文件 oos.writeObject(huffmanCodes);//写入哈夫曼编码 } catch (Exception e) { e.printStackTrace(); } finally { try { is.close(); os.close(); oos.close(); } catch (IOException e) { e.printStackTrace(); } } } public static byte[] decode(Map huffmanCodes, byte[] bytes) { // StringBuilder stringBuilder = new StringBuilder(); for (int i = 0; i < bytes.length; i++) { byte b = bytes[i]; boolean flag = (i == bytes.length - 1); stringBuilder.append(byteToBitString(!flag, b)); } System.out.println(stringBuilder.length()); //将huffmanCodes 翻转便于比较 HashMap map = new HashMap<>(); for (Map.Entry entry : huffmanCodes.entrySet()) { map.put(entry.getValue(), entry.getKey()); } //存储比较完成的字符串 ArrayList list = new ArrayList<>(); for (int i = 0; i < stringBuilder.length(); ) { int count = 1; boolean flag = true; Byte b = null; while (flag) { String s = stringBuilder.substring(i, i + count); b = map.get(s); if (b == null) { count++; } else { flag = false; } } list.add(b); i += count; } byte[] bytes1 = new byte[list.size()]; for (int i = 0; i < list.size(); i++) { bytes1[i] = list.get(i); } return bytes1; } public static String byteToBitString(boolean flag, byte b) { int temp = b;//将字节转化为整数类型 temp |= 256;//整数需要补位 按位与256运算 1 0000 0000 | 0000 0001 => 1 0000 0001 String str = Integer.toBinaryString(temp);//将整数转化为二进制补码 if (flag) { return str.substring(str.length() - 8);//每个整数占4个字节,32位需取后八位 } else { return str.substring(str.length() - lastCode);//如果字节数组的最后一位位整数,解析时不需要补位 } } public static byte[] huffmanZip(byte[] bytes) { //调用getCodes方法将字节数组转化为结点类型 List nodes = getNodes(bytes); //创建哈夫曼树 Node huffmanTree = createHuffmanTree(nodes); //获取哈夫曼编码 Map codes = getCodes(huffmanTree); byte[] zip = zip(bytes, codes); return zip; } public static byte[] zip(byte[] bytes, Map huffmanCodes) { //将所有字节的哈夫曼编码拼接 StringBuilder stringBuilder = new StringBuilder(); for (byte b : bytes) { //遍历字节数组,进行哈夫曼编码拼接 stringBuilder.append(huffmanCodes.get(b)); } // System.out.println(stringBuilder.toString()); int len; //每8位代表一个字节 if (stringBuilder.length() % 8 == 0) { len = stringBuilder.length() / 8; } else { lastCode = stringBuilder.length() % 8; len = stringBuilder.length() / 8 + 1; } byte[] bys = 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); } else { strByte = stringBuilder.substring(i, i + 8); } bys[index] = (byte) Integer.parseInt(strByte, 2); index++; } return bys; } public static void getCodes(Node node, String code, StringBuilder stringBuilder) { StringBuilder stringBuilder1 = new StringBuilder(stringBuilder); stringBuilder1.append(code); if (node != null) { if (node.data == null) { //代表非叶子结点 getCodes(node.left, "0", stringBuilder1); getCodes(node.right, "1", stringBuilder1); } else { //如果是叶子结点,代表该字符的编码已拼接完成,加入到Map中 huffmanCodes.put(node.data, stringBuilder1.toString()); } } } public static Map getCodes(Node root) { if (root == null) { return null; } getCodes(root.left, "0", stringBuilder); getCodes(root.right, "1", stringBuilder); return huffmanCodes; } public static void preOrder(Node root) { if (root != null) { root.preOrder(); } else { System.out.println("树为空,无法遍历"); } } //将字节数组转化为结点类型 public static List getNodes(byte[] bytes) { ArrayList nodes = new ArrayList<>();//储存结点 HashMap map = new HashMap<>();//储存每种字节出现的次数 for (byte b : bytes) { //遍历数组记录每种字节出现的次数 Integer count = map.get(b); if (count == null) { map.put(b, 1); } else { map.put(b, count + 1); } } for (Map.Entry entry : map.entrySet()) { //遍历Map将每种字节及其出现的次数转化为结点 nodes.add(new Node(entry.getKey(), entry.getValue())); } return nodes; } public static Node createHuffmanTree(List nodes) { while (nodes.size() > 1) { //按weight升序排序 Collections.sort(nodes); //从结点列表nodes中选取两个最小的结点 Node leftNode = nodes.get(0); Node rightNode = nodes.get(1); //通过选取的结点构建一棵树,其根节点的weight为两个最小结点的和 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); } } class Node implements Comparable { //在给定的序列中,每种字符是一个data,weight代表每种字符出现堆得次数 Byte data; int weight; Node left; Node right; public Node(Byte data, int weight) { this.data = data; this.weight = weight; } @Override public String toString() { return "Node{" + "data=" + data + ", weight=" + weight + '}'; } //自定义比较器,通过weight进行升序排序 @Override public int compareTo(Node o) { return this.weight - o.weight; } //先序遍历 用于查看构建的大顶堆是否正确 public void preOrder() { System.out.println(this); if (this.left != null) { this.left.preOrder(); } if (this.right != null) { this.right.preOrder(); } } }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)