§ 3. Сжатие данных

Определения и обозначения

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

Коэффициент сжатия — отношение объёма исходных данных к объёму после сжатия: K = Vисх / Vсж. Например, файл 1200 Кбайт, ставший 800 Кбайт, имеет коэффициент 1,5. Чем он больше единицы, тем сильнее уменьшился файл; при сравнении нужно использовать одинаковые единицы измерения.

Сжатие без потерь — способ уменьшения объёма, при котором исходные данные можно восстановить полностью и без изменений. Оно необходимо там, где важен каждый символ или бит, например в документах и программах. После распаковки результат должен совпадать с исходным файлом.

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

Как это устроено

Сжатие становится возможным, если данные избыточны: в них повторяются фрагменты или проявляются закономерности. Вместо многократной записи одного и того же алгоритм может сохранить короткое описание повтора. Это не всегда работает одинаково хорошо: случайные данные трудно описать короче, потому что в них почти нет регулярностей.

При сжатии без потерь одинаковые подряд идущие символы можно заменить указанием символа и длины серии. Например, вместо длинной цепочки букв записывают, сколько раз повторяется одна буква, а при распаковке разворачивают описание обратно. Если сама цепочка короткая, такая запись может оказаться невыгодной из-за дополнительных обозначений.

Другой приём без потерь — назначать часто встречающимся символам более короткие коды, а редким более длинные. Средняя длина записи уменьшается, потому что короткий код используется чаще. Чтобы правильно прочитать поток битов, алгоритм должен однозначно определять границы кодов и знать таблицу соответствий.

Словарные методы находят фрагмент, который уже встречался, и вместо повторной записи сохраняют ссылку на него. Например, если слово или последовательность символов повторяется много раз, достаточно один раз записать её полностью, а затем обращаться к сохранённому фрагменту. Экономия растёт, когда повторов много, но для восстановления декодеру нужны словарь или правила его построения.

При сжатии с потерями удаляют детали, менее заметные человеку или менее важные для восприятия. В изображении можно упростить цветовые переходы, а в звуке — убрать часть компонентов, которые маскируются более громкими. Чем сильнее упрощение, тем меньше файл, но тем выше риск заметного ухудшения качества.

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

Сравнение способов сжатия данных

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

Разбор задач

Коэффициент и процент уменьшения

Исходный файл занимает 1200 Кбайт, после сжатия — 800 Кбайт. Нужно найти коэффициент сжатия и процент уменьшения относительно исходного объёма. Сначала сравним объёмы, затем вычислим, какую долю исходного размера удалось убрать.

1. Коэффициент равен отношению исходного объёма к сжатому: K = 1200 / 800 = 1,5.
2. Находим разницу объёмов: 1200 − 800 = 400 Кбайт.
3. Делим разницу на исходный размер и переводим долю в проценты: 400 / 1200 × 100% ≈ 33,3%.

Проверка показывает, что сжатый файл составляет две трети исходного размера, а удалённая часть — примерно треть. Коэффициент 1,5 не означает уменьшение на 50 процентов: он показывает, во сколько раз исходный файл больше сжатого. Ответ: коэффициент сжатия равен 1,5, объём уменьшился примерно на 33,3%.

Кодирование серии

Строка состоит из 30 одинаковых подряд идущих символов. Представим её короче записью длины серии и самого символа, например «30А». Сравним количество знаков, считая, что исходный символ и цифры занимают по одному знаку.

1. Исходная запись содержит 30 символов.
2. В сокращённой записи указываем число 30 и один символ: это 2 цифры и 1 буква, всего 3 знака.
3. Экономия составляет 30 − 3 = 27 знаков, или 27 / 30 × 100% = 90%.

При распаковке число сообщает, сколько раз нужно повторить символ. Для точного сравнения реальных файлов учитывают не знаки на бумаге, а способ их кодирования и служебные данные. Ответ: строку можно записать как «30А», сократив условную запись с 30 до 3 знаков.

Выбор способа для документов и изображения

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

1. Для архива выбираем сжатие без потерь, чтобы после распаковки получить исходные документы без изменений.
2. Для публикации выбираем сжатие с потерями, если допустимо некоторое ухудшение изображения.
3. Проверяем результат визуально и при необходимости уменьшаем степень сжатия, чтобы сохранить приемлемое качество.

Один и тот же выбор не подходит всем задачам: требования определяет ценность точного восстановления и условия использования файла. Если изображение нужно для печати или дальнейшей обработки, потеря качества может быть нежелательной. Ответ: документы архивируем без потерь, а для веб-публикации изображения можно применить сжатие с потерями при контроле результата.

Типичные ошибки

Иногда коэффициент сжатия считают как Vсж / Vисх. Так можно получить число меньше единицы, хотя в школьных задачах обычно используют обратное отношение, чтобы результат эффективного сжатия был больше единицы. Проверьте себя: подставьте исходный объём первым и убедитесь, что он больше сжатого.

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

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

Нельзя рассчитывать, что после сжатия с потерями удастся получить оригинал. Если информация уже отброшена, распаковка лишь создаст приближённый результат, а не вернёт удалённые детали. Перед выбором метода спросите себя, требуется ли точная копия; если да, выбирайте сжатие без потерь.

Связь с другими темами

Чтобы изучать сжатие, нужно уметь измерять объём данных и понимать, как символы кодируются последовательностями битов. Тогда можно сравнивать размер файла до и после обработки, а также оценивать, сколько места занимает запись. Эти знания связывают тему с кодированием информации и системами единиц измерения.

Сжатие применяют при хранении и передаче файлов, а также при обработке изображений, звука и видео. Оно влияет на размер архивов, скорость загрузки и требования к качеству медиа. Поэтому выбор способа связан с задачами компьютерных сетей, мультимедиа и организации хранения данных.

Что запомнить

• Сжатие уменьшает объём данных за счёт выявления и устранения избыточности.
• При сжатии без потерь исходные данные восстанавливаются точно.
• При сжатии с потерями точное восстановление невозможно.
• Коэффициент сжатия обычно вычисляют как отношение исходного объёма к сжатому.
• Эффективность сжатия зависит от вида данных и выбранного метода.
• Сжатие с потерями оправдано, когда допустимо некоторое ухудшение качества.