Что это
Вспомни игру «угадай число»: хороший вопрос сразу отсекает половину вариантов. Ответ «да» или «нет», когда оба одинаково вероятны, несёт ровно один бит информации. А сжатие — это умение записать то же самое меньшим числом бит, как короткие сокращения в записке другу.
Зачем это нужно
Без сжатия не было бы видеосвязи, музыки в телефоне и снимков, которые космические аппараты присылают с других планет. Дата-центры, где обучают и запускают ИИ, тратят огромные деньги на хранение и передачу данных, и каждый сэкономленный бит там на счету. ИИ умеет сжимать, но решать, где можно выбросить детали, а где нельзя терять ни бита, как в тексте программы или банковской выписке, должен человек. Кто понимает, сколько информации в сообщении, тот проектирует связь, хранилища и форматы будущего.
Как это работает
Чтобы угадать число от одного до шестидесяти четырёх, достаточно шести вопросов, если каждый раз делить оставшиеся числа ровно пополам. Сжатие держится на частоте: частым символам дают короткие коды, редким — длинные; так устроен код Хаффмана, а в азбуке Морзе частая буква Е — всего одна точка. При этом ни один код не должен быть началом другого, иначе текст не расшифруешь однозначно — это условие Фано. Клод Шеннон доказал, что чем предсказуемее текст, тем сильнее его можно сжать. Архивы ЗИП и картинки ПНГ сжимают без потерь, а музыка МП3, фото ДЖЕЙПЕГ и видео — с потерями: выбрасывают то, чего ухо и глаз почти не замечают.
Немного истории
Код Хаффмана придумал студент Дэвид Хаффман в начале пятидесятых годов. Преподаватель предложил группе выбор: сдать экзамен или написать работу о самом выгодном двоичном коде. Хаффман долго бился над задачей, уже почти сдался и собирался готовиться к экзамену, как вдруг нашёл простой способ, который оказался лучше методов самого преподавателя.
Формула: количество информации
Каждый вопрос с ответом «да» или «нет» делит варианты пополам. Значит, после одного вопроса различаем два варианта, после двух — четыре, после и вопросов — два в степени и. Отсюда формула Хартли: эн равно два в степени и, или иначе и равно логарифм по основанию два от эн. Здесь эн — число равновероятных вариантов, а и — количество информации в битах, то есть сколько вопросов нужно. Если эн не степень двойки, логарифм получается дробным, и вопросов берут с запасом, округляя вверх: для ста чисел нужно семь вопросов. Увеличишь число вариантов вдвое — понадобится всего один лишний вопрос.
N = 2ᴵN — число равновероятных вариантов, —
I — количество информации, битI = log₂NI — количество информации (число вопросов), бит
N — число вариантов, —
Формула: объём сообщения
Если каждый символ записан кодом одной длины, объём всего сообщения считается просто: и большое равно ка умножить на и маленькое. Здесь ка — число символов в сообщении, и маленькое — сколько бит уходит на один символ, а и большое — объём сообщения в битах. Сколько бит нужно на символ, решает алфавит: для пяти букв хватает трёх бит, потому что два в кубе — восемь, это не меньше пяти, а для тридцати двух букв нужно пять бит. Удлинишь сообщение вдвое — объём вырастет вдвое; сократишь коды частых букв — объём уменьшится, на этом и держится сжатие.
I = K · iI — объём сообщения, бит
K — число символов, —
i — бит на один символ, бит
Что будем делать на практике
А теперь давай попробуем выполнить практическое задание. В первой части ведущий загадал число от одного до шестидесяти четырёх, а ты нажимаешь число ка — это вопрос «больше ка?». Ведущий хитрый: из двух ответов он выберет тот, после которого чисел останется больше, поэтому каждый раз думай, сколько чисел останется при «да» и при «нет», и старайся делить ровно пополам. Во второй части сожми строку «ОКОЛО_КОЛОКОЛА»: сейчас у каждой буквы код из трёх бит, и выходит сорок два бита, а надо уложиться в тридцать. Посчитай, какая буква встречается чаще всего, и меняй длины кодов, а программа сама построит префиксный код и пересчитает объём. Если что-то осталось непонятным — ничего страшного, спроси меня о чём угодно, я отвечу. Не переживай.