Определение

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

До тех пор пока полоса пропускания сети будет дорогим ресурсом, а люди — нетерпеливыми, сжатие данных не утратит актуальности. Проще говоря, методы сжатия преобразуют данные — текст, графику, аудио или видео — в восстанавливаемый с помощью компьютера формат, при этом объем полученной «информации» составляет 10-99% от исходного. Данные занимают при хранении меньше места и при передаче по Internet требуют меньшей полосы пропускания. Кроме того, многие методы позволяют сжимать несколько файлов в один, называемый архивом.

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

«Сжатие с потерей данных — это компромисс. Точность приносится в жертву более сильному сжатию, — заметил Стив Хоффеберг, менеджер компании Sound Vision, работающей с цифровыми изображениями. — Если сжимаются банковские записи, должна быть гарантия того, что исходная информация и восстановленная будут идентичны. Но при работе с аудио- и видеофайлами, как правило, вовсе не обязательно восстанавливать каждый бит данных».

Сжатие без потери данных

Программы сжатия без потери данных ищут в документах избыточную или повторяющуюся информацию, а затем ее кодируют. Например, текстовый документ может содержать 200 пробелов, 100 экземпляров одного и того же слова и 50 обращений. Программа ищет эти повторяющиеся слова и пробелы и заменяет их на короткий шаблон или числовой символ — свой для каждого слова и хранящийся в «словаре».

После дешифровки файла шаблоны декодируются, и данные восстанавливаются. Никакая информация не теряется и не искажается.

Сейчас создано множество программ сжатия данных, например StuffIt (для компьютеров Macintosh) компании Aladdin Systems, WinZip (для Windows) компании WinZip Computing, PKZip, разработанный компанией PKWare. Причем PKZip — это самая популярная программа для сжатия данных в DOS и Windows.

Джим Петерсон из компании PKWare подчеркнул, что с распространением Internet сжатие данных будет приобретать все большую важность.

«Сжатие данных весьма актуально, поскольку платить приходится и за память, и за полосу пропускания», — отметил он. Типичные документы, такие как электронные таблицы Microsoft Excel или презентации PowerPoint, можно сжать примерно вполовину, а документы с большим числом повторов можно сжать примерно до 20% их исходного размера.

Сжатие с потерей данных

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

Еще одна тонкость, как отметил Карл Джерленд, аналитик компании Current Analysis, заключается в том, что соединения, основанные на медной проводке, не в состоянии достаточно хорошо работать с несжатыми аудио- и видеосигналами. «Последняя миля от коммутатора до дома потребителя или офиса компании обслуживается витой медной парой, и здесь, как правило, возникают серьезные ограничения на полосу пропускания, связанные с тем, что данные пересылаются на разных скоростях», — объяснил Джерленд.

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


Стандарты на сжатие

Joint Photographic Experts Group (JPEG): метод сжатия с потерей данных для статических изображений, который использует уравнения дискретного тригонометрического преобразования для сжатия изображений в несколько (до 20) раз без значительных искажений.

Lempel-Ziv-Welch: этот алгоритм, применяемый во многих форматах сжатия, в том числе в формате обмена графикой и Tag Image File Format, для каждой последовательности разрядов заданной длины создает запись в таблице поиска и код меньшего размера. Записи таблицы поиска составляют часть сжатого файла, и по ним программа декодирования воссоздает таблицу.

Moving Pictures Experts Group (MPEG): метод сжатия с потерей данных для видео. MPEG-1 используется для информации, размещаемой на компакт-дисках и видеодисках. MPEG-2 сжимает видеозаписи для обычного телевидения и телевидения с высоким разрешением.

MPEG Audio Layer 3 (MP3): технология сжатия аудиозаписей, входящая в состав MPEG-1, использует перцепционное кодирование аудиосигналов для сжатия высококачественного аудио (качества компакт-дисков) почти в 12 раз.

Fractal: метод сжатия с потерей данных для цветных изображений, который хорошо подходит для природных объектов. Допускает сжатие до 100 раз.

PKZip: популярный метод сжатия без потерь, разработанный компанией PKWare. Эта программа использует алгоритм и библиотеку данных для кодирования или архивирования множества файлов с данными. PKUnzip восстанавливает файлы в их исходное состояние.

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

Windows Media Technology: этот продукт компании Microsoft обеспечивает более высокое качество звука, чем MP3 для файлов того же размера, и практически не уступает по качеству видео на DVD.

Ли Коупланд, Рассел Кей

Как работает алгоритм сжатия

Далее описана одна упрощенная методика сжатия

Рассмотрим предложение: I thought I ought to go through with this new chore, though I knew I hadn?t been through. (Смысл этой забавной скороговорки в чем-то противоположен нашему высказыванию «За что боролись, на то и напоролись». — Прим. ред.) Многие элементы повторяются (для ясности на приведенном ниже рисунке они окрашены одинаковыми цветами).

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

I [пробел]##new[пробел]//
th@@or>>
ough**начало определения{{
t[пробел]$$конец определения}}
o[пробел]&&  

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

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

Поделитесь материалом с коллегами и друзьями