前言

在使用http1.1協(xié)議傳輸數據的時候，會有一些固定的字段，比如cookie、編碼方式、接收的數據類型，另外會有一些大量重復的字段造成請求報文過于冗長，為了解決這個問題，在http2.0的時候，采用了二進制對請求報文進行編碼，同時客戶端和服務端維護一張靜態(tài)表和靜態(tài)表，對我們的請求報文進行二進制編碼，同時采用Huffman編碼進行壓縮。

Huffman編碼是一種編碼方式，對出現頻次更高的字段采取更短的編碼，Huffman編碼要求每個字符的編碼不能是其他字符編碼的前綴，這篇文章就是準備記錄一下用Java實現Huffman編碼。

一、實現思路

將出現的字符和字符出現的頻次一一映射，將所有字符放進優(yōu)先隊列，優(yōu)先隊列的堆頂存放的是頻次最小的字符，彈出頻次最小的的兩個字符，申請一個新的根節(jié)點，新的根節(jié)點左子結點是最小頻次的字符，右子結點是第二小頻次的字符，頻次為左子節(jié)點和右子結點頻次的和，將新結點加入優(yōu)先隊列重復上述過程

二、準備Huffman結點

public class Node {//編碼字符private char data;//頻次private int freq;//左子節(jié)點private Node left;//右子節(jié)點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