本文共 8085 字，大约阅读时间需要 26 分钟。

霍夫曼编码

基本介绍

1. 霍夫曼编码是一种编码方式，属于一种程序算法
2. 霍夫曼编码是霍夫曼树在通讯领域的经典应用之一
3. 霍夫曼编码广泛用于数据文件的压缩，压缩率通常在20% 到90%，通常数据的重复率越高，那么压缩率就越高
4. 霍夫曼编码是可变字长编码（VLC）的一种，由霍夫曼提出，又称之为最佳编码

通讯领域中常用的编码方式

1. 定长编码

• 对原始数据不加任何的修改，原原本本按照对应的编码集，转成二进制代码进行存储。占用空间大。
  

2. 变长编码

• 按照字符出现的次数进行编码，原则上是出现的次数越多，则编码越小。
• 是比较简洁，但是会出现多义性，因为代码彼此之间有重复。
• 前缀编码：字符的编码不是其余字符编码的前缀。
  

3. 霍夫曼编码

• 对所给字符串的各个字符出现的个数进行统计
• 按照上面字符出现的次数构建霍夫曼树，次数作为权值，同时你的节点上要有所代表的字符。
• 根据霍夫曼树给各个字符进行编码：
  • 向左的路径为0，向右的路径为1
  • 根据到达给节点的路径确定该节点代表字符的编码
  • 生成的编码是前缀的编码，每一个编码都不会是另外一个字符的前缀。致使在匹配的时候不会出现多义性
• 按照上面的霍夫曼编码，将原先的字符换转换成编码。此编码是前缀编码，不会出现多义性，同时又对在定长编码编译情况下原长码进行压缩处理，是无损压缩。
• 
• 问题：当有大量的字符是相同的出现次数时，相同权值的不同叶子节点可能排在不同的位置，形成不同的霍夫曼树，故而形成不同的代码，但是WPL始终是相同的，所以没有必要担心。最终形成的压缩文件的大小一定相同，因为WPL始终是相同的。

思路分析

1. 梗概：将每一个字符本身的ASCII码和其出现的次数两者结合，以出现的次数为权构建霍夫曼树，再根据到达对应节点的路径生成对应的霍夫曼编码。
2. 总体步骤：构建相应的霍夫曼树——》遍历读取生成相应的霍夫曼编码
3. 具体分析

• 节点类：在满足基本节点的特征的基础上，必须把出现的次数作为权值，结点必须包含其本身代表的字符的ASCII码值。同时涉及到构建霍夫曼值，所以必须实现Comparable接口
• 主类中：
  • 将所给的字符串生成字节型数组
  • 将字节型数组根据自身的内容和出现的次数，生成对应的Node结点（用Map类处理计数），然后转成包含Node的集合类对象list
  • 生成霍夫曼树
  • 遍历霍夫曼树生成对应的霍夫曼编码

代码实现

1. Code类：

class Node implements Comparable
   
    {
       Byte date;    //表示字符对应的ASCII码    int weight;    //表示对应字符出现的次数    Node left;    Node right;    public Node(Byte date, int weight) {
           this.date = date;        this.weight = weight;    }    @Override    public int compareTo(Node o) {
           return this.weight - o.weight;    }    @Override    public String toString() {
           return "Node{" +                "date=" + date +                ", weight=" + weight +                '}';    }    public void preOrder(){
           if (this != null){
               System.out.println(this);        }        if (this.left != null){
               this.left.preOrder();        }        if (this.right != null){
               this.right.preOrder();        }    }}
   

2. 主类中

• 统计各字符出现的次数，并将之转换成对应的集合类

private static List
   
     getNodes(byte[] bytes){
           List
    
      list = new ArrayList
     
      ();        //创建对应的集合类，用来创建霍夫曼树---每一个对象是节点类Node        //遍历对应的生成的Byte【】数组，然后统计一下各个字符出现的次数---用Map类，键值对数据        Map
      
        counts = new HashMap
       
        ();        for (byte ch : bytes){
               Integer count = counts.get(ch);            //获取出现字节对应的次数            if (count == null){
                   //如果对应的Integer是空，说明第一次出现                counts.put(ch,1);                //再map类中，put是添加，put也是修改            }else{
                   //如果对应的Integer不为空，说明已经录入过相应的数字                //所以将原来的数字加1                counts.put(ch,count + 1);            }        }        //遍历Map类中的每一个键值对，将之生成对应的list类对象        for(Map.Entry
        
          entry:counts.entrySet()){ list.add(new Node(entry.getKey(),entry.getValue())); //key是对应的字符，value是对应的出现的次数 } return list; }
        
       
      
     
    
   

• 根据生成的集合类，整理生成对应的霍夫曼树

private static Node huffmanTree(byte[] bytes){
           List
   
     list = getNodes(bytes);        Node left;        Node right;        while (list.size() > 1){
               Collections.sort(list);            left = list.get(0);            list.remove(left);            right = list.get(0);            list.remove(right);            Node parent = new Node(null,left.weight + right.weight);            parent.left = left;            parent.right = right;            list.add(parent);        }        return list.get(0);    }
   

• 遍历霍夫曼树生成各个叶子节点的对应的路径

static Map
   
     huffmanCodes = new HashMap
    
     ();//存放霍夫曼编码的Map类，公共变量，每一次递归都要存储，所以静态变量static StringBuilder stringBuilder = new StringBuilder();//拼接字符串的起点，根节点对应的拼接点/**     * 功能描述：将传入的node节点的所有叶子结点的霍夫曼编码并且放入到霍夫曼编码集合中     *     * @param node 对应的传入待处理的节点，     * @param code  分别代码不同方向路径的值，左子节点为0，右子节点为1     * @param stringBuilder   用于拼接路径，是不是说一个每一条路都对应了一个个stringbuilder     */    private static void getCodes(Node node,String code,StringBuilder stringBuilder){
           //首先用你传入的Stringbuilder构建一个Stringbuilder        StringBuilder stringBuilder1 = new StringBuilder(stringBuilder);        //一开始就两条路，那就两个，然后每一次走不通的路都会生成不同的值，        // 同时还是在上一个节点的基础上进行生成        stringBuilder1.append(code);        //已经在原先的基础上生成了一个对应的一个stringbuilder，而选择不同的路径也要增加一个code值，代表我走的这条路        if (node != null){
               //如果node等于空就不去处理，说明已经到达结尾，不为空才有相关的值进行判断            // 判断当前节点是叶子节点还是非叶子节点            if (node.date == null){
                   //说明是非叶子结点，因为本身就没有代表字母                //向两边进行递归                getCodes(node.left,"0",stringBuilder1);                getCodes(node.right,"1",stringBuilder1);            }else{
                   //data不为空，说明是叶子节点，进行存储               huffmanCodes.put(node.date,stringBuilder1.toString());            }        }    }
    
   

• main方法：

public static void main(String[] args) {
       String content = "I like Java.Do you like Java?";    byte[] contentBytes = content.getBytes();    //字符串和字节的区别是什么？字节就是将字符转成为对应的ASCII码，字符就是输出字符的本身    getCodes(huffmanTree(contentBytes),"",stringBuilder);    System.out.println("生成的霍夫曼编码表" + huffmanCodes);}

分析与总结

1. 处理处理存在映射关系的两组数据，用Map类，既便于计算出现次数，又便于形成一一对应的关系，用于翻译输出，所以整个过程有两次转换，第一次是在统计各个字符出现的次数，将字节型数组转成Map类；第二次是在由霍夫曼树生成霍夫曼编码时，由树生成Map的编码。
2. 在形成编码的过程中，“边走边成路！”，每一次走不同的结点都会迭代之前的路径生成对应的不同的路径，而路径本身又生成对应的编码。关键点还是还设置一个共有的起点Stringbuilder，共有的记录册HashMap HuffmanCode
3. 总的过程：字符串 —— 》字节型数组——》HashMap<Byte,String>——》ArrayList list——》霍夫曼树——》霍夫曼编码
4. 对于集合类的操作很不流畅，都忘得差不多了，尤其是在遍历键值对的部分关于entry。

复习代码：

package huffmancode;import java.util.*;public class HuffmanCode2 {
       public static void main(String[] args) {
           String str = "I have no choice but I have to do!I believe in myself!";        byte[] bytes = str.getBytes();        //然后将字节型数组生成对应的节点类        //将节点类生成霍夫曼树        //有霍夫曼树生成对应的霍夫曼编码        System.out.println(acquireHuffmanCode(bytes));    }    //改良，连续调用方法，我自己都晕，将所有的方法封装起来进行调用    public static Map
   
     acquireHuffmanCode(byte[] bytes){
           getHuffmanCode(getHuffmanTree(getNode(bytes)),"",stringBuilder);        return HuffmanCode;    }    //第三部分，有对应的霍夫曼树生成对应的霍夫曼编码    //编码Map类承装，设置一个地图碎片的蓝本，用于拼接    static Map
    
      HuffmanCode = new HashMap
     
      ();    static StringBuilder stringBuilder = new StringBuilder();    private static void getHuffmanCode(Node2 node2,String code,StringBuilder stringBuilder){
           StringBuilder stringBuilder1 = new StringBuilder(stringBuilder);        stringBuilder1.append(code);        if (node2 != null){
               //说明当前节点不为空，可以斤西瓜下一步的递归操作            //节点类型有两种，叶子节点和非叶子节点            if (node2.ch == null){
                   //非叶子节点进行左右递归,并且不用判定左右节点是否为空                getHuffmanCode(node2.left,"0",stringBuilder1);                getHuffmanCode(node2.right,"1",stringBuilder1);            }else{
                   //是叶子节点说明已经递归完毕                HuffmanCode.put(node2.ch,stringBuilder1.toString());            }        }    }    //根据生成的集合list整理生成对应的霍夫曼树    private static Node2 getHuffmanTree(List
      
        list){
           //生成霍夫曼树就两步，不断重复，排序，建树        while (list.size() > 1){
               //排序            Collections.sort(list);            Node2 left = list.get(0);            Node2 right = list.get(1);            list.remove(left);            list.remove(right);            Node2 parent = new Node2(null,left.val + right.val);            parent.left = left;            parent.right = right;            list.add(parent);        }        return list.get(0);    }    //将字节型数组生成对应的节点类    private static List
       
         getNode(byte[] bytes){
           List
        
          list = new ArrayList
         
          (); //创建一个集合用来存储转换过后生成的节点 Map
          
            counts = new HashMap
           
            (); //调用Map集合类，利用其键值对的存储方式，便于统计书出现次数 //遍历字节数组，调用Map类，进行统计 for (byte ch:bytes){ Integer count = counts.get(ch); //第一次输入，看看是否有对应的数字 if (count != null){ //如果count不为null，说明已经遍历过了，可以进一部存储 counts.put(ch,count + 1); }else{ //如果count为null，说明没有遍历过，是第一次出现 counts.put(ch,1); } } //统计完数据之后，用来创建对应的节点类 for (Map.Entry
            
              enty:counts.entrySet()){ //说明counts是可以当作数组来及进行遍历 list.add(new Node2(enty.getKey(),enty.getValue())); } return list; }}class Node2 implements Comparable
             
              { public Byte ch; //对应的字符的字节码 int val; //对应字符出现的次数 Node2 left; Node2 right; public Node2(Byte ch, int val) { this.ch = ch; this.val = val; } @Override public String toString() { return "Node2{" + "ch=" + ch + ", val=" + val + '}'; } @Override public int compareTo(Node2 o) { return this.val - o.val; }}
             
            
           
          
         
        
       
      
     
    
   

转载地址：http://oqgpb.baihongyu.com/