前言

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

Huffman編碼是一種編碼方式，對(duì)出現(xiàn)頻次更高的字段采取更短的編碼，Huffman編碼要求每個(gè)字符的編碼不能是其他字符編碼的前綴，這篇文章就是準(zhǔn)備記錄一下用Java實(shí)現(xiàn)Huffman編碼。

一、實(shí)現(xiàn)思路

將出現(xiàn)的字符和字符出現(xiàn)的頻次一一映射，將所有字符放進(jìn)優(yōu)先隊(duì)列，優(yōu)先隊(duì)列的堆頂存放的是頻次最小的字符，彈出頻次最小的的兩個(gè)字符，申請(qǐng)一個(gè)新的根節(jié)點(diǎn)，新的根節(jié)點(diǎn)左子結(jié)點(diǎn)是最小頻次的字符，右子結(jié)點(diǎn)是第二小頻次的字符，頻次為左子節(jié)點(diǎn)和右子結(jié)點(diǎn)頻次的和，將新結(jié)點(diǎn)加入優(yōu)先隊(duì)列重復(fù)上述過程

二、準(zhǔn)備Huffman結(jié)點(diǎn)

public class Node {//編碼字符private char data;//頻次private int freq;//左子節(jié)點(diǎn)private Node left;//右子節(jié)點(diǎn)private Node right;
}

三、主要實(shí)現(xiàn)

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");}//運(yùn)行結(jié)果//a: 0//c: 100//b: 101//f: 1100//e: 1101//d: 111