用Java实现Huffman编码

---

前言

在使用http1.1协议传输数据的时候，会有一些固定的字段，比如cookie、编码方式、接收的数据类型，另外会有一些大量重复的字段造成请求报文过于冗长，为了解决这个问题，在http2.0的时候，采用了二进制对请求报文进行编码，同时客户端和服务端维护一张静态表和静态表，对我们的请求报文进行二进制编码，同时采用Huffman编码进行压缩。

Huffman编码是一种编码方式，对出现频次更高的字段采取更短的编码，Huffman编码要求每个字符的编码不能是其他字符编码的前缀，这篇文章就是准备记录一下用Java实现Huffman编码。

一、实现思路

将出现的字符和字符出现的频次一一映射，将所有字符放进优先队列，优先队列的堆顶存放的是频次最小的字符，弹出频次最小的的两个字符，申请一个新的根节点，新的根节点左子结点是最小频次的字符，右子结点是第二小频次的字符，频次为左子节点和右子结点频次的和，将新结点加入优先队列重复上述过程

二、准备Huffman结点

public class Node {//编码字符private char data;//频次private int freq;//左子节点private Node left;//右子节点private Node right;
}

三、主要实现

public static void main(String[] args) {char[] charArray = { 'a', 'b', 'c', 'd', 'e', 'f' };int[] charFreq = { 45, 13, 12, 16, 9, 5 };PriorityQueue<Node> priorityQueue = new PriorityQueue<>(6, new Comparator<Node>() {@Overridepublic int compare(Node o1, Node o2) {return o1.getFreq() - o2.getFreq();}});for (int i = 0; i < 6; i++) {Node node = new Node();node.setData(charArray[i]);node.setFreq(charFreq[i]);priorityQueue.add(node);}Node root = null;while (priorityQueue.size() > 1) {Node newNode = new Node();Node left = priorityQueue.peek();newNode.setLeft(left);priorityQueue.poll();Node right = priorityQueue.peek();newNode.setRight(right);priorityQueue.poll();newNode.setFreq(left.getFreq() + right.getFreq());root = newNode;priorityQueue.add(newNode);}printCode(root, "");}public static void printCode(Node root, String code) {if (root.getLeft() == null && root.getRight() == null && Character.isLetter(root.getData())) {System.out.println(root.getData() + ": " + code);return;}printCode(root.getLeft(), code + "0");printCode(root.getRight(), code + "1");}//运行结果//a: 0//c: 100//b: 101//f: 1100//e: 1101//d: 111

---