Коротко о сжатии информации

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

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

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

Под необратимым сжатием подразумевают такое преобразование входных данных, при котором невозможно получить точную копию исходных данных из архива, а можно получить только более или менее близкую к оригиналу копию. Часть информации, которая была в оригинале, безвозвратно теряется. Такие подходы и алгоритмы используются для сжатия, например, данных растровых графических файлов. При подобном подходе используются свойство структуры формата графического файла и возможность представить графическую картинку, приблизительно схожую по качеству отображения (для восприятия человеческим глазом), несколькими способами. Поэтому, кроме степени или величины сжатия в таких алгоритмах возникает понятие качества. А поскольку исходное изображение в процессе сжатия изменяется, качество характеризуется степенью соответствия исходного и результирующего изображения. Для графических файлов такое соответствие определяется визуально, хотя, конечно, для этого разработаны соответствующие интеллектуальные алгоритмы и программы. Данный подход реализован в популярных форматах представления видео- и фотоинформации, известных как JPEG- и JFIF-алгоритмы и JPG- и JIF-форматы файлов. Необратимое сжатие невозможно применять в тех областях, где требуется точное восстановление сжатой информации.

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

Обратимое сжатие данных основано на простой идее: отображение представления данных из одной группы символов на другую, более компактную серию символов. Рассмотрим два алгоритма: кодирование Хаффмена (Huffman) и LZW-кодирование (по начальным буквам фамилий Лемпел (Lempel) и Зив (Ziv) — его создателей и Уэлч (Welch), существенно его модифицировавшего).

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

Кодирование Хаффмена, предложенное впервые где-то в начале 50-х, уменьшает количество битов, используемых для представления часто встречающихся символов, и увеличивает количество бит, используемых для редких символов. Метод LZW, с другой стороны, кодирует строки символов, используя входной поток для построения расширенного алфавита, основанного на строках, которые он обрабатывает. Оба подхода работают путем уменьшения лишней информации во входных данных.