Huffman encoding and decoding

Huffman encoding and decoding offer efficient methods for lossless data compression. By analyzing symbol frequencies .

Huffman encoding is a method for lossless data compression. It involves analyzing the frequency of symbols in the input data, constructing a binary tree based on these frequencies, assigning shorter codewords to more frequent symbols, and generating the encoded data. Huffman decoding reconstructs the original data by traversing the Huffman tree based on the encoded bits. This technique efficiently compresses data, especially when some symbols occur more frequently than others.

The project scope involves implementing Huffman encoding and decoding algorithms, optimizing their performance, and potentially integrating them into existing compression tools. Additionally, the project may include developing a user interface, conducting research on compression effectiveness, and creating educational materials..

Huffman encoding and decoding offer efficient methods for lossless data compression. By analyzing symbol frequencies and constructing compact codewords, these algorithms can significantly reduce the size of data while preserving its original content. Integrating these algorithms into applications or systems can enhance their performance and usability. Overall, Huffman encoding and decoding remain valuable tools in the realm of data compression, offering effective solutions for minimizing storage space and transmission bandwidth requirements.

function [ codeword ] = huffman_encode( p )

%UNTITLED2 Summary of this function goes here

% Detailed explanation goes here

%%

%This block initiates necessary important matrices and cells and stuffs

n=length(p);

codeword=cell(1,n);%Where the codewords are going to be stored

X=zeros(n,n);%This matrix helps us track which elemnts we have worked on

temp=p;%We will work on temp not to temper with original p

%%

%Building the relationship matrix X.This matrix has all elements zero

%except for few entries which are substituted with 10 or 11.Number 10 denotes this

%entry is the minimum in the column and 11 indicates this is the second

%minimum.the minimum is replaced by 100 and second minimum is replaced by

%sum of the minimum and the second minimum.And processing for the next

%column progresses

for i=1:n-1

[~ ,l]=sort(temp);

X(l(1),i)=10;

X(l(2),i)=11;

temp(l(2))=temp(l(2))+temp(l(1));

temp(l(1))=100;

end

%%

%Filling in codewords.The key is the relationship between the 11 marked

%entry in each columnThis ties the column with the next one.

i=n-1;

rows=find(X(:,i)==10);

codeword(rows)=strcat(codeword(rows),'1');

rows=find(X(:,i)==11);

codeword(rows)=strcat(codeword(rows),'0');

for i=n-2:-1:1

row11=find(X(:,i)==11);

row10=find(X(:,i)==10);

codeword(row10)=strcat(codeword(row11),'1');

codeword(row11)=strcat(codeword(row11),'0');

end

end

function [msg] = huffman_decode(symb,code,bitstream)

%UNTITLED Summary of this function goes here

% Detailed explanation goes here

%Assuming code to be in cell format

%n is the number of messages

% maxlen is maximum length of code

%Idea is simple.We are going to search for matching of bits until we reach

%maximum length of the codeword or match is found.When a match between bit

%or group of bits is found we notedown the corresponding symbol of the

%group of bits.

n=length(symb);

lengths=[];

for i=1:n

len=length(char(code(i)));

lengths=[lengths len];

end

maxlen=max(lengths);

msg='';

%bitstream length is denoted by streamlen

streamlen=length(bitstream);

i=1;

while i<=streamlen

j=0;

while j<maxlen

c=bitstream(i:i+j);

ind=1;

while (ind<=n && ~isequal(char(code(ind)),c))

ind=ind+1;

end

if ind<=n

msg=[msg char(symb(ind))];

break

else j=j+1;

end

end

i=i+j+1;

end