Информатика -взгляд 2


Теоретические основы сжатия данных - часть 3


 

 

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

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

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

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

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

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

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

Таблица 14.1.

 Свойства алгоритмов сжатия

 

Алгоритм

Выходная структура

Сфера применения

Примечание

RLE (Run-Length Encoding

Список (вектор данных)

Графические данные

Эффективность алгоритма не зависит от объема данных

KWE (Keyword Encoding)

Таблица данных (словарь)

Текстовые данные

Эффективен для массивов большого объема

Алгоритм Хафмана

Иерархическая структура (дерево кодировки)

Любые данные

Эффективен для массивов большого объема

 

Алгоритм RLE

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

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

 

Значение

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

0

3

127

2

0

1

255

4

 

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

0; 3; 127; 2; 0; 1; 255; 4 (всего 8 байтов). В данном примере коэффициент сжатия равен 8/10 (80 %).

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


Начало  Назад  Вперед



Книжный магазин