§ 3. Сжатие данных ГДЗ по Информатике 11 класс. Углубленный уровень. В 2 ч. Поляков К.Ю.
3. Текстовый файл, записанный в однобайтной кодировке, содержит только 33 заглавные русские буквы, цифры и пробел. Ответьте на следующие вопросы:
• какое минимальное число битов нужно выделить на символ при передаче, если каждый символ кодируется одинаковым числом битов?
• сколько при этом будет занимать заголовок пакета данных?
• при какой минимальной длине текста коэффициент сжатия будет больше 1?
Ответ
Для решения задачи определим, сколько битов необходимо для кодирования символов, сколько будет занимать заголовок пакета данных и минимальную длину текста, при которой коэффициент сжатия будет больше 1.
1. Минимальное число битов на символ:
Для кодирования символов необходимо учитывать количество уникальных символов, которые нужно закодировать. У нас есть 33 заглавные русские буквы, 10 цифр и пробел, итого:
33+10+1=44 символа
Чтобы закодировать 44 символа, нам нужно log2(44) бит:
log2(44)≈5.46
Так как каждый символ должен быть представлен целым числом бит, округляем до ближайшего большего целого числа: 6 бита на символ
2. Размер заголовка пакета данных:
Заголовок пакета данных может включать в себя информацию о:
- Длине сообщения
- Кодировке
- Контрольных данных для проверки ошибок
Размер заголовка пакета данных зависит от протокола передачи. В отсутствие конкретного протокола предположим, что заголовок содержит базовую информацию:
- Длина сообщения: если размер сообщения может достигать 2^16 символов, то для длины потребуется 16 бит (2 байта).
- Кодировка и контрольная информация: например, еще 1 байт.
Итого: 16 бит (длина)+8 бит (кодировка и контрольная информация)=24 бита=3 байта
3. Минимальная длина текста для коэффициента сжатия больше 1:
Коэффициент сжатия определяется как:
Коэффициент сжатия = Исходный размер / Сжатый размер
Исходный размер текста в однобайтной кодировке:
n символов×8 бит/символ
Сжатый размер текста в 6-битной кодировке:
n символов×6 бит/символ+размер заголовка
Для коэффициента сжатия больше 1:
Решим это неравенство:
- Умножим обе стороны на n×6+24n: 8n>6n+24
- Перенесем 6n влево: 2n>24
- Разделим обе стороны на 2: n>12
Таким образом, минимальная длина текста должна быть больше 12 символов, чтобы коэффициент сжатия был больше 1.
Итоги:
- Минимальное число битов на символ: 6 бит.
- Размер заголовка пакета данных: 3 байта.
- Минимальная длина текста для коэффициента сжатия больше 1: больше 12 символов.