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

Характерной особенностью большинства «классических» типов данных, с которыми работает человек, является их избыточность. Степень избыточности зависит от типа данных и от принятой системы кодирования. Избыточность информации нередко связана с представлением о ее качестве, поскольку избыточность, как правило, повышает восприятие информации, особенно в неблагоприятных условиях (восстановление повреждённого графического материала, чтение текста в условиях недостаточной видимости...). Однако когда речь заходит о хранении информации и их передаче, то избыточность можно уменьшить, что дает эффект сжатия.

В зависимости от того, в каком объекте размещены данные, подвергаемые сжатию, различают:

- уплотнение файлов – уменьшение их размеров дня хранения и передачи по каналам связи;

- уплотнение (архивацию) папок – уменьшение размеров и архивация для длительного хранения;

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

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

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

Характерными форматами сжатия с потерей информации являются;

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

-.MPG для видеоданных;

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

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

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

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

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

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

Разные алгоритмы по-разному сжимают разные типы и объемы данных.

Пример 1.

Алгоритм RLE.

Исходный код:

0 0 0 127 127 0 255 255 255 255 – 10 байт

Код после архивации:

0 3 127 2 0 1 255 6 – 8 байт. Коэффициент. сжатия = 80%

Особенности:

- высокая скорость сжатия;

- низкий коэффициент сжатия;

- хорош для графических файлов с большими одноцветными участками.

Пример 2.

Алгоритм KWE.

Кодирование лексических единиц исходного документа группами байтов фиксированной длины в архив вкладывается словарь. Такой алгоритм эффективен для англоязычных текстов большой длины.

Пример 3.

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

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

- перед началом проводится частотный анализ документа (выявляется частота повторения каждого символа);

- чем чаще встречается символ тем меньше битовая последовательность;

- образующаяся последовательность прикладывается к результирующему файлу.

Дата добавления: 2014-01-07