vlambda博客
学习文章列表

10010100011110101010010011100001001011101110110010100101110011111000101011110101000101001101110011101111011111101000111101100001111100101011110101000101000111101100001111100

/** * 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;  //保存 ”通过赫夫曼树编码表取出的二进制编码“ String s;  //拼接赫夫曼树的节点的路径，节点的左路径用“0” 表示，右路径用“1”表示 StringBuilder sb = new StringBuilder();  Map<Byte,String> huffumanCodes = new HashMap<Byte,String>();  public static void main(String[] args) { String s = "the virus mutated and became weaker and weaker"; byte[] bs = s.getBytes(); Test test = new Test(); byte[] bytes = test.huffumanZip(bs); System.out.println("压缩后的字节数组：" + Arrays.toString(bytes)); System.out.println("压缩后的字节数组长度：" + bytes.length); }  private byte[] huffumanZip(byte[] bs) { List<Node> list = getNode(bs);  //创建赫夫曼树 root = createHuffmanTree(list);  //生成赫夫曼编码表，将 赫夫曼编码表 存放到 huffumanCodes 中 getCodes(root, "", sb);  /** * 该方法通过赫夫曼编码得到对应的二进制编码， * 最后通过压缩二进制编码得到 对应的赫夫曼编码字节数组 */ 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)); } s = sb.toString(); System.out.println("s = " + s); 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) { StringBuilder sb2 = new StringBuilder(sb);  //将code 加入到 sb2 中 sb2.append(code); if (node != null) {  //非叶子节点 if (node.getData() == null) {  //向左递归处理 getCodes(node.getLeft(), "0", sb2);  //向右递归处理 getCodes(node.getRight(), "1", sb2);  //是叶子节点 } 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); }
}

10010100011110101010010011100001001011101110110010100101110011111000101011110101000101001101110011101111011111101000111101100001111100101011110101000101000111101100001111100

 /** * 将压缩后的字节数组反编译为二进制数字串 * @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) { String s = "the virus mutated and became weaker and weaker"; byte[] bs = s.getBytes(); Test test = new Test(); byte[] bytes = test.huffumanZip(bs); System.out.println("压缩后的字节数组：" + Arrays.toString(bytes)); System.out.println("压缩后的字节数组长度：" + bytes.length); String decodeBinaryStr = test.decodeBinaryStr(bytes); String result = test.s.equals(decodeBinaryStr) ? "相同" : "不相同"; System.out.println("通过赫夫曼编码表取出的二进制编码与解压后的二进制编码是否相同？" + result); }

10010100011110101010010011100001001011101110110010100101110011111000101011110101000101001101110011101111011111101000111101100001111100101011110101000101000111101100001111100

 /** * 根据解压后的二进制编码串和赫夫曼编码表得到原始的字符串内容 * * @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; }

public static void main(String[] args) { String s = "the virus mutated and became weaker and weaker"; byte[] bs = s.getBytes(); Test test = new Test(); byte[] bytes = test.huffumanZip(bs); System.out.println("压缩后的字节数组：" + Arrays.toString(bytes)); System.out.println("压缩后的字节数组长度：" + bytes.length); String decodeBinaryStr = test.decodeBinaryStr(bytes); System.out.println("decodeBinaryStr = " + decodeBinaryStr); String result = test.s.equals(decodeBinaryStr) ? "相同" : "不相同"; System.out.println("通过赫夫曼编码表取出的二进制编码与解压后的二进制编码是否相同？" + result); byte[] decodeByte = test.decodeContent(decodeBinaryStr, test.huffumanCodes); System.out.println("解压后的数据：" + new String(decodeByte)); }