"Привести пример частот при кодировке 5 символов, при которой длина всех кодов будет больше 1"

Частота это сколько раз встречается буква в тексте. Я вообще не понял вопрос.

задан 8 Янв 22:12

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

Имеется в виду следующий "сюжет". Представим себе, что у нас имеется какой-нибудь файл, в котором с разной частотой могут встречаться те или иные символы. Пусть их всего имеется $%n$%. Можно рассмотреть случай $%n=256$%. Если каждый символ закодировать в виде 8-битного двоичного слова, файл всегда можно однозначно декодировать. Однако те или иные символы могут встречаться чаще или реже других. Тогда выгодно было бы "редкие" символы закодировать длинными словами (двоичными), а те, которые встречаются чаще -- более короткими. Точная постановка задачи такая.

Даны положительные числа $%p_1,\ldots,p_n$%, сумма которых равна 1. Это частоты символов; они как бы даны нам "сверху". Например, при чтении файла мы можем составить частотный словарик, и эти числа узнать. Требуется построить однозначно декодируемый двоичный код, у которого длины кодовых слов равны $%l_1,\ldots,l_n$% соответственно. При этом требуется, чтобы средняя длина кодового слова, то есть величина $%p_1l_1+\cdots+p_nl_n$%, была минимально возможной.

Общее решение этой задачи излагается в учебниках по дискретной математике -- см., например, книгу С.В.Яблонского (раздел про коды с минимальной избыточностью, или коды Хаффмана).

Здесь требуется подобрать 5 таких чисел (частот), чтобы ни у какого кодового слова длина не оказалась равной 1. Этого добиться легко, если не брать "слишком больших" частот. Скажем, если один символ встречается с частотой 96%, а остальные четыре с частотой 1%, то становится ясно, что первый из них выгодно закодировать всего одним символом (например, 0), а остальные четыре -- кодовыми словами типа 100, 101, 110, 111 длины три.

Если же взять равные или примерно равные частоты -- например, 20% для каждого из символов, то по алгоритму Хаффмана будет построен код типа 000, 001, 01, 10, 11 с длинами кодовых слов 2 или 3. Он будет при этом однозначно декодируемым и оптимальным.

ссылка

отвечен 8 Янв 22:58

Про алгоритм Хаффмана я читал. просто не понимал условие задачи. Спасибо большое. Очень понятно объяснили.

(9 Янв 2:51) abaranci
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,065
×647

задан
8 Янв 22:12

показан
188 раз

обновлен
9 Янв 2:51

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

по почте:

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

по RSS:

Ответы

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

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