您的位置: 首页  >  文章  >  数据结构之霍夫曼树

数据结构之霍夫曼树

分类: 文章 • 2025-02-24 20:31:47

计算机里每个字符在没有压缩的文本文件中都由一个字节（如ASCII码）或两个字节（如Unicode码）表示。这些方案中，每个字符需要相同的位数

下表列出了字母对应的ASCII码

字母            十进制                二进制

A                  65                 01000001

B                  66                 01000010

C                  67                 01000011

……

X                  88                 01011000

Y                  89                 01011001

Z                  90                 01011010

在英文中，字母E的使用频率最高，而字母Z的使用频率最低，但是，无论使用频率高低，我们一律使用相同位数的编码来存储，是不是有些浪费空间呢？试想，如果我们对使用频率高的字母用较少的位数来存储，而对使用频率低的字母用较多的位数来存储，会大大提升存储效率

霍夫曼编码就是根据以上的设想来处理数据压缩的

例如，我们要发送一句消息：

SUSIE SAYS IT IS EASY

统计所有符号出现的频率：

换行符        1次

T                  1次

U                  1次

A                  2次

E                  2次

Y                  2次

I                   3次

空格            4次

S                  6次

S出现的频率最多，我们可以将它的编码设为10，其次是空格，我们将它设置为00，接下来的编码必须增加位数了。三位码我们有八种选择：000,001,010,011,100,101,110,111。但是，以10或00开头的是不能使用的，只能从010,011,110,111中选择。因为如果我们用101表示I，用010表示Y，101010既可以分解为101,010两个有意义的编码，也能分解为10,10,10三个有意义的编码，这显然是不允许的。我们必须保证，任何信息编码之后，解码时都不会出现歧义。借助霍夫曼树就能便捷的实现编码

霍夫曼树是最优二叉树。树的带权路径长度规定为所有叶子结点的带权路径长度之和，带权路径长度最短的树，即为最优二叉树。在最优二叉树中，权值较大的结点离根较近。

首先就需要构建一个霍夫曼树，一般利用优先级队列来构建霍夫曼树

以上面的消息为例，我们先来分析一下构建霍夫曼树的过程，下图中，if代表换行符，sp代表空格

数据结构之霍夫曼树

首先，将字符按照频率插入一个优先级队列，频率越低越靠近队头，然后循环执行下面的操作：

1、取出队头的两个树

2、以它们为左右子节点构建一棵新树，新树的权值是两者之和

3、将这棵新树插入队列

直到队列中只有一棵树时，这棵树就是我们需要的霍夫曼树

接下来我们用java来实现上面的过程，代码如下：

[java] view plain copy
  1. //节点类  
  2. public class Node{  
  3.       private String key;           //树节点存储的关键字，如果是非叶子节点为空  
  4.       private int frequency;        //关键字词频  
  5.       private Node left;            //左子节点  
  6.       private Node right;           //右子节点  
  7.       private Node next;            //优先级队列中指向下一个节点的引用  
  8.        
  9.       public Node(int fre,String str){  //构造方法1  
  10.              frequency = fre;  
  11.              key = str;  
  12.       }  
  13.       public Node(int fre){  //构造方法2  
  14.              frequency = fre;  
  15.       }  
  16.        
  17.       public String getKey() {  
  18.              return key;  
  19.       }  
  20.       public void setKey(String key) {  
  21.              this.key = key;  
  22.       }  
  23.       public Node getLeft() {  
  24.              return left;  
  25.       }  
  26.       public void setLeft(Node left) {  
  27.              this.left = left;  
  28.       }  
  29.       public Node getRight() {  
  30.              return right;  
  31.       }  
  32.       public void setRight(Node right) {  
  33.              this.right = right;  
  34.       }  
  35.       public Node getNext() {  
  36.              return next;  
  37.       }  
  38.       public void setNext(Node next) {  
  39.              this.next = next;  
  40.       }  
  41.       public int getFrequency() {  
  42.              return frequency;  
  43.       }  
  44.       public void setFrequency(int frequency) {  
  45.              this.frequency = frequency;  
  46.       }  
  47. }  


[java] view plain copy
  1. //用于辅助创建霍夫曼树的优先级队列  
  2. public class PriorityQueue{  
  3.       private Node first;  
  4.       private int length;  
  5.        
  6.       public PriorityQueue(){  
  7.              length = 0;  
  8.              first = null;  
  9.       }  
  10.        
  11.       //插入节点  
  12.       public void insert(Node node){  
  13.              if(first == null){  //队列为空  
  14.                     first = node;  
  15.              }else{  
  16.                     Node cur = first;  
  17.                     Node previous = null;  
  18.                     while(cur.getFrequency()< node.getFrequency()){  //定位要插入位置的前一个节点和后一个节点  
  19.                            previous = cur;  
  20.                            if(cur.getNext() ==null){  //已到达队尾  
  21.                                   cur = null;  
  22.                                   break;  
  23.                            }else{  
  24.                                   cur =cur.getNext();  
  25.                            }  
  26.                             
  27.                     }  
  28.                     if(previous == null){  //要插入第一个节点之前  
  29.                            node.setNext(first);  
  30.                            first = node;  
  31.                     }else if(cur == null){  //要插入最后一个节点之后  
  32.                            previous.setNext(node);  
  33.                     }else{  //插入到两个节点之间  
  34.                            previous.setNext(node);  
  35.                            node.setNext(cur);  
  36.                     }  
  37.              }  
  38.              length++;  
  39.       }  
  40.        
  41.       //删除队头元素  
  42.       public Node delete(){  
  43.              Node temp = first;  
  44.              first = first.getNext();  
  45.              length--;  
  46.              return temp;  
  47.       }  
  48.        
  49.       //获取队列长度  
  50.       public int getLength(){  
  51.              return length;  
  52.       }  
  53.        
  54.       //按顺序打印队列  
  55.       public void display(){  
  56.              Node cur = first;  
  57.              System.out.print("优先级队列：\t");  
  58.              while(cur != null){  
  59.                     System.out.print(cur.getKey()+":"+cur.getFrequency()+"\t");  
  60.                     cur = cur.getNext();  
  61.              }  
  62.              System.out.println();  
  63.       }  
  64.        
  65.       //构造霍夫曼树  
  66.       public HuffmanTree buildHuffmanTree(){  
  67.              while(length > 1){  
  68.                     Node hLeft = delete();  //取出队列的第一个节点作为新节点的左子节点  
  69.                     Node hRight = delete(); //取出队列的第二个节点作为新节点的右子节点  
  70.                     //新节点的权值等于左右子节点的权值之和  
  71.                     Node hRoot = new Node(hLeft.getFrequency()+hRight.getFrequency());  
  72.                     hRoot.setLeft(hLeft);  
  73.                     hRoot.setRight(hRight);  
  74.                     insert(hRoot);  
  75.              }  
  76.              //最后队列中只剩一个节点，即为霍夫曼树的根节点  
  77.              return new HuffmanTree(first);  
  78.       }  
  79.        
  80. }  
 
[java] view plain copy
  1. import java.util.HashMap;  
  2. import java.util.Map;  
  3. //霍夫曼树类  
  4. public class HuffmanTree {  
  5.       private Node root;  
  6.       private Map codeSet = new HashMap();  //该霍夫曼树对应的字符编码集  
  7.        
  8.       public HuffmanTree(Node root){  
  9.              this.root = root;  
  10.              buildCodeSet(root,"");  //初始化编码集  
  11.       }  
  12.        
  13.       //生成编码集的私有方法，运用了迭代的思想  
  14.       //参数currentNode表示当前节点，参数currentCode代表当前节点对应的代码  
  15.       private void buildCodeSet(NodecurrentNode,String currentCode){  
  16.              if(currentNode.getKey() != null){  
  17.                     //霍夫曼树中，如果当前节点包含关键字，则该节点肯定是叶子节点，将该关键字和代码放入代码集  
  18.                     codeSet.put(currentNode.getKey(),currentCode);  
  19.              }else{//如果不是叶子节点，必定同时包含左右子节点，这种节点没有对应关键字  
  20.                     //转向左子节点需要将当前代码追加0  
  21.                     buildCodeSet(currentNode.getLeft(),currentCode+"0");  
  22.                     //转向右子节点需要将当前代码追加1  
  23.                     buildCodeSet(currentNode.getRight(),currentCode+"1");  
  24.              }  
  25.       }  
  26.        
  27.       //获取编码集  
  28.       public Map getCodeSet(){  
  29.              return codeSet;  
  30.       }  
  31.        
  32. }  

 
[java] view plain copy
  1. //测试类  
  2. public static void main(String[] args) throws Exception{  
  3.              PriorityQueue queue = new PriorityQueue();  
  4.              Node n1 = new Node(1,"if");  
  5.              Node n2 = new Node(1,"U");  
  6.              Node n3 = new Node(1,"T");  
  7.              Node n4 = new Node(2,"Y");  
  8.              Node n5 = new Node(2,"E");  
  9.              Node n6 = new Node(2,"A");  
  10.              Node n7 = new Node(3,"I");  
  11.              Node n8 = new Node(4,"sp");  
  12.              Node n9 = new Node(5,"S");  
  13.              queue.insert(n3);  
  14.              queue.insert(n2);  
  15.              queue.insert(n1);  
  16.              queue.insert(n6);  
  17.              queue.insert(n5);  
  18.              queue.insert(n4);  
  19.              queue.insert(n7);  
  20.              queue.insert(n8);  
  21.              queue.insert(n9);  
  22.              queue.display();  
  23.               
  24.              HuffmanTree tree =queue.buildHuffmanTree();  
  25.              Map map = tree.getCodeSet();  
  26.              Iterator it =map.entrySet().iterator();  
  27.              System.out.println("霍夫曼编码结果：");  
  28.              while(it.hasNext()){  
  29.                     Entry<String,String>entry = (Entry)it.next();  
  30.                     System.out.println(entry.getKey()+"——>"+entry.getValue());  
  31.              }  
  32.       }  

控制台打印结果如下图所示：

数据结构之霍夫曼树

可见，达到了预期的效果

秉承没有最好，只有更好的精神，我们不应该就此止步。现在我们做到的只是得到某个字符对应的霍夫曼编码，但是这个字符的词频仍然需要我们手工去统计、输入，更深入的思考一下，能不能更智能化一点，只要我们输入完整的一段消息，就能给出对应的霍夫曼编码，而且能对编码进行解码呢？

显然是可以的，先面就让我们用神奇的java语言来对上面的底层操作进行更高级的封装，来达到预期的功能

就是说，我们要利用上面已经写出的代码来封装一个编码类，这个类的一个方法接受一个字符串消息，返回霍夫曼编码，此外，还有一个解码类，接受一段完整的霍夫曼编码，返回解码后的消息内容。这实际上就是压缩与解压的模拟过程

[java] view plain copy
  1. import java.util.HashMap;  
  2. import java.util.Iterator;  
  3. import java.util.Map;  
  4. import java.util.Map.Entry;  
  5.    
  6. //霍夫曼编码器  
  7. public class HuffmanEncoder {  
  8.       private PriorityQueue queue;       //辅助建立霍夫曼树的优先级队列  
  9.       private HuffmanTree tree;         //霍夫曼树  
  10.       private String [] message;            //以数组的形式存储消息文本  
  11.       private Map keyMap;                            //存储字符以及词频的对应关系  
  12.       private Map codeSet;                     //存储字符以及代码的对应关系  
  13.        
  14.       public HuffmanEncoder(){  
  15.              queue = new PriorityQueue();  
  16.              keyMap = new HashMap<String,Integer>();  
  17.       }  
  18.        
  19.       //获取指定字符串的霍夫曼编码  
  20.       public String encode(String msg){  
  21.              resolveMassage(msg);  
  22.              buildCodeSet();  
  23.              String code = "";  
  24.              for(inti=0;i<message.length;i++){//将消息文本的逐个字符翻译成霍夫曼编码  
  25.                     code =code+codeSet.get(message[i]);  
  26.              }  
  27.              return code;  
  28.       }  
  29.        
  30.       //将一段字符串消息解析成单个字符与该字符词频的对应关系，存入Map  
  31.       private void resolveMassage(String msg){  
  32.               
  33.              char [] chars =msg.toCharArray();  //将消息转换成字符数组  
  34.              message = new String[chars.length];  
  35.              for(int i =0;i<chars.length;i++){  
  36.                     String key = "";  
  37.                     key =chars[i]+"";  //将当前字符转换成字符串  
  38.                      
  39.                     message [i] =  key;  
  40.                     if(keyMap.containsKey(key)){//如果Map中已存在该字符，则词频加一  
  41.                            keyMap.put(key,(Integer)keyMap.get(key)+1);  
  42.                     }else{//如果Map中没有该字符，加入Map  
  43.                            keyMap.put(key,1);  
  44.                     }  
  45.              }  
  46.       }  
  47.        
  48.       //建立对应某段消息的代码集  
  49.       private void buildCodeSet(){  
  50.              Iterator it =keyMap.entrySet().iterator();  
  51.              while(it.hasNext()){  
  52.                     Entry entry =(Entry)it.next();  
  53.                     //用该字符和该字符的词频为参数，建立一个新的节点，插入优先级队列  
  54.                     queue.insert(new Node((Integer)entry.getValue(),(String)entry.getKey()));  
  55.              }  
  56.              queue.display();  
  57.              tree =queue.buildHuffmanTree();  //利用优先级队列生成霍夫曼树  
  58.              codeSet = tree.getCodeSet();   //获取霍夫曼树对应的代码集  
  59.       }  
  60.        
  61.       //打印该段消息的代码集  
  62.       public void printCodeSet(){  
  63.              Iterator it =codeSet.entrySet().iterator();  
  64.              System.out.println("代码集：");  
  65.              while(it.hasNext()){  
  66.                     Entry entry =(Entry)it.next();  
  67.                     System.out.println(entry.getKey()+"——>"+entry.getValue());  
  68.              }  
  69.              System.out.println();  
  70.       }  
  71.        
  72.       //获取该段消息的代码集  
  73.       public Map getCodeSet(){  
  74.              return codeSet;  
  75.       }  
  76. }  

 
[java] view plain copy
  1. import java.util.Iterator;  
  2. import java.util.Map;  
  3. import java.util.Map.Entry;  
  4.    
  5. //霍夫曼解码器  
  6. public class HuffmanDecoder {  
  7.       private Map codeSet;  //代码段对应的代码集  
  8.        
  9.       public HuffmanDecoder(Map map){  
  10.              codeSet = map;  
  11.       }  
  12.        
  13.       //将代码段解析成消息文本  
  14.       public String decode(String code){  
  15.              String message = "";  
  16.              String key = "";  
  17.              char [] chars = code.toCharArray();  
  18.              for(int i=0;i<chars.length;i++){  
  19.                     key += chars[i];  
  20.                     if(codeSet.containsValue(key)){  //代码集中存在该段代码  
  21.                            Iterator it =codeSet.entrySet().iterator();  
  22.                            while(it.hasNext()){  
  23.                                   Entry entry = (Entry)it.next();  
  24.                                   if(entry.getValue().equals(key)){  
  25.                                          message+= entry.getKey();  //获取该段代码对应的键值，即消息字符  
  26.                                   }  
  27.                            }  
  28.                            key ="";  //代码段变量置为0  
  29.                     }else{  
  30.                            continue;  //该段代码不能解析为文本消息，继续循环  
  31.                     }  
  32.              }  
  33.              return message;  
  34.       }  
  35. }  

 
[java] view plain copy
  1. //测试类  
  2. public static void main(String[] args){  
  3.               
  4.              String message = "chen long fei is hero !";  
  5.              HuffmanEncoder encoder = new HuffmanEncoder();  
  6.              String code =encoder.encode(message);  
  7.               
  8.              encoder.printCodeSet();  
  9.              System.out.print("编码结果：");  
  10.              System.out.println(code);  
  11.               
  12.              HuffmanDecoder decoder = new HuffmanDecoder(encoder.getCodeSet());  
  13.              String message2 =decoder.decode(code);  
  14.              System.out.print("解码结果：");  
  15.              System.out.println(message);  
  16.       }  


运行结果如下图所示：

数据结构之霍夫曼树


相关推荐