java哈夫曼編碼壓縮

A. 利用哈夫曼編碼進行壓縮壓縮率一般達到多少

哈夫曼編碼進行壓縮的壓縮率是根據平均碼長來計算的，壓縮率比較低。

例如：用三位二進行數進行的等長編碼平均長度為3，而根據哈夫曼樹編碼的平均碼長為：

4*0.07+2*0.19+5*0.02+4*0.06+2*0.32+5*0.03+2*0.21+4*0.10=2.61

2.61/3=0.87=87%

其平均碼長是等長碼的87%，所以平均壓縮率為13%。

哈夫曼編碼，又稱霍夫曼編碼，是一種編碼方式，哈夫曼編碼是可變字長編碼(VLC)的一種。

Huffman於1952年提出一種編碼方法，該方法完全依據字元出現概率來構造異字頭的平均長度最短的碼字，有時稱之為最佳編碼，一般就叫做Huffman編碼（有時也稱為霍夫曼編碼）。

壓縮率，描述壓縮文件的效果名，是文件壓縮後的大小與壓縮前的大小之比，例如：把100m的文件壓縮後是90m，壓縮率為90/100*100%=90%，壓縮率一般是越小越好，但是壓得越小，解壓時間越長。

(1)java哈夫曼編碼壓縮擴展閱讀

哈夫曼編碼的具體方法：先按出現的概率大小排隊，把兩個最小的概率相加，作為新的概率 和剩餘的概率重新排隊，再把最小的兩個概率相加，再重新排隊，直到最後變成1。

每次相 加時都將「0」和「1」賦與相加的兩個概率，讀出時由該符號開始一直走到最後的「1」， 將路線上所遇到的「0」和「1」按最低位到最高位的順序排好，就是該符號的哈夫曼編碼。

B. 哈夫曼編碼與解碼 java

class HaffmanNode //哈夫曼樹的結點類
{
int weight; //權值
int parent,left,right; //父母結點和左右孩子下標

public HaffmanNode(int weight)
{
this.weight = weight;
this.parent=-1;
this.left=-1;
this.right=-1;
}
public HaffmanNode()
{
this(0);
}
public String toString()
{
return this.weight+", "+this.parent+", "+this.left+", "+this.right;
}
return code;
}

public static void main(String[] args)
{
int[] weight={5,29,7,8,14,23,3,11}; //指定權值集合
HaffmanTree htree = new HaffmanTree(weight);
System.out.println("哈夫曼樹的結點數組:\n"+htree.toString());
String[] code = htree.haffmanCode();
System.out.println("哈夫曼編碼:");
for (int i=0; i<code.length; i++)
System.out.println(code[i]);
}
}

C. 哈夫曼編碼（理論）

哈夫曼編碼是一種無損壓縮文件一種方法，他的思路很簡單，卻又十分經典，他利用的是無重復前綴這種思想，就是每個字元的前綴是唯一的，若a的編碼是001，那麼就不會存在另一個以001開頭的編碼了，因為，哈夫曼編碼是以二叉樹為基礎實現的，而二叉樹到每一個葉子節點的路徑是唯一的，那麼也就是說每一個字元的編碼也是唯一的。

哈夫曼編碼是一種變長編碼，比起定長編碼的ascii碼來說，哈夫曼編碼能節省很多的空間，因為每一個字元出現的頻率不是一致的，例如在英語中，『e』出現的次數是最高的，那麼如果我把『e』的編碼定義的短一點，那麼是不是比起定長編碼來說，空間就減少了？

基於這種思路，哈夫曼編碼的具體實現過程如下：
（1）首先統計文本中各字元出現的頻率（權重）。
（2）使用這些頻率（權重），構建出哈夫曼樹。
（3）規定從根節點開始，向葉子節點行走，經過左子樹，編碼為0，右子樹，編碼為1，這樣就能得到每一個葉子節點字元的編碼值了。

D. 為什麼說哈夫曼編碼是壓縮率最高的編碼

假設用於通信的電文由字元集{a,b,c,d,e,f,g,h}中的字母構成，這8個字母在電文中出現的概率分別為{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}。

哈夫曼編碼 根據上面可得編碼表： a:1001 b:01 c:10111 d:1010 e:11 f:10110 g:00 h:1000

用三位二進行數進行的等長編碼平均長度為3，而根據哈夫曼樹編碼的平均碼長為：4*0.07+2*0.19+5*0.02+4*0.06+2*0.32+5*0.03+2*0.21+4*0.10=2.61 2.61/3=0.87=87%其平均碼長是等長碼的87%，所以平均壓縮率為13%。

因為定長編碼已經用相同的位數這個條件保證了任一個字元的編碼都不會成為其它編碼的前綴,所以這種情況只會出現在變長編碼當中，要想避免這種情況，

就必須用一個條件來制約定長編碼，這個條件就是要想成為壓縮編碼，變長編碼就必須是前綴編碼，所謂的前綴編碼就是任何一個字元的編碼都不能是另一個字元編碼的前綴。

(4)java哈夫曼編碼壓縮擴展閱讀：

實際應用中，除採用定時清洗以消除誤差擴散和採用緩沖存儲以解決速率匹配以外，主要問題是解決小符號集合的統計匹配，

例如黑（1）、白（0）傳真信源的統計匹配，採用0和1不同長度遊程組成擴大的符號集合信源。遊程，指相同碼元的長度（如二進碼中連續的一串0或一串1的長度或個數）。按照CCITT標准，需要統計2×1728種遊程（長度），

這樣，實現時的存儲量太大。事實上長遊程的概率很小，故CCITT還規定：若l表示遊程長度，則l=64q+r。其中q稱主碼，r為基碼。編碼時，不小於64的遊程長度由主碼和基碼組成。而當l為64的整數倍時，只用主碼的代碼，已不存在基碼的代碼。

E. 用java實現哈夫曼編碼

只要自己再加個類Tree就可以了。
代碼如下：

public class Tree {
double lChild, rChild, parent;
public Tree (double lChild, double rChild, double parent) {
this.lChild = lChild;
this.rChild = rChild;
this.parent = parent;
}
public double getLchild() {
return lChild;
}
public void setLchild(double lChild) {
this.lChild = lChild;
}
public double getRchild() {
return rChild;
}
public void setRchild(double rChild) {
this.rChild = rChild;
}
public double getParents() {
return parent;
}
public void setParents(double root) {
this.parent = root;
}

}

F. 哈夫曼編碼的壓縮實現

壓縮代碼非常簡單，首先用ASCII值初始化511個哈夫曼節點：
CHuffmanNode nodes[511];
for(int nCount = 0; nCount < 256; nCount++)
nodes[nCount].byAscii = nCount;
其次，計算在輸入緩沖區數據中，每個ASCII碼出現的頻率：
for(nCount = 0; nCount < nSrcLen; nCount++)
nodes[pSrc[nCount]].nFrequency++;
然後，根據頻率進行排序：
qsort(nodes, 256, sizeof(CHuffmanNode), frequencyCompare);
哈夫曼樹，獲取每個ASCII碼對應的位序列：
int nNodeCount = GetHuffmanTree(nodes); 構造哈夫曼樹非常簡單，將所有的節點放到一個隊列中，用一個節點替換兩個頻率最低的節點，新節點的頻率就是這兩個節點的頻率之和。這樣，新節點就是兩個被替換節點的父節點了。如此循環，直到隊列中只剩一個節點（樹根）。
// parent node
pNode = &nodes[nParentNode++];
// pop first child
pNode->pLeft = PopNode(pNodes, nBackNode--, false);
// pop second child
pNode->pRight = PopNode(pNodes, nBackNode--, true);
// adjust parent of the two poped nodes
pNode->pLeft->pParent = pNode->pRight->pParent = pNode;
// adjust parent frequency
pNode->nFrequency = pNode->pLeft->nFrequency + pNode->pRight->nFrequency; 有一個好的訣竅來避免使用任何隊列組件。ASCII碼只有256個，但實際分配了511個(CHuffmanNode nodes[511])，前255個記錄ASCII碼，而用後255個記錄哈夫曼樹中的父節點。並且在構造樹的時候只使用一個指針數組(ChuffmanNode *pNodes[256])來指向這些節點。同樣使用兩個變數來操作隊列索引(int nParentNode = nNodeCount;nBackNode = nNodeCount –1)。
接著，壓縮的最後一步是將每個ASCII編碼寫入輸出緩沖區中：
int nDesIndex = 0;
// loop to write codes
for(nCount = 0; nCount < nSrcLen; nCount++)
{
*(DWORD*)(pDesPtr+(nDesIndex>>3)) |=
nodes[pSrc[nCount]].dwCode << (nDesIndex&7);
nDesIndex += nodes[pSrc[nCount]].nCodeLength;
}
(nDesIndex>>3): >>3 以8位為界限右移後到達右邊位元組的前面
(nDesIndex&7): &7 得到最高位.
此外，在壓縮緩沖區中，必須保存哈夫曼樹的節點以及位序列，這樣才能在解壓縮時重新構造哈夫曼樹（只需保存ASCII值和對應的位序列）。 解壓縮比構造哈夫曼樹要簡單的多，將輸入緩沖區中的每個編碼用對應的ASCII碼逐個替換就可以了。只要記住，這里的輸入緩沖區是一個包含每個ASCII值的編碼的位流。因此，為了用ASCII值替換編碼，我們必須用位流搜索哈夫曼樹，直到發現一個葉節點，然後將它的ASCII值添加到輸出緩沖區中：
int nDesIndex = 0;
DWORD nCode;
while(nDesIndex < nDesLen)
{
nCode = (*(DWORD*)(pSrc+(nSrcIndex>>3)))>>(nSrcIndex&7);
pNode = pRoot;
while(pNode->pLeft)
{
pNode = (nCode&1) ? pNode->pRight : pNode->pLeft;
nCode >>= 1;
nSrcIndex++;
}
pDes[nDesIndex++] = pNode->byAscii;
}