Классификация методов сжатия

Методы сжатия данных можно разделить на два типа:

1. Неискажающие (loseless) методы сжатия (называемые также методами сжатия без потерь) гарантируют, что декодированные данные будут в точности совпадать с исходными;
2. Искажающие (lossy) методы сжатия (называемые также методами сжатия с потерями) могут искажать исходные данные, например за счет удаления несущественной части данных, после чего полное восстановление невозможно.

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

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

Кроме того, можно выделить:

• методы сжатия общего назначения (general-purpose), которые не зависят от физической природы входных данных и, как правило, ориентированы на сжатие текстов, исполняемых программ, объектных модулей и библиотек и т. д., т. е. данных, которые в основном и хранятся в ЭВМ;
• специальные (special) методы сжатия, которые ориентированны на сжатие данных известной природы, например, звука, изображений и т. д. И за счет знания специфических особенностей сжимаемых данных достигают существенно лучшего качества и/или скорости сжатия, чем при использовании методов общего назначения.

Критерии оценки методов сжатия

Основными свойствами какого-либо алгоритма сжатия данных являются:

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

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

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

Понятно, что критерии оценки методов сжатия с практической точки зрения сильно зависят от предполагаемой области применения. Например, при использовании сжатия в системах реального времени необходимо обеспечить высокую скорость кодирования и декодирования; для встроенных систем критический параметр – объем требуемой памяти; для систем долговременного хранения данных – качество сжатия и/или скорость декодирования и т. д.

Надежность программ и сложность алгоритмов

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

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

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

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