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

.

Если при равномерном кодировании требуется два двоичных разряда (n=2), чтобы различить 4 сообщения, то в данном примере n_ср=1.75, т.е. меньше. Коэффициент избыточности кода, построенного по алгоритму Шеннона ‑ Фано, в соответствии с примером равен нулю, т.е. построенный код не имеет избыточности.

Пример. Декодировать заданную последовательность символов в кодах рассмотренного выше примера.

код сообщение

0 111 10 110 0₂ ® X₁ X₄ X₂ X₃ X₁

Х₁ Х₄ Х₂ Х₃ Х₁

В настоящее время более распространен метод кодирования по Хаффмену. Этот метод похож на алгоритм Шеннона-Фано мы его не рассматриваем подробно и он остается для самомтоятельного изучения.

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

Первый подход применяется для сжатия текстов и графики (алгоритм Лемпеля-Зива – Lempel-Ziv, LZ, RLE – Run Length Encoding, алгоритм Хаффмена и др.).

Алгоритм Лемпеля-Зива (Lempel-Ziv, LZ) лежит в основе архиваторов и программ динамического сжатия дисков. Основная идея этого алгоритма состоит в том, что второе и последующие вхождения некоторой строки символов в сообщение заменяются ссылкой на её первое появление в сообщении.

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

Хаффмена – тоже что и Шеннона-Фано.Чем чаще используется символ, тем короче кодовая последовательность

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

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

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

Особенности алгоритмов сжатия.

· нет алгоритма, одинаково эффективного для данных разной природы;

· приведённые алгоритмы рассчитаны на сжатие данных, в которых есть последовательности одинаковых символов или одни символы встречаются чаще других.

Пример сжатия текстовой информации

Сжать сообщение: _мама_мыла_раму_, используя энтропийное кодирование. Символы сообщения закодируем двумя способами: равномерными и неравномерными (по Шеннону ‑ Фано) кодовыми комбинациями.

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