Компрессия данных

Компрессия, или сжатие, данных применяется для сокращения времени их пе­редачи. Так как на компрессию данных передающая сторона тратит дополни­тельное время, к которому нужно еще прибавить аналогичные затраты времени на декомпрессию этих данных принимающей стороной, то выгоды от сокра­щения времени на передачу сжатых данных обычно бывают заметны только на низкоскоростных каналах. Соответствующий порог скорости для современной аппаратуры составляет около 64 Кбит/с. Многие программные и аппаратные средства сети способны выполнять динамическую компрессию данных в отличие от статической, когда данные сначала компрессируются (например, с помощью популярных архиваторов типа WinZip), а уже затем отсылаются в сеть.

На практике может использоваться ряд алгоритмов компрессии, каждый из ко­торых применим к определенному типу данных. Некоторые модемы (называе­мые интеллектуальными) предлагают адаптивную компрессию, при которой в зависимости от передаваемых данных выбирается определенный алгоритм ком­прессии. Рассмотрим некоторые из общих алгоритмов компрессии данных.

Когда данные состоят только из чисел, значительную экономию можно получить путем уменьшения количества используемых на цифру битов с 7 до 4, используя простое двоичное кодирование десятичных цифр вместо кода ASCII. Просмотр таблицы ASCII показывает, что старшие три бита всех кодов десятичных цифр содержат комбинацию 011. Если все данные в кадре информации состоят из де­сятичных цифр, то, поместив в заголовок кадра соответствующий управляющий символ, можно существенно сократить длину кадра. Этот метод носит название десятичной упаковки.

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

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

В методе кодирования с помощью кодов переменной длины используется тот факт, что не все символы в передаваемом кадре встречаются с одинаковой часто­той. Поэтому во многих схемах кодирования коды часто встречающихся символов заменяют кодами меньшей длины, а редко встречающихся — кодами большей длины. Такое кодирование называется также статистическим кодированием. Из-за того что символы имеют разную длину, для передачи кадра возможна только бит-ориентированная передача. При статистическом кодировании коды выбира­ются таким образом, чтобы при анализе последовательности битов можно было бы однозначно определить соответствие определенной порции битов тому или иному символу или же запрещенной комбинации битов. Если данная последова­тельность битов представляет собой запрещенную комбинацию, то необходимо к ней добавить еще один бит и повторить анализ. Например, если при неравномер­ном кодировании для наиболее часто встречающегося символа «Р» выбран код 1, состоящий из одного бита, то значение 0 однобитного кода будет запрещенным. Иначе мы сможем закодировать только два символа. Для другого часто встре­чающегося символа «О» можно использовать код 01, а код 00 оставить как за­прещенный. Тогда для символа «А» можно выбрать код 001, для символа «П» — код 0001 и т. п.

Неравномерное кодирование наиболее эффективно, когда неравномерность рас­пределения частот передаваемых символов велика, как при передаче длинных текстовых строк. Напротив, при передаче двоичных данных, например кодов программ, оно малоэффективно, так как 8-битные коды при этом распределены почти равномерно.

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

Многие модели коммуникационного оборудования, такие как модемы, мосты, коммутаторы и маршрутизаторы, поддерживают протоколы динамической ком­прессии, позволяющие сократить объем передаваемой информации в 4, а иногда и в 8 раз. В таких случаях говорят, что протокол обеспечивает коэффициент сжа­тия 1:4 или 1:8. Существуют стандартные протоколы компрессии, например V.42bis, а также большое количество нестандартных, фирменных протоколов. Реальный коэффициент компрессии зависит от типа передаваемых данных. Так, графиче­ские и текстовые данные обычно сжимаются хорошо, а коды программ — хуже.