Зачем на ЕГЭ нужен раздел «Сжатие данных»
Сжатие данных — фокусная тема, без которой не решить сразу несколько заданий профильного экзамена. Авторы КИМ-ов проверяют здесь умение переводить информацию из символов в двоичный код, выбирать оптимальную систему кодирования и оценивать экономию памяти. Звучит объёмно, но на практике алгоритмы просты, если их разобрать по шагам. Выпускник, уверенно владеющий этой темой, получает быстрые и почти бесплатные баллы: задачи редко изменяются по структуре, а подсчёты опираются на две-три стандартные формулы.
Кроме прямой пользы для ЕГЭ, навык помогает понимать, как хранятся файлы в телефоне или почему одна фотография «весит» меньше другой при той же чёткости. Школьники, осознавшие связь между теорией и повседневной практикой, запоминают тему глубже и тратят меньше времени на повторение.
Ключевые термины: бит, байт и кодовое слово
Прежде чем решать задачи, стоит уточнить базовые единицы. Бит — минимальная порция памяти, принимающая значение 0 или 1. Восемь бит образуют байт. На ЕГЭ почти всегда спрашивают объёмы в байтах, но расчёт идёт в битах, поэтому нужно помнить шаг обратного перевода: делим результат на восемь.
Кодовое слово — двоичная цепочка, соответствующая одному символу исходного алфавита. Если алфавит содержит N различных символов и каждое слово фиксированной длины L, то общий объём равен N · L бит. Отсюда быстро выводится минимальная L: она должна удовлетворять неравенству 2L ≥ N.
В заданиях иногда встречается термин «избыточность». Он показывает, сколько лишних бит тратится по сравнению с теоретическим минимумом. Для экзамена достаточно формулы: избыточность = фактический объём − оптимальный объём.
Формула Шеннона и оценка минимального объёма
Когда символы алфавита встречаются неравновероятно, фиксированная длина слова станет невыгодной. Здесь вступает в игру энтропия Шеннона. Формула H = −Σ pi log₂ pi даёт нижнюю границу средней длины кодового слова. Например, если символ «А» появляется в тексте с вероятностью 0,5, а «Б», «В» и «Г» — по 0,166…, энтропия приблизится к 1,5 бита.
На самом экзамене редко требуют вычислять логарифмы вручную, но понимание помогает оценивать, можно ли сжать текст сильнее. Зная H, легко получить теоретический минимум объёма: Umin = H · K, где K — количество символов в сообщении.
Если реальный объём близок к этому пределу, значит выбранный алгоритм близок к идеалу. В противном случае стоит применить переменную длину кодов.
Кодирование без потерь: алгоритм Хаффмана
Самый популярный метод переменной длины на ЕГЭ — алгоритм Хаффмана. Он строит оптимальное префиксное дерево, где пути к частым символам короче. Посчитаем простой случай: сообщение состоит из букв «А» (50 %), «Б» (25 %), «В» (15 %), «Г» (10 %). Дерево даёт код 0 для «А», 10 для «Б», 110 для «В» и 111 для «Г». Средняя длина слова: 0,5 · 1 + 0,25 · 2 + 0,15 · 3 + 0,1 · 3 = 1,75 бита. Это почти совпадает с энтропией 1,74, а значит близко к пределу Шеннона.
Чтобы экзаменуемый не строил полное дерево, задание часто приводит уже готовую таблицу символ ↔ код. Школьнику остаётся лишь умножить длины кодов на количество повторений и суммировать результат. Важно всегда проверять, является ли код префиксным: ни одно слово не должно быть началом другого. Если правило нарушено, декодирование станет неоднозначным, а ответ задачи изменится.
Практика задания 5: считайте биты правильно
Задание 5 профильного экзамена просит найти объём закодированного сообщения. Алгоритм действий удобен в виде короткого списка:
- Определите, сколько раз встречается каждый символ. Частоты либо даны, либо выводятся из контекста.
- Запишите длину кодового слова для каждого символа.
- Умножьте длину на частоту, сложите результаты и получите число бит.
- Переведите биты в байты, разделив на восемь и округлив вверх, если требуют целое число байт.
Главная ловушка — невнимательность к единицам. Иногда условие сразу просит ответ в килобайтах, а школьник машинально оставляет биты. Потерянный балл обиден, ведь арифметика уже сделана.
Сжатие данных и таблицы словарного типа
Помимо кодов переменной длины, экзамен проверяет словарные методы. Самый известный — LZW, упрощённая версия которого встречается под названием «таблица фраз». Сущность проста: сообщения анализируются слева направо, и каждый новый фрагмент добавляется в словарь. Затем вместо самой фразы хранится индекс.
Для решения нужно уметь:
- Восстановить словарь по порядку появления цепочек.
- Определить, сколько бит выделено под один индекс: L должен удовлетворять 2L ≥ M, где M — размер текущего словаря.
- Посчитать общий объём как сумму L · k по всем записям.
Часто экзаменаторы добавляют контрольный вопрос: «Во сколько раз исходный текст длиннее получившегося архива?». Делим начальный объём на итоговый и получаем коэффициент сжатия.
Типичные ошибки выпускников и как их избежать
Первая ошибка — смешение битов и байтов. Решение: всегда выписывайте размерность рядом с числом. Вторая — игнорирование кодовых слов длиной ноль в таблице. Если такая строка появилась, значит условие неполно. Третья — неправильное округление. Если нужно минимальное целое число байт, округляем вверх, даже если остаток равен единице.
Четвёртая ошибка связана с копированием чужих алгоритмов без понимания. Студент применяет схему Хаффмана, хотя код уже оптимален. Время потеряно, хотя можно было обойтись простой формулой N · L.
Пятая — забытый символ новой строки. В текстах, содержащих служебные знаки, каждый из них тоже кодируется. Пропуск меняет итог сразу на несколько байт и лишает балла.
Стратегия подготовки за неделю до экзамена
За семь дней не стоит изучать новые теории. Лучше закрепить уже знакомые схемы. Распределите время так:
- День 1–2: прорешайте пять вариантов задания 5 и разберите каждую ошибку.
- День 3–4: потренируйтесь на задачах с алгоритмом Хаффмана, выделяя частоты вручную.
- День 5: повторите словарные методы и запомните границу 2L ≥ M.
- День 6: составьте шпаргалку единиц измерения, от бита до гигабайта.
- День 7: решите один полный вариант и проверьте себя по критериям ФИПИ.
В день перед экзаменом важно спать не меньше семи часов. Свежая голова ускорит вычисления и снизит вероятность описки при переводе битов.