HuffmanCode фиксированная длина битов на символ

Question

Как вы определяете, сколько битов на символ требуется для кода фиксированной длины в строке, используя huffman?У меня была идея, что вы посчитаете количество различных символов в строке, чем вы представляете это число в двоичном виде, так что это будет фиксированная длина, но это не работает.Например, в строке «letty lotto любит много lolly» ... есть 10 различных символов, исключая кавычки (поскольку 10 = 0101 (4 бита), я думал, что это означает, что все символы могут быть представлены с использованием 4 бит)частота f равна 1 и кодируется как 11111 (5 бит), а не 4.

Answer 1

Допустим, у вас есть строка с 50 "A", 35 "B" и 15 "C".

При кодировании с фиксированной длиной вы можете представить каждый символ в этой строке, используя2 битаВсего 100 символов, поэтому при использовании этого метода длина сжатой строки будет 200 бит.

Кроме того, вы можете использовать схему кодирования переменной длины.Если вы позволите символам иметь переменное число битов, вы можете представить «A» с 1 битом («0»), «B» с 2 битами («10») и «C» с 2 битами («11»)).При использовании этого метода длина сжатой строки составляет 150 битов, поскольку для представления наиболее распространенных фрагментов информации в строке требуется меньше битов.

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

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