СЖАТИЕ ДАННЫХ

Сжатие (компрессия) данных — это процесс сокращения числа битов, необходимых для передачи и хранения некоторого объема информации. Сжатие может быть без потерь — информация, восстановленная из сжатого сообщения, в точности соответствует исходной, и с потерями — восстановленная информация только частично соответствует исходной. Первое применяется для сжатия текстов и графики (алгоритм Лемпеля—Зива, RLE—Run Length Encoding, алгоритм Хаффмена и др.).

Алгоритм Лемпеля—Зива (Lempel—Ziv, LZ) лежит в основе архиваторов (pkzip, arj, lha) и программ динамического сжатия дисков

(Stacker, DoubleSpace). Основная идея этого алгоритма состоит в том, что второе и последующие вхождения некоторой строки символов в сообщение заменяются ссылкой на ее первое появление в сообщении.

Алгоритм RLE применяют для сжатия графики и видеоматериалов. Непрерывная последовательность одинаковых символов заменяется двумя байтами. В первом байте — символ, во втором — счетчик, т.е. число, которое показывает, сколько таких символов идет подряд.

Кодирование по Хаффмену состоит в замене информационных символов кодовыми последовательностями различной длины. Чем чаще используется символ, тем короче кодовая последовательность.

Сжатие с потерями [алгоритмы JPEG (Joint Photographic Expert Group), M-JPEG, MPEG (Motion Picture Expert Group)] ориентировано на сжатие неподвижных изображений.

Алгоритм М-JPEG использует для компрессии видео, в котором каждый отдельный кадр сжимается по методу JPEG.

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

Из приведенного краткого обзора алгоритмов сжатия очевидны два вывода:

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

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

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

Так, информация, содержащаяся в файлах, во многих случаях избыточна, и для устранения избыточности используют специальные методы сжатия данных, основанные на поиске этой избыточной информации и последующем ее кодировании с целью получения минимального объема. Для представления сообщений с меньшим расходом знаков (разрядов) часто применяют энтропийные методы кодирования, например по Шеннону—Фано или Хаффмену (см. подраздел 3.6.6).

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

Поскольку буквы в сообщении появляются с разной вероятностью, например, О и Е — чаще, Э, Ф — реже, то среднее количество информации на один символ сообщения, т.е. энтропия, рассчитывается по формуле

где Р, — вероятность появления i-й буквы.

То есть энтропия определяется статистическими свойствами источника сообщения. В случае равномерности и независимости букв энтропию можно вычислить как Н0 = log232 = 5 бит/букву. В случае разных вероятностей появления букв энтропия равна Н0 = 4,1 бит/букву.

Таким образом, можно видеть, что описание каждой буквы пятью двоичными разрядами является избыточным. Сообщение из N букв в случае равновероятных исходов потенциально может переносить I0 = 5N бит информации, в случае разновероятных — количество переносимой информации составит I = 4,1N бит.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ   След >