Код Хаффмана и условие Фано

11 класс, углублённый уровень. Обзорный практикум ко второй паре: шесть задач по содержанию темы.

Что нужно сделать
Шесть задач — по одной на каждый вопрос темы, и все сразу на странице: решай в любом порядке. Ответил верно — вопрос закрыт. Ошибся — сразу видно, как это решается, а вопрос остаётся открытым: кнопка «Новые числа» даёт ту же задачу с другими данными, и её можно сдать ещё раз. Сколько закрыл, столько и наработал. Времени нужно около десяти минут.
Отметка и добор
Закрыто 6 из 6 — «5», 5 — «4», 3 или 4 — «3». Кнопка «Получить код» внизу страницы появляется, как только закрыто три вопроса: можно забрать код сразу, а можно дорешать оставшиеся и получить код получше — решать самому, до какой отметки добирать.
Ответ — целое число
Без единиц измерения и без пробелов: 34, а не 34 бита. На КЕГЭ ответ читает машина, и здесь так же.
Как сдать
В конце появится код работы и кнопка «Сдать работу»: впишешь код ученика, кнопка сама откроет форму с уже вписанным кодом. Переписывать код руками не надо — на этом чаще всего и ошибаются.
Не успел на уроке
Открой эту же страницу дома и пройди целиком: вариант будет другой, а сдаётся всё так же — одним кодом.

Вопросы темы

наработано на—

Подсказка: код Хаффмана и условие Фано

Равномерный код

На n различных букв нужно по log₂n битов, округлённым вверх: на 5 букв — 3 бита, потому что 2² = 4 мало, а 2³ = 8 хватает. Запас неиспользованных слов — 8 − 5 = 3.

Код Хаффмана: как строится

  1. выписать частоты букв;
  2. взять две наименьшие и слить в один узел — его вес равен их сумме;
  3. повторять, пока не останется один узел;
  4. длина всего сообщения = сумма весов всех слияний.

При совпадающих весах дерево можно построить по-разному, и коды отдельных букв получатся разными, — а сумма нет. Поэтому спрашивают именно её, а не «какой код у буквы Б».

Условие Фано

Ни одно кодовое слово не должно быть началом другого. Тогда поток читается однозначно, слева направо, и разделители не нужны.

0, 10, 110 — годится. 0, 01 — нет: 0 есть начало 01.

Декодирование

Читать слева направо, накапливая биты, пока накопленное не совпадёт с кодовым словом; совпало — записать букву и начать заново. Возвращаться назад не приходится — за это и отвечает условие Фано.

Выигрыш против равномерного кода

K · (log₂n вверх) − (сумма слияний), где K — длина сообщения в буквах. Если частоты букв близки, дерево выходит ровным и выигрыша нет вовсе: Хаффман помогает там, где буквы встречаются по-разному часто.

Материалы подготовлены с использованием технологий искусственного интеллекта.