Как рассчитать длину кода Хаффмана без создания фактического кода Хаффмана

Question

Учитывая вектор V в Matlab Я хочу, чтобы вычислить длину кода без генерации кода ...

v = [0.1,0.1,0.1,0.2, 0.2,0.3]; длина кода = 17. Как я могу вычислить его без генерации кода.

Thanks

Answer 1

Значит, есть шесть символов? Тогда максимальная длина кода не может быть 17. Максимальная длина кода с шестью символами для любой набор частот составляет пять бит. (0, 10, 110, 1110, 11110, 11111).

Для этого конкретного набора вероятностей, предполагающих один символ на вероятность и что вероятности являются точными, вы можете получить два разных кода в зависимости от выбора, сделанного при выполнении алгоритма Хаффмана. Один имеет максимальную длину 3, другую - максимальную длину 4. Оба кода одинаково оптимальны при кодировании символов. Два кода имеют длину кода в том же частотном порядке (4,4,3,2,2,2) и (3,3,3,3,2,2).

Вы можете означать сумму бит над шестью возможными символами, которая на самом деле составляет 17 для одного из кодов, но 16 для другого. Однако это бессмысленная мера, поскольку вы использовали каждый символ один раз, в противоречие с их заявленными вероятностями. Полезной мерой было бы умножение каждой длины символа в битах на вероятность получения средней длины символа в битах. Это два бита для обоих этих кодов. Вот как вы подтверждаете, что оба кода одинаково оптимальны.

В целом вам необходимо применить алгоритм Хаффмана, чтобы определить максимальную длину кода. Других ярлыков нет. Вы можете пересечь дерево, чтобы найти максимальную длину. Вам не нужно явно генерировать код как таковой, но код подразумевается деревом.

Вы можете вычислить энтропию, чтобы получить нижнюю границу средней длины символа в битах. Это сумма каждой вероятности, умноженная на ее отрицательный логарифм базы-2. В этом случае энтропия равна 2.446.

Answer 2

Возможно, я не понял свой вопрос, но я думаю, что этот код вернет минимальную длину кода для вектора данных 'v'.

% return the huffman lenght of a matrix 
function S = hufman_length(v) 


    v = (v(:)); 
    v = hist(v,256); 
    v = v(find(v>0)); 
    S = 0; 
    %acumulating the probability 
    while (length(v) >= 2) 
    v = sort(v); 
    S = S + v(1) + v(2); 
    v(2) = v(1) + v(2); 
    v = v(2:length(v)); 

    end 


end