Сжатие данных

Закодированные сообщения передаются по каналам связи, хранятся в запоминающих устройствах, обрабатываются процессором. Объемы данных, циркулирующих в АСУ, велики, и поэтому в о многих случаях важно обеспечить такое кодирование данных, которое характеризуется минимальной длиной получающихся сообщений. Эта проблема сжатия данных. Решение её обеспечивает увеличение скорости передачи информации и уменьшение требуемой памяти запоминающих устройств. В конечном итоге это ведет к повышению эффективности системы обработки данных.

Существует два подхода (или два этапа) сжатия данных:

- сжатие, основанное на анализе конкретной структуры и смыслового содержания данных;

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

4.1. Сжатие на основе смыслового содержания данных

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

Переход от естественных обозначений к более компактным. Значения многих конкретных данных кодируются в виде, удобном для чтения человеком. При этом они содержат обычно больше символов, чем это необходимо. Например, дата записывается в виде «26 января 1982 г.» или в самой краткой форме: «26.01.82». при этом многие кодовые комбинации, например «33.18.53» или «95.00.11», никогда не используются. Для сжатия таких данных день можно закодировать пятью разрядами, месяц – четырьмя, год – семью, т.е. вся дата займет не более двух байтов. Другой способ записи даты, предложенный еще в средние века состоит в том, чтобы записывать общее число дней, прошедших к настоящему времени с некоторой точки отсчета. При этом часто ограничиваются четырьмя последними цифрами этого представления. Например, 24 мая 1967 года записывается в виде 0000 и отсчет дней от этой даты требует, очевидно, два байта в упакованном десятичном формате.

Аналогичным образом могут быть сжаты номера изделий, уличные адреса и т.п.

Подавление повторяющихся символов. Во многих данных часто присутствуют повторяющиеся подряд символы: в числовых – повторяющиеся старшие или младшие нули, в символьных – пробелы и т.п. Если воспользоваться специальным символом указывающим на повторение, а после него помещать в закодированном виде число повторений, то тем самым можно уменьшить избыточность, обусловленную повторениями. Например, подавление повторений может быть произведено по следующей схеме. В коде ДКОИ-8 большая часть допустимых кодовых комбинаций не используется. Одну из таких комбинаций (например, с нулем во второй позиции) можно использовать как признак повторения. Тогда байт следующего вида с последующим байтом кода символа заменяют цепочку повторяющихся символов