哈夫曼壓縮代碼

㈠ 哈夫曼編碼進行圖像壓縮

% 演示圖象的哈夫曼編解碼過程
% chenyong 2009.04.20

clear all;
close all;
clc;
Dimens = 256; % 矩陣維數，假設矩陣為方陣即256*256
src_size = Dimens^2; % 矩陣元素的個數
gray_level = 9; % 灰度級

src = randn(Dimens); %產生模擬圖像矩陣，滿足正態分布，零均值，方差為1
%src = randint(Dimens,Dimens,gray_level); % 產生隨機圖像矩陣，灰度值為0~63，滿足均勻分布
src_one = reshape(src,1,src_size);
src_max = max(src_one);
src_min = min(src_one);
quan = linspace(src_min,src_max,gray_level); % 產生均勻量化區間
src_d = []; % 數字矩陣
for row = 1:Dimens % 逐點量化
for vol = 1:Dimens
diff = abs(src(row,vol)-quan);
[min_diff,min_index] = min(diff);
quan_gray = min_index -1;
src_d(row,vol) = quan_gray;
end
end

%將數字圖像矩陣還原成模擬矩陣
src_a = [];
quan_space = quan(2)-quan(1);
for row = 1:Dimens
for vol = 1:Dimens
src_a(row,vol) = src_d(row,vol) * quan_space + src_min;
end
end

% prob數組保存圖像中各灰度出現的概率
prob = [];
for src_value=0:(gray_level-1)
index = find(src_d==src_value);
i = src_value + 1;
prob(i) = length(index)/src_size;
end

% 畫出直方圖
% stem(0:gray_level-1,prob);
% xlabel('灰度值');
% ylabel('概率');
% title('灰度直方圖');

% huffman編碼
p = prob;
n=length(p);
q=p;
m=zeros(n-1,n);
for i=1:n-1
[q,l]=sort(q);
m(i,:)=[l(1:n-i+1),zeros(1,i-1)];
q=[q(1)+q(2),q(3:n),1];
end
bre=zeros(n-1,n);
bre(n-1,1)=0+j; %虛部表示當前的二進制數的位數，以下類似
bre(n-1,2)=1+j;
for time=1:n-2
loc_1 = find(real(m(n-time,:))==1);
prebit = bre(n-time,loc_1);
bre(n-time-1,1) = (real(prebit)*2 + 0) + j*(imag(prebit)+1);
bre(n-time-1,2) = (real(prebit)*2 + 1) + j*(imag(prebit)+1);

loc_not1 = find(real(m(n-time,:))>1);
bre(n-time-1,3:3+time-1) = bre(n-time,loc_not1);
end
[m1,index] = sort(m(1,:));
code = bre(1,index);
code_data = real(code);
code_bits = imag(code);
disp(['gray level',' ', 'huffman code']);
for i = 1:length(code)
disp([num2str(i-1),' ' ,num2str(dec2bin(code_data(i)))]);
disp([num2str(i-1),' ' ,num2str(dec2bin(code_data(i),code_bits(i)))]);
end
code_binary = dec2bin(code_data);

%逐點編碼
out = [];
for row = 1:Dimens
for vol = 1:Dimens
now_gray = src_d(row,vol);
now_code = code_binary(now_gray+1,:);
now_bits = code_bits(now_gray+1);
now_code = now_code(end-now_bits+1:end);
out = [out, now_code];
end
end

%計算壓縮比
real_bitnum = length(out);
bitnum_no_huffman = src_size*nextpow2(gray_level);
comp_ratio =bitnum_no_huffman/real_bitnum;
Lavg = real_bitnum/src_size;
Hshannon = (-1)*prob*(log2(prob))';
disp(['Lavg = ',num2str(Lavg)]);
disp(['normal bit num = ',num2str(nextpow2(gray_level))]);
disp(['comp_ratio = ',num2str(comp_ratio)]);
disp(['Hshannon = ',num2str(Hshannon)]);

㈡ 哈夫曼編碼的壓縮實現

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

㈢ 跪求哈夫曼編碼壓縮與其它壓縮演算法的比較（復雜性和壓縮效果）

（1）所形成的Huffman編碼的碼字是不是唯一的，但是可以被指定為唯一的編碼效率為「1」大，小的是「0」時，兩個最小概率符號賦值。反之也可以。如果兩個符號的發生的概率是相等的，排列無論前面是可能的，所以霍夫曼碼字的結構不是唯一的，對於相同的信息源，不管如何在上述的順序安排的，它的平均碼字長度是不改變，因此，編碼效率是獨一無二的。
（2）只有當不均勻時，每個符號的信息源的發生的概率，霍夫曼編碼的效果是唯一明顯的。
（3）霍夫曼編碼必須是精確的原始文件中的各符號的發生頻率的統計數據，並且如果沒有準確的統計數據，壓縮將低於預期。 Huffman編碼通常必須經過兩道，第一遍統計的第二次產生編碼，編碼速度是比較慢的。電路的復雜性的另一種實現的各種長度的編碼，解碼處理是相對復雜的，因此，解壓縮處理是相對緩慢。
（4）Huffman編碼只能使用整數來表示一個符號，而不是使用小數，這在很大程度上限制了壓縮效果。
（5）霍夫曼是所有的位，如果改變其中一個可以使數據看起來完全不同