Huffman Algorithm in Matlab

A brief introduction to Huffman coding

In computer science and information theory, Huffman coding is an entropy encoding algorithm used for lossless data compression. The term refers to the use of a variable-length code table for encoding a source symbol (such as a character in a file) where the variable-length code table has been derived in a particular way based on the estimated probability of occurrence for each possible value of the source symbol. It was developed by David A. Huffman while he was a Ph.D. student at MIT, and published in the 1952 paper “A Method for the Construction of Minimum-Redundancy Codes”.

The Code is divided in three files , the constructor for the node , the main file and the tree traversal recursive algorithm

1. Node Constructor

Save the file as Huffman.m

% Code by Jay Kanakiya
% http://blog.jaykanakiya.com

classdef Huffman
   properties
      leftNode = []
      rightNode = []
      probability
      code = ''
      character
   end
end

2.The Main Script file for Matlab

% Code by Jay Kanakiya
% http://blog.jaykanakiya.com

clc;
clear all;
close all;

a = [0.1 0.1 0.2 0.2 0.4];
b = ['a' 'b' 'c' 'd' 'e'];

% Empty Array of Object Huffman
thearray = Huffman.empty(5,0);

% Assign Initial Values
for i=1:length(a)
    thearray(i).probability = a(i);
    thearray(i).character = b(i);
end

temparray = thearray;

% Create the Binary Tree
for k = 1:size(temparray,2)-1

    % First Sort the temp array

    for i=1:size(temparray,2)
        for j = 1:size(temparray,2)-1
            if (temparray(j).probability > temparray(j+1).probability)
                %tempnode = temparray(j);
                %temparray(j) = temparray(j+1);
                %temparray(j+1) = tempnode;
            end
        end
    end

    % Create a new node 

    newnode = Huffman;

    % Add the probailities
    newnode.probability = temparray(1).probability + temparray(2).probability;

    % Add Codes
     temparray(1).code = '0';
     temparray(2).code = '1';

    % Attach Chlldren Nodes
    newnode.leftNode = temparray(1);
    newnode.rightNode = temparray(2);

    % Delete the first two nodes

     temparray = temparray(3:size(temparray,2));

    % Prepend the new node

     temparray = [newnode temparray];

end

rootNode = temparray(1);
codec = '';

% Looping though the tree
% See recursive function loop.m

loop(rootNode,codec);

disp(codec)

3.The Recursive Tree Traversal Algorithm
Save this file as loop.m
% Code by Jay Kanakiya
% http://blog.jaykanakiya.com

function f = loop(tempNode,codec)
if ~isempty(tempNode)
codec = [codec tempNode.code];

if ~isempty(tempNode.character)
disp(tempNode.character);
disp(codec);
end
if ~isempty(tempNode.code)

end
loop(tempNode.leftNode,codec);
loop(tempNode.rightNode,codec);
end
f = codec;
end

Save the above three files in the same directory.