
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.
Very nice, efficent, and elegant.