電子發(fā)燒友App
霍夫曼壓縮算法概述
霍夫曼壓縮算法的主要思想是用較少的比特表示出現(xiàn)頻率較高的字符，用較多的比特表示出現(xiàn)頻率較低的字符。如下圖所示，
霍夫曼壓縮算法實現(xiàn)
?、僮x入完整的輸入流，并轉化為字符數(shù)組。
?、谟嬎忝總€字符出現(xiàn)的次數(shù)
?、蹣嫿℉uffman樹
?、軜嫿ň幾g表
?、輰卧~查找樹編碼成比特輸出串并寫入到輸出流
?、迣卧~總數(shù)編碼成比特輸出串并寫入到輸出流
?、呤褂镁幾g表翻譯每個輸入字符
12345678
霍夫曼壓縮算法節(jié)點的表示
private static final int R = 256; //字符為ASCII表示
private static class Node implements Comparable《Node》 {
private final char ch;
private final int freq;
private final Node left， right;
public Node（char ch， int freq， Node left， Node right） {
this.freq = freq;
this.ch = ch;
this.left = left;
this.right = right;
}
private boolean isLeaf（） {
return left == null && right == null;
}
@Override
public int compareTo（Node that） {
return this.freq - that.freq;
}
}
123456789101112131415161718192021222324252627
構建Huffman單詞查找樹
構建初始有一堆沒有父節(jié)點的節(jié)點，將它們放到最小隊列中，這樣對頭總是freq為最小的那個節(jié)點。
從隊列中找到freq最小的兩個節(jié)點，創(chuàng)建一個它們的父節(jié)點，將三個節(jié)點歸并成一個大節(jié)點，接著放入隊列中，
循環(huán)往復直至隊列中只剩一個節(jié)點。
/**
* @param freq 字符出現(xiàn)的次數(shù)
* @return
*/
private static Node buildTrie（char［］ freq） {
MinPQ《Node》 pq = new MinPQ《Node》（）;
//初始化多個將構成一顆Huffman樹的結點
for （char i = 0; i 《 R; i++） {
if （freq［i］ 》 0） pq.insert（new Node（i， freq［i］， null， null））;
}
// special case in case there is only one character with a nonzero frequency
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））;
}
//歸并兩個小樹
while （pq.size（） 》 1） {
Node left = pq.delMin（）;
Node right = pq.delMin（）;
Node parent = new Node（‘\0’， left.freq + right.freq， left， right）; //創(chuàng)建連接子樹的中間結點
pq.insert（parent）;
}
return pq.delMin（）;
}123456789101112131415161718192021222324252627282930
將Huffman單詞查找樹轉化成字節(jié)流寫到壓縮文件中
做如下規(guī)定：
中間結點寫0；葉子結點寫1，并在后面寫結點上的字符。
/**
* 將單詞查找樹編碼成比特輸出串并寫入到輸出流
* 用前序遍歷
*/
private static void writeTrie（Node x） {
if （x.isLeaf（）） {
BinaryStdOut.write（true）;
BinaryStdOut.write（x.ch）;
return;
}
BinaryStdOut.write（false）;
writeTrie（x.left）;
writeTrie（x.right）;
}
12345678910111213141516
將壓縮文件中字節(jié)流轉化為Huffman單詞查找樹
按寫入時的規(guī)定解析字節(jié)流。
/**
* 讀比特流，得出一顆單詞查找樹
*/
private static Node readTrie（） {
if （BinaryStdIn.readBoolean（）） { //讀到1，說明是葉子結點
return new Node（BinaryStdIn.readChar（）， 0， null， null）;
}
//讀到的是0，說明是中間結點，需要遞歸直到讀到1為止
Node left = readTrie（）;
Node right = readTrie（）;
return new Node（‘\0’， 0， left， right）;
}
123456789101112131415
構建編譯表
構建編譯表st，索引為字符，值為路徑（比特字符串）。
根據(jù)這張表，可以將源文件中的某個字符，壓縮為更少bit表示的Huffman樹上的路徑。
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;
}
}
12345678910
壓縮
/**
* 從輸入流中讀字節(jié)流，并將壓縮后的結果寫入輸出流
*/
private static void compress（） {
//①讀入完整的輸入流，并轉化為字符數(shù)組
String s = BinaryStdIn.readString（）;
char［］ input = s.toCharArray（）;
//②計算每個字符出現(xiàn)的次數(shù)，沒有出現(xiàn)的就為0
char［］ freq = new char［R］;
for （int i = 0; i 《 input.length; i++） {
freq［input［i］］++;
}
//③構建Huffman樹
Node root = buildTrie（freq）;
//④構建編譯表，將輸入中的每個char值與一個比特字符串（即Huffman樹上路徑）相關聯(lián)
String st［］ = new String［R］;
buildCode（st， root， “”）;
//⑤將單詞查找樹編碼成比特輸出串并寫入到輸出流
writeTrie（root）;
//⑥將單詞總數(shù)編碼成比特輸出串并寫入到輸出流
BinaryStdOut.write（input.length）;
//⑦使用編譯表翻譯每個輸入字符
for （int i = 0; i 《 input.length; i++） {
String code = st［input［i］］; //code表示Huffman單詞查找數(shù)上的路徑
for （int j = 0; j 《 code.length（）; j++） { //要一位一位地輸出
if （code.charAt（j） == ‘1’） {
BinaryStdOut.write（true）;
} else {
BinaryStdOut.write（false）;
}
}
}
BinaryStdOut.close（）;
}
12345678910111213141516171819202122232425262728293031323334353637383940414243444546
### 解壓
/**
* 解壓
* 讀取壓縮文件的比特流，
* 將比特流對應為路徑在單詞查找樹上找，將找到的結點中的字符寫出
*/
private static void expand（） {
Node root = readTrie（）;
int N = BinaryStdIn.readInt（）; //讀出存在壓縮文件中的字符串長度
for （int i = 0; i 《 N; i++） { //找出源文件中每個字符
Node x = root;
while （！x.isLeaf（）） { //遍歷，知道葉子結點
if （BinaryStdIn.readBoolean（）） {
x = x.right;
} else {
x = x.left;
}
}
BinaryStdOut.write（x.ch）;
}
BinaryStdOut.close（）;
}
工商網(wǎng)監(jiān)
評論