Обратимость сжатия.

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

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

Если при сжатии данных происходит изменение их содержания, метод сжатия необратим и при восстановлении данных из сжатого файла не происходит полного восстановления исходной последовательности. Они применимы только для тех типов данных, для которых утрата части содержания не приводит к значительному снижению потребительских свойств. В первую очередь, это относится к мультимедийным данным: видеорядам, музыкальным записям, звукозаписям и рисункам. Методы сжатия с потерей информации обычно обеспечивают более высокую степень сжатия, чем обратимые методы. Но их нельзя применять к текстовым документам, базам данных, тем более к программному коду. Характерными форматами сжатия с потерей информации являются:

JPG – для графических данных

MPG – для видеоданных

MP3 – для звуковых данных.

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

-GIF, TIF, PCX и многие другие для графических данных

AVI – для видеоданных

ZIP, ARJ, RAR, LZH, LH, CAB и многие другие для любых типов данных

Методы сжатия. Алгоритмы обратимых методов.

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

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

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

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

Рассматривая различные методы сжатия, следует иметь в виду, что максимальную эффективность они демонстрируют для данных разных типов и разных объемов.

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

Таблица. Свойства алгоритмов сжатия

Алгоритм	Выходная структура	Сфера применения	Примечание
RLE (Run-Length Encoding)	Список (вектор данных)	Графические данные	Эффективность алгоритма не зависит от объема данных
KWE (Keyword Encoding)	Таблица данных (словарь)	Текстовые данные	Эффективен для массивов большого объема
Алгоритм Хафмана	Иерархическая структура	Любые данные	Эффективен для массивов большого объема

-

Алгоритм RLE

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

1 1 1 1 2 2 3 4 4 4

В алгоритме RLE предлагается заменить ее следующей структурой (записать в строку): 1 4 2 2 3 1 4 3, где первое число каждой пары чисел - это код данных, а второе - коэффициент повторения. Если для хранения каждого элемента данных входной последовательности отводится 1 байт, то вся последовательность будет занимать 10 байт памяти, тогда как выходная последовательность (сжатый вариант) будет занимать 8 байт памяти. Коэффициент сжатия равен 8/10 (80%).

Например, для последовательности: 0;0;0;127;127;0;255;255;255;255 (всего 10 байтов) образуется следующий вектор:

Значение	Коэффициент повтора

При записи в строку он имеет вид:

0;3;127;2;0;1;255;4 (всего 8 байтов).

В данном примере коэффициент сжатия равен 8/10 (80%).

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

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

Дата добавления: 2015-12-08