Обратимые и необратимые методы сжатия. Привести примеры методов сжатия

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

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

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

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

•.МPG для видеоданных;

•.МРЗ для звуковых данных.

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

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

•.АVI для видеоданных;

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

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

Алгоритм RLE

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

Например, для последовательности: 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-04-24