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

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

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

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

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

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

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

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

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

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

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

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

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

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

Разбор задач

Задача 1

Файл объёмом 240 Кбайт после сжатия занимает 120 Кбайт. Требуется найти коэффициент сжатия. Оба объёма уже выражены в одинаковых единицах, поэтому дополнительно переводить их не нужно.

1. Запишем формулу: K = Vисх / Vсж.
2. Подставим значения: K = 240 / 120.
3. Выполним деление: K = 2.

Ответ: коэффициент сжатия равен 2. Это означает, что исходный файл был в два раза больше сжатого.

Задача 2

В строке ААААББВВВВ одинаковые символы, идущие подряд, заменяют символом и числом повторений. Нужно записать получившееся представление и проверить возможность восстановления. Каждая серия обрабатывается отдельно, потому что между сериями стоят другие символы.

1. Четыре символа А записываем как А4.
2. Два символа Б записываем как Б2.
3. Четыре символа В записываем как В4.
4. Соединяем записи в прежнем порядке: А4Б2В4.

Ответ: А4Б2В4. Строка восстановится точно, если правило означает число повторений каждого символа, поэтому это пример сжатия без потерь.

Задача 3

Изображение объёмом 8 Мбайт сжали до 1,6 Мбайт. Нужно найти коэффициент и процент уменьшения, а затем выяснить, можно ли по размерам определить вид сжатия. Размеры даны в одинаковых единицах, поэтому их можно сразу сравнивать.

1. Коэффициент: K = 8 / 1,6 = 5.
2. Уменьшившийся объём равен 8 − 1,6 = 6,4 Мбайт.
3. Доля уменьшения: 6,4 / 8 · 100% = 80%.
4. Размер стал равен 20% исходного, потому что 100% − 80% = 20%.

Ответ: коэффициент сжатия равен 5, объём уменьшился на 80%. По одним размерам нельзя установить, было ли сжатие без потерь: для этого нужно знать, восстановилось ли исходное изображение полностью.

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

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

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

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

Ожидать восстановления качества после сжатия с потерями. Распаковка возвращает закодированный результат, а не удалённые сведения. Проверьте вид сжатия: если часть информации была отброшена, прежнее качество вернуть нельзя.

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

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

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

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

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

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