Условие для единственного разрядного кода для символа в коде Хаффмана?
Это - вопрос, с которым я столкнулся в школьных настройках, но это продолжает прослушивать меня так, я решил спросить это здесь.
В сжатии по алгоритму Хаффмана, (символы) последовательностей фиксированной длины кодируются последовательностями переменной длины. Длина кодовой последовательности зависит от частот (или вероятности) исходных символов.
Мои вопросы: какова минимальная самая высокая частота символов, которой тот символ будет закодирован единственным битом?
2 ответа
Оказывается, что ответ равен 0.4, то есть, если наибольшая частота p равна p >= 0.4, то гарантирован 1-битный код для соответствующего символа. Другими словами, это достаточное условие.
Также верно, что p >= 1/3 является необходимым условием. То есть, могут быть примеры, когда 0.4 > p >= 1/3, и кратчайший код 1-битный, но таких случаев нет, если p < 1/3.
Способ рассуждения об этом состоит в том, чтобы посмотреть на способ построения кодового дерева, в частности, на частоты трех последних выживших поддеревьев. Доказательство появилось в Johnsen, "On the redundancy of binary Huffman codes", 1980 (к сожалению, это платная ссылка).
В общем, около 50% входящего потока символов должно состоять из заданного символа, чтобы Хаффман закодировал его как один бит. Причина этого в том, что из-за того, как работает кодирование Хаффмана (кодировка одного символа не может быть префиксом другого), кодируя символ одним битом, вы требуете, чтобы первый бит для каждого другого символа быть противоположным значением (т.е. если один символ закодирован как 0 , все остальное должно начинаться с 1 плюс еще как минимум один бит). Поскольку вы исключаете половину возможного пространства кодирования для любой заданной длины в битах, вам необходимо получить способ кодировать по крайней мере половину вводимых символов, чтобы обеспечить безубыточность.
Обратите внимание, что есть особый случай, когда пространство символов состоит только из 3 символов. В таком случае любой символ, имеющий наибольшую частоту, будет закодирован 1 битом (поскольку два других будут вариациями 2-го бита в зависимости от того, какое значение первого бита не выбрано) - если 2 или более имеют одинаково большую вероятность, любой из них мог быть закодирован. Таким образом, в случае с 3 символами возможно, что символ, скажем, с вероятностью 34% теоретически может быть закодирован как один бит (скажем, 0 ), в то время как два других могут иметь вероятность 33% или меньше. и иметь код 10 и 11 .
Итак, если вы рассматриваете все возможности, то технически все, что 1/3 или выше, потенциально может быть закодировано как один бит (в случае трех символов).