Generate Huffman Code with Probability

48 次查看（过去 30 天）
Rooter Boy
Rooter Boy 2021-1-18
编辑： Rooter Boy 2021-1-18
Huffman code generation method. I need the code of this Methot in Matlab. If someone will help me, i will be very happy.
1. Arrange the symbols to be coded according to the occurrence probability from high to low;
2. The two symbols with the lowest probability of occurrence are combined, and the probabilities of the two are added to obtain the combined probability;
3. Sort the obtained combined probabilities and the probabilities of other symbols;
4. Repeat (2) until the combination probability is 1.
First, arrange according to the occurrence probability of each symbol;
Find the two symbols with the smallest probability and combine them. Here is the minimum of a3 and a5, the probability of combining the two is 0.1;
Treat the combined two symbols as a new symbol and arrange them again with other symbols to find the two with the smallest occurrence probability;
Combining two symbols with a small probability of occurrence again, there is a combination probability;
Go on like this, knowing that the probability of combining is 1;
At this point, the Huffman "tree" is finished and can be encoded;
Starting with a probability of 1 (far right), the upper fork is numbered 1, the lower fork is numbered 0 (or vice versa), and numbered to the left.
Reading from right to left:
a2 = 1;
a6 = 01;
a1 = 001;
a4 = 0001;
a3 = 00001;
a5 = 00000;
My tried code block:
clear all; clc;
% Getting charecter probabilities from file
[filename,datapath] = uigetfile('*.*', 'select the file');
if isequal(filename,0)
disp('User selected Cancel');
else
disp(['User selected ', fullfile(datapath,filename)]);
end
fid = fopen(filename);
ftell(fid)
tline1 = fgetl(fid) % read the first line
% str = string(tline1)
sym_dict=unique(tline1);
In_s = sym_dict; %Input symbols
% Calculate probabilities of the symbols
for k1=1:length(sym_dict)
prob(k1) = (sum(tline1==sym_dict(k1)))/length(tline1);
end
[z i]=sort(prob,'ascend');
sort_u =sym_dict(i);
In_p = z;
org_len = length(In_p);
%We have sorted array of probabilities in ascending order with track of symbols
ind=1;
len_tr = [org_len];
pos_tr = [0];
total_array(ind,:)=In_p;
append1=[];
lp_j=1;
while(ind<org_len-1)
firstsum = In_p(lp_j)+In_p(lp_j+1); %sum the lowest probabilities
append1 = [append1,firstsum]; %appending sum in array
In_p = [In_p((lp_j+2):length(In_p)),firstsum]; % reconstrucing prob array
In_p = sort(In_p);
ind = ind+1;
total_array(ind,:) = [In_p,zeros(1,org_len-length(In_p))]; %setting track of probabilities
len_tr = [len_tr,length(In_p)]; %lengths track
for i=1:length(In_p)
if(In_p(i)==firstsum)
pos = i; %position after swapping of new sum
end
end
pos_tr = [pos, pos_tr];
end
main_arr = total_array';
%columns indicates no.of times we have done sorting which length-1;
%rows have the prob values with zero padded at the end.
code = cell(org_len,org_len-1); % create cell array
col=org_len-1;
row=1;
% Assigning 0 and 1 to 1st and 2nd row of last column
code{row,col}='0';
code{row+1,col}='1';
while col~=1
i=1;
x=1;
z=0;
if (main_arr(row,col-1) + main_arr(row+1,col-1))==main_arr(row,col)
code{row,col-1}=[code{row,col} '0'];
code{row+1,col-1}=[code{row,col} '1'];
while ~isempty(code{row+i,col})
code{row+1+i,col-1}=code{row+i,col};
i=i+1;
end
else
code{row,col-1}=[code{row+1,col} '0'];
code{row+1,col-1}=[code{row+1,col} '1'];
while ~isempty(code{row+x,col})
code{row+1+x,col-1}=code{row+z,col};
x=x+1;
z=z+2;
end
end
col=col-1;
end

请先登录，再回答此问题。

回答（0 个）

类别

在 Help Center 和 File Exchange 中查找有关 Denoising and Compression 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by