Учебная информация
Сжатие данных в вычислительной технике и системах связи (используются также термины архивация данных, когда сжатие применяется к готовым документам; программные средства, выполняющие эти операции, называют архиваторами, например, WinZip, WinRAR, WinArj, PKZIP.EXE, RAR.EXE, ARJ.EXE; используется и синонимы слова сжатие упаковка, компрессия) - это процесс кодирования массивов данных таким образом, чтобы объем занимаемый полученным кодом в запоминающих устройствах, был бы, по возможности минимальным.
При этом процесс сжатия должен быть полностью или частично обратимым, т.е. должна существовать обратная процедура, называемая декодированием (распаковкой, разархивацией), позволяющая восстановить из сжатых данных набор данных, в той или иной мере соответствующий исходным данным.
Такое определение под сжатием понимает следующие процедуры преобразования данных: неискажающее сжатие цифровых данных, сжатие цифровых данных с регулируемыми потерями, получение экономного представления входного аналогового сигнала.
При неискажающем сжатии цифровых данных исходный массив цифровых данных (исходное сообщение) представляется таким образом, чтобы получить минимизированный объем закодированных данных. Сжатие должно быть полностью обратимым, т.е. должна существовать процедура, позволяющая восстановить из сжатых данных точную копию исходного массива данных. Подчеркивая эту особенность, такой процесс часто называют сжатием без потерь, обратимым сжатием. Исходные данные представляются каким-либо двоичным кодом: коды символов текста, команд процессора, яркости точек растрового изображения, амплитуды аналогового сигнала, ссылки на другие фрагменты данных.
При сжатии цифровых данных с регулируемыми потерями обеспечивается экономное представление цифровых данных, но процедура сжатия не является полностью обратимой, т.е. распаковка не позволяет во всех случаях восстановить исходный массив данных до отдельного бита. Как правило, потери допускаются только в той части данных, которая не является существенной при дальнейшем использовании распакованного сообщения. Ясно, что в общем случае «существенность» потерь данных оценить невозможно, поэтому сжатие с потерями допускается только для данных, которые допускают некоторую потерю. Обычно это аналоговые по своей природе данные, например, оцифрованные изображения или звук: цифровые фотографии, видеоряды, звукозаписи.
Алгоритмы сжатия без потерь
Для сжатия без потерь доказаны следующие теоремы.
1. Для любой последовательности данных существует теоретический предел сжатия, который не может быть превышен без потери части информации.
2. Для любого алгоритма сжатия можно найти такую последовательность данных, для которой он обеспечит лучшую степень сжатия, чем другие алгоритмы.
3. Для любого алгоритма сжатия можно найти такую последовательность данных, для которой данный алгоритм вообще не позволит получить сжатия.
Из сформулированных теорем следует, что наивысшую эффективность алгоритмы сжатия демонстрируют для разных типов данных и разных объемов данных. Поэтому разработано в настоящее время достаточно большое количество алгоритмов сжатия без потерь. Наиболее распространенные алгоритмы сжатия без потерь приведены на рис. 1.
