vlambda博客
学习文章列表

/** * Node 实现 Comparable 是为了让Node 对象持续排序 Collections 集合排序 */public class Node implements Comparable<Node>{ private Byte data;//存放十进制的 Ascill 码，比 'a' 字符，那么 Ascill 码就是97 private int weight;//权值 private Node left;//左孩子 private Node right;//右孩子 @Override public int compareTo(Node arg0) { // 从小到大排序 return this.weight - arg0.weight; } public Node(Byte data, int weight) { super(); this.data = data; this.weight = weight; }  public Byte getData() { return data; }  public Node getLeft() { return left; } public void setLeft(Node left) { this.left = left; } public Node getRight() { return right; } public void setRight(Node right) { this.right = right; }  public int getWeight() { return weight; }
}

public class Test { Node root;  //拼接赫夫曼树的节点的路径，节点的左路径用“0” 表示，右路径用“1”表示 StringBuilder sb = new StringBuilder();  public static void main(String[] args) { Test test = new Test(); test.compressFile("C:\\Users\\86188\\Desktop\\cc\\file.txt", "C:\\Users\\86188\\Desktop\\cc\\file.zip"); }  private void compressFile(String srcFilePath, String desFilePath) { // 初始化输入输出流 FileInputStream is = null; FileOutputStream os = null; ObjectOutputStream oos = null;
 try { // 读取文件字节码 is = new FileInputStream(srcFilePath);  //文件里面的原始字节数组 byte[] bytes = new byte[is.available()]; is.read(bytes); // 构造赫夫曼编码表 Map<Byte, String> pathMap = new HashMap<>();  //通过赫夫曼编码表转换成字节数组 byte[] huffmanBytes = huffumanZip(bytes, pathMap);  // 写数据到目标文件中, 作为压缩文件 os = new FileOutputStream(desFilePath); oos = new ObjectOutputStream(os);  ////将 赫夫曼编码表 保存到 路径为desFilePath的文件中 oos.writeObject(pathMap);  //将 赫夫曼编码表转换成的字节数组 保存到 路径为desFilePath的文件中 oos.writeObject(huffmanBytes); oos.flush(); } catch (Exception e) { e.printStackTrace(); } finally { try { if (is != null) { is.close(); } if (os != null) { os.close(); } if (oos != null) { oos.close(); } } catch (IOException e) { e.printStackTrace(); } }
 }  private byte[] huffumanZip(byte[] bs,Map<Byte,String> huffumanCodes) { List<Node> list = getNode(bs);  //创建赫夫曼树 root = createHuffmanTree(list);  //生成赫夫曼编码表，将 赫夫曼编码 存放到 huffumanCodes 中 getCodes(root, "", sb,huffumanCodes);  /** * 该方法通过赫夫曼编码得到对应的二进制编码， * 最后通过压缩二进制编码得到 对应的赫夫曼编码字节数组 */ byte[] bytes = zip(bs,huffumanCodes);  //对应的赫夫曼编码字节数组 return bytes; }  /** * 该方法通过赫夫曼编码得到对应的二进制编码， * 最后通过压缩二进制编码得到 对应的赫夫曼编码字节数组 *  */ private byte[] zip(byte[] bytes,Map<Byte, String> heffumanCodes) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < bytes.length; i++) { byte b = bytes[i]; sb.append(heffumanCodes.get(b)); } int length = 0; if (sb.length() % 8 == 0) { length = sb.length() / 8; } else { length = sb.length() / 8 + 1; }  /** * 创建压缩后的 byte数组 */ byte[] bytes2 = new byte[length];  /** * 记录 bytes2 的索引 */ int num = 0;  for (int i = 0; i < sb.length(); i += 8) { String stringByte ; if (i + 8 >= sb.length()) { stringByte = sb.substring(i,sb.length()); } else { stringByte = sb.substring(i,i + 8); } bytes2[num] = (byte) Integer.parseInt(stringByte, 2);  num++; } return bytes2; }  //生成赫夫曼编码表 /** *  * @param node 传入的节点 * @param code 节点的左路径用“0” 表示，右路径用“1”表示 * @param sb 拼接code * @return */ private void getCodes(Node node,String code,StringBuilder sb,Map<Byte, String> huffumanCodes) { StringBuilder sb2 = new StringBuilder(sb);  //将code 加入到 sb2 中 sb2.append(code); if (node != null) {  //非叶子节点 if (node.getData() == null) {  //向左递归处理 getCodes(node.getLeft(), "0", sb2,huffumanCodes);  //向右递归处理 getCodes(node.getRight(), "1", sb2,huffumanCodes);  //是叶子节点 } else { huffumanCodes.put(node.getData(), sb2.toString()); } } }  private List<Node> getNode(byte[] bs) { ArrayList<Node> list = new ArrayList<Node>();  //统计byte出现的次数 Map<Byte,Integer> map = new HashMap<Byte,Integer>();  for (int i = 0; i<bs.length; i++) { Integer count = map.get(bs[i]);  //第一次存放该字节 if (count == null) { map.put(bs[i],1); } else { map.put(bs[i], count + 1); } }  for (Map.Entry<Byte, Integer> entry : map.entrySet()) { Byte data = entry.getKey(); int weight = entry.getValue(); Node node = new Node(data,weight); list.add(node); } return list; }  //创建赫夫曼树 private Node createHuffmanTree(List<Node> list) { while (list.size() > 1) {
 // 排序，从小到大排序 Collections.sort(list);
 // System.out.println("list = " + list);
 /** * 这个一定是权值最小的节点 */ Node minNode = list.get(0);
 /** * 除了 minNode 节点，该节点就是权值最小的节点，只是该节点比 minNode 节点大， 比其他节点都小 */ Node secondMinNode = list.get(1);
 /** * 构建一棵新的二叉树 */ Node parentNode = new Node(null,minNode.getWeight() + secondMinNode.getWeight()); parentNode.setLeft(minNode); parentNode.setRight(secondMinNode);
 /** * 从 list 集合中删除2棵已经构建成一棵二叉树的2个节点 */ list.remove(minNode); list.remove(secondMinNode);
 /** * 将新的二叉树的父节点加入到 list 集合中 */ list.add(parentNode); }
 /** * 构建完哈夫曼树后，list 集合中的第一个节点肯定是根节点 */ return list.get(0); }
}

decodeDecimal(boolean isNeedSub, int encodeByte)decodeBinaryStr(byte[] encodeBytes)reverseMap(Map<Byte, String> pathMap)doDecodeContent(String binaryStr, Map<String, Byte> pathByteMap)decodeContent(String binaryStr, Map<Byte, String> pathMap) decode(byte[] encodeBytes, Map<Byte, String> pathMap)decompress(String srcFilePath, String desFilePath)

 /** * 文件解压 * * @param srcFilePath 压缩文件路径 * @param desFilePath 解压文件路径 */ private void decompress(String srcFilePath, String desFilePath) { FileInputStream is = null; ObjectInputStream ois = null; FileOutputStream os = null;
 try { is = new FileInputStream(srcFilePath); ois = new ObjectInputStream(is);  // 读取赫夫曼编码表 Map<Byte, String> pathMap = (Map<Byte, String>) ois.readObject(); byte[] bytes = (byte[]) ois.readObject();  // 解压为原始的字节数组，也就是 file.txt 文件内容直接转换的字节数组 byte[] needBytes = decode(bytes, pathMap);  os = new FileOutputStream(desFilePath); os.write(needBytes); os.flush(); } catch (Exception e) { e.printStackTrace(); } finally { try { is.close(); ois.close(); os.close(); } catch (Exception e) { e.printStackTrace(); } } }  /** * 解压为原始的字节数组，也就是 file.txt 文件内容直接转换的字节数组 * @param encodeBytes 赫夫曼编码的字节数组 * @param pathMap  * @return */ private byte[] decode(byte[] encodeBytes, Map<Byte, String> pathMap) { // 赫夫曼编码的字节数组转变为二进制数字串 String binaryStr = decodeBinaryStr(encodeBytes);  // 转换二进制数字串为原始字符的字节数组，也就是 file.txt 文件内容直接转换的字节数组 byte[] bytes = decodeContent(binaryStr, pathMap); return bytes; }  /** * 根据解压后的二进制编码串和赫夫曼编码表得到原始的字符串内容 * * @param binaryStr 压缩后的字节数组转换成的二进制编码串 * @param pathMap 赫夫曼编码表 * @return */ private byte[] decodeContent(String binaryStr, Map<Byte, String> pathMap) { //将映射关系倒换过来，即保存的<key,value>变成保存<value,key> Map<String, Byte> pathByteMap = reverseMap(pathMap);  // 根据路径一段段截取二进制数字串, 并拼凑为有效的byte码 byte[] resultBytes = doDecodeContent(binaryStr, pathByteMap); return resultBytes; }  /** * 反编译为最终需要的字节码 * @param binaryStr 压缩后的字节数组转换成的二进制编码串 * @param pathByteMap 赫夫曼编码表(<Byte,String>)的倒映射表(<String, Byte>) * @return */ private byte[] doDecodeContent(String binaryStr, Map<String, Byte> pathByteMap) { // 截取的每一个数字, 添加到集合中 List<Byte> lstBytes = new ArrayList<>(); for (int i = 0; i < binaryStr.length();) { int count = 1; while(true) {  // 1、以count作为一个标识位, 一直向后移动；举例：假设 binaryStr = "1001010001111010101001001110000..." // 那么就用 count 一个个往后移动一位，直到匹配到 pathByteMap 的 key，currStr 就有可能是 "1"、"10"、"100"... String currStr = binaryStr.substring(i, i + count);  // 如果路径到字符映射中, 包含该路径, 则匹配成功;举例：假设 binaryStr = "1001010001111010101001001110000...", //假设pathByteMap的内容是<{"1001",116},{"01000",104}...> //当key = "1"、"10"、"100"时拿出来的 Byte 那就是为空，key = "1001"时，Byte 就不为空，则证明匹配成功，查找到这个字节 if (null != pathByteMap.get(currStr)) {  // 将 字节添加到 lstBytes 集合中，也就是将字符的10进制 Ascill 码添加到 lstBytes 集合中 lstBytes.add(pathByteMap.get(currStr)); break; } count++; }  // 匹配成功后, i直接进count位, 进行下一位字节查找；举例假设 binaryStr = "1001010001111010101001001110000...", //假设pathByteMap的内容是<{"1001",116},{"01000",104}...>， //当执行binaryStr.substring(0, 5)这条语句的时候就找到了第一个字节(从"1001"从pathByteMap拿到一个字节) //那么查找下一个字节的count就从5开始 i += count; } // 将List集合的Byte转换为byte数组保存 byte[] bytes = new byte[lstBytes.size()]; int index = 0; for (Byte currByte : lstBytes) { bytes[index++] = currByte; } return bytes; }   /** * 反转赫夫曼编码表(Map<String,Byte>)，将(Map<String,Byte>)变为(Map<Byte,String>) * * @param pathMap * @return */ private Map<String,Byte> reverseMap(Map<Byte, String> pathMap) { Map<String, Byte> path2ByteMap = new HashMap<>(16); for (Map.Entry<Byte, String> entry : pathMap.entrySet()) { path2ByteMap.put(entry.getValue(), entry.getKey()); } return path2ByteMap; }  /** * 将压缩后的字节数组反编译为二进制数字串 * @param encodeBytes  * @return 二进制数字串 */ private String decodeBinaryStr(byte[] encodeBytes) { StringBuilder sb = new StringBuilder(); boolean isNeedSub = true; for (int i = 0; i < encodeBytes.length; i++) { if (i == encodeBytes.length - 1 && encodeBytes[i] > 0) { isNeedSub = false; } sb.append(decodeDecimal(isNeedSub, encodeBytes[i])); } return sb.toString(); }  /** * 转换 * @param isNeedSub 是否需要截取 * @param encodeByte 当前需要转换的数据 * @return */ private String decodeDecimal(boolean isNeedSub, int encodeByte) { String str = "";  /*1、为什么要 encodeByte |= 256 ？当encodeByte是负数的时候，Integer.toBinaryString(encodeByte) 得到的是32位的字符串 可以执行 str.substring(str.length() - 8) 不报错；当encodeByte是正数的时候，Integer.toBinaryString(encodeByte) 得到不一定是 大于等于8位的字符串，执行 str.substring(str.length() - 8) 就有可能报错，就比如正数7，执行Integer.toBinaryString(7)就得到 "111"，"111".substring("111".length() - 8)就会报错；如果 7 |= 256 就等于 363，再执行 Integer.toBinaryString(363) 就得到 "100000111"，再执行 "100000111".substring("100000111".length() - 8) 就得到 "00000111"，目的是7转换成二进制的时候，如果不够8位， 就用0在前面补够8位嘛  2、256的二进制为: 1 0000 0000, 无论任务数字与256进行或运算后, 绝对能保证第九位的1, 则后八位有效 转换完成后, 截取后八位作为有效数据  3、注意: 最后一位需要处理的数据不一定满8位, 所以不满八位的情况下一定为正数, 需要原样处理,所以 isNeedSub 为 false */ if (isNeedSub) { encodeByte |= 256; }  //返回 encodeByte 对应的二进制补码 str = Integer.toBinaryString(encodeByte); if (isNeedSub) { str = str.substring(str.length() - 8); }  return str; }

public static void main(String[] args) { Test test = new Test(); test.decompress("C://Users//86188//Desktop//cc//file.zip", "C://Users//86188//Desktop//cc//file.txt");}