赫夫曼树JAVA实现及分析-阿里云开发者社区

一，介绍

1）构造赫夫曼树的算法是一个贪心算法，贪心的地方在于：总是选取当前频率(权值)最低的两个结点来进行合并，构造新结点。

2）使用最小堆来选取频率最小的节点，有助于提高算法效率，因为要选频率最低的，要么用排序，要么用堆。用堆的话，出堆的复杂度为O(logN)，而向堆中插入一个元素的平均时间复杂度为O(1)，在构建赫夫曼树的过程中，新生成的结点需要插入到原来的队列中，故用堆来维持这种顺序比排序算法要高效地多。

二，赫夫曼算法分析

①用到的数据结构分析

首先需要构造一棵赫夫曼树，因此需要二叉链表这种数据结构（类似于二叉树）；其次，假设树中各个结点出现的频率保存在一维数组中，初始时，根据该数组构造出每个结点。

算法每次从选取两个频率最小的结点，构造出一个新结点，新结点的频率为这个结点的频率之和。那么如何选取频率最小的那两个结点呢？

一种方式是先将结点的频率排序，另一种方式是使用优先级队列（比如最小堆），这里我们使用优先级队列。

结点之间要能够比较（比较谁出现的频率小啊），故结点类需要实现Comparable接口，结点类（内部类）的定义如下：

 1 private class BinaryNode implements Comparable<BinaryNode>{
 2         int frequency;//出现的频率
 3         BinaryNode left;
 4         BinaryNode right;
 5         BinaryNode parent;
 6         
 7         public BinaryNode(int frequency, BinaryNode left, BinaryNode right, BinaryNode parent) {
 8             this.frequency = frequency;
 9             this.left = left;
10             this.right = right;
11             this.parent = parent;
12         }
13 
14         @Override
15         public int compareTo(BinaryNode o) {
16             return frequency - o.frequency;
17         }
18     }

注意：这里需要一个parent指针。因为，在对各个结点进行编码的时候，需要根据儿子结点，向上遍历查找父亲结点。

对于赫夫曼树而言，需要知道树的指针，同时，我们还额外定义了一个属性，记录树中的结点个数

public class HuffmanCode{
    
    private BinaryNode root;//root of huffman tree
    private int nodes;//number of total nodes in huffman tree
    
    private class BinaryNode implements Comparable<BinaryNode>{
            
        //........

②构造赫夫曼树的算法具体实现步骤

1)根据各个结点出现的频率来构造结点。初始时，根据每个频率构造一棵单结点的树

2)将结点放到优先级队列(最小堆)中保存起来，这样易于每次选取当前两个最小频率的结点

算法正式开始：

3)从优先级队列中弹出两个结点，再创建一个新的结点作为这两个结点的父亲，新结点的频率为这两个结点的频率之和，并把新结点插入到优先级队列中

4)重复步骤 3) 直到优先级队列中只剩下一个结点为止

最后剩下的这一个结点，就是已经构造好的赫夫曼树的根结点

注意，第 1) 步中构造的为赫夫曼树的叶子结点，而在第 3) 步中构造的结点全是非叶子结点。赫夫曼树中只有两个类型的结点，一种是叶子结点，另一种是度为2的非叶子结点

赫夫曼树中总结点的个数为：叶子结点的个数乘以2 再减去1

1) 和 2) 步骤的实现代码如下：

 1         /**
 2          * 根据各个结点的权值构造 N 棵单根节点的树
 3          * @param frequency 
 4          * @return 
 5          */
 6         public List<BinaryNode> make_set(Integer[] frequency){
 7             List<BinaryNode> nodeList = new ArrayList<HuffmanCode.BinaryNode>(frequency.length);
 8             for (Integer i : frequency) {
 9                 nodeList.add(new BinaryNode(i, null, null, null));
10             }
11             nodes = frequency.length<<1 -1;//huffman 树中结点个数等于叶子结点个数乘以2减去1
12             return nodeList;
13         }

3) 和 4) 步骤的实现代码如下：

 1         /**
 2          * 
 3          * @param roots initial root of each tree
 4          * @return root of huffman tree
 5          */
 6         public BinaryNode buildHuffmanTree(List<BinaryNode> roots){
 7             if(roots.size() == 1)//一共只有一个结点
 8                 return roots.remove(0);
 9             PriorityQueue<BinaryNode> pq = new PriorityQueue<BinaryNode>(roots);
10             while(pq.size() != 1){
11                 BinaryNode left = pq.remove();
12                 BinaryNode right = pq.remove();
13                 BinaryNode parent = new BinaryNode(left.frequency+right.frequency, left, right,null);
14                 left.parent = parent;
15                 right.parent = parent;
16                 pq.add(parent);
17             }
18             return (root = pq.remove());//最后剩下的这个结点就是构造好的赫夫曼树的树根
19         }

三，赫夫曼编码

①如何编码？

编码的实现思路:

从赫夫曼树的叶子结点开始，依次沿着父结点遍历直到树根，如果该叶子结点是其父亲的左孩子，则编码为0，否则编码为1

对所有的叶子结点执行上面操作，就可以把各个结点编码了。

编码的思路类似于求解赫夫曼树中所有叶子结点的频率之和，也就是整个赫夫曼树的代价。求解赫夫曼树的代价的代码如下：

 1         /**
 2          * 
 3          * @param root huffman树的根结点
 4          * @param nodeList huffman树中的所有叶子结点列表
 5          * @return 
 6          */
 7         public int huffman_cost(List<BinaryNode> nodeList){
 8             int cost = 0;
 9             int level;
10             BinaryNode currentNode;
11             for (BinaryNode binaryNode : nodeList) {
12                 level = 0;
13                 currentNode = binaryNode;
14                 while(currentNode != root){
15                     currentNode = currentNode.parent;
16                     level++;
17                 }
18                 cost += level*binaryNode.frequency;
19             }
20             return cost;
21         }

②如何解码？

解码就是根据0 ,1组成的'字符串' 去查找结点。步骤是：对于每个叶子结点，都从赫夫曼的根结点开始，取出每一位，如果是0，往左走；如果是1，往右走。直到遇到一个叶子结点，此时取出的 0，1 位(二进制位)就是该结点的编码了。

 1     public Map<BinaryNode, String> huffmanDecoding(String encodeString) {
 2         BinaryNode currentNode = root;
 3         //存储每个叶子结点对应的二进制编码
 4         Map<BinaryNode, String> node_Code = new HashMap<HuffmanCode.BinaryNode, String>();
 5         StringBuilder sb = new StringBuilder();//临时保存每个结点的二进制编码
 6         for (int i = 0; i < encodeString.length(); i++) {
 7             
 8             char codeChar = encodeString.charAt(i);
 9             sb.append(codeChar);
10             if (codeChar == '0')
11                 currentNode = currentNode.left;
12             else//codeChar=='1'
13                 currentNode = currentNode.right;
14             if (currentNode.left == null && currentNode.right == null)// 说明是叶子结点
15             {
16                 node_Code.put(currentNode, sb.toString());
17                 sb.delete(0, sb.length());//清空当前结点,为存储下一个结点的二进制编码做准备
18                 currentNode = root;//下一个叶子结点的解码,又从根开始
19             }
20         }
21         return node_Code;
22     }

第18行，当解码完一个叶子结点后，又从根结点开始解码下一个叶子结点。

四，赫夫曼编码的应用

①文件压缩

假设有8个字符如下：a,e,i,s,t,空格(space),换行(newline)。'a'出现的频率为10，'e'出现的频率为15……

由于有8个字符，故需要3bit才能完成表示这8个字符(2^3=8)，比如 000 表示 'a'；101 表示空格字符(space)....

由于 'a' 出现了10次，故一共需要 3*10=30bit来存储所有的'a'

经过计算，一共需要174个bit来存储上面的字符。

而若使用赫夫曼编码，则只需要146个bit来存储上面的编码，原因是：对于那些出现频率高的字符，赫夫曼编码使用较短的位来存储，而对于那些出现频率低的字符，可能需要较长的位来存储。

程序运行后得到下面的结果：

可以看出，只出现了三次的 's' 字符，它的赫夫曼编码为11011，长度为5bit。而出现了15次的字符 'e' 的赫夫曼编码为 10，长度为2bit

②最优二叉查找树

假设有这样一种情况，某些东西经常出现，比如英语中的: is 、a、hello、you、.....这样的单词经常看到，而有些单词很冷门。

我们把那些经常需要查询的单词(用到的单词)放到赫夫曼树的顶部（即给它们以较短的赫夫曼编码），那在查找它们时，只需要经过少量的几次比较就可以找到了。这就是优化了的二叉查找树。

即把查找频率高的单词放到离树根近的地方，这样就不需要每次都查找到叶子结点后，才能找到要想的单词。

五，完整代码

  1 import java.util.ArrayList;
  2 import java.util.HashMap;
  3 import java.util.List;
  4 import java.util.Map;
  5 import java.util.PriorityQueue;
  6 import java.util.Set;
  7 
  8 public class HuffmanCode {
  9 
 10     private BinaryNode root;// root of huffman tree
 11     private int nodes;// number of total nodes in huffman tree
 12 
 13     private class BinaryNode implements Comparable<BinaryNode> {
 14         int frequency;// 出现的频率
 15         BinaryNode left;
 16         BinaryNode right;
 17         BinaryNode parent;
 18 
 19         public BinaryNode(int frequency, BinaryNode left, BinaryNode right,
 20                 BinaryNode parent) {
 21             this.frequency = frequency;
 22             this.left = left;
 23             this.right = right;
 24             this.parent = parent;
 25         }
 26 
 27         @Override
 28         public int compareTo(BinaryNode o) {
 29             return frequency - o.frequency;
 30         }
 31 
 32         public boolean isLeftChild() {
 33             return parent != null && parent.left == this;
 34         }
 35 
 36         public boolean isRightChild() {
 37             return parent != null && parent.right == this;
 38         }
 39     }
 40 
 41     /**
 42      * 
 43      * @param roots
 44      *            initial root of each tree
 45      * @return root of huffman tree
 46      */
 47     public BinaryNode buildHuffmanTree(List<BinaryNode> roots) {
 48         if (roots.size() == 1)// 只有一个结点
 49             return roots.remove(0);
 50         PriorityQueue<BinaryNode> pq = new PriorityQueue<BinaryNode>(roots);//优先级队列保存所有叶子结点
 51         while (pq.size() != 1) {
 52             BinaryNode left = pq.remove();//频率最小的先出队列
 53             BinaryNode right = pq.remove();
 54             BinaryNode parent = new BinaryNode(
 55                     left.frequency + right.frequency, left, right, null);//构造父结点
 56             left.parent = parent;
 57             right.parent = parent;
 58             pq.add(parent);//新构造好的根结点插入到优先级队列中
 59         }
 60         return (root = pq.remove());
 61     }
 62 
 63     /**
 64      * 根据各个结点的权值构造 N 棵单根节点的树
 65      * 
 66      * @param frequency
 67      * @return
 68      */
 69     public List<BinaryNode> make_set(Integer[] frequency) {
 70         List<BinaryNode> nodeList = new ArrayList<HuffmanCode.BinaryNode>(
 71                 frequency.length);
 72         for (Integer i : frequency) {
 73             nodeList.add(new BinaryNode(i, null, null, null));
 74         }
 75         nodes = frequency.length << 1 - 1;// huffman 树中结点个数等于叶子结点个数乘以2减去1
 76         return nodeList;
 77     }
 78 
 79     /**
 80      * 
 81      * @param root
 82      *            huffman树的根结点
 83      * @param nodeList
 84      *            huffman树中的所有叶子结点列表
 85      * @return
 86      */
 87     public int huffman_cost(List<BinaryNode> nodeList) {
 88         int cost = 0;
 89         int level;
 90         BinaryNode currentNode;
 91         for (BinaryNode binaryNode : nodeList) {
 92             level = 0;
 93             currentNode = binaryNode;
 94             while (currentNode != root) {
 95                 currentNode = currentNode.parent;
 96                 level++;
 97             }
 98             cost += level * binaryNode.frequency;
 99         }
100         return cost;
101     }
102 
103     public String huffmanEncoding(List<BinaryNode> nodeList) {
104         StringBuilder sb = new StringBuilder();
105         BinaryNode currentNode;
106         for (BinaryNode binaryNode : nodeList) {
107             currentNode = binaryNode;
108             while (currentNode != root) {
109                 if (currentNode.isLeftChild())
110                     sb.append("0");// 左孩子编码为0
111                 else if (currentNode.isRightChild())
112                     sb.append("1");// 右孩子编码为1
113                 currentNode = currentNode.parent;
114             }
115         }
116         return sb.toString();
117     }
118 
119     public Map<BinaryNode, String> huffmanDecoding(String encodeString) {
120         BinaryNode currentNode = root;
121         //存储每个叶子结点对应的二进制编码
122         Map<BinaryNode, String> node_Code = new HashMap<HuffmanCode.BinaryNode, String>();
123         StringBuilder sb = new StringBuilder();//临时保存每个结点的二进制编码
124         for (int i = 0; i < encodeString.length(); i++) {
125             
126             char codeChar = encodeString.charAt(i);
127             sb.append(codeChar);
128             if (codeChar == '0')
129                 currentNode = currentNode.left;
130             else
131                 currentNode = currentNode.right;
132             if (currentNode.left == null && currentNode.right == null)// 说明是叶子结点
133             {
134                 node_Code.put(currentNode, sb.toString());
135                 sb.delete(0, sb.length());//清空当前结点,为存储下一个结点的二进制编码做准备
136                 currentNode = root;//下一个叶子结点的解码,又从根开始
137             }
138         }
139         return node_Code;
140     }
141 
142     // for test purpose
143     public static void main(String[] args) {
144         Integer[] frequency = { 10, 15, 12, 3, 4, 13, 1 };//各个结点的初始频率
145         HuffmanCode hc = new HuffmanCode();
146         List<BinaryNode> nodeList = hc.make_set(frequency);//构造各个单节点树
147         hc.buildHuffmanTree(nodeList);//构建huffman tree
148         int totalCost = hc.huffman_cost(nodeList);//计算huffman tree的代价
149         System.out.println(totalCost);
150         String encodeStr = hc.huffmanEncoding(nodeList);//将各个叶子结点进行huffman 编码
151         System.out.println("编码后的字符串" + encodeStr);
152         
153         //根据编码字符串解码
154         Map<BinaryNode, String> decodeMap = hc.huffmanDecoding(encodeStr);
155         Set<Map.Entry<BinaryNode, String>> entrys = decodeMap.entrySet();
156         for (Map.Entry<BinaryNode, String> entry : entrys) {
157             BinaryNode node = entry.getKey();
158             String code = entry.getValue();
159             System.out.println("Node's frequency=" + node.frequency + " : " + code);
160         }
161     }
162 }