РусҚаз

Количество информации и сжатие

Информатика · 5 класс · Информация · Урок 4 из 4

Открыть интерактивный урок ›Опыт своими руками, лекция голосом, ИИ-наставник и тест. Бесплатно.

Что это

Вспомни игру «угадай число»: хороший вопрос сразу отсекает половину вариантов. Ответ «да» или «нет», когда оба одинаково вероятны, несёт ровно один бит информации. А сжатие — это умение записать то же самое меньшим числом бит, как короткие сокращения в записке другу.

Двое детей сидят на ковре друг напротив друга, один загадал число и улыбается, другой задумчиво подпирает подбородок.

Зачем это нужно

Без сжатия не было бы видеосвязи, музыки в телефоне и снимков, которые космические аппараты присылают с других планет. Дата-центры, где обучают и запускают ИИ, тратят огромные деньги на хранение и передачу данных, и каждый сэкономленный бит там на счету. ИИ умеет сжимать, но решать, где можно выбросить детали, а где нельзя терять ни бита, как в тексте программы или банковской выписке, должен человек. Кто понимает, сколько информации в сообщении, тот проектирует связь, хранилища и форматы будущего.

Девушка в наушниках смотрит видеозвонок на ноутбуке в поезде, за окном мелькают поля.

Как это работает

Чтобы угадать число от одного до шестидесяти четырёх, достаточно шести вопросов, если каждый раз делить оставшиеся числа ровно пополам. Сжатие держится на частоте: частым символам дают короткие коды, редким — длинные; так устроен код Хаффмана, а в азбуке Морзе частая буква Е — всего одна точка. При этом ни один код не должен быть началом другого, иначе текст не расшифруешь однозначно — это условие Фано. Клод Шеннон доказал, что чем предсказуемее текст, тем сильнее его можно сжать. Архивы ЗИП и картинки ПНГ сжимают без потерь, а музыка МП3, фото ДЖЕЙПЕГ и видео — с потерями: выбрасывают то, чего ухо и глаз почти не замечают.

Почтальон аккуратно складывает и утрамбовывает вещи в маленькую посылочную коробку, чтобы всё поместилось.

Немного истории

Код Хаффмана придумал студент Дэвид Хаффман в начале пятидесятых годов. Преподаватель предложил группе выбор: сдать экзамен или написать работу о самом выгодном двоичном коде. Хаффман долго бился над задачей, уже почти сдался и собирался готовиться к экзамену, как вдруг нашёл простой способ, который оказался лучше методов самого преподавателя.

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

Формула: количество информации

Каждый вопрос с ответом «да» или «нет» делит варианты пополам. Значит, после одного вопроса различаем два варианта, после двух — четыре, после и вопросов — два в степени и. Отсюда формула Хартли: эн равно два в степени и, или иначе и равно логарифм по основанию два от эн. Здесь эн — число равновероятных вариантов, а и — количество информации в битах, то есть сколько вопросов нужно. Если эн не степень двойки, логарифм получается дробным, и вопросов берут с запасом, округляя вверх: для ста чисел нужно семь вопросов. Увеличишь число вариантов вдвое — понадобится всего один лишний вопрос.

  • N = 2ᴵN — число равновероятных вариантов, —
    I — количество информации, бит
  • I = log₂NI — количество информации (число вопросов), бит
    N — число вариантов, —

Формула: объём сообщения

Если каждый символ записан кодом одной длины, объём всего сообщения считается просто: и большое равно ка умножить на и маленькое. Здесь ка — число символов в сообщении, и маленькое — сколько бит уходит на один символ, а и большое — объём сообщения в битах. Сколько бит нужно на символ, решает алфавит: для пяти букв хватает трёх бит, потому что два в кубе — восемь, это не меньше пяти, а для тридцати двух букв нужно пять бит. Удлинишь сообщение вдвое — объём вырастет вдвое; сократишь коды частых букв — объём уменьшится, на этом и держится сжатие.

  • I = K · iI — объём сообщения, бит
    K — число символов, —
    i — бит на один символ, бит

Что будем делать на практике

А теперь давай попробуем выполнить практическое задание. В первой части ведущий загадал число от одного до шестидесяти четырёх, а ты нажимаешь число ка — это вопрос «больше ка?». Ведущий хитрый: из двух ответов он выберет тот, после которого чисел останется больше, поэтому каждый раз думай, сколько чисел останется при «да» и при «нет», и старайся делить ровно пополам. Во второй части сожми строку «ОКОЛО_КОЛОКОЛА»: сейчас у каждой буквы код из трёх бит, и выходит сорок два бита, а надо уложиться в тридцать. Посчитай, какая буква встречается чаще всего, и меняй длины кодов, а программа сама построит префиксный код и пересчитает объём. Если что-то осталось непонятным — ничего страшного, спроси меня о чём угодно, я отвечу. Не переживай.

Задание в опыте

Угадайте число от 1 до 64 за наименьшее число вопросов, а затем сожмите строку ОКОЛО_КОЛОКОЛА до 30 бит или меньше.
Открыть интерактивный урок ›Опыт своими руками, лекция голосом, ИИ-наставник и тест. Бесплатно.

Уроки темы: Информация

  1. Что такое информация
  2. Кодирование: азбука Морзе
  3. Биты и байты
  4. Количество информации и сжатие