導航:首頁 > 文件處理 > 文件壓縮哈夫曼樹

文件壓縮哈夫曼樹

發布時間:2022-11-30 10:17:32

① 哈夫曼編碼壓縮概念的基本思想如何回答(精簡的說)

哈夫曼編碼(Huffman Coding)是一種編碼方式,哈夫曼編碼是可變字長編碼(VLC)的一種。 Huffman於1952年提出一種編碼方法,該方法完全依據字元出現概率來構造異字頭的平均長 度最短的碼字,有時稱之為最佳編碼,一般就叫作Huffman編碼。 以哈夫曼樹─即最優二叉樹,帶權路徑長度最小的二叉樹,經常應用於數據壓縮。 在計算機信息處理中,「哈夫曼編碼」是一種一致性編碼法(又稱"熵編碼法"),用於數據的無損耗壓縮。這一術語是指使用一張特殊的編碼表將源字元(例如某文件中的一個符號)進行編碼。這張編碼表的特殊之處在於,它是根據每一個源字元出現的估算概率而建立起來的(出現概率高的字元使用較短的編碼,反之出現概率低的則使用較長的編碼,這便使編碼之後的字元串的平均期望長度降低,從而達到無損壓縮數據的目的)。這種方法是由David.A.Huffman發展起來的。 例如,在英文中,e的出現概率很高,而z的出現概率則最低。當利用哈夫曼編碼對一篇英文進行壓縮時,e極有可能用一個位(bit)來表示,而z則可能花去25個位(不是26)。用普通的表示方法時,每個英文字母均佔用一個位元組(byte),即8個位。二者相比,e使用了一般編碼的1/8的長度,z則使用了3倍多。倘若我們能實現對於英文中各個字母出現概率的較准確的估算,就可以大幅度提高無損壓縮的比例。

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

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

例如:用三位二進行數進行的等長編碼平均長度為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%,壓縮率一般是越小越好,但是壓得越小,解壓時間越長。

(2)文件壓縮哈夫曼樹擴展閱讀

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

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

③ 哈夫曼編碼的壓縮實現

壓縮代碼非常簡單,首先用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;
}

閱讀全文

與文件壓縮哈夫曼樹相關的資料

熱點內容
微信伺服器連接失敗是什麼原因 瀏覽:694
命令行執行sql腳本亂碼 瀏覽:751
屬於三灣改編譯的視頻 瀏覽:165
仿射密碼演算法 瀏覽:859
如何用命令格式化系統盤 瀏覽:54
伺服器主板響怎麼解決 瀏覽:569
為什麼安卓手機要root許可權 瀏覽:520
一台伺服器如何配置多個域名 瀏覽:857
pdf導入多看 瀏覽:243
剪切一半取消了文件夾怎麼恢復 瀏覽:994
空氣壓縮機符號 瀏覽:279
吹氣打氣泵空氣壓縮機怎麼用 瀏覽:617
程序員面試通過後又拒絕接受offer 瀏覽:520
linux獲取進程的父進程 瀏覽:22
android文件編輯器 瀏覽:985
美東伺服器叫什麼 瀏覽:532
四年級平均值怎麼算簡單演算法 瀏覽:183
冷撲大師演算法 瀏覽:373
重復數據比對演算法 瀏覽:740
golang調用python 瀏覽:171