adaptivehuffman.m

用visual C++实现的huffman编码程序 很实用的哦

    end
    close(wb)     %Close progress bar
end
%==========================================================================
%End of Adaptive Huffman Coding, Sub Functions follow
%==========================================================================

function treeloop(symbol)
%==========================================================================
%Performs loop for putting symbols into the tree
%==========================================================================
    if sum(NYT == symbol)     %Has symbol been seen before
        newsymbol(symbol);     %Expand NYT Node
        updatetree(symbol,1);     %Update tree
    else
        updatetree(symbol,0);     %Update tree, do not go to parent node
    end
end

function newsymbol(symbol)
%==========================================================================
%Inserts a new symbol into the tree
%==========================================================================
    parent = location(NYTlocation);     %Find the location of the NYT node
    nyt = length(tree)+1;     %Find the next available tree space
    right = length(tree)+2;     %Find another available tree space
%--------------------------------------------------------------------------
%Insert the new symbol
%--------------------------------------------------------------------------
    nodenumber = nodenumber - 1;    %Decrease node number
    tree(right) = tree(parent);     %Copy structure to the right child
    tree(right).number = nodenumber;     %Assign node a number
    tree(right).parent = parent;     %Assign Parent Node
    tree(right).symbol = symbol;     %Assign New Symbol
    tree(right).weight = 1;     %Weight of one
    location(symbol+1) = right;     %Update location of node
%--------------------------------------------------------------------------
%Move the Not Yet Transmitted Node
%--------------------------------------------------------------------------
    nodenumber = nodenumber - 1;    %Decrease node number    
    tree(nyt) = tree(parent);     %Copy NYT node to the left child
    tree(nyt).number = nodenumber;     %Assign node a number
    tree(nyt).parent = parent;     %Assign parent node
    tree(nyt).symbol = NYTlocation;     %Assign NYT symbol
    location(NYTlocation) = nyt;     %Update location of NYT node
%--------------------------------------------------------------------------
%Update Parent
%--------------------------------------------------------------------------
    tree(parent).left = nyt;     %Assign child node
    tree(parent).right = right;     %Assign child node
    tree(parent).symbol = [];     %Blank symbol as branch
    tree(parent).weight = 1;     %Set weight
%--------------------------------------------------------------------------
%Remove Symbol from NYT list
%--------------------------------------------------------------------------
    NYT(NYT==symbol) = [];
end

function updatetree(symbol,skip)
%==========================================================================
%Reorganises tree if necessary andincrease the weight of the node
%==========================================================================
    position = location(symbol+1);      %Set pointer position
    while 1     %Continue to loop
        if skip     %Skips node number checking from NYT node
%--------------------------------------------------------------------------
%Put weights and node numbers into an array
%--------------------------------------------------------------------------
            weights = [];weights = [weights tree.weight];
            numbers = [];numbers = [numbers tree.number];
%--------------------------------------------------------------------------
%Check node if is highest ranked for weight and if so the highest rank is
%not the root node or the nodes parent
%--------------------------------------------------------------------------
            if tree(position).number ~= max(numbers(weights == tree(position).weight))...
                    && find(max(numbers(weights == tree(position).weight))) ~= 1 &&...
                    find(max(numbers(weights == tree(position).weight))) ~= tree(position).parent;
%--------------------------------------------------------------------------
%Store position of node with the higher rank
%--------------------------------------------------------------------------
                bignode = find(numbers == max(numbers(weights == tree(position).weight)));
%--------------------------------------------------------------------------
%Store current nodes parent and node number
%--------------------------------------------------------------------------
                tempparent = tree(position).parent;
                tempnodenumber = tree(position).number;
%--------------------------------------------------------------------------
%Move current node
%--------------------------------------------------------------------------
                tree(position).parent = tree(bignode).parent;
                tree(position).number = tree(bignode).number;
%--------------------------------------------------------------------------
%Update parents child locator
%--------------------------------------------------------------------------
                if tree(tree(position).parent).left == tree(position).parent
                    tree(tree(position).parent).left = position;
                else
                    tree(tree(position).parent).right = position;
                end
%--------------------------------------------------------------------------
%Update old node
%--------------------------------------------------------------------------
                tree(bignode).parent = tempparent;
                tree(bignode).number = tempnodenumber;
%--------------------------------------------------------------------------
%Update parents child locator
%--------------------------------------------------------------------------
                if tree(tree(bignode).parent).left == tree(bignode).parent
                    tree(tree(bignode).parent).left = bignode;
                else
                    tree(tree(bignode).parent).right = bignode;
                end
                clear bignode tempparent tempnodenumber     %Keep workspace tidy
            end    
        tree(position).weight = tree(position).weight + 1;     %Inc Weight by 1
        end
        if skip;skip = 0;end     %Enables node number checking 
        if position == 1;break;end;
        position = tree(position).parent;
        clear weights numbers    %Keep workspace tidy
    end
    clear position
end

function nodecode(symbol)
%==========================================================================
%Finds the code from the root to the leaf
%==========================================================================
    position = location(symbol+1);      %Set pointer position
    tempcode = [];
    while position ~= 1
        if tree(tree(position).parent).left == position     %If left branch
            tempcode = [uint8(0) tempcode];    %Assign binary zero
        else     %If right branch
            tempcode = [uint8(1) tempcode];    %Assign binary one
        end
        position = tree(position).parent;     %Move up tree
    end
    huffstream = [huffstream tempcode];     %Add symbol code to Huffman stream
    clear tempcode position     %Keep workspace tidy
end

function treedetails
%==========================================================================
%Displays tree details (debug)
%==========================================================================
    fprintf('   ,------------');for n=1:length(tree);fprintf('-------');               end;    fprintf('.\n');
    fprintf('   |Tree node   ');for n=1:length(tree);fprintf('| % 4i ',n);             end;    fprintf('|\n');
    fprintf('   |------------');for n=1:length(tree);fprintf('-------');               end;    fprintf('|\n');
    fprintf('   |Node Number ');for n=1:length(tree);fprintf('| % 4i ',tree(n).number);end;    fprintf('|\n');
    fprintf('   |Node Parent ');for n=1:length(tree);fprintf('| % 4i ',tree(n).parent);end;    fprintf('|\n');
    fprintf('   |Node Left   ');for n=1:length(tree);fprintf('| % 4i ',tree(n).left);  end;    fprintf('|\n');
    fprintf('   |Node Right  ');for n=1:length(tree);fprintf('| % 4i ',tree(n).right); end;    fprintf('|\n');
    fprintf('   |Node Symbol ');for n=1:length(tree);
                          if isempty(tree(n).symbol);fprintf('|empty ',tree(n).symbol);else
                                                     fprintf('| % 4i ',tree(n).symbol);end;end;fprintf('|\n');    
    fprintf('   |Node Weight ');for n=1:length(tree);fprintf('| % 4i ',tree(n).weight);end;    fprintf('|\n');  
    fprintf('   ''------------');for n=1:length(tree);fprintf('-------');              end;    fprintf('''\n');
end

end     %End of adaptive huffman

%==========================================================================
%Seperate functions
%==========================================================================

function dec = bits2dec(bits)
%==========================================================================
%Returns a decimal value from a bit array
%==========================================================================
     dec = bin2dec(int2str(bits));
end