Сжатие информации

Сжатие информации, компрессия, англ. data compression — алгоритмическое преобразование данных (кодирование), при котором за счет уменьшения их избыточности уменьшается их обьём.

Принципы  сжатия информации

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

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

Преобразование сжатия обеспечивает получение сжатого  сообщения из исходного. Разжатие же обеспечивает получение исходного сообщения (или его приближения) из сжатого.

Все методы сжатия делятся  на два основных класса: без потерь, с потерями.

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

Характеристики  алгоритмов сжатия и  применимость

Коэффициент сжатия

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

k = So/Sc,

где k — коэффициент сжатия, So — размер несжатых данных, а Sc — размер сжатых. Таким образом, чем выше коэффициент сжатия, тем алгоритм лучше. Следует отметить:

если k = 1, то алгоритм не производит сжатия, то есть получает выходное сообщение размером, равным входному;

если k < 1, то алгоритм порождает при сжатии сообщение большего размера, нежели несжатое, то есть, совершает „вредную“ работу.  

Ситуация с k < 1 вполне возможна при сжатии. Невозможно получить алгоритм сжатия без потерь, который при любых данных образовывал бы на выходе данные меньшей или равной длины. Обоснование этого факта заключается в том, что количество различных сообщений длиной n Шаблон:Е:бит составляет ровно 2n. Тогда количество различных сообщений с длиной меньшей или равной n (при наличии хотя бы одного сообщения меньшей длины) будет меньше 2n. Это значит, что невозможно однозначно сопоставить все исходные сообщения сжатым: либо некоторые исходные сообщения не будут иметь сжатого представления, либо нескольким исходным сообщениям будет соответствовать одно и то же сжатое, а значит их нельзя отличить.  

Коэффициент сжатия может быть как постоянным коэффициентом (некоторые алгоритмы сжатия звука, изображения и т. п., например А-закон, μ-закон, ADPCM), так и переменным. Во втором случае он может быть определён либо для какого либо конкретного сообщения, либо оценён по некоторым критериям:

среднее (обычно по некоторому тестовому набора данных);

максимальное (случай наилучшего сжатия);

минимальное (случай наихудшего сжатия);  

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

Допустимость  потерь

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

символические данные, изменение которых неминуемо  приводит к изменению их семантики: программы и их исходные тексты, двоичные массивы и т. п.;

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

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

Однако сжатие с  потерями позволяет добиться гораздо больших коэффициентов сжатия за счёт отбрасывания незначащей информации, которая плохо сжимается. Так, например алгоритм сжатия звука без потерь FLAC, позволяет в большинстве случаев сжать звук в 1,5—2,5 раза, в то время как алгоритм с потерями Vorbis, в зависимости от установленного параметра качетсва может сжать до 15 раз с сохранением приемлемого качества звучания.

Системные требования алгоритмов

Различные алгоритмы  могут требовать различного количества ресурсов вычислительной системы, на которых  исполняются:

оперативной памяти (под промежуточные данные);

постоянной памяти (под код программы и константы);

процессорного времени.

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

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

Алгоритм  сжатия гораздо требовательнее к ресурсам, нежели алгоритм расжатия.

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

Алгоритмы сжатия и расжатия имеют примерно равные требования.

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

Алгоритм  сжатия существенно  менее требователен, чем алгоритм разжатия.

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