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