Java版赫夫曼编码

文章收藏的好句子：人不需要活太多样子，你认真做好一件事，会解释所有事。

目录

1、赫夫曼编码

     1、1 赫夫曼编码的基本介绍

     1、2 通信领域中信息的处理方式

          1、2、1 定长编码

          1、2、2 变长编码

           1、2、3 赫夫曼编码

1、赫夫曼树编码

1、1 赫夫曼编码的基本介绍

赫夫曼编码是一种编码方式，也是—种程序算法；赫夫曼编码是赫夫曼树在电讯通信中的经典的应用之—；赫夫曼编码广泛地用于数据文件压缩，其压缩率一般在20%~90%之间；赫夫曼码是可变字长编码的一种，Huffman于1952年提出一种编码方法，称之为最佳编码。

1、2 通信领域中信息的处理方式

1、2、1 定长编码

我们列举通信领域中信息的处理方式-定长编码，假设我要发送一句话给别人 “the virus mutated and became weaker and weaker” ，按照定长编码的方式，这句话转化成二进制编码后长度是多少呢？我们先给出一张 Ascill 编码表，如图1所示；

图1

空格（图1未给出空格）的十进制 Ascill 编码是 32，二进制 Ascill 编码是 00100000 ； 看图1，a 的十进制 Ascill 编码是 97，二进制 Ascill 编码是 01100001 ；看懂了图1的 a 字符 Ascill 编码，其他字符的Ascill 编码也应该能看懂了吧？图1中的其他字符 Ascill 编码我不再一一描述，但不管怎么看图1中的字符，它的二进制 Ascill 编码都是8位。我们把上面要发送的一句话放在记事本统计一下字符数，如图2所示；

                                                       图2

看图2，发送的这句话字符长度是46个；然后再看图1字符二进制的 Ascill 码，一个字符占8位，所以发送的这句话换成二进制，长度就是 46 X 8 = 368 。

1、2、2 变长编码

假设我要发送一句话给别人也是 “the virus mutated and became weaker and weaker”，要进行传输的过程，肯定是要转换成二进制编码的，用变长编码的方式可以减少字节所占用的内存；好，我们现在开始进行变长编码分析，我们先把 “the virus mutated and became weaker and weaker” 这句话中每个字符出现的个数用表格列举出来，如下表1所示；

好，我们现在对表1的字符进行二进制编码，原则上出现次数越多的，编码就越小；例如，字符 e ，出现的次数是最多的，我们把它的编码弄成0，好了，现在我们也把表1的字符弄一个编码表出来，如表2所示；

我们把 “the virus mutated and became weaker and weaker” 这句话，全部转换成用表2中的二进制编码表示，得到表3；

表3中的字符装不下那么多，我就省略了；“the virus mutated and became weaker and weaker” 这句话按照表2的规则转换成二进制编码就是 1001101011011110011111111011000111100101000101110110101111110100001010000110010101010011110110101110010101010011 ；把这串二进制编码放入记事本总计其长度，得到如图3的长度统计；

                           图3

二进制长度为112，相对于定长编码来说，“the virus mutated and became weaker and weaker” 这句话的压缩率为 （368-112）/ 368 X 100% = 70% ，但是我们解码的时候就麻烦了，比如开头的编码是解码成10呢还是101，如果是解码成10就变成字母 a 了，就解码错了。

1、2、3 赫夫曼编码

赫夫曼编码使用了定长编码和变长编码的一些优点，例如它要用到十进制的 Ascill 码和用到字符出现的次数作为二进制编码，这样就可以做到压缩字节码又可以解码无损失。好，我们现在先画一棵含有赫夫曼编码的一棵树，方便下面说的内容好理解，如图3所示；

看图3，节点左边的路径就用0表示，右边的路径用1表示，a 字符的编码是 10 。

我们继续使用 “the virus mutated and became weaker and weaker” 这句话进行传输，这次我们用赫夫曼编码，步骤如下所示；

（1）还是使用表1中字符。

（2）将表1中字符出现的次数作为权值构建赫夫曼树（构建赫夫曼树的过程可以看Java版赫夫曼树这篇文章）。

（3）根据赫夫曼树，向左的路径为0，向右的路径为1，我们要发送的字符串中字符二进制编码如表2所示。

（4）用十进制的 Ascill 码作为叶子节点的 data 值，用节点的权值转化为二进制码。

（5）构建成赫夫曼编码的这棵树肯定是赫夫曼树，最后根据赫夫曼编码使得 “the virus mutated and became weaker and weaker” 这句话转化成二进制码是：1000101111001100011101111010110110000010000100100010101000101001010111100

好，我们现在代码实现一把；

（1）创建一个节点类 Node ：

public class Node implements Comparable{
  private Byte data;//存放十进制的 Ascill 码，比 'a' 字符，那么 Ascill 码就是97
  private int weight;//权值
  private Node left;//左孩子
  private Node right;//右孩子
  @Override
  public int compareTo(Node arg0) {
    // 从小到大排序
    return this.weight - arg0.weight;
  }
  public Node(Byte data, int weight) {
    super();
    this.data = data;
    this.weight = weight;
  }
  
  public Byte getData() {
    return data;
  }
  
  public Node getLeft() {
    return left;
  }
  public void setLeft(Node left) {
    this.left = left;
  }
  public Node getRight() {
    return right;
  }
  public void setRight(Node right) {
    this.right = right;
  }
  
  public int getWeight() {
    return weight;
  }


  
}

（2）创建一个生成赫夫曼编码的类 Test ：

public class Test {
    Node root;
  public static void main(String[] args) {
    String s = "the virus mutated and became weaker and weaker";
    byte[] bs = s.getBytes();
    System.out.println("s的长度为：" + s.length());
    Test test = new Test();
    List list = test.getNode(bs);
    test.root = test.createHuffmanTree(list);
    
    //生成赫夫曼编码表，将 赫夫曼编码表 存放到 huffumanCodes 中
    test.getCodes(test.root, "", test.sb);
    
    s = "";
    for (Map.Entry map : test.huffumanCodes.entrySet()){
      s = s + map.getValue();
    }
    
    System.out.println("s根据赫夫曼编码而生成对应的二进制码是" + s);
  }
  
  //拼接赫夫曼树的节点的路径，节点的左路径用“0” 表示，右路径用“1”表示
  StringBuilder sb = new StringBuilder();
  
  Map huffumanCodes = new HashMap();
  
  //生成赫夫曼编码表
  
  private void getCodes(Node node,String code,StringBuilder sb) {
    StringBuilder sb2 = new StringBuilder(sb);
    
    //将code 加入到 sb2 中
    sb2.append(code);
    if (node != null) {
      
      //非叶子节点
      if (node.getData() == null) {
        
        //向左递归处理
        getCodes(node.getLeft(), "0", sb2);
        
        //向右递归处理
        getCodes(node.getRight(), "1", sb2);
        
        //是叶子节点
      } else {
        huffumanCodes.put(node.getData(), sb2.toString());
      }
    }
  }
  
  private List getNode(byte[] bs) {
    ArrayList list = new ArrayList();
    
    //统计byte出现的次数
    Map map = new HashMap();
    
    for (int i = 0; i entry : map.entrySet()) {
      Byte data = entry.getKey();
      int weight = entry.getValue();
      Node node = new Node(data,weight);
      list.add(node);
    }
    return list;
  }
  
  //创建赫夫曼树
  private Node createHuffmanTree(List list) {
      while (list.size() > 1) {


        // 排序，从小到大排序
        Collections.sort(list);


        // System.out.println("list = " + list);


        
        Node minNode = list.get(0);


        
        Node secondMinNode = list.get(1);


        
        Node parentNode = new Node(null,minNode.getWeight()
            + secondMinNode.getWeight());
        parentNode.setLeft(minNode);
        parentNode.setRight(secondMinNode);


        
        list.remove(minNode);
        list.remove(secondMinNode);


        
        list.add(parentNode);
      }


      
      return list.get(0);
    }


}

日志打印如下所示：

从日志可以看出，跟我们上面所说的结果，根据赫夫曼编码转化成二进制码是一样的；这里说的是赫夫曼编码，下一篇会写赫夫曼解码，敬请期待。