一灶泵、定義
霍夫曼（Huffman）編碼是一種編碼方式，主要用于數(shù)據(jù)文件的壓縮补箍。它的主要思想是放棄文本文件的普通保存方式：不再使用7位或8位二進(jìn)制數(shù)表示每一個(gè)字符改执，而是用較少的比特表示出現(xiàn)頻率高的字符，用較多的比特表示出現(xiàn)頻率低的字符坑雅。
引例：假設(shè)需要對(duì)文本字符串“ABRACADABRA!”編碼
- 一種方式是辈挂，用較短的比特表示所有可能的字符。
如A-0裹粤、B-1终蒂、R-00、C-01遥诉、D-10拇泣、!-11，這樣“ABRACADABRA!”的編碼就是0 1 00 0 01 0 10 0 1 00 0 11矮锈。這種表示方法只用了17位霉翔，而7位的ASCII編碼則用了77位。但是這種方法存在一個(gè)問(wèn)題：當(dāng)不存在分隔符的時(shí)候苞笨，我們無(wú)法根據(jù)一連串比特碼區(qū)分字符與比特碼的映射關(guān)系债朵。如01000010100100011也可以表示成CRRDDCRCB或其它字符串子眶。 - 第二種方式是，如果任一字符的編碼都不是其它字符編碼的前綴葱弟，那么就不需要分隔符了壹店。
如A-0猜丹、B-1111芝加、R-1110、C-110射窒、D-100藏杖、!-101。而霍夫曼編碼就是尋找這種變長(zhǎng)前綴的算法脉顿，且能使最終構(gòu)造出的比特流最小蝌麸。
二、實(shí)現(xiàn)方式
霍夫曼編碼艾疟，首先需要根據(jù)輸入文本来吩，構(gòu)造一棵二叉樹，樹的左鏈接表示比特"0"蔽莱，右鏈接表示比特"1"弟疆，葉子結(jié)點(diǎn)表示字符。字符所對(duì)應(yīng)的霍夫曼編碼值就是從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的鏈接值盗冷。
總體實(shí)現(xiàn)步驟如下：
【壓縮步驟】
壓縮用于將原始文本轉(zhuǎn)換成一條編碼過(guò)的比特流怠苔。
- 讀取輸入；
- 統(tǒng)計(jì)輸入中每個(gè)字符的頻次仪糖；
- 根據(jù)頻次柑司，構(gòu)造Huffman樹；
- 構(gòu)造編譯表锅劝，用于將字符與變長(zhǎng)前綴映射攒驰；
- 將Huffman樹編碼為比特字符串，并寫入輸出流故爵；
- 將文本長(zhǎng)度編碼為比特字符串玻粪，并寫入輸出流；
- 壓縮數(shù)據(jù)稠集，即使用編譯表翻譯每個(gè)文本字符奶段，寫入輸出流。
【解壓縮步驟】
解壓縮用于將一條編碼過(guò)的比特流轉(zhuǎn)換為原始文本剥纷。
- 讀取Huffman樹（編碼在比特流的開(kāi)頭）痹籍；
- 讀取需要解碼的字符數(shù)量；
- 根據(jù)步驟1還原的Huffman樹解碼壓縮數(shù)據(jù)晦鞋。
三蹲缠、源碼實(shí)現(xiàn)
3.1 構(gòu)造Huffman樹
構(gòu)造一顆Huffman樹的步驟如下：
1棺克、遍歷一遍文本，統(tǒng)計(jì)各個(gè)字符出現(xiàn)的頻次线定；
2娜谊、對(duì)每個(gè)字符構(gòu)造一個(gè)葉子結(jié)點(diǎn)，結(jié)點(diǎn)包含該個(gè)字符的頻次斤讥；
3纱皆、每次從所有結(jié)點(diǎn)中選出頻次最小的兩個(gè)根結(jié)點(diǎn)，構(gòu)造一個(gè)新結(jié)點(diǎn)芭商，新結(jié)點(diǎn)作為根結(jié)點(diǎn)派草，兩個(gè)根結(jié)點(diǎn)作為其左右子結(jié)點(diǎn)，新結(jié)點(diǎn)的頻次為左右子根結(jié)點(diǎn)的頻次和铛楣；
4近迁、重復(fù)第3步，直到最后只剩一個(gè)根結(jié)點(diǎn)簸州。
樹結(jié)點(diǎn)定義：
private static class Node implements Comparable<Node> {
private final char ch; //字符
private final int freq; //每個(gè)結(jié)點(diǎn)保存以該結(jié)點(diǎn)為根的子樹中的字符數(shù)量
private final Node left, right;
Node(char ch, int freq, Node left, Node right) {
this.ch = ch;
this.freq = freq;
this.left = left;
this.right = right;
}
private boolean isLeaf() {
return (left == null) && (right == null);
}
public int compareTo(Node that) {
return this.freq - that.freq;
}
}
構(gòu)造Huffman樹：
//構(gòu)造Huffman樹
private static Node buildTrie(int[] freq) {
MinPQ<Node> pq = new MinPQ<Node>(); //優(yōu)先級(jí)隊(duì)列
for (char i = 0; i < R; i++) //R為字母表
if (freq[i] > 0)
pq.insert(new Node(i, freq[i], null, null));
//只有一個(gè)結(jié)點(diǎn)鉴竭，特殊處理
if (pq.size() == 1) {
if (freq['\0'] == 0) pq.insert(new Node('\0', 0, null, null));
else pq.insert(new Node('\1', 0, null, null));
}
// merge two smallest trees
while (pq.size() > 1) {
Node left = pq.delMin();
Node right = pq.delMin();
Node parent = new Node('\0', left.freq + right.freq, left, right);
pq.insert(parent);
}
return pq.delMin();
}
3.2 構(gòu)造編譯表
編譯表就是將每個(gè)字符與它的比特字符串相關(guān)聯(lián)的符號(hào)表。
// 構(gòu)造編譯表
private static String[] buildCode(Node root) {
String[] table = new String[R];
buildCode(table, root, "");
return table;
}
private static void buildCode(String[] st, Node x, String s) {
if (!x.isLeaf()) {
buildCode(st, x.left, s + '0');
buildCode(st, x.right, s + '1');
} else {
st[x.ch] = s;
}
}
3.3 編碼Huffman樹岸浑，并壓縮數(shù)據(jù)
采用先序遍歷對(duì)Huffman樹編碼搏存。（之所以要對(duì)Huffman樹編碼是為了從壓縮后的比特流中還原出Huffman樹，這樣后續(xù)才能解碼）
從根結(jié)點(diǎn)開(kāi)始助琐，遇到內(nèi)部結(jié)點(diǎn)寫入比特"0"祭埂；遇到葉子結(jié)點(diǎn)，寫入比特"1"兵钮，然后寫入字符比特值蛆橡。
/**
* 使用先序遍歷將Huffman樹編碼為比特流
*/
private static void writeTrie(Node x) {
if (x.isLeaf()) {
BinaryStdOut.write(true);
BinaryStdOut.write(x.ch, 8);
return;
}
BinaryStdOut.write(false);
writeTrie(x.left);
writeTrie(x.right);
}
/**
* 壓縮數(shù)據(jù) 最終的比特流結(jié)果為：Huffman樹編碼值+文本長(zhǎng)度+壓縮后的數(shù)據(jù)
*/
public static void compress() {
// read the input
String s = BinaryStdIn.readString();
char[] input = s.toCharArray();
// 統(tǒng)計(jì)頻次
int[] freq = new int[R];
for (int i = 0; i < input.length; i++)
freq[input[i]]++;
// 構(gòu)建Huffman樹
Node root = buildTrie(freq);
// 構(gòu)建編譯表
String[] st = new String[R];
buildCode(st, root, "");
// 編碼Huffman樹
writeTrie(root);
// 寫入文本長(zhǎng)度
BinaryStdOut.write(input.length);
// 壓縮數(shù)據(jù)
for (int i = 0; i < input.length; i++) {
String code = st[input[i]]; // 根據(jù)編譯表，得到字符對(duì)應(yīng)的變長(zhǎng)前綴
for (int j = 0; j < code.length(); j++) {
if (code.charAt(j) == '0') {
BinaryStdOut.write(false);
} else if (code.charAt(j) == '1') {
BinaryStdOut.write(true);
} else
throw new IllegalStateException("Illegal state");
}
}
BinaryStdOut.close();
}
3.4 解碼Huffman樹掘譬，并解壓縮數(shù)據(jù)
/**
* 將比特流解碼為Huffman樹
*
* @return 返回Huffman樹的根結(jié)點(diǎn)
*/
private static Node readTrie() {
boolean isLeaf = BinaryStdIn.readBoolean();
if (isLeaf) {
return new Node(BinaryStdIn.readChar(), -1, null, null);
} else {
return new Node('\0', -1, readTrie(), readTrie());
}
}
/**
* 解壓縮數(shù)據(jù)
*/
public static void expand() {
// 解碼比特流泰演，還原Huffman樹
Node root = readTrie();
// 解碼文本長(zhǎng)度
int length = BinaryStdIn.readInt();
// 解碼文本數(shù)據(jù)
for (int i = 0; i < length; i++) { // i追蹤字符，每次循環(huán)還原一個(gè)文本字符
Node x = root;
while (!x.isLeaf()) {
boolean bit = BinaryStdIn.readBoolean();
if (bit)
x = x.right;
else
x = x.left;
}
BinaryStdOut.write(x.ch, 8);
}
BinaryStdOut.close();
}
3.5 完整源碼
public class Huffman {
private static final int R = 256; // 字母表
private Huffman() {
}
// 樹結(jié)點(diǎn)定義
private static class Node implements Comparable<Node> {
private final char ch; // 字符
private final int freq; // 子樹中所有字符的頻次
private final Node left, right;
Node(char ch, int freq, Node left, Node right) {
this.ch = ch;
this.freq = freq;
this.left = left;
this.right = right;
}
private boolean isLeaf() {
return (left == null) && (right == null);
}
public int compareTo(Node that) {
return this.freq - that.freq;
}
}
/**
* 構(gòu)建Haffman樹
*/
private static Node buildTrie(int[] freq) {
MinPQ<Node> pq = new MinPQ<Node>();
for (char i = 0; i < R; i++)
if (freq[i] > 0)
pq.insert(new Node(i, freq[i], null, null));
if (pq.size() == 1) {
if (freq['\0'] == 0)
pq.insert(new Node('\0', 0, null, null));
else
pq.insert(new Node('\1', 0, null, null));
}
// merge two smallest trees
while (pq.size() > 1) {
Node left = pq.delMin();
Node right = pq.delMin();
Node parent = new Node('\0', left.freq + right.freq, left, right);
pq.insert(parent);
}
return pq.delMin();
}
/**
* 構(gòu)造編譯表
*/
private static void buildCode(String[] st, Node x, String s) {
if (!x.isLeaf()) {
buildCode(st, x.left, s + '0');
buildCode(st, x.right, s + '1');
} else {
st[x.ch] = s;
}
}
/**
* 壓縮數(shù)據(jù) 最終的比特流結(jié)果為：Huffman樹編碼值+文本長(zhǎng)度+壓縮后的數(shù)據(jù)
*/
public static void compress() {
// read the input
String s = BinaryStdIn.readString();
char[] input = s.toCharArray();
// 統(tǒng)計(jì)頻次
int[] freq = new int[R];
for (int i = 0; i < input.length; i++)
freq[input[i]]++;
// 構(gòu)建Huffman樹
Node root = buildTrie(freq);
// 構(gòu)建編譯表
String[] st = new String[R];
buildCode(st, root, "");
// 編碼Huffman樹
writeTrie(root);
// 寫入文本長(zhǎng)度
BinaryStdOut.write(input.length);
// 壓縮數(shù)據(jù)
for (int i = 0; i < input.length; i++) {
String code = st[input[i]]; // 根據(jù)編譯表葱轩，得到字符對(duì)應(yīng)的變長(zhǎng)前綴
for (int j = 0; j < code.length(); j++) {
if (code.charAt(j) == '0') {
BinaryStdOut.write(false);
} else if (code.charAt(j) == '1') {
BinaryStdOut.write(true);
} else
throw new IllegalStateException("Illegal state");
}
}
BinaryStdOut.close();
}
/**
* 解壓縮數(shù)據(jù)
*/
public static void expand() {
// 解碼比特流睦焕，還原Huffman樹
Node root = readTrie();
// 解碼文本長(zhǎng)度
int length = BinaryStdIn.readInt();
// 解碼文本數(shù)據(jù)
for (int i = 0; i < length; i++) { // i追蹤字符，每次循環(huán)還原一個(gè)文本字符
Node x = root;
while (!x.isLeaf()) {
boolean bit = BinaryStdIn.readBoolean();
if (bit)
x = x.right;
else
x = x.left;
}
BinaryStdOut.write(x.ch, 8);
}
BinaryStdOut.close();
}
/**
* 將比特流解碼為Huffman樹
*
* @return 返回Huffman樹的根結(jié)點(diǎn)
*/
private static Node readTrie() {
boolean isLeaf = BinaryStdIn.readBoolean();
if (isLeaf) {
return new Node(BinaryStdIn.readChar(), -1, null, null);
} else {
return new Node('\0', -1, readTrie(), readTrie());
}
}
/**
* 使用先序遍歷將Huffman樹編碼為比特流
*/
private static void writeTrie(Node x) {
if (x.isLeaf()) {
BinaryStdOut.write(true); // 葉子結(jié)點(diǎn)寫入"1"
BinaryStdOut.write(x.ch, 8); // 寫入字符的比特值
return;
}
BinaryStdOut.write(false); // 內(nèi)部結(jié)點(diǎn)寫入"0"
writeTrie(x.left);
writeTrie(x.right);
}
/**
* 用例： Execution: java Huffman - < input.txt (compress) Execution: java
* Huffman + < input.txt (expand)
*/
public static void main(String[] args) {
if (args[0].equals("-"))
compress();
else if (args[0].equals("+"))
expand();
else
throw new IllegalArgumentException("Illegal command line argument");
}
}
四靴拱、最優(yōu)性證明
為什么根據(jù)Huffman算法垃喊，生成的字符變長(zhǎng)前綴之和是最優(yōu)的？
首先明確一個(gè)概念袜炕，即加權(quán)外部路徑長(zhǎng)度：表示Huffman樹中葉子結(jié)點(diǎn)的頻次 X 葉子結(jié)點(diǎn)高度的和本谜。
*Huffman樹的加權(quán)外部路徑長(zhǎng)度，就是文本編碼后總比特長(zhǎng)度偎窘。
要證明Huffman算法構(gòu)造的變長(zhǎng)前綴是最優(yōu)的乌助，就是證明Huffman樹的加權(quán)外部路徑長(zhǎng)度是最短的溜在。可以采用數(shù)學(xué)歸納法得到證明他托，具體可以參考《算法導(dǎo)論》或相關(guān)論文掖肋。
