Опрос

Какой архиватор наиболее эффективный?:

Новички

Виктор Васильев
Юрий Антонов
Сергей Андреевич
Генадий
Avanasy

Пример 2

В качестве данных источника, подлежащих сжатию, выберем фрагмент изображения размером 4х4 элемента и содержащее 4 цвета: R = ="красный", O = "оранжевый", Y = "синий", G = "зеленый":


R

R

O

Y

R

O

O

Y

O

O

Y

G

Y

Y

Y

G

Просканируем это изображение по строкам и каждому из цветов присвоим соответствующую интенсивность, например, R = 3, O = 2, Y = 1 и G = 0, в результате чего получим вектор данных X = (3,3,2,1,3,2,2,1,2,2,1,0,1,1,1,0).

Для сжатия данных возьмем кодер, использующий следующую таблицу перекодирования данных источника в кодовые слова (вопрос о выборе таблицы оставим на будущее):

Кодер

Отсчет

Кодовое слово

3

001

2

01

1

1

0

000

Используя таблицу кодирования, заменим каждый элемент вектора X соответствующей кодовой последовательностью из таблицы (так называемое кодирование без памяти). Сжатые данные (кодовое слово B ( X )) будут выглядеть следующим образом:

B ( X ) = ( 0,0,1,0,0,1,0,1,1,0,0,1,0,1,0,1,1,0,1,0,1,1,0,0,0,1,1,1,0,0,0).

Коэффициент сжатия при этом составит r = 32/31, или 1,03. Соответственно скорость сжатия R = 31/16 бит на отсчет.

Пример 3. Сравним два различных кодера, осуществляющих сжатие одного и того же вектора данных

X = ABRACADABRA .

Первый кодер - кодер без памяти, аналогичный рассмотренному в предыдущем примере (каждый элемент вектора X кодируется независимо от значений других элементов - кодер без памяти). Таблица кодирования для него выглядит следующим образом:


Кодер 1

Символ

Кодовое слово

A

0

B

10

R

110

C

1110

D

1111

Второй кодер при кодировании текущего символа учитывает значение предшествующего ему символа, таким образом, кодовое слово для текущего символа A будет различным в сочетаниях RA , DA и CA ( иными словами, код обладает памятью в один символ источника):

Кодер 2

Символ, предыдущий символ

Кодовое слово

( A ,-)

1

(B,A)

0

(C,A)

10

(D,A)

11

(A,R)

1

(R,B)

1

(A,C)

1

( A , B )

1

Кодовые слова, соответствующие вектору данных X = ABRACADABRA , при кодировании с использованием этих двух таблиц будут иметь вид:

B 1 ( X ) = 01011001110011110101100,

B 2 ( X ) = 10111011111011.

Таким образом, скорость сжатия при использовании кодера 1 (без памяти) составит 23/11 = 2,09 бита на символ данных, тогда как для кодера 2 - 13/11 = =1,18 бита на символ. Использование второго кодера, следовательно, является более предпочтительным, хотя он и более сложен.