Huffman Coding

clear all
struct_levels_to_print(20);

# Lendo imagem e calculando histograma
#######################################################################
    img = imread("brain.jpg");

# Criando histograma
    [w, h] = size(img);
    count = w*h;

    histogram = [1:256];
    histogram(1:256) = 0;

    # Preenchendo
    for i = 1:count
      histogram(img(i) + 1) = histogram(img(i) + 1) + 1;
    endfor

    #normalizando
    for i = 1:256
      histogram(i) = histogram(i) / count;
    endfor


# Criando a árvore do dicionário de huffman
#######################################################################
memory = {};
flag = true;
REMOVED_FREQ = 2;
last_built_tree = -1;

function retval = istree (mem, c)
    retval = isfield(mem, strcat("a", num2str(c)));
endfunction

function retval = gettree (mem, c)
    retval = getfield(mem, strcat("a", num2str(c)));
endfunction

function retval = settree (mem, c, tree)
    retval = setfield(mem, strcat("a", num2str(c)), tree);
endfunction



# removendo cores com probabilidade zero
[freq, col] = sort(histogram);

i = 1;
while(flag)
    if (freq(i) == 0)
        histogram(col(i)) = REMOVED_FREQ;
    else
        flag = false;
    endif
    i = i + 1;
endwhile

# criando a árvore de huffman
flag = true;
while(flag)
    [freq, col] = sort(histogram);
    a = col(1);
    b = col(2);
    freq_a = freq(1);
    freq_b = freq(2);



    a_is_a_tree = istree(memory, a);
    b_is_a_tree = istree(memory, b);

    if (freq_a == REMOVED_FREQ)
        flag = false;
    elseif (freq_b == REMOVED_FREQ)
        flag = false;
    else
        newtree = {};
        if (a_is_a_tree && b_is_a_tree)
            newtree.left = gettree(memory, a);
            newtree.right = gettree(memory, b);
            memory = settree(memory, a, newtree);
        elseif (a_is_a_tree)
            newtree.left = gettree(memory, a);
            newtree.right = freq_b;
            newtree.right_color = b;
            memory = settree(memory, a, newtree);
        elseif (b_is_a_tree)
            newtree.left = freq_a;
            newtree.left_color = a;
            newtree.right = gettree(memory, b);
            memory = settree(memory, a, newtree);
        else
            newtree.left = freq_a;
            newtree.left_color = a;
            newtree.right = freq_b;
            newtree.right_color = b;
            memory = settree(memory, a, newtree);
        endif

        last_built_tree = a;
        histogram(a) = freq_a + freq_b;
        histogram(b) = REMOVED_FREQ;
    endif
endwhile

huffmantree = gettree(memory, last_built_tree);

# Criando o dicionário de huffman
#######################################################################


stack = {};
dict = {};
flag = true;
i = 1;
stack_top = 2;

element = {};
element.branch = huffmantree;
element.code = "";

stack.a1 = element;


while(flag)
    istr = strcat("a", num2str(i));

    if (isfield(stack, istr))
        t = getfield(stack, istr);

        if (isfield(t.branch, "left_color"))
            code = strcat(t.code, "1");
            dict = setfield(dict, strcat("a", num2str(t.branch.left_color)), code);
        else
            element = {};
            element.branch = t.branch.left;
            element.code = strcat(t.code, "1");

            stack = setfield(stack, strcat("a", num2str(stack_top)), element);
            stack_top = stack_top + 1;
        endif

        if (isfield(t.branch, "right_color"))
            code = strcat(t.code, "0");
            dict = setfield(dict, strcat("a", num2str(t.branch.right_color)), code);
        else
            element = {};
            element.branch = t.branch.right;
            element.code = strcat(t.code, "0");

            stack = setfield(stack, strcat("a", num2str(stack_top)), element);
            stack_top = stack_top + 1;
        endif
    else
        flag = false;
    endif
    i = i + 1;
endwhile


# Codificando a imagem
#######################################################################

    encoded_image = "Image: ";

    [w, h] = size(img);
    count = w*h;
    for i = 1:count
        c = img(i) + 1;
        v = getfield(dict, strcat("a", int2str(c)));
        encoded_image = strcat(encoded_image, v, ".");
    endfor

# Mostrando o código gerado
#######################################################################

    encoded_image