哈夫曼树（赫夫曼树）：给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度（WPL）达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树。

哈夫曼树 - 图1

路径：在一棵树中，从一个结点到另一个结点所经过的所有结点，被我们称为两个结点之间的路径。
路径长度：在一棵树中，从一个结点到另一个结点所经过的“边”的数量，被我们称为两个结点之间的路径长度。
结点的带权路径长度：树的每一个结点，都可以拥有自己的“权重”（Weight），权重在不同的算法当中可以起到不同的作用。结点的带权路径长度，是指树的根结点到该结点的路径长度和该结点权重的乘积。
树的带权路径长度：在一棵树中，所有叶子结点的带权路径长度之和，被称为树的带权路径长度，也被简称为WPL。

哈夫曼树构建步骤：
1、构建森林：把每一个叶子结点，都当做树一颗独立的树（只有根结点的树），这样就形成了一个森林，将全部叶子结点排序；
2、取出根结点权值最小的两颗二叉树；
3、组成一棵新的二叉树，该二叉树的根结点的权值是这两颗二叉树根结点权值之和；
4、再将这颗新的二叉树的根结点权值跟未处理的结点权值再次排序，不断重复1、2、3、4的步骤，直到数列中所有结点都被处理，就得到一棵哈夫曼树；

  1. /**
  2.  * 《哈夫曼树》
  3.  */
  4. public class HuffmanTree {
  6.     /**
  7.      * 根结点
  8.      */
  9.     private TreeNode rootNode;
  11.     /**
  12.      * 结点类
  13.      */
  14.     private class TreeNode implements Comparable<TreeNode>{
  15.         private Integer value;
  16.         private TreeNode left;
  17.         private TreeNode right;
  19.         public TreeNode(Integer value) {
  20.             this.value = value;
  21.         }
  23.         public TreeNode(Integer value, TreeNode left, TreeNode right) {
  24.             this.value = value;
  25.             this.left = left;
  26.             this.right = right;
  27.         }
  29.         /**
  30.          * 前序遍历
  31.          */
  32.         public void beforeOrder() {
  33.             if (this == null) {
  34.                 return;
  35.             }
  36.             // 1、输出结点
  37.             System.out.printf("%s ", this.value);
  38.             // 2、前序遍历左子树
  39.             if (this.left != null) {
  40.                 this.left.beforeOrder();
  41.             }
  42.             // 3、前序遍历右子树
  43.             if (this.right != null) {
  44.                 this.right.beforeOrder();
  45.             }
  46.         }
  48.         @Override
  49.         public int compareTo(TreeNode o) {
  50.             return this.value - o.value;
  51.         }
  52.     }
  54.     /**
  55.      * 前序遍历
  56.      */
  57.     public void beforeOrderPrint() {
  58.         if (rootNode == null) {
  59.             System.out.println("前序遍历为空");
  60.             return;
  61.         }
  62.         rootNode.beforeOrder();
  63.     }
  65.     /**
  66.      * 构建哈夫曼树
  67.      */
  68.     public void buildHuffman(int arr[]) {
  69.         // 创建存放结点的集合
  70.         List<TreeNode> nodeList = new ArrayList<>();
  71.         for (int v: arr) {
  72.             nodeList.add(new TreeNode(v));
  73.         }
  75.         while (nodeList.size() > 1) {
  76.             // 1、将集合按从小到大排序
  77.             Collections.sort(nodeList);
  78.             // 2、取出根结点权值最小的两颗二叉树
  79.             TreeNode leftNode = nodeList.get(0);
  80.             TreeNode rightNode = nodeList.get(1);
  81.             // 3、组成一棵新的二叉树，该二叉树的根结点的权值是这两颗二叉树根结点权值之和
  82.             TreeNode parentNode = new TreeNode((leftNode.value + rightNode.value), leftNode, rightNode);
  83.             // 4、添加新的二叉树根结点
  84.             nodeList.add(parentNode);
  85.             // 5、移除刚刚处理过的两个二叉树根结点
  86.             nodeList.remove(leftNode);
  87.             nodeList.remove(rightNode);
  88.         }
  89.         rootNode = nodeList.get(0);
  90.     }
  92.     public static void main(String[] args) {
  93.         int[] arr = new int[]{13, 7, 8, 3, 29, 6, 1};
  94.         HuffmanTree binaryTree = new HuffmanTree();
  95.         // 构建哈夫曼树
  96.         binaryTree.buildHuffman(arr);
  97.         System.out.print("前序遍历哈夫曼树：");
  98.         binaryTree.beforeOrderPrint();
  99.     }
  101. }


哈夫曼编码

  1.  哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码（有时也称为霍夫曼编码）。<br />     哈夫曼编码具有广泛的应用，利用哈夫曼树构造的用于通信的二进制编码称为哈夫曼编码。<br />例如： 有一段电文"CAST囗TAT囗A囗SA"（ 其中,"囗"表示一个空格）。统计电文中字母的频度 f('C')=1,f('S')=2,f('T')=3,f('囗')=3,f('A')=4；用频度{ 1 ， 2 ， 3 ， 3 ， 4 } 为权值生成哈夫曼树，并在每个叶子上注明对应的字符。树中从根到每个叶子都有一条路径，对路径上的各分枝约定指向左子树根的分枝表示"0"码，指向右子树的分枝表示"1"码，取每条路径上的"0"或"1"的序列作为和各个叶子对应的字符的编码，这就是哈夫曼编码。对应下图的哈夫曼树，上述字符编码为：<br /> ![](https://cdn.nlark.com/yuque/0/2021/jpeg/12644954/1613642908868-e6808e78-fc4b-43a0-9a97-dfbcf30d754d.jpeg#align=left&display=inline&height=66&margin=%5Bobject%20Object%5D&originHeight=66&originWidth=371&size=0&status=done&style=none&width=371)![](https://cdn.nlark.com/yuque/0/2021/jpeg/12644954/1613642908976-f51c1cba-3376-47b5-8ffa-8e2e412ff786.jpeg#align=left&display=inline&height=213&margin=%5Bobject%20Object%5D&originHeight=213&originWidth=306&size=0&status=done&style=none&width=306)
  1. /**
  2.  * 《哈夫曼编码》
  3.  */
  4. public class HuffmanCode {
  6.     /**
  7.      * 根结点
  8.      */
  9.     private TreeNode rootNode;
  11.     /**
  12.      * 哈夫曼编码表存放集合
  13.      */
  14.     private Map<Byte, String> huffmanCodeMap = new HashMap<>();
  16.     /**
  17.      * 暂存可能不足一个字节的字符编码
  18.      */
  19.     private String lastByte = "";
  21.     /**
  22.      * 结点类
  23.      */
  24.     private class TreeNode implements Comparable<TreeNode>{
  25.         // 数据
  26.         private Byte data;
  27.         // 权重
  28.         private Integer weight;
  29.         // 左结点
  30.         private TreeNode left;
  31.         // 右结点
  32.         private TreeNode right;
  34.         public TreeNode(Byte data, Integer weight, TreeNode left, TreeNode right) {
  35.             this.data = data;
  36.             this.weight = weight;
  37.             this.left = left;
  38.             this.right = right;
  39.         }
  41.         @Override
  42.         public String toString() {
  43.             return "TreeNode{" + "data=" + data + ", weight=" + weight + '}';
  44.         }
  46.         @Override
  47.         public int compareTo(TreeNode o) {
  48.             return this.weight - o.weight;
  49.         }
  50.     }
  52.     /**
  53.      * 前序遍历
  54.      */
  55.     public void beforeOrderPrint() {
  56.         if (rootNode == null) {
  57.             System.out.println("前序遍历为空");
  58.             return;
  59.         }
  60.         beforeOrderPrint(rootNode);
  61.     }
  63.     private void beforeOrderPrint(TreeNode node) {
  64.         if (node == null) {
  65.             return;
  66.         }
  67.         // 1、输出结点
  68.         System.out.println(node);
  69.         // 2、前序遍历左子树
  70.         beforeOrderPrint(node.left);
  71.         // 3、前序遍历右子树
  72.         beforeOrderPrint(node.right);
  73.     }
  75.     /**
  76.      * 生成哈夫曼编码表
  77.      */
  78.     private void createHuffmanCode(){
  79.         if (rootNode == null) {
  80.             System.out.println("根结点为空！");
  81.             return;
  82.         }
  83.         getNodeCode(rootNode, null);
  84.     }
  86.     /**
  87.      * 获取结点对应的编码
  88.      * @param node 结点
  89.      * @param code 编码
  90.      */
  91.     private void getNodeCode(TreeNode node, String code) {
  92.         if (code == null) {
  93.             code = "";
  94.         }
  95.         // 如果当前结点是非子结点时，继续往下
  96.         if (node.data == null) {
  97.             if (node.left != null) {
  98.                 getNodeCode(node.left, code + "0");
  99.             }
  100.             if (node.right != null) {
  101.                 getNodeCode(node.right, code + "1");
  102.             }
  103.         } else {
  104.             huffmanCodeMap.put(node.data, code);
  105.         }
  106.     }
  108.     /**
  109.      * 构建哈夫曼树
  110.      */
  111.     private void buildHuffmanTree(byte[] bytes) {
  112.         // 统计编码的频度
  113.         Map<Byte, Integer> collectMap = getCollectMap(bytes);
  114.         if (collectMap == null || collectMap.isEmpty()) {
  115.             return;
  116.         }
  118.         // 创建存放结点的集合
  119.         List<TreeNode> nodeList = new ArrayList<>();
  120.         collectMap.forEach((k, v) -> {
  121.             nodeList.add(new TreeNode(k, v, null, null));
  122.         });
  124.         while (nodeList.size() > 1) {
  125.             // 1、将集合按从小到大排序
  126.             Collections.sort(nodeList);
  127.             // 2、取出根结点权值最小的两颗二叉树
  128.             TreeNode leftNode = nodeList.get(0);
  129.             TreeNode rightNode = nodeList.get(1);
  130.             // 3、组成一棵新的二叉树，该二叉树的根结点的权值是这两颗二叉树根结点权值之和
  131.             TreeNode parentNode = new TreeNode(null, (leftNode.weight + rightNode.weight), leftNode, rightNode);
  132.             // 4、添加新的二叉树根结点
  133.             nodeList.add(parentNode);
  134.             // 5、移除刚刚处理过的两个二叉树根结点
  135.             nodeList.remove(leftNode);
  136.             nodeList.remove(rightNode);
  137.         }
  138.         rootNode = nodeList.get(0);
  139.     }
  141.     /**
  142.      * 统计编码的频度
  143.      * @return
  144.      */
  145.     private Map<Byte, Integer> getCollectMap(byte[] bytes) {
  146.         if (bytes == null || bytes.length == 0) {
  147.             return Collections.EMPTY_MAP;
  148.         }
  149.         Map<Byte, Integer> collectMap = new HashMap<>();
  150.         for (Byte b : bytes) {
  151.             Integer count = collectMap.get(b);
  152.             if (count == null) {
  153.                 collectMap.put(b, 1);
  154.             } else {
  155.                 collectMap.put(b, count + 1);
  156.             }
  157.         }
  158.         return collectMap;
  159.     }
  161.     /**
  162.      * 获取哈夫曼编码
  163.      * @return
  164.      */
  165.     private String getHuffmanCode(byte[] bytes) {
  166.         if (bytes == null || bytes.length == 0) {
  167.             return null;
  168.         }
  169.         // 1、构建哈夫曼树
  170.         buildHuffmanTree(bytes);
  171.         // 2、生成哈夫曼编码表
  172.         createHuffmanCode();
  173.         // 3、获取待编码字符对应的哈夫曼编码
  174.         StringBuilder sb = new StringBuilder();
  175.         for (byte b : bytes) {
  176.             sb.append(huffmanCodeMap.get(b));
  177.         }
  178.         return sb.toString();
  179.     }
  181.     /**
  182.      * byte转成二进制字符串(按补码返回)
  183.      * @return
  184.      */
  185.     private String byteToBitString(byte b) {
  186.         int temp = b;
  187.         // 如果是正数需要补高位，按位与256（1 0000 0000）
  188.         temp |= 256;
  189.         String str = Integer.toBinaryString(temp);
  190.         return str.substring(str.length() - 8);
  191.     }
  193.     /**
  194.      * 哈夫曼编码压缩
  195.      *  1、获取待编码字符对应的哈夫曼编码（01字符串）
  196.      *  2、遍历哈夫曼编码，每8位（一个字节）转换成byte类型，压缩成byte数组
  197.      * @return
  198.      */
  199.     public byte[] huffmanZip(byte[] bytes) {
  200.         // 1、获取待编码字符对应的哈夫曼编码
  201.         String code = getHuffmanCode(bytes);
  202. //        System.out.println("哈夫曼编码：" + code);
  204.         // 2、将哈夫曼编码压缩成byte数组
  205.         // 压缩数组的长度
  206.         int len = code.length() / 8;
  207.         if (code.length() % 8 != 0) {
  208.             // 编码长度不能被8整除，保存多余的不足8位的部分
  209.             lastByte = code.substring(len * 8);
  210.         }
  211.         System.out.println("lastByte: " + lastByte);
  212.         // 存储压缩的byte数组
  213.         byte[] huffmanCodeBytes = new byte[len];
  214.         for (int i = 0; i < len; i++) {
  215.             huffmanCodeBytes[i] = (byte)Integer.parseInt(code.substring(i * 8, i * 8 + 8), 2);
  216.         }
  217.         return huffmanCodeBytes;
  218.     }
  220.     /**
  221.      * 哈夫曼编码解压
  222.      *  1、逐个遍历压缩后的byte数组，将每个byte元素转换成8位二进制字符串，得到哈夫曼编码字符串
  223.      *  2、根据哈夫曼编码表，将哈夫曼编码字符串转化成对应的字节数组
  224.      * @return
  225.      */
  226.     public byte[] huffmanUnZip(byte[] bytes, Map<Byte, String> codeTable) {
  227.         // 1、先得到压缩后的字节数组对应的二进制字符串
  228.         StringBuffer sb = new StringBuffer();
  229.         for(int i = 0; i < bytes.length; i++) {
  230.             sb.append(byteToBitString(bytes[i]));
  231.         }
  232.         // 拼接最后不足一个字节的字符编码
  233.         sb.append(lastByte);
  235.         // 2、根据哈夫曼编码表，将二进制字符串转化成对应的字节
  236.         // 将哈夫曼编码表key和value反转
  237.         Map<String, Byte> codeMap = new HashMap<>();
  238.         codeTable.forEach((k, v) -> {
  239.             codeMap.put(v, k);
  240.         });
  242.         List<Byte> byteList = new ArrayList<>();
  243.         for (int i = 0; i < sb.length(); ) {
  244.             int count = 1;
  245.             while (true) {
  246.                 String str = sb.substring(i, i+count);
  247.                 if (codeMap.containsKey(str)) {
  248.                     byteList.add(codeMap.get(str));
  249.                     i += count;
  250.                     break;
  251.                 }
  252.                 count++;
  253.             }
  254.         }
  255.         // 转成字节数组
  256.         byte[] byteArr = new byte[byteList.size()];
  257.         for (int i = 0; i < byteArr.length; i++) {
  258.             byteArr[i] = byteList.get(i);
  259.         }
  260.         return byteArr;
  261.     }
  263.     /**
  264.      * 哈夫曼编码压缩文件
  265.      */
  266.     public void zipFile(String srcFile, String dstFile) {
  267.         InputStream is = null;
  268.         ObjectOutputStream os = null;
  269.         try {
  270.             is = new FileInputStream(srcFile);
  271.             os = new ObjectOutputStream(new FileOutputStream(dstFile));
  272.             // 创建一个源文件一样大小的byte数组
  273.             byte[] b = new byte[is.available()];
  274.             // 1、读取来源文件
  275.             is.read(b);
  276.             // 2、压缩源文件
  277.             byte[] huffmanBytes = huffmanZip(b);
  278.             // 3、写入压缩后的文件到目标文件
  279.             os.writeObject(huffmanBytes);
  280.             // 同时也要写入哈夫曼编码表，便于解压
  281.             os.writeObject(huffmanCodeMap);
  282.         } catch (Exception e) {
  283.             e.printStackTrace();
  284.         } finally {
  285.             try {
  286.                 if (os != null) {
  287.                     os.close();
  288.                 }
  289.                 if (is != null) {
  290.                     is.close();
  291.                 }
  292.             } catch (IOException e) {
  293.                 e.printStackTrace();
  294.             }
  295.         }
  296.     }
  298.     /**
  299.      * 哈夫曼编码解压文件
  300.      */
  301.     public void unZipFile(String srcFile, String dstFile) {
  302.         ObjectInputStream is = null;
  303.         OutputStream os = null;
  304.         try {
  305.             is = new ObjectInputStream(new FileInputStream(srcFile));
  306.             os = new FileOutputStream(dstFile);
  307.             // 1、读取压缩文件
  308.             // 读取压缩byte数组
  309.             byte[] huffmanBytes = (byte[])is.readObject();
  310.             // 读取哈夫曼编码表
  311.             Map<Byte, String> huffmanCodeTable = (Map<Byte, String>)is.readObject();
  312.             // 2、解压源文件
  313.             byte[] bytes = huffmanUnZip(huffmanBytes, huffmanCodeTable);
  314.             // 3、写入目标文件
  315.             os.write(bytes);
  316.         } catch (Exception e) {
  317.             e.printStackTrace();
  318.         } finally {
  319.             try {
  320.                 if (os != null) {
  321.                     os.close();
  322.                 }
  323.                 if (is != null) {
  324.                     is.close();
  325.                 }
  326.             } catch (IOException e) {
  327.                 e.printStackTrace();
  328.             }
  329.         }
  330.     }
  332.     public static void main(String[] args) {
  333.         String str = "CAST&TAT&A&SAT&AA&";
  334.         System.out.println("原数据：" + str);
  335.         HuffmanCode binaryCode = new HuffmanCode();
  336.         byte[] bytes = binaryCode.huffmanZip(str.getBytes());
  337.         System.out.println("压缩：" + Arrays.toString(bytes));
  338.         System.out.println("解压：" + new String(binaryCode.huffmanUnZip(bytes, binaryCode.huffmanCodeMap)));
  340.         System.out.println("测试文件压缩测试");
  341.         binaryCode.zipFile("/Users/yupan/Desktop/123.txt", "/Users/yupan/Desktop/456.txt");
  342.         System.out.println("文件压缩成功！");
  343.         binaryCode.unZipFile("/Users/yupan/Desktop/456.txt", "/Users/yupan/Desktop/789.txt");
  344.         System.out.println("文件解压成功！");
  345.     }
  346. }