1. 基础概念

  1. 1.基本介绍
  2.     赫夫曼编码是变长（不定长）编码的一种。
  3.     将【字符出现频率】作为权重，权重越高的节点路劲长度越短
  4.     编码规则，从根点触发，通路分支向左为0，向右为1
  5.     压缩率在20%-90%
  7. 2.编码步骤
  8.     1.将文本中的字符各个封转为节点，以出现次数为权重
  9.     2.将节点构造哈夫曼树，叶子节点为数据节点
  10.     3.根据路径左0右1规则给数据节点编码，得到数据-编码的映射（编码表）
  11.     4.根据编码表对原始文本的byte数组进行编码，得到二进制编码字符串
  12.     5.将二进制字符串解析成byte数组（最后的编码，将其长度/原始文本bytes长度=压缩率）
  14. 3.解码步骤
  15.     1.将byte数据，二进制字符串（8位）
  16.     2.将编码表逆向<byte,String> -> <String,byte>
  17.     3.同逆向编码表得到byte数组
  18.     4.直接将byte数组转成String

代码实现

  1. import com.alibaba.fastjson.JSONObject;
  2. import lombok.Getter;
  3. import lombok.Setter;
  4. import org.junit.Test;
  6. import javax.persistence.criteria.CriteriaBuilder;
  7. import java.io.*;
  8. import java.util.*;
  10. @Setter
  11. @Getter
  12. class HeffmanNode implements Comparable{
  14.     // 字符的ascall码
  15.     private Byte value;
  16.     // 字符在文本中出现的次数（权重）
  17.     private int weight;
  18.     // 左子节点
  19.     private HeffmanNode left;
  20.     private HeffmanNode right;
  22.     public HeffmanNode(Byte value, int weight) {
  23.         this.value = value;
  24.         this.weight = weight;
  25.     }
  27.     @Override
  28.     public int compareTo(Object o) {
  29.         return this.weight - ((HeffmanNode)o).weight;
  30.     }
  31. }
  32. public class HeffmanEncodeTest {
  34.     /**
  35.      * NodeList (初始森林)
  36.      * @param sourceBytes
  37.      * @return
  38.      */
  39.     private List<HeffmanNode> getNodeList(byte[] sourceBytes){
  40.         Map<Byte, Integer> countMap = new HashMap<>();
  41.         // 统计出现频率
  42.         for(byte b : sourceBytes) {
  43.             Integer count = countMap.get(b);
  44.             if(count==null){
  45.                 countMap.put(b,1);
  46.             }else {
  47.                 countMap.put(b, count+1);
  48.             }
  49.         }
  50.         // 构建NodeList
  51.         List<HeffmanNode> nodes = new ArrayList<>();
  52.         countMap.forEach((key,value)-> {
  53.             HeffmanNode node = new HeffmanNode(key, value);
  54.             nodes.add(node);
  55.         });
  56.         return nodes;
  57.     }
  59.     /**
  60.      * 构建赫夫曼树（根节点）
  61.      * @param nodes
  62.      * @return
  63.      */
  64.     private HeffmanNode buildHeffmantree(List<HeffmanNode> nodes) {
  65.         while (nodes.size()>1) {
  66.             Collections.sort(nodes);
  67.             HeffmanNode min1 = nodes.get(0);
  68.             HeffmanNode min2 = nodes.get(1);
  69.             HeffmanNode newNode = new HeffmanNode(null, min1.getWeight() + min2.getWeight());
  70.             newNode.setLeft(min1);
  71.             newNode.setRight(min2);
  72.             nodes.remove(min1);
  73.             nodes.remove(min2);
  74.             nodes.add(newNode);
  75.         }
  76.         return nodes.get(0);
  77.     }
  79.     /**
  80.      * 根据赫夫曼树建立编码表
  81.      *    编码顺序：从上往下
  82.      *    编码规则：左 0 右 1
  83.      * @param root
  84.      * @return
  85.      */
  86.     private Map<Byte,String> getCodeTable(HeffmanNode root) {
  88.         if(root==null){
  89.             return null;
  90.         }
  91.         //编码表
  92.         StringBuilder sb = new StringBuilder();
  93.         Map<Byte,String> codeMap = new HashMap<>();
  94.         // 处理左节点
  95.         getCodeStr(root.getLeft(), "0",sb,codeMap);
  96.         // 处理右边节点
  97.         getCodeStr(root.getRight(), "1",sb,codeMap);
  98.         return codeMap;
  99.     }
  102.     /**
  103.      * 功能：
  104.      *   细节：因为该方法有递归，所有编码表定义为成员变量
  105.      * @param node: 当前待处理的节点
  106.      * @param subPath： 当前需要添加的路径（左0右1）
  107.      * @param sb ： 前边非叶子节点走下来的路径
  108.      */
  109.     private void getCodeStr(HeffmanNode node,String subPath, StringBuilder sb,Map<Byte,String> codeMap) {
  111.         // 先拼上前面的路径(这里一定要照sb2，否则会对右边的路径有影响)
  112.         StringBuilder sb2 = new StringBuilder(sb);
  113.         sb2.append(subPath);
  114.         // 非叶子节点，继续往后走
  115.         if(node.getValue() == null) {
  116.             // 左0 ,右1
  117.             if(node.getLeft()!=null) {
  118.                 getCodeStr(node.getLeft(),"0",sb2, codeMap);
  119.             }
  120.             if(node.getRight()!=null) {
  121.                 getCodeStr(node.getRight(),"1",sb2, codeMap);
  122.             }
  123.         }
  124.         // 将叶子节点的编码放入编码表
  125.         else {
  126.             codeMap.put(node.getValue(),sb2.toString());
  127.         }
  129.     }
  132.     /**
  133.      * 根据编码表,通过ASCALL码Byte获取编码字符串
  134.      */
  135.     private StringBuilder getEncodeStringByCodeTable(byte[] sourceBytes, Map<Byte,String> codeMap) {
  136.         StringBuilder sb = new StringBuilder();
  137.         for(byte b : sourceBytes) {
  138.             sb.append(codeMap.get(b));
  139.         }
  140.         return sb;
  141.     }
  143.     /**
  144.      * 将编码字符串作为二进制补码生成byte[],
  145.      *          一个byte字节，8bit
  146.      */
  147.     private byte[] getHeffmanEncodeBytesByEncodeString(StringBuilder encodeStringBuilder) {
  149.         // 计算byte长度
  150.         // 下面的计算过程可以简写： int len = (encodeStringBuilder.length() + 7)/ 8+1 ;
  151.         int len = 0;
  152.         if(encodeStringBuilder.length()%8==0){
  153.             len = encodeStringBuilder.length()/8;
  154.         }else{
  155.             len = encodeStringBuilder.length()/8+1;
  156.         }
  158.         byte[] bytes = new byte[len];
  159.         int j = 0;
  160.         for(int i=0; i<encodeStringBuilder.length(); i+=8) {
  161.             String bitStr = null;
  162.             // 截取的最后端可能不满8位
  163.             if(i+8 >= encodeStringBuilder.length()) {
  164.                 bitStr = encodeStringBuilder.substring(i);
  165.             }else {
  166.                 bitStr = encodeStringBuilder.substring(i,i+8);
  167.             }
  168.             byte bit = (byte)Integer.parseInt(bitStr, 2);
  169.             bytes[j] = bit;
  170.             j++;
  171.         }
  172.         return bytes;
  173.     }
  175.     /**
  176.      * 根据被编码数据动态创建编码表
  177.      * @param source 被编码数据
  178.      * @return: 生成的赫夫曼编码表{32=01, 97=100, 100=11000, 117=11001, 101=1110, 118=11011, 105=101, 121=11010, 106=0010, 107=1111, 108=000, 111=0011}
  179.      */
  180.     public Map<Byte,String>buildEncodeTable(String source) {
  181.         // 1.获得原始森林
  182.         List<HeffmanNode> nodes = getNodeList(source.getBytes());
  183.         // 2. 根据原始森林构建赫夫曼树
  184.         HeffmanNode root = buildHeffmantree(nodes);
  185.         // 3. 由于赫夫曼树构建编码表
  186.          return getCodeTable(root);
  187.     }
  189.     /**
  190.      * 编码
  191.      * @param source: 被编码的原数据
  192.      */
  193.     public byte[] encode(String source,Map<Byte,String> encodeTable){
  195.         // 4. 根据编码表，对元数据进行编码
  196.         StringBuilder sb = getEncodeStringByCodeTable(source.getBytes(),encodeTable);
  197.         // 5. 为了减小数据长度，将编码后的字符串"100111....",放入HeffmanEncodeByte[], 一个字节八位，
  198.         byte[] targetBytes = getHeffmanEncodeBytesByEncodeString(sb);
  199.         return targetBytes;
  200.     }
  204.     ///////////////////////////解码////////////////////////////////////
  206.     /**
  207.      * 将一个byte 转成一个二进制的字符串, 如果看不懂，可以参考我讲的Java基础 二进制的原码，反码，补码
  208.      * @param b 传入的 byte
  209.      * @param flag 标志是否需要补高位如果是true ，表示需要补高位，如果是false表示不补, 如果是最后一个字节，无需补高位
  210.      * @return 是该b 对应的二进制的字符串，（注意是按补码返回）
  211.      */
  212.     private static String byteToBitString(boolean flag, byte b) {
  213.         //使用变量保存 b
  214.         int temp = b; //将 b 转成 int
  215.         //如果是正数我们还存在补高位
  216.         if(flag) {
  217.             temp |= 256; //按位与 256  1 0000 0000  | 0000 0001 => 1 0000 0001
  218.         }
  219.         String str = Integer.toBinaryString(temp); //返回的是temp对应的二进制的补码
  220.         if(flag) {
  221.             return str.substring(str.length() - 8);
  222.         } else {
  223.             return str;
  224.         }
  225.     }
  227.     //完成数据的解压
  228.     //思路
  229.     //1. 将huffmanCodeBytes [-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]
  230.     //   重写先转成 赫夫曼编码对应的二进制的字符串 "1010100010111..."
  231.     //2.  赫夫曼编码对应的二进制的字符串 "1010100010111..." =》 对照 赫夫曼编码  =》 "i like like like java do you like a java"
  234.     //编写一个方法，完成对压缩数据的解码
  235.     /**
  236.      *
  237.      * @param encodeTable 赫夫曼编码表 map
  238.      * @param huffmanBytes 赫夫曼编码得到的字节数组
  239.      * @return 就是原来的字符串对应的数组
  240.      */
  241.     private static byte[] decode(byte[] huffmanBytes, Map<Byte,String> encodeTable) {
  243.         //1. 先得到 huffmanBytes 对应的 二进制的字符串 ， 形式 1010100010111...
  244.         StringBuilder stringBuilder = new StringBuilder();
  245.         //将byte数组转成二进制的字符串
  246.         for(int i = 0; i < huffmanBytes.length; i++) {
  247.             byte b = huffmanBytes[i];
  248.             //判断是不是最后一个字节
  249.             boolean flag = (i == huffmanBytes.length - 1);
  250.             stringBuilder.append(byteToBitString(!flag, b));
  251.         }
  253.         //2. 把赫夫曼编码表进行调换，因为反向查询 a->100 100->a
  254.         Map<String, Byte>  map = new HashMap<String,Byte>();
  255.         for(Map.Entry<Byte, String> entry: encodeTable.entrySet()) {
  256.             map.put(entry.getValue(), entry.getKey());
  257.         }
  259.         //创建要给集合，存放byte
  260.         List<Byte> list = new ArrayList<>();
  261.         //i 可以理解成就是索引,扫描 stringBuilder
  262.         for(int  i = 0; i < stringBuilder.length(); ) {
  263.             int count = 1; // 小的计数器
  264.             boolean flag = true;
  265.             Byte b = null;
  267.             while(flag) {
  268.                 //1010100010111...
  269.                 //递增的取出 key 1
  270.                 String key = stringBuilder.substring(i, i+count);//i 不动，让count移动，指定匹配到一个字符
  271.                 b = map.get(key);
  272.                 if(b == null) {//说明没有匹配到
  273.                     count++;
  274.                 }else {
  275.                     //匹配到
  276.                     flag = false;
  277.                 }
  278.             }
  279.             list.add(b);
  280.             i += count;//i 直接移动到 count
  281.         }
  282.         //当for循环结束后，我们list中就存放了所有的字符  "i like like like java do you like a java"
  283.         //把list 中的数据放入到byte[] 并返回
  284.         byte b[] = new byte[list.size()];
  285.         for(int i = 0;i < b.length; i++) {
  286.             b[i] = list.get(i);
  287.         }
  288.         return b;
  290.     }
  292.     /**
  293.      * 测试解压
  294.      */
  295.     @Test
  296.     public void test() {
  298.         // 被编码数据
  299.         String source = "i like like like java do you like a java";
  300.         // 动态创建编码表解码
  301.         Map<Byte, String> encodeTable = buildEncodeTable(source);
  302.         // 编码
  303.         byte[] encodeBytes = encode(source, encodeTable);
  304.         // 解码
  305.         byte[] retByte = decode(encodeBytes,encodeTable);
  306.         System.out.println("decodeStr:" + new String(retByte));
  307.     }
  309. }