Количество информации и сжатие данных
Как измерить информацию в битах — и как сделать файл меньше. 11 класс, углублённый уровень — пара первая.
Уроки 1–2 поурочного плана: «Количество информации» и «Алгоритмы сжатия данных». Всё, что здесь есть, понадобится весь год: в задачах ЕГЭ на объём рисунка, звука и текста, на коды и пароли считают теми же формулами.
Бит — ответ на вопрос «да или нет»
Загадано число от 1 до 8. Сколько вопросов «да/нет» нужно, чтобы его точно узнать?
Каждый вопрос «больше четырёх?» отбрасывает половину вариантов:
Это алфавитный взгляд: считаем, сколько двоичных знаков нужно на выбор. Смысл сообщения в счёт не идёт.
Формула Хартли
N — сколько равновероятных вариантов, i — сколько бит несёт сообщение о том, какой выпал.
Степени двойки надо знать наизусть — по этой таблице решается больше половины задач:
Знаем N — ищем i
32 варианта: 32 = 25, значит 5 бит.Знаем i — ищем N
6 бит: 26 = 64 варианта.Закон аддитивности
Выбрали одну из 8 букв, потом — одну из 4 цифр. Сколько бит в сообщении о полном результате?
Проверка по Хартли: 8 · 4 = 32 = 25, и 3 + 2 = 5. Сходится — так и должно быть, ведь 23 · 22 = 23+2.
Информационный объём сообщения
K — сколько символов в сообщении, i — сколько бит весит один символ. Вес символа берём из мощности алфавита по Хартли: N = 2i.
Алфавит из 32 символов, сообщение из 40 символов:
| 1 байт | 8 бит |
|---|---|
| 1 Кбайт | 1024 байта |
| 1 Мбайт | 1024 Кбайт |
Вероятность и количество информации
Если варианты не равновероятны, информация зависит от вероятности события p:
В ящике 16 шаров, белых — 2. Достали белый: p = 2/16 = 1/8.
Формула Хартли — частный случай: у N равновероятных вариантов p = 1/N, и log2N = i.
Зачем сжимать и как
Сжатие — запись тех же данных меньшим числом бит: файл быстрее передаётся и меньше места занимает.
Без потерь
Распакованный файл совпадает с исходным бит в бит. Так сжимают тексты, программы, таблицы: там нельзя потерять ни одного знака.С потерями
Выбрасывается то, чего человек не заметит: мелкие оттенки, неслышные звуки. Файл намного меньше, но выброшенное не вернуть. Так сжимают фото, звук, видео.RLE — сжатие серий
Подряд идущие одинаковые символы — серия. Каждую серию заменяем парой «сколько, что».
Каждая серия даёт два символа записи, сколько бы в ней ни было букв. Длина записи = число серий · 2.
Кто сжимает с потерями
| без потерь | RLE, алгоритм Хаффмана, LZW, ZIP, PNG, GIF |
|---|---|
| с потерями | JPEG, MP3, AAC, MPEG-4 (видео), уменьшение глубины кодирования цвета |
Подсказка для памяти: фото, звук и видео «для человека» — почти всегда с потерями. Архивы и картинки-схемы (PNG, GIF) — без потерь.
Хаффман и LZW разберём на следующих парах — это тоже сжатие без потерь.
Что делаем дальше
- Обзорный практикум — шесть задач, все сразу на странице, в любом порядке: формула Хартли, закон аддитивности, объём сообщения, вероятность, RLE, с потерями или без.
- Таблицу степеней двойки держи перед глазами — она на карточке в тетрадь.
- Ответ везде — целое число, без единиц:
, а не «34 бита».
Ошибся — сразу виден разбор, а «Новые числа» дают ту же задачу с другими данными. Отметка: закрыто 6 из 6 — «5», 5 — «4», 3 или 4 — «3».
За работу
Практикум «Количество информации и сжатие данных» — в общей папке и на сайте. Не успел на уроке — пройди дома: вариант будет другой, сдаётся тем же кодом.
Карточку в тетрадь можно взять с собой: на ней формула Хартли с таблицей степеней двойки, объём сообщения, вероятность, RLE и список «с потерями и без».