Сжатие данных — процесс уменьшения объема данных, необходимых для хранения или передачи определенного фрагмента информации, обычно с помощью методов кодирования. Сжатие данных появилось еще до появления цифровых технологий: оно использовалось в азбуке Морзе, которая присваивала самые короткие коды наиболее распространенным символам, и в телефонии, которая отсекала высокие частоты при передаче голоса. Сегодня, когда цифровое изображение без сжатия может занимать 20 мегабайт, сжатие данных играет важную роль при хранении информации в цифровом виде на компьютерных дисках и при передаче ее по сетям связи.
В цифровом виде информация кодируется в виде набора 0 и 1, или битов (двоичных цифр). Для алфавита из четырех букв (a, e, r, t) потребовалось бы два бита на символ, если бы все символы были одинаково вероятны. Таким образом, все буквы в предложении «Крыса съела пирожное за чаем» можно закодировать с помощью 2 × 18 = 36 битов. Поскольку в этом тексте чаще всего встречается буква a, а второй по частоте — буква t, то при назначении двоичного кода переменной длины — a: 0, t: 10, r: 110, e: 111 — сжатое сообщение будет состоять всего из 32 бит. Это кодирование обладает тем важным свойством, что ни один код не является префиксом другого. То есть для разделения кодов букв не требуется дополнительных битов: 010111 однозначно расшифровывается как ate.
Сжатие данных может быть без потерь (точным) или с потерями (неточным). Сжатие без потерь можно изменить на обратное, чтобы получить исходные данные, в то время как при сжатии с потерями теряются детали или появляются небольшие ошибки при обратном изменении. Сжатие без потерь необходимо для текста, где важен каждый символ, в то время как сжатие с потерями может быть приемлемым для изображений или голоса (ограничение частотного спектра в телефонии является примером сжатия с потерями). Три наиболее распространенные программы сжатия общих данных — Zip (на компьютерах с операционной системой Windows), StuffIt (на компьютерах Apple) и gzip (на компьютерах под управлением UNIX); все они используют сжатие без потерь. Распространенным форматом для сжатия статичных изображений, особенно для показа через Интернет, является GIF (формат обмена графикой), который также сжимается без потерь, за исключением того, что изображения в нем ограничены 256 цветами. Более широкий диапазон цветов можно использовать в стандарте форматирования JPEG (Joint Photographic Experts Group), который использует как методы сжатия без потерь, так и методы сжатия с потерями, как и различные стандарты MPEG (Moving Picture Expert Group) для видео.
Чтобы программы сжатия работали, они должны иметь модель данных, которая описывает распределение символов, слов или других элементов, например, частоту встречаемости отдельных символов в английском языке. Фиксированные модели, такие как простой пример четырехсимвольного алфавита, приведенный выше, могут не очень хорошо характеризовать отдельный текст, особенно если он содержит табличные данные или использует специализированную лексику. В этих случаях адаптивные модели, полученные из самого текста, могут оказаться лучше. Адаптивные модели оценивают распределение символов или слов на основе того, что они уже обработали. Важным свойством адаптивного моделирования является то, что если программы сжатия и распаковки используют одни и те же правила формирования модели и одну и ту же таблицу кодов, которые они присваивают ее элементам, то саму модель не нужно передавать программе распаковки. Например, если программа сжатия присваивает следующий доступный код элементу the, когда он встречается в третий раз, то программа декомпрессии будет следовать тому же правилу и ожидать этот код для элемента the после его второго появления.
Кодирование может работать как с отдельными символами, так и со словами. Коды Хаффмана используют статическую модель и строят коды, подобные тем, что были проиллюстрированы ранее на примере четырехбуквенного алфавита. Арифметическое кодирование кодирует строки символов как диапазоны вещественных чисел и позволяет получить более близкие к оптимальным коды. Оно медленнее, чем кодирование Хаффмана, но подходит для адаптивных моделей. Кодирование по длине строки (RLE) хорошо подходит для повторяющихся данных, заменяя их подсчетом и одной копией повторяющегося элемента. Методы адаптивного словаря строят таблицу строк, а затем заменяют их более короткими кодами. Алгоритм Лемпеля-Зива, изобретенный израильскими компьютерщиками Абрахамом Лемпелем и Якобом Зивом, использует в качестве словаря сам текст, заменяя последующие вхождения строки числами, указывающими, где она встречалась ранее, и ее длину. В Zip и gzip используются разновидности алгоритма Лемпеля-Зива.
Сжатие с потерями расширяет эти методы за счет удаления деталей. В частности, цифровые изображения состоят из пикселей, которые представляют полутоновую или цветовую информацию. Если пиксель незначительно отличается от соседних, его значение может быть заменено их значением, после чего «сглаженное» изображение может быть сжато с помощью RLE. Если сглаживание большого участка изображения будет бросаться в глаза, то при распределении на небольшие разрозненные участки изменения будут гораздо менее заметны. Наиболее распространенный метод использует дискретное косинусное преобразование — математическую формулу, связанную с преобразованием Фурье, которая разбивает изображение на отдельные части с разной степенью важности для качества изображения. Эта техника, а также фрактальные методы позволяют достичь превосходных коэффициентов сжатия. Если эффективность сжатия без потерь оценивается по степени сжатия, то сжатие с потерями оценивается по вносимой им ошибке. Существуют математические методы расчета погрешности, но мера погрешности также зависит от того, как будут использоваться данные: например, отбрасывание высокочастотных тонов приводит к незначительным потерям при записи устной речи, но к неприемлемому ухудшению качества музыки.
Видеоизображения можно сжимать, сохраняя лишь незначительные различия между последовательными кадрами. MPEG-1 широко используется для сжатия видео для CD-ROM; он также лежит в основе формата MP3, используемого для сжатия музыки. MPEG-2 — это формат более высокого «вещательного» качества, используемый для DVD (см. компакт-диск: DVD) и некоторых телевизионных сетевых устройств. MPEG-4 предназначен для приложений с низкой пропускной способностью и используется для трансляции видео через Всемирную паутину (WWW). (MPEG-3 был включен в состав MPEG-2.) Сжатие видео позволяет достичь коэффициента сжатия, приближающегося к 20 к 1, с минимальными искажениями.
Существует компромисс между временем и памятью, которые требуются алгоритмам сжатия, и степенью сжатия, которую они достигают. Английский текст обычно можно сжать до половины или трети от его первоначального размера. Изображения часто можно сжать в 10-20 и более раз. Несмотря на рост объема памяти компьютеров и скорости сетей, сжатие данных остается важным инструментом для хранения и передачи все больших массивов данных. См. также теория информации: Сжатие данных; телекоммуникации: Кодирование источника.
