huff.txt

利用数据结构的二叉树概念编写的MATLAB程序实现HUFFMAN编码。

。。。% HUFFMAN.M -  Find the binary Huffman code for a given set of 
%              probabilities.
% EE740 W98 - J. Schamus

function [code, L] = huffman(P)
P = [8 7 6 5 4 3 2 1]
P = P / (sum(P) + ~sum(P));
Psave = P;

n = length(P);
P = [P zeros(1,n - 1) + 2];
code = zeros((n * 2) - 2, 1) - 1;
tree = zeros(n-1, 3);

% Build Binary Tree for Huffman Code
for i = 1:n-1,
   [index1, index2] = findmin2(P);
   tree(i, 1) = P(index1) + P(index2);
   P(n + i) = tree(i, 1);
   tree(i, 2) = index1;
   tree(i, 3) = index2;
   P(index1) = 2;
   P(index2) = 2;
end
tree

% Walk back through the Binary Tree to determine code
code(tree(n-1,2),1) = 0;
code(tree(n-1,3),1) = 1;
codelen = 1;
for i = n-2:-1:1,
   tempcode = code(i + n,find(code(i + n,:) > -1));
   tlen = length(tempcode);
   [row, col] = size(code);
   while col < tlen + 1,         % add to the code length as necessary
      code = [code (zeros((n * 2) - 2, 1) - 1)];
      codelen = codelen + 1;
      col = col + 1;
   end
   code(tree(i,2), 1:tlen) = tempcode;
   code(tree(i,2), tlen + 1) = 0;
   code(tree(i,3), 1:tlen) = tempcode;
   code(tree(i,3), tlen + 1) = 1;
end
code = code(1:n, :)

% Calculate L
L = 0;
for i=1:n,
   L = L + (Psave(i) * length(find(code(i,:) > -1)));
end



% FINDMIN2.M - Find the smallest two probabilities.
%
% ee740 w98 - J. Schamus


function [index1, index2] = findmin2(P)

min1 = 3;
min2 = 3;
n = length(P);
for i = 1:n,
   if P(i) < min1,
      index1 = i;
      min1 = P(i);
   end
end
P(index1) = 2;
for i = 1:n,
   if P(i) < min2,
      index2 = i;
      min2 = P(i);
   end
end