function [new_stream, dict] = compress_bitstream(bitstream, bits_per_word)

fill_bits_len = ceil(log2(bits_per_word));
len           = length(bitstream) + fill_bits_len;

fill_bits  = bits_per_word - mod(len, bits_per_word);
bitstream  = [ dec2bin(fill_bits, fill_bits_len), bitstream, false(1, fill_bits) ];

[symb, prob, stream] = get_symbols(bitstream, bits_per_word);
dict                 = huffmandict(symb, prob);
enco                 = huffmanenco(stream, dict);
[new_stream, dict]   = apply_dictionary(bitstream, dict);

end


function [symb, prob, decimal_stream] = get_symbols(bitstream, bits_per_word)

len = length(bitstream);

if mod(len, bits_per_word) ~= 0
    disp('The length of the bitstream has to be a multiple of the bits_per_word parameter.')
    return
end

num_symbols    = len / bits_per_word;
decimal_stream = zeros(1, num_symbols);

for dec_idx = 1 : num_symbols
    bin_idx = (dec_idx-1) * bits_per_word + 1;
    end_idx = bin_idx + bits_per_word - 1;
    
    decimal_stream(dec_idx) = bin2dec(bitstream(bin_idx:end_idx), false);
end

% Compute the frequency of each symbol
unique_symbs = unique(decimal_stream);
prob         = histc(decimal_stream, unique_symbs) / num_symbols;

% num_symbs = length(unique_symbs);
% symb      = false(num_symbs, bits_per_word);
% for i = 1 : num_symbs
%     symb(i,:) = dec2bin(unique_symbs(i), bits_per_word);
% end

symb = unique_symbs;

end


function [new_bitstream, dict] = apply_dictionary(bitstream, huf_dict)

len           = length(bitstream);
[num_symb, ~] = size(huf_dict);

[symbs] = huf_dict(:,1);
symbs   = cell2mat(symbs);

bits_per_word = ceil(log2(max(symbs)));

for ith_symb = 1 : num_symb
    huf_dict{ith_symb,1} = dec2bin(symbs(ith_symb), bits_per_word);
end

new_bitstream = [];
for idx = 1 : bits_per_word : len
    cur_word = bitstream(idx:idx+bits_per_word-1);
    
    found    = false;
    ith_symb = 1;
    while found == false && ith_symb <= num_symb
        dict_word = huf_dict{ith_symb,1};
        
        if sum(xor(cur_word, dict_word)) == 0
            new_bitstream = [ new_bitstream, huf_dict{ith_symb,2} ];
            found = true;
        end
        
        ith_symb = ith_symb + 1;
    end
end

dict = huf_dict;

end
