Файл: прикладная теория информации.pdf

57
Упорядочение
Редукция
????
????
????
!
???? ????
0,4 0,2 0,15 0,15 0,1
Редукция
????
????
????
! ???? ????
0,4 0,2 0,15 0,25
Упорядочение
???? ! ???? ???? ????
????
0,4 0,25 0,2 0,15
Редукция
???? ! ???? ???? ????????
0,4 0,25 0,35
Упорядочение
????
???????? ! ???? ????
0,4 0,35 0,25
Редукция
???? ????????! ???? ????
0,4 0,6
Упорядочение
????????! ???????? ????
0,6 0,4
Редукция
????????! ???? ????????
1
Рис. 4.1. Последовательность шагов алгоритма Хаффмена
Далее изобразим кодовое дерево, как показано на рис. 4.2.
????
????
????
!
????
????
0,4 0,2 0,15 0,15 0,05 0,05

58
Рис. 4.2. Кодовое дерево источника ???? = {????, ????, ????, ????, ????, !}
Соответственно, кодовые слова кода Хаффмена имеют следующий вид:
???? → 1010,
???? → 1011,
! → 100,
???? → 110,
???? → 111,
???? → 0.
Средняя длина полученного однозначно декодируемого кода равна
????
????
= ∑ ????
????
6
????=1
????
????
= 0,05 ∙ 4 + 0,15 ∙ 3 + 0,05 ∙ 4 + 0,4 ∙ 1 + 0,2 ∙ 3 + 0,15 ∙ 3 = 2,3.
Энтропия источника равна
???? = ∑
−????
????
6
????=1
log
2
????
????
= (−0,05 log
2 0,05) + (−0,15 log
2 0,15) +
+(−0,05 log
2 0,05) + (0,4 log
2 0,4) +
+ (0,2 log
2 0,2) + (−0,15 log
2 0,15) = 2,25 бит/символ.
Полученные значения средней длины ????
????
кода и энтропии
???? удовлетворяют выражению (3.6):
???? ≤ ???? ≤ ???? + 1,
2,25 < 2,3 < 3,25.

59
4.4.2. Эффективность кода
Определение 4.1. Эффективностью кода, или фактором сжатия, называется отношение энтропии к средней длине кода:
???? =
????
????
????
В примере 4.6 эффективность кода равна
η =
2,25 2,3
= 0,976.
4.4.3. Коды Хаффмена блоковых источников
Пусть источник формирует одиночные символы ???? = {????, ????} = {0,1} c веро- ятностями {????
1
=
1 3
, ????
2
=
2 3
}. Энтропия источника равна ???? = 0,918 бит/символ
(см. пример 4.3). Kодирование этого источника кодом Хаффмена приводит к двум словам с минимальной длиной ???? = 1.
1. Имеется блоковый источник с двукратным расширением
????
2
=
= {(00), (01), (10), (11)} = {????
1
, ????
2
, ????
3
, ????
4
, }. Символы ????
1
, ????
2
, ????
3
, ????
4
получены рас- ширением источника одиночных символов ???? = {????, ????} c вероятностями {????
1
=
=
1 3
, ????
2
=
2 3
}. Вероятности ????(с
????
) появления символов источника ????
2
определяются множеством
{
????(????
1
) =
1 9
, ????(????
2
) = ????(????
3
) =
2 9
, ????(????
4
) =
4 9
}.
Энтропия источника ????
2
равна
????
2
= ∑
−????(????
????
)
4
????=1
log
2
????(????
????
) = 1,83 бит/символ (см. пример 4.4).
Кодирование блокового источника ????
2
реализуем на основе алгоритма
Хаффмена. Алгоритму соответствует следующая последовательность шагов рис. 4.3.

60
Упорядочение
Редукция
????
4
????
2
????
1
????
3 4
9 2
9 3
9
Упорядочение
????
4
????
1
????
3
????
2 4
9 3
9 2
9
Редукция
????
4
????
1
????
3
????
2 4
9 5
9
Упорядочение
????
1
????
3
????
2
????
4 5
9 4
9
Редукция
????
1
????
3
????
2
????
4 1
Рис. 4.3. Последовательность шагов алгоритма Хаффмена
Далее изобразим кодовое дерево кода Хаффмена (рис. 4.4).
Рис. 4.4. Кодовое дерево
????
4
????
2
????
3
????
1 4
9 2
9 2
9 1
9

61
Кодовые слова имеют следующий вид:
????
1
→ (011),
????
2
→ (00),
????
3
→ (010),
????
4
→ (1).
Средняя длина полученного двоичного кода Хаффмена равна
????
????
= ∑ ????(????
????
)
4
????=1
????
????
=
1 9
∙ 3 +
2 9
∙ 2 +
2 9
∙ 3 +
4 9
∙ 1 =
17 9
≅ 1,88.
Средняя длина слова на один символ источника равна
????
????
????
=
17 9∙2
=
17 18
≅ 0,944.
Как видно, средняя длина кода источника ???? = {????, ????} уменьшилась с ???? = 1 до
????
????
????
≅ 0,94 > ???? = 0,918.
2. Имеется блоковый источник с трехкратным расширением
????
3
= {????
1
, ????
2
, ????
3
, ????
4
, ????
5
, ????
6
, ????
7
, ????
8
} =
= {(000), (001), (010), (011), (100), (101), (110), (111)}.
Символы блокового источника ????
3
получены расширением источника оди- ночных символов ???? = {0,1} c вероятностями {????
1
=
1 3
, ????
2
=
2 3
}. Вероятности ????(с
????
) появления символов источника ????
3
определяются как
????(????
1
) = ????
1
∙ ????
1
∙ ????
1
=
1 27
,
????(????
2
) = ????
1
∙ ????
1
∙ ????
2
=
2 27
,
????(????
3
) = ????
1
∙ ????
2
∙ ????
1
=
2 27
,
????(????
4
) = ????
1
∙ ????
2
∙ ????
2
=
4 27
????(????
5
) = ????
2
∙ ????
1
∙ ????
1
=
2 27
,
????(????
6
) = ????
2
∙ ????
1
∙ ????
2
=
4 27
,

62
????(????
7
) = ????
2
∙ ????
2
∙ ????
1
=
4 27
,
????(????
8
) = ????
2
∙ ????
2
∙ ????
2
=
8 27
Энтропия источника ????
3
равна
????
3
= ???????? = 3 ∙ 0,918 = 2,754.
Кодирование блокового источника ????
3
реализуем на основе алгоритма
Хаффмена. Структуре алгоритма соответствует последовательность перестано- вок исходных данных, показанная на рис. 4.5
Исходные данные
Упорядочение
Редукция
Упорядочение
Редукция
Упорядочение
????
1
????
2
????
3
????
4
????
5
????
6
????
7
????
8 1
27 2
27 2
27 4
27 2
27 4
27 4
27 8
27
????
8
????
7
????
6
????
4
????
5
????
3
????
2
????
1 8
27 4
27 4
27 4
27 2
27 2
27 2
27 1
27
????
8
????
7
????
6
????
4
????
5
????
3
????
2
????
1 8
27 4
27 4
27 4
27 2
27 2
27 3
27
????
8
????
7
????
6
????
4
????
2
????
1
????
5
????
3 8
27 4
27 4
27 4
27 3
27 2
27 2
27
????
8
????
7
????
6
????
4
????
2
????
1
????
5
????
3 8
27 4
27 4
27 4
27 3
27 4
27
????
8
????
7
????
6
????
4
????
5
????
3
????
2
????
1 8
27 4
27 4
27 4
27 4
27 3
27

63
Редукция
Упорядочение
Редукция
Редукция
Упорядочение
Редукция
Упорядочение
Редукция
Рис. 4.5. Последовательность перестановок исходных данных по алгоритму Хаффмена
Далее представим кодовое дерево (рис. 4.6).
????
8
????
7
????
6
????
4
????
5
????
3
????
2
????
1 8
27 4
27 4
27 4
27 7
27
????
8
????
5
????
3
????
2
????
1
????
7
????
6
????
4 8
27 7
27 4
27 4
27 4
27
????
8
????
6
????
4
????
5
????
3
????
2
????
1
????
7 8
27 8
27 7
27 4
27
????
8
????
6
????
4
????
7
????
5
????
3
????
2
????
1 8
27 8
27 11 27
????
7
????
5
????
3
????
2
????
1
????
8
????
6
????
4 11 27 8
27 8
27
????
7
????
5
????
3
????
2
????
1
????
8
????
6
????
4 11 27 16 27
????
8
????
6
????
4
????
7
????
5
????
3
????
2
????
1 16 27 11 27
????
8
????
6
????
4
????
7
????
5
????
3
????
2
????
1 1

64
Рис. 4.6. Кодовое дерево
Код Хаффмена:
????
1
→ (0101),
????
2
→ (0100),
????
3
→ (0111),
????
4
→ (111),
????
5
→ (0110),
????
6
→ (110),
????
7
→ (00),
????
8
→ (10).
Средняя длина полученного двоичного кода Хаффмена равна
????
????
= ∑ ????(????
????
)
8
????=1
????
????
=
1 27
∙ 4 +
2 27
∙ 4 +
2 27
∙ 4 +
4 27
∙ 3 +
2 27
∙ 4 +
4 27
∙ 3 +
+
4 27
∙ 2 +
8 27
∙ 2 =
76 27
≅ 2,81.
Средняя длина слова на один символ источника равна
????
????
????
≅
2,81 3
≅ 0,938.
Как видно, средняя длина кода источника ???? = {0,1} уменьшилась с ???? = 1 до
????
????
????
≅ 0,938 > ???? = 0,918.

65
Результаты расчетов для блоковых источников сведены в табл. 4.1. Ана- лиз данных таблицы позволяет сформулировать следующие выводы:
1. С увеличением степени расширения блокового источника значение сред- ней длины (на один символ блокового источника) слова кода Хаффмена умень- шается и стремится к энтропии одиночного источника.
2. С увеличением степени расширения блокового источника увеличивается эффективность кода или сжатие источника.
3. Недостатком алгоритма Хаффмена является требование априорного зна- ния значений вероятностей появления символов, или оценок этих вероятностей.
Таблица. 4.1
Эффективность кодирования источников
Источник одиночных символов ????
Блоковый источник ????
2
Блоковый источник ????
3
Символы
????
1
→ (0)
????
2
→ (1)
Энтропия источника
???? = 0,918 бит/символ
Код Хаффмена
????
1
→ (011)
????
2
→ (00)
????
3
→ (010)
????
4
→ (1)
Код Хаффмена
????
1
→ (0100)
????
2
→ (0101)
????
3
→ (0111)
????
4
→ (111)
????
5
→ (0110)
????
6
→ (110)
????
7
→ (00)
????
8
→ (10)
Cредняя длина кода на один символ источника
????
1
Cредняя длина кода на один символ источника
????
2
≅ 0,944
Cредняя длина кода на один символ источника
????
3
≅ 0,938
Эффективность кода
(η =
????
????
????
)
???? =
0,918 1
= 0,918
Эффективность кода
η =
1,836 1,88
≅ 0,944
Эффективность кода
η =
2,754 2,81
≅ 0,980
4.4.4. Декодирование кода Хаффмена
При приеме символа кодового слова декодирование начинается с началь- ной точки отсчета дерева (с корня дерева). Если входному символу соответствует значение 1, следует двигаться по ветви с присвоенным значением 1. Если прини- мается 0, следует идти по ветви, соответствующей значению 0. При попадании на конечный узел дерева принимается решение о принятом символе. При попа- дании в узел, из которого выходят две ветви, следующий принятый символ (0 или 1) указывает, по какой ветви следует двигаться. Движение по дереву продол- жается до достижения конечного узла. Для наглядности процесса декодирования кодового слова (1011) изобразим (рис. 4.7) кодовое дерево декодера источника

66
???? = {????, ????, ????, ????, ????, !}, (см. пример 4.6). Очевидно, декодирование кодовой после- довательности (1011) по дереву приводит к символу ????.
Замечание. Передача информации посредством эффективного кодирова- ния требует использования каналов, характеризующихся повышенной надежно- стью. Вероятность ошибки в таком канале должна быть сравнительно малой.
Даже одиночная ошибка в потоке кодированной информации приводит к непра- вильному декодированию сообщения источника. Рассмотрим это замечание на примере.
Рис. 4.7. Кодовое дерево декодера источника ???? = {????, ????, ????, ????, ????, !}
Пример 4.7 . Пусть для передачи сообщения «????????????????????!» используется код
Хаффмена, полученный в примере 4.6. Код состоит из следующих слов:
???? → 1010,
???? → 1011,
! → 100,
???? → 110,
???? → 111,
???? → 0.
Сообщению «????????????????????» соответствует поток двоичных символов
???? = 010101011111110100.
Пусть в процессе передачи этого потока из-за воздействия помехи

67 в канале возникла одиночная ошибка в 4-м двоичном символе. На вход декодера поступила последовательность
???? = 010????01011111110100.
Декодирование входной последовательности ???? = 010????01011111110100 с использованием кодового дерева (рис. 4.8) приводит к формированию ошибоч- ного сообщения «D!DNKE!».
Легко убедится, что структура кодового дерева отвечает следующему по- следовательному соответствию символов: 0 → ????, 100 → !,0 → ????, 1011→ ????,
111 → ????, 110 → ????, 100 → !.
Как видно, один бит, принятый с ошибкой, приводит к тому, что часть сим- волов или все последующие символы будут декодированы неправильно.
Рис. 4.9. Декодирование двоичного потока символов
Очевидными недостатками энтропийного метода кодирования являются:
– необходимость априорного знания вероятностных характеристик (стати- стик) символов источника;
– увеличенная вероятность ошибочного приема информации, т. к. сжатие данных снижает избыточность, что в свою очередь понижает надежность пере- дачи информации.
4.4.5. Адаптивный алгоритм Хаффмена
Адаптивный алгоритм эффективного кодирования реализуется с помощью двух операций:

68 1. Вначале выполняется кодирование источника в предположении, что все символы имеют равные вероятности появления.
2. По мере накопления знаний о статистических характеристиках источ- ника выполняется кодирование по алгоритму Хаффмена.
4.5. Универсальный алгоритм сжатия
Реализация этого алгоритма не требует предварительных знаний стати- стики символов источника и, по сути, является адаптивным. Универсальный ал- горитм сжатия информации основан на идее использования словаря последова- тельностей символов, слов, фраз и пр., или по-другому – образцов, встречаю- щихся в несжатых данных. Образцам последовательных символов, встречаю- щихся в текстах, изображениях, данных ставятся в соответствие кодовые слова.
При этом каждое кодовое слово представляется определенным индексом. Посте- пенно последовательности несжатых данных заменяются кодовыми словами, ко- торые имеются в словаре. Чем больше объем словаря образцов, и чем чаще они встречаются в несжатых данных, тем больше выигрыш в сжатии. Универсальный метод сжатия эффективен при архивации текстовой информации при обработке изображений, звуков и др.
4.5.1. Алгоритм эффективного кодирования Лемпеля
− Зива
Метод сжатия на основе словаря был разработан А. Лемпелем (Abraham
Lempel) и Я. Зивом (Jacob Ziv) в 1977 г. и известен как LZ77. Метод LZ77 явля- ется основой алгоритмов сжатия ZIP, ARJ, gzip и др., применяемых в компьюте- рах, используется в растровом файловом формате сжатия изображений PNG
(Portable Network Grafic).
Замечание. В формате PNG используется разновидность кодирования
LZ77, включающая кодирование Хаффмена.
Многие реальные источники информационных символов характеризуются тем, что не всегда символы удовлетворяют свойству независимости. Например, в любом языке вероятность появления той или иной буквы зависит от предыду- щей буквы. В этом случае говорят о межсимвольной зависимости, коррелиро- ванности. Кроме того, практически в любом тексте слова, фразы повторяются.
Можно сказать, что текст состоит из образцов, которые образуют некоторый сло- варь. Кодирование текста можно свести к некоторому алгоритму выбора образ- цов из словаря.
Процесс кодирования методом Лемпеля – Зива начинается сразу после по- ступления выходных символов источника на вход кодера. Кодирование инфор- мации производится по следующему алгоритму:

69 1. Передающая сторона записывает в специальный буфер поиска то, что было уже отправлено (символ, последовательность символов, слово, фразу и пр.). Принимающая сторона также записывает то, что было уже получено для осуществления декодирования.
2. При подготовке следующего фрагмента текста передающая сторона на- ходит в ранее переданном фрагменте образцы.
3. Далее идет процесс передачи не самих образцов, а только информации об этих образцах в виде ссылок.
4. Ссылка записывается в форме трех указателей
(????, ????, ????):
– ???? указывает относительный адрес образца в буфере поиска. Адрес опре- деляется местом (позицией) записи образца в буфере поиска. Значение позиции определяется числом позиций, которые надо пройти в обратном направлении в буфере от текущего символа до образца;
– ???? обозначает длину образца – число совпадающих символов образца и символов несжатых данных;
– ???? обозначает следующую букву в буфере, которая отличается от продол- жения фразы в словаре образцов. Например, ссылке (7, 4, А) соответствует но- вый текст, состоящий из 4 букв образца, который начинается с 7-й буквы в об- ратном направлении буфера, и что в новом тексте следующая за образцом идет буква А.
Таким образом, кодирование осуществляется посредством использования кодового слова (????, ????, ????). Закодированная информация представляется последова- тельностью ссылок – кодовых слов.
Пример 4 .8 . Необходимо передать сообщение: ДЕКОДИРОВАНИЕ_
КОДА с помощью алгоритма кодирования LZ77.
Решение
1. Процесс передачи сообщения начинается с кодирования первой буквы сообщения:
Сообщение
Д.
Кодовое слово выглядит как Д→ (0, 0, Д). Символ Д еще не содержится в буфере поиска (словаре образцов), поэтому:
− адрес ???? → 0;
− длина образца y → 0;
− следующая буква z → Д.
Замечание. Если символ не содержится в словаре образцов, он кодируется словом вида

70
(0, 0, символ).
Такое слово называется «нулевой фразой». При декодировании оно распо- знается по двум нулям.
2. Буфер поиска (словарь образцов) еще пуст. Буфер поиска имеет вид
–.
3. Далее идет кодирование и передача следующей буквы Е. Формируется вновь слово «нулевая фраза»:
(0, 0, Е).
4. В буфере поиска уже записана буква Д. Буфер поиска имеет вид
Д.
5. Далее идет кодирование словами «нулевая фраза» других символов: К,
О.
6. Далее передается ссылка (4, 1, И), которая указывает, что уже передава- лась буква Д, а также показывает следующую за ней букву И. Символ И (указа- тель ???? в слове (4, 1, И)) – это следующая буква кодируемого сообщения. Факти- чески эта ссылка (кодовое слово) соответствует передаче двух букв. Число 4 ко- дового слова (4, 1, И) соответствует позиции в обратном направлении от теку- щего передаваемого символа «Д» до записанного уже ранее в буфер поиска этого символа фразы ДЕКО. Последующие шаги алгоритма приведены в табл. 4.2.
Таблица 4.2.
Алгоритм кодирования LZ77
№ п/п
Буфер поиска
Буфер для предварительной записи сообщения
Кодовое слово
(
????, ????, ????)
1
–