目录

一：基本介绍

二：原理剖析

三：实现步骤

四：代码实现

一：基本介绍

1. 赫夫曼编码也翻译为哈夫曼编码，又称霍夫曼编码，是一种编码方式，属于一种程序算法。
2. 赫夫曼编码是赫夫曼树在电讯通信中的经典的应用之一。
3. 赫夫曼编码广泛地用于数据文件压缩。其压缩率通常在20%-90%之间。
4. 赫夫曼码是可变子长编码（VLC）的一种。huffman于1952年提出一种编码方法，称之为最佳编码。

二：原理剖析

三：实现步骤

（1）i like like like java do you like a java

(2)d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5  (空格)：9 //各个字符对应的个数

（3）按照上面字符出现的次数构建一颗赫夫曼树，次数作为权值。

(4)根据哈夫曼树，给各个字符，规定编码(前缀编码)，向左的路径为0，向右的路径为1，编码如下：

o:1000 u:10010 d:100110 y:100111 i:101 a:110 k:1110 e:1111 j:0000 v:0001 l:001 (空格):01

说明：

（1）原来长度是359，压缩了（359-133）/359==62.9%

（2）此编码满足前缀编码，即字符的编码都不能是其他字符编码的前缀。不会造成匹配的多义性。

（3）赫夫曼编码是无损处理方案。

注意：这个哈夫曼树根据排序方法不同，也可能不太一样，这样对应的哈夫曼编码也不完全一样，但是wpl是一样的，都是最小的，比如：如果我们让每次生成的新的二叉树总是排在权值相同的二叉树的最后一个，则又会产生不一样的二叉树。

功能：根据哈夫曼编码压缩数据的原理，需要创建“i like like like java do you like a java”对应的哈夫曼树。

思路：

（1）Node{data（存放数据），weight（权值），left和right….}

（2）得到“i like like like java do you like a java”对应的byte[]数组

（3）编写一个方法，将准备构建哈夫曼树的Node节点放到List

（4）可以通过list创建对应的哈夫曼树。

四：代码实现

package huffmanCode;

import java.util.*;

public class huffmanCode {
    public static void PreOrder(Node root){
        if(root!=null){
            root.PreOrder();
        }else {
            System.out.println("哈夫曼树为空，不能遍历");
        }
    }
    //可以通过List创建对应的哈夫曼树
    public static Node createHuffmanTree(List<Node> nodes){
        while(nodes.size()>1){
            //排序
            Collections.sort(nodes);
            //取出两个权值的最小的二叉树
            Node left=nodes.get(0);
            Node right=nodes.get(1);

            //构造新的二叉树
            Node parent=new Node(null,left.weight+right.weight);
            parent.left=left;
            parent.right=right;

            //删除已经处理的二叉树
            nodes.remove(left);
            nodes.remove(right);
            //添加新的二叉树
            nodes.add(parent);
        }
        //返回根节点
        return nodes.get(0);
    }
    public static void main(String[] args) {
        String content="i like like like java do you like a java";
        byte[] contentBytes=content.getBytes();;
        //System.out.println(contentBytes.length);//40
        List<Node> nodes=getNodes(contentBytes);
        //System.out.println(nodes+" ");
        Node root=createHuffmanTree(nodes);
        PreOrder(root);

    }
    public static List<Node> getNodes(byte[] bytes){
        //1.创建一个ArrayList
        ArrayList<Node>nodes=new ArrayList<>();

        //2.遍历bytes，统计每一个byte出现的次数-》map【key，value】
        Map<Byte,Integer> map=new HashMap<>();
        for(byte b:bytes){
            map.put(b,map.getOrDefault(b,0)+1);
        }
        Set<Byte> set=map.keySet();
        for(byte b:set){
            nodes.add(new Node(b,map.get(b)));
        }
        return nodes;
    }
}
class Node implements Comparable<Node>{
    Byte data;//存放数据（字符）本身
    int weight;//权值，表示字符出现的次数
    Node left;
    Node right;
    public Node(Byte data,int weight){
        this.data=data;
        this.weight=weight;
    }

    @Override
    public int compareTo(Node o) {
        return this.weight-o.weight;
    }
    public String toString(){
        return "Node [data ="+data +",weight="+weight+"]";
    }
    //前序遍历
    public void PreOrder(){

        System.out.println(this.toString());

        if(this.left!=null){
            this.left.PreOrder();
        }
        if(this.right!=null){
            this.right.PreOrder();
        }
    }
}