0
1

Докажите, что если частоты всех символов меньше $%1/3$% (другими словами, каждый символ в исходную строку s входит строго меньше $%|s|/3$% раз), то коды всех символов в коде Хаффмана будут длиннее одного бита.

задан 9 Ноя '15 18:04

10|600 символов нужно символов осталось
2

Это прямо следует из способа построения кода Хаффмана. У нас имеется упорядоченный список частот символов: $%\frac13 > p_1\ge p_2\ge\cdots\ge p_m$%. На каждом шаге мы складываем две минимальные величины, формируя новое число $%p'=p_{m-1}+p_m$%, и помещаем его в список. Если частота какого-то символа объединилась с какой-то другой, то из способа построения следует, что его кодовое слово будет более чем однобитным. Следовательно, если какое-то кодовое слово получится однобитным, то соответствующая ему частота оставалась в списке неизменной до окончания процесса. Рассмотрим предпоследний шаг, когда частот было три, и частота $%q_1$% ни с чем не объединялась, а суммировались $%q_2\le q_1$% и $%q_3\le q_1$%. Тогда получится, что сумма частот меньше единицы, так как $%q_1+q_2+q_3\le3q_1 < 1$%. Но этого быть не может.

ссылка

отвечен 9 Ноя '15 18:58

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×313
×177
×146
×87
×49

задан
9 Ноя '15 18:04

показан
1341 раз

обновлен
9 Ноя '15 18:58

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru