树论-哈夫曼树（Huffman Tree）

欢迎大家来到IT世界,在知识的湖畔探索吧!

哈夫曼树（Huffman Tree）

Kitten 2023-09-07

前言

我们都对身边的压缩软件都不陌生了，它们使用高效的压缩算法给我们平时工作活着生活中带来极大的便利，你是否经常会思考压缩算法是如何将数据进行压缩又是如何解压的呢。如何确保数据能被压缩到极致？又如何确保数据解压后不丢失或者乱码呢？

映射关系

我们不妨先忘却压缩算法，我们做一种思考，首先我们可以确定的是无论是文件或者是网络报文，计算机中存储和传输数据的最小单位是字节(byte)。但是计算机传输数据的最小单位是位（bit），那么是否可以通过某种映射关系将原来需要8位表示的字节（1byte=8it），可以用较少的位来表示。比如我们有这样一个字符串数据：ABCDEFGH，那么传输它就需要64（bit）空间，加入我们可以通过某种映射关系：A => 000，B => 001，C => 010 ，D => 100。我们用3bit表达了8bit的内容，那么数据占有的空间将大大的降低。

映射关系带来的问题

假如我们有如下映射关系：A => 0，B => 001，C => 010 ，D => 100，那么字符串ABCDAAAA可以表示为：000。那么问题来了，此时就产生了歧义，前面的000是被解析成3个A？还是是一个A和一个B。因为此时发生了B的映射码前缀包含了A这种场景，而这样的场景的出现就会导致数据最终解码后是错误的。

欢迎大家来到IT世界,在知识的湖畔探索吧!

前缀编码

因为一个字符的映射元数包含了其他字符的映射元数据的时候，就会出现歧义，就会导致数据的解码紊乱，那么换句话说，只要我们确保对每个字符做映射关系的时候确保不包含其它字符的前缀，那么就可以解决这个问题。那么解决这个技术问题数学家哈夫曼就研究出了哈夫曼编码，也叫做前缀编码。那么我们所说的哈夫曼树其实就是对哈夫曼编码的一种实现方式，目的就是为了生成不重复的映射编码集合。并且保证对原字符集做编码的时候最短。

权重

对于一个任意字符集而言，为了尽可能提高压缩的效率，需要做到一个前提条件，即需要对目标数据中出现的字符频率进行统计，即对每个字符赋予一个权重，重复的字符越多，那么权重越高。那么对于实现一个编码表来说，我们需要将权重高的优先分配一个较短的二进制数据来表示该字符的关系，那么在对原字符串进行编码的时候，字符出现次数越高（权重越高）那么对于整体的压缩的效率来说就越高。

哈夫曼树和二叉树

哈夫曼树是用于实现哈夫曼编码的一种技术手段，树的每一个叶子节点代表着需要编码的目标字符字符，该叶子节点到根节点的路径长度就是相应哈夫曼编码字符串的长度，树的路径长度是从树根到树中每一结点的路径长度之和最短。

前缀不重复

为了满足编码表的两个条件：

（一）任意字符的编码不能包含其它字符编码的前缀。

（二）为权重大的字符优先分配编码。

为了实现第一个前提条件，我们想到了使用一颗二叉树数据结构。每个结点使用左右指针连接，刚好可以代表二进制中的0和1，形成互斥关系，从根节点出发到每个结点的路径就可以表示我们的编码。为了确保前缀不重复，我们将每个叶子结点才存放目标字符，数学家莱布尼茨曾对德国皇帝说：“世界上没有完全相同的两片树叶”。放在这里也有异曲同工之妙了，因为节点的左右子树指针要么是0要么是1，那么根节点到叶子节点的路径绝对是唯一的，也就是它绝对不能成为其它叶子节点的路径的前缀（如下面右图）。但是如果目标字符存落于非叶子节点那就无法保证了。比如下面左图中C和D的结点都拥有共同前缀1，也就是说当于他们的编码前缀包含了B。

最优路径

但是仅仅使用普通的一颗二叉树并不能满足我们的期望，我们期望的是最终被利用的编码尽可能的短，也就要保证二叉树满足以下特性。即：设二叉树具有n个带权值的叶节点，那么从根节点到各个叶节点的路径长度与相应节点权值的乘积（也叫二叉树的带权路径长度）的和最小。

（权： 权代表的是叶子结点的数据信息，是具体的值，也就是结点所储存的值）

在上图中，3棵二叉树都有4个叶子结点A、B、C、D，分别带权7、5、2、4，则它们的带权路径长度为

（a）WPL = 7×2 + 5×2 + 2×2 + 4×2 = 36

（b）WPL = 4×2 + 7×3 + 5×3 + 2×1 = 46

（c）WPL = 7×1 + 5×2 + 2×3 + 4×3 = 35

其中（c）的WPL最小，其实C就是一个最优路径树，也就是哈夫曼树。

哈夫曼树的实现

哈弗曼树的构造

构造哈夫曼树的原则

（一）权值越大的叶节点越靠近根节点。

（二）权值越小的叶节点越远离根节点。

对于最优二字首先我们就该想到的算法就应该是贪心算法，实际上也确实如此，哈夫曼树的构造也就是使用贪心算法。大致流程为：将需要编码的数据排序，每次从中取两个权重最小的结点，新建一个新的结点，被取出的结点中权重小的作为新结点的左子树，权重大的作为新结点的右子树。然后将左右子树的权重相加作为新结点的权重。然后将新结点重新放入有序集合中，进行下一轮的选举。重复这一步骤最终就可以构造出一颗哈弗曼树。

代码实现

 public class HuffmanTree { //表示根节点，用于根节点向子树遍历 private Node 
  
    root; //表示叶子节点也就是目标字符的集合 private List<Node 
   
     > leafNodes; public HuffmanTree() { this.leafNodes = new ArrayList<>(); root = null; } // 哈弗曼树的结点信息 private static class Node<C, W extends Comparable 
    
      > implements Comparable<Node 
     
       > { // 目标字符 private C character; // 权重 private W weight; // 父结点 private HuffmanTree.Node 
      
        parent; // 左子树 private HuffmanTree.Node 
       
         left; // 右子树 private HuffmanTree.Node 
        
          right; public Node(C character, W weight) { this.left = null; this.character = character; this.weight = weight; this.right = null; this.right = null; } @Override public int compareTo(Node 
         
           node) { return weight.compareTo(node.weight); } } } 
          
         
        
       
      
     
    
  

欢迎大家来到IT世界,在知识的湖畔探索吧!

欢迎大家来到IT世界,在知识的湖畔探索吧!public void create(Map 
  
    map) { if (map.size() == 1) { String key = map.keySet().toArray(new String[0])[0]; Node 
   
     node = new Node<>(key, map.get(key)); root = node; this.leafNodes.add(node); return; } // 为了方便使用优先队列，可以使用插入排序/堆排序来实现。 // 构建优先级队列 PriorityQueue<Node 
    
      > priorityQueue = new PriorityQueue<>(); map.forEach((k, v) -> { Node 
     
       node = new Node<>(k, v); priorityQueue.offer(node); }); // 遍历的次数就是结点个数-1 int len = priorityQueue.size(); for (int i = 0; i < len - 1; i++) { // 拿出权重最小的两个节点（如果自己用排序实现除了拿出元素，需要手动移除元素） Node 
      
        left = priorityQueue.poll(); Node 
       
         right = priorityQueue.poll(); // 权重相加赋给新结点 Integer w = left.weight + right.weight; Node 
        
          node = new Node<>(null, w); left.parent = node; right.parent = node; node.left = left; node.right = right; this.root = node; // 添加到叶子节点集合中 if (left.left == null && left.right == null) { leafNodes.add(left); } if (right.left == null && right.right == null) { leafNodes.add(right); } // 新节点重新入队 priorityQueue.offer(node); } } 
         
        
       
      
     
    
  

public void code() { // 遍历所有叶子节点 for (Node 
  
    node : leafNodes) { Node 
   
     cur = node; Node 
    
      p = cur.parent; StringBuilder code = new StringBuilder(); while (p != null) { // 因为是从叶子节点向上遍历所以编码得从前面插 // 当前节点是父节点的右子树，就在编码前面+1 if (p.right == cur) { code.insert(0, 1); } // 当前节点是父节点的右子树，就在编码前面+0 else { code.insert(0, 0); } cur = p; p = cur.parent; } System.out.println("节点" + node.character + ":" + code); } }