Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow Информатика
Посмотреть оригинал

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

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

Равномерное кодирование

С учетом пробелов алфавит сообщения содержит семь символов, для кодирования которых достаточно трех двоичных разрядов (табл. 3.6). Длина комбинации определяется как ближайшее большее целое (ББЦ)

пкк = ]1<Л527[ББЦ = 3, а заданный текст сообщения может быть представлен в виде последовательности двоичных символов длиной 48 бит:

000 010 001 010 001 000 010 ПО 011 001 000 100 001 010 101 000 мама_мыла_раму

Таблица 3.6

Равномерное кодирование

Символ

КК

000

А

001

М

010

Л

011

Р

100

У

101

Ы

110

Поскольку общее число символов в сообщении равно 16, количество информации в сообщении

10 = Н0-16 = 3 бит7_-16 символов = 48 бит.

Однако заметим, что расходование 3 бит на букву не означает, что каждая двоичная комбинация переносит 3 бита информации.

Неравномерное кодирование

Вероятности появления символов Р, легко оценить, посчитав, сколько раз каждый из них встречается в передаваемом сообщении: Р(-) = Р(А) = Р(М) = 1/4; Р(Л) = Р(Р) = Р(У) = Р(Ы) = 1/16.

Далее в соответствии с методом кодирования (см. подраздел 3.6.6) строим табл. 3.7.

Таблица 3.7

Кодирование символов по Шеннону—Фано

Результаты неравномерного (энтропийного) кодирования символов сообщения сведены в табл. 3.8.

Таблица 3.8

Неравномерное кодирование

Символ

КК

00

А

01

М

10

Л

1100

Р

1101

У

1110

Ы

1111

После подстановки полученных кодов вместо символов то же самое передаваемое сообщение будет представлено последовательностью двоичных символов длиной 40 бит:

00 10 01 10 01 00 10 1111 1100 01 00 1101 01 10 1110 00 мама_м ы ла_ р аму

С учетом вероятности появления символов в сообщении энтропия Н, (среднее количество битов на символ) рассчитывается по формуле

Тогда количество информации в том же сообщении будет равно

Таким образом, в результате энтропийного кодирования длина передаваемого сообщения сократилась с 48 до 40 бит.

Сжатие изображений

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

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

В цифровом изображении главным объектом является пиксель. Пусть требуется передать массив данных, представляющий собой «копию экрана», где на белом фоне изображена картинка (рис. 3.50).

Копия экрана

Рис. 3.50. Копия экрана

Простейшая схема сжатия изображений представлена на рис. 3.51, а кодирование байтов — в табл. 3.9.

Сжатие изображений

Рис. 3.51. Сжатие изображений

Кодирование байтов

Таблица 3.9

Исходные байты

Упакованные байты

0000 0000

0

0000 0001

10

0000 0011

110

Пусть картинка содержит 90 байт:

  • 80 байт — 0000 0000 — белый;
  • 7 байт — 0000 0001 — серый;
  • 3 байта — 0000 0011 — черный.

Программа сжатия выполняет несколько этапов:

  • 1) анализ повторения байтов. Строится гистограмма;
  • 2) составляются новые кодирующие последовательности (см. табл. 3.9);
  • 3) исходный массив сжимается. К нему пишется кодировочная таблица.

Рассмотрим пример расшифровки полученного сообщения.

Полученное сообщение:

С учетом сжатия картинка (см. рис. 3.50) вместо 90 байт будет содержать 103 бит:

  • 80 байт —> 80 бит
  • 7 байт —> 7-2 бит
  • 3 байт —> 3-3 бит
 
Посмотреть оригинал
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 

Популярные страницы