基本介绍

1. 哈夫曼编码，也称为最佳编码，是一种编码方式，也属于一种程序算法。
2. 哈夫曼编码是哈夫曼树在电讯通讯中的经典应用之一。
3. 哈夫曼编码广泛的应用于数据文件压缩，其压缩率通常在20%~90%之间。
4. 哈夫曼编码是可变字长编码的一种，是一种及时码，是Huffman于1952年提出的一种编码方法，称之为最佳编码。

原理刨析

1. 定长编码
   • 字符串： i like java 共11个字符
   • 对应的ascii码值：105，32，108，105，107，101，32，106，97，118，97
   • 对应的二进制：01101001 00100000 01101100 01101001 01101011 01100101 00100000 01101010 01100001 01110110 01100001
   • 按照二进制进行传输需要传输88bit
2. 变长编码
   • 字符串： i like java 共11个字符
   • " "：2， a：2，i：2，e：1，k：1，l：1，j：1，v：1 （每个字符对应的次数）
   • " "：0， a：1，i：10，e：11，k：110，l：111，j：1110，v：1111 (传输时对应的二进制，出现的次数越多，对应的编码越小，所传输的bit数就越小)
   • 所传输的bit流为：100111101101101110111111 （24bit）
   • 但此编码会出现异议，比如所前二位10，是1，0 还是10，这和编码方式有的编码是其他编码的前缀所以不是唯一可译码
3. 哈夫曼编码-最佳编码（唯一可译码，即使码）
   • 字符串： i like java 共11个字符
   • " "：2， a：2，i：2，e：1，k：1，l：1，j：1，v：1 （每个字符对应的次数）
   • 按照上面说出现的次数为权值，构建一颗哈夫曼数，然后进行编码。

步骤：
将每个字符看成一个结点（一棵树），出现的次数作为权值，从小到大排序
取出最小的两个结点，将它们的权值相加，组成一个新的根结点。
将上面新节点的权值大小，再次进行排序
不断重复上面的步骤，直到所有的数据均被处理，最后只剩一棵树。
如下图所示：

根据Huffman树，给各个字符进行编码，向左的路径为0，向右的为1编码如下：

可以得到各个的编码：
e：000, k: 001 ,l: 010,j : 011, v: 100, " " : 101,a:110,i:111

按照上面的编码我们可以得到它的二进制串
i like java
111101010111001000101011110100110 （33bit）
其中任一码字都不是其他的前缀，也是即时码
注意：因为各个字符出现的次数差别不大，所以都是三位，如果字符出现的次数差别很大，就会很明显的发现，出现次数多的字符，他的编码越短

注意事项：

根据你排序相同权值的结点所放的位置不同，所对应的Huffman编码也不完全一样，但是最后生成的Huffman编码长度一样。
在上面我将合成的新的二叉树总是放在相同权值的后面，如果放在前面就会生成不一样的二叉树。

下面我们看一下具体的代码实现：

首先我们创建Node结点：
需要注意的是，Node结点实现了Comparable，因为我们要对结点进行排序

package Huffmanzip;/*** 构建Node结点  保存对应的值即码值* @ClassName: Node* @Author* @Date 2022/1/24*/public class Node implements Comparable<Node> {//对应的数据域 保存的是字符private Byte data ;//权重  即出现的次数private int weight ;//左子节点 和 右子节点private Node left;private Node right;//构造方法public Node(Byte data, int weight) {this.data = data;this.weight = weight;}public Byte getData() {return data;}public void setData(Byte data) {this.data = data;}public int getWeight() {return weight;}public void setWeight(int weight) {this.weight = weight;}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;}@Overridepublic String toString() {return "Node{" +"data=" + data +", weight=" + weight +'}';}@Overridepublic int compareTo(Node o) {return this.weight - o.weight;}//前序遍历public void preOrder(Node node){if (node!=null){System.out.println(node);preOrder(node.left);preOrder(node.right);}}}

然后我们编写一个方法：将所传入的字符，全部转换为结点，利用map统计相同结点出现的次数，然后将结点值和权重存入list集合中，方便我们比较

package Huffmanzip;import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;/*** 用来得到byte[]对应的链表* @ClassName: GetList* @Author* @Date 2022/1/24*/
public class GetList {/*** 根据传入的字节 构建一个链表* @param bytes 由字符串拆分而成的字节* @return 最终构建的链表*/public static List<Node> getList(byte[] bytes){List<Node> list = new ArrayList<>();//定义一个Map用来统计个数Map<Byte,Integer> map = new HashMap<>();//遍历统计for (byte b : bytes){if (map.containsKey(b)){map.put(b,map.get(b)+1);}else {map.put(b,1);}}//遍历map得到其对应的键值对for (Map.Entry<Byte,Integer>  entry : map.entrySet()){list.add(new Node(entry.getKey(), entry.getValue()));}return list;}
}

上面我们已经得到了，所有的结点，其保存在一个list集合中，下面我们需要对将结点准换为一个Huffman树

我们编写一个方法：根据传进来的链表，转换成一颗Huffman树，返回根节点

package Huffmanzip;import java.util.Collections;
import java.util.List;/*** 根据传进来链表 创建一颗Huffman树* @ClassName: CreateHuffmanTree* @Author* @Date 2022/1/24*/
public class CreateHuffmanTree {public static Node creat(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.getWeight()+right.getWeight());parent.setLeft(left);parent.setRight(right);//移除旧结点 添加新节点nodes.remove(left);nodes.remove(right);nodes.add(parent);}return nodes.get(0);}//前序遍历方法public static void preOrder(Node node){node.preOrder(node);}}

上面我们已经生成了huffman树，然后我们编写一个 方法：根据Huffman树，返回对应字节，所对应的编码

//编码方法

package Huffmanzip;import java.util.HashMap;
import java.util.Map;/*** @ClassName: HuffmanCoding* @Author* @Date 2022/1/24*/
public class HuffmanCoding {/**** @param node 根节点* @param code 编码为0还是1* @param str 进行编码拼接* @param ans 返回的字节与编码的对应关系*/static Map<Byte,String> ans = new HashMap<>();public static Map<Byte,String> getHuffmanCoding(Node node,String code,StringBuilder str){StringBuilder sb = new StringBuilder(str);sb.append(code);if (node!=null){if (node.getData()==null){//说明不是叶子结点//向左getHuffmanCoding(node.getLeft(),"0",sb);getHuffmanCoding(node.getRight(),"1",sb);}else {ans.put(node.getData(),sb.toString());}}return ans;}
}

最后一步，根据原始字符串和编码对照表，返回编码后的字节数组

package Huffmanzip;import java.util.Map;/*** @ClassName: ByteToHuffmanCode* @Author* @Date 2022/1/24*/
public class ByteToHuffmanCode {/*** 将原数据对应的字符串的字节数组 转换为 编码后的字节数组* @param bytes 原数据对应的字节数组* @param codes 编码表* @return 编码后的字节数组*/public static byte[] byteToHuffmanCode(byte[] bytes, Map<Byte,String> codes){//用来将编码进行拼接StringBuilder sb = new StringBuilder();//进行拼接 根据字节得到对应的编码for (byte b : bytes){sb.append(codes.get(b));}//拼接完成后进行处理//新数组的长度int length = (sb.length() + 7) / 8 ;//新数组byte[] ans = new byte[length];int index = 0;for (int i = 0; i < sb.length();i+=8){String string;if (i+8>sb.length()){string = sb.substring(i);}else {string = sb.substring(i,i+8);}ans[index++] = (byte) Integer.parseInt(string,2);}return ans;}}

就这样我们就得到了编码后的字节数组。
最后我们将上面的所有方法封装在一个类中，只需要传入字符串就可以得到相应压缩后的字节数组。

package Huffmanzip;import java.nio.charset.StandardCharsets;
import java.util.List;
import java.util.Map;/*** 将元素据转换为压缩后的字节* @ClassName: HuffmanCodingCompress* @Author* @Date 2022/1/24*/public class HuffmanCodingCompress {public static byte[] compress(String str){byte[] bytes = str.getBytes(StandardCharsets.UTF_8);//得到了listList<Node> list = GetList.getList(bytes);//构建huffmanTree 得到树的根节点Node root = CreateHuffmanTree.creat(list);//进行编码 编码值保存在map中Map<Byte, String> huffmanCoding = HuffmanCoding.getHuffmanCoding(root, "", new StringBuilder());//        for (Map.Entry<Byte,String> entry : huffmanCoding.entrySet()){
//            System.out.println(entry.getKey()+": "+entry.getValue());
//        }return ByteToHuffmanCode.byteToHuffmanCode(bytes, huffmanCoding);}
}

测试代码：

public class Test {public static void main(String[] args) {String str = "i like java";byte[] bytes = HuffmanCodingCompress.compress(str);for (byte b : bytes) {System.out.print( b + " ");}}
}

结果：