Сжатие информации

Как хранение, так и передача информации связаны с потреблением различного рода ограниченных ресурсов: объема памяти для хранения информации, объема сообщения для передачи информации, времени на передачу сообщения с информацией и т.п. Зная стоимость носителя и его емкость (Мбайт, Гбайт), можно подсчитать, во что обходится хранение единицы информации, а зная пропускную способность канала связи (Мбит/с) и стоимость его использования (аренды), можно определить затраты на передачу единицы информации. Результаты обычно составляют вполне значимые величины как для корпоративных пользователей, так и для индивидуальных. В связи с этим возможность сжатия информации позволяет пользователю организовать эффективное хранение или передачу информации. Соответственно, для доступа к информации, представленной в сжатом виде, требуется процедура восстановления информации в первоначальном виде.

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

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

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

• .JPG для графической информации;

• .MPG для видеоинформации;

• .MP3 для звуковой информации.

Характерными форматами структурного сжатия информации без потери являются:

• .GIF, .TIF, .PNG для графической информации;

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

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

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

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

Метод RLE (Run-Length Encoding). В основу метода положен принцип выявления повторяющихся последовательностей знаков и замены их простой структурой, в которой указывается код знака и коэффициент повтора. Информация просматривается последовательно знак за знаком. Если выявляется повторяющаяся последовательность знаков, она заменяется одним кодом знака и коэффициентом повторения.

Например, для последовательности знаков (полагаем, что знак хранится в 1 байте памяти), содержащих восьмеричные коды:

000 000 000 127 127 000 255 255 255 255 (всего 10 байтов),

сжатая информация примет вид:

000 003 127 002 000 001 255 004 (всего 8 байтов).

В данном примере коэффициент сжатия информации равен 8/10 = 0.8 - (80%). Т.е. в сжатом виде информация составляет 80% от исходного объема.

Метод KWE (Keyword Encoding). В основу метода положен принцип кодирования лексических единиц исходного документа группами байтов фиксированной длины. В качестве лексической единицы документа рассматривается последовательность символов, справа и слева ограниченная пробелами или символами конца абзаца. Предполагается, что выделяемые в документе в результате анализа структуры документа лексические единицы превышают по размеру комбинацию байтов соответствующего кода. Результаты структурного лексического анализа документа сводятся в таблицу, называемую словарем. Для сжатия исходного документа все выделенные лексические единицы заменяются соответствующими кодами, взятыми из словаря. Словарь добавляется в конец сжатого документа. Результат сжатия содержимого документа вместе со словарём составляет документ в сжатом виде. Для преобразования документа в исходное состояние необходимо коды заменить соответствующими лексическими единицами.

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