%% Codage de Huffman

%Source (ou vecteur d'occurrences pour chaque élément (A=1, nA=10), (B=2, nB=8), ...)
S = [ones(1,10), 2*ones(1,8), 3*ones(1,6), 4*ones(1,5), 5*ones(1,2)];
X = ['A';'B';'C';'D';'E']; %valeurs associées

%Source matrice image (img, D, etc.)
% S = D(:); %la matrice de l'exercice précédent.
% X = unique(S(:));

X_ind = 1:length(X); %indices des symboles
M = length(S); %Longueur de la source
N = length(unique(S(:))); %Nombre d'éléments différents = taille du dictionnaire

%Calcul de l'histogramme de la source
[ni_init,ci] = hist(S(:), unique(S(:)));
%figure,bar(ci,ni)

paths = {}; %On va stocker ici les embranchements successifs
%path{i,1} = les indices des noeuds fusionnés
%path{i,2} = 0 ou 1

%%
noeuds_Huffman = cell(1,N); %On va stocker les noeuds restants à fusionner
for i=1:N
   noeuds_Huffman{1,i} = ci(i); %Au début tous les noeuds sont indépendants
end
noeuds_Huffman
%%

ni = ni_init; %On tient la liste des occurrences fusionnées
while(length(ni)>1)
   
    %Tri des occurrences fusionnées
    [ni_sort, ind_sort] = sort(ni, 'ascend');
    
    %Deux plus rares éléments dans la liste
    ind_1 = ind_sort(1);
    ind_2 = ind_sort(2);
    
    %Pour accéder à(ux) élément(s) le(s) plus rare(s) on aura un 0
    paths{end+1,1} = noeuds_Huffman{ind_1};
    paths{end,2} = 0;
    %Pour accéder à(ux) second(s) élément(s) le(s) plus rare(s) on aura un 1
    paths{end+1,1} = noeuds_Huffman{ind_2};
    paths{end,2} = 1;
    
    %On crée une nouvelle entrée dans le vecteur d'occurrences
    ni(end+1) = ni_sort(1)+ni_sort(2);
    noeuds_Huffman{end+1} = [noeuds_Huffman{ind_1} noeuds_Huffman{ind_2}];
    %Et on supprime les anciens noeufs fusionnés
    ni([ind_1 ind_2]) = [];
    noeuds_Huffman([ind_1 ind_2]) = [];
    
end

%Reconstruction des codes
alphabet_Huffman = cell(3,N);
for i=1:N
   alphabet_Huffman{1,i} = X(i); %Symboles triés par ordre croissant
   alphabet_Huffman{2,i} = ni_init(i); %Nombre d'occurrences
end
%alphabet_Huffman{3,i} = vecteur de code associé au symbole alphabet_Huffman{1,i}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% A COMPLETER %%%%%
for i=1:length(paths)

end
alphabet_Huffman

%Calculer la longueur moyenne des codes associés à la source S et comparer à l'entropie

%Comparer à l'entropie de la source


%%
%Calculer la longueur moyenne des codes associés à la source S et comparer à l'entropie
l_moy = 0;
for i=1:N
   ...
end
%Comparer à l'entropie de la source



% .... FIN DU TRAVAIL....
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
