Кодирование инф. Курс лекций по темам раздела Кодирование информации, методические рекомендации для подготовки ответа на экзаменационные вопросы, задания для самопроверки

• Название: Курс лекций по темам раздела Кодирование информации, методические рекомендации для подготовки ответа на экзаменационные вопросы, задания для самопроверки
• Дата: 30.03.2023
• Размер: 1.18 Mb.
• Имя файла: Кодирование инф.pdf
• Тип: Курс лекций; #1026909
• страница: 4 из 7

0
1
1
0
0
1
1
0
0
1

То есть избыточность кода Шеннона-Фано для нашего шестибуквенного алфавита составляет всего около 1,7 %.
Заметим, что для русского алфавита избыточность кодирования кодом Шеннона-Фано составила бы примерно 1,47%.
Вопросы для самопроверки:
1.
Объясните алгоритм построения кода Шеннона-Фано.
2.
Докажите, что построенный по алгоритму Шеннона-
Фано код будет префиксным.
3.
Постройте код Шеннона-Фано для символов первичного
алфавита А={«+», «-», «*», «/»} с известными вероятностями
появления символов Р={0,4; 0,2; 0,3; 0,1}:
а) при помощи таблицы,
б) при помощи графа.
Префиксный код Хаффмана.
При ответе на данный вопрос необходимо привести
пример построения префиксного кода Хаффмана для заданного
начального алфавита и известных частот использования
символов этого алфавита с помощью таблицы и графа.
В 1952 году Давид Хаффман показал, что предложенный им метод кодирования является оптимальным префиксным кодом для дискретных источников без памяти (заметим, что для таких источников все генерируемые сообщения независимы друг от друга).
Алгоритм кодирования методом Хаффмана состоит из двух этапов. На первом этапе исходный алфавит на каждом шаге сокращается на один символ и на следующем шаге рассматривается новый, сокращенный первичный алфавит.
43

Число таких шагов будет на две единицы меньше первоначального числа символов. На втором этапе происходит пошаговое формирование кода символов, при этом заполнение кода осуществляется с символов последнего сокращенного первичного алфавита.
Рассмотрим алгоритм построения кода Хаффмана на примере. Пусть имеется первичный алфавит, состоящий из шести символов: {A; B; C; D; E; F}, также известны вероятности появления этих символов в сообщении соответственно {0,15;
0,2; 0,1; 0,3; 0,2; 0,05}. Расположим эти символы в таблице в порядке убывания их вероятностей.
Первичный алфавит
D
B
E
A
C
F
Вероятности появления символов
0,3 0,2 0,2 0,15 0,1 0,05
На первом шаге алгоритма два символа исходного алфавита, который мы назовем A
0
, с наименьшими вероятностями объединяются в один новый символ. Вероятность нового символа есть сумма вероятностей тех символов, которые его образовали. Таким образом, получаем новый алфавит, который содержит на один символ меньше чем предыдущий. На следующем шаге алгоритма описанная процедура применяется к новому алфавиту. И так до тех пор, пока в очередном алфавите не остается только двух символов.
Процедура построения всех промежуточных алфавитов отражена в следующей таблице (в каждом алфавите символы упорядочены по убыванию вероятностей, верхний индекс символа совпадает с индексом промежуточного алфавита, которому он принадлежит, а нижний — показывает порядковый номер символа):
44

A
0
Код
А
0
A
1
Код
А
1
А
2
Код
А
2
А
3
Код
А
3
А
4
Код
А
4
a
0 1
=D
P = 0,3
a
1 1
P = 0,3
a
2 1
P = 0,3
a
3 1
P = 0,4
a
4 1
P = 0,6
a
0 2
=B
P = 0,2
a
1 2
P = 0,2
a
2 2
P = 0,3
a
3 2
P = 0,3
a
4 2
P = 0,4
a
0 3
=E
P = 0,2
a
1 3
P = 0,2
a
2 3
P = 0,2
a
3 3
P = 0,3
a
0 4
=A
P = 0,15
a
1 4
P = 0,15
a
2 4
P = 0,2
a
0 5
=C
P = 0,1
a
1 5
P = 0,15
a
0 6
=F
P = 0,05
Теперь начинается второй этап алгоритма кодирования по
Хаффману. Для формирования кода мы нумеруем символы всех промежуточных алфавитов, начиная с последнего. В нашем примере – с А
4
В А
4
всего два символа. Они получают соответственно номера 0 и 1. В алфавите А
3
уже три символа. Причем, один из символов алфавита А
4
, назовем этот символ «предок», был получен объединением двух символов алфавита А
3
, назовем первый из этих символов «дочкой», а второй «сыном». Коды этих двух символов формируются следующим образом. К номеру «предка» приписываются справа 0, чтобы получить номер «дочки», и 1 – чтобы получить номер «сына». Следующая итерация алгоритма по той же схеме формирует коды символов алфавита А
2
. В нем два первых символа будут иметь те же коды, что были у них в А
1
, а два последних символа изменят свой код,
45

удлинив его на 1 символ («0» и «1» соответственно). Процесс останавливается при достижении первичного алфавита A
0
– коды для знаков первичного алфавита получены.
Отразим формирование кода в построенной таблице:
A
0
Код
А
0
A
1
Код
А
1
А
2
Код
А
2
А
3
Код
А
3
А
4
Код
А
4
a
0 1
=D
P = 0,3 00
a
1 1
P = 0,3 00
a
2 1
P = 0,3 00
a
3 1
P = 0,4 1
a
4 1
P = 0,6 0
a
0 2
=B
P = 0,2 10
a
1 2
P = 0,2 10
a
2 2
P = 0,3 01
a
3 2
P = 0,3 00
a
4 2
P = 0,4 1
a
0 3
=E
P = 0,2 11
a
1 3
P = 0,2 11
a
2 3
P = 0,2 10
a
3 3
P = 0,3 01
a
0 4
=A
P = 0,15 010
a
1 4
P = 0,15 010
a
2 4
P = 0,2 11
a
0 5
=C
P = 0,1 0110
a
1 5
P = 0,15 011
a
0 6
=F
P = 0,05 0111
Данный алгоритм построения можно осуществить и с помощью графа. Расположим символы первичного алфавита в порядке убывания вероятностей их появления. Эти символы будут листьями будущего кодового дерева. Будем считать, что уровень этих концевых узлов равен N.
D
0,3
B
0,2
E
0,2
A
0,15
C
0,1
F
0,05
Теперь соединим два крайних правых символа (C и F), имеющих наименьшую вероятность появления, дугами, исходящими из одного и того же узла уровня N-1 (в основании узла указана суммарная вероятность использования
46

получившегося символа нового промежуточного алфавита):
D
0,3
B
0,2
E
0,2
A
0,15
C
0,1
F
0,05
В получившемся промежуточном алфавите вновь выбираем два символа с наименьшей частотой использования. Это символ
А с вероятностью 0,15 и новый символ, получившийся в результате объединения символов C и F на предыдущем этапе и имеющий ту же вероятность использования. Соединяем эти символы дугами, исходящими из одного узла N-2 уровня:
D
0,3
B
0,2
E
0,2
A
0,15
C
0,1
F
0,05
Продолжая описанный алгоритм построения, получим следующее дерево:
B
0,2
E
0,2
A
0,15
C
0,1
F
0,05
D
0,3
Также как в методе Шеннона-Фано пронумеруем каждую левую исходящую дугу узла цифрой 0, а каждую правую дугу цифрой 1. Теперь для получения кода символа достаточно пройти от корня до нужного символа и записать номера дуг, по которым осуществляется прохождение.
47
0,15
0,3
0,4
0,6
0
1
0
0
0
0
1
1
1
1
0,15
0,3
0,15

Посчитаем среднюю длину кодового слова для кода
Хаффмана и нашего первичного алфавита А.
К(Хаффман, А, Binary) = 0,3*2 + 0,2*2 + 0.2*2 + 0,15*3 +
+0,1*4 + 0.05*4 = 2,45 символа
Среднее количество информации на один символ первичного алфавита равно:
I
A
= - (0,3* log
2
0,3 + 0,2* log
2
0,2 + 0,2* log
2
0,2 +
+ 0,15* log
2
0,15 + 0,1* log
2
0,1 + 0,05* log
2
0,05) = 2,41 бит.
Относительная избыточность кода Хаффмана в нашем случае:
Q(Хаффмана, A, Binary) = 2,45/2,41 – 1 = 0,01659751.
Таким образом, для нашего примера код Шеннона-Фано и код Хаффмана обладают одинаковой избыточностью. Однако, в тех случаях когда вероятности символов первичного алфавита сильно разнятся, ситуация меняется. Код Хаффмана обладает существенно меньшей избыточностью. Например, для русского языка избыточность кодирования кодом Хаффмана оказывается равной примерно 0,0090.
Вопросы для самопроверки:
1.
Объясните алгоритм построения кода Хаффмана.
2.
Докажите, что построенный по алгоритму Хаффмана
код будет префиксным.
3.
Постройте код Хаффмана для символов первичного
алфавита А={«+», «-», «*», «/»} с известными вероятностями
появления символов Р={0,4; 0,2; 0,3; 0,1}:
а) при помощи таблицы,
б) при помощи графа.
48

Арифметическое кодирование.
При ответе на данный вопрос необходимо объяснить
понятие «арифметическое кодирование», сравнить его с
другими известными вам способами кодирования и рассказать
об алгоритме построения арифметического кода некоторого
сообщения.
Арифметическое кодирование — один из алгоритмов энтропийного сжатия. Алгоритм арифметического кодирования обеспечивает почти оптимальную степень сжатия с точки зрения энтропийной оценки кодирования Шеннона. На каждый символ требуется почти H бит, где H — информационная энтропия источника.
Арифметическое кодирование является методом, позволяющим упаковывать символы входного алфавита без потерь при условии, что известно распределение частот этих символов и является наиболее оптимальным, т.к. достигается теоретическая граница степени сжатия.
Последовательность символов, при сжатии методом арифметического кодирования рассматривается как некоторая
двоичная дробь из интервала [0, 1). Результат сжатия представляется как последовательность двоичных цифр из записи этой дроби.
Опишем алгоритм построения этого кода. Пусть у нас есть некий первичный алфавит, состоящий из трех символов: A = {a, b, !}, а также данные о вероятности использования символов P =
{0,3; 0,6; 0,1}. Последний символ рассматриваемого алфавита
(«!») не несет информационной нагрузки, а является признаком конца сообщения. Он необходим декодировщику для однозначного декодирования полученного сообщения. На
49

практике вероятность его использования берут заведомо малой.
Данный символ можно не использовать только в том случае, когда декодировщику точно известна длина кодируемого сообщения.
Пусть требуется закодировать сообщение S = «bab!».
Рассмотрим на координатной прямой отрезок от 0 до 1. Назовём этот отрезок рабочим. Расположим на нём точки таким образом, что длины образованных отрезков будут равны частоте использования символа, и каждый такой отрезок будет соответствовать одному символу.
Рабочий отрезок [0;1)
Символ
Частота использования
Отрезок a
0,3
[0; 0,3)
b
0,6
[0,3; 0,9)
!
0,1
[0,9; 0,1)
Первый символ сообщения S — символ «b». Ему соответствовала часть рабочего отрезка от 0,3 до 0,9. Теперь эта часть рабочего отрезка сама становится рабочим отрезком следующего этапа кодирования. Разобьём его таким образом чтобы соотношения длин получаемых отрезков соответствовало соотношению вероятностей использования символов — 3:6:1.
Длина рассматриваемого рабочего отрезка d = 0,9 - 0,3 = 0,6.
Разбиваем его на 10 равных частей (3 + 6 + 1 = 10) длиной 0,06 каждая. Три части (отрезок длиной 0,18) относим к рабочему отрезку буквы «a», шесть частей (отрезок длиной 0,36) — к рабочему отрезку буквы «b» и одну часть длиной 0,06 — к рабочему отрезку символа «!». Порядок следования рабочих отрезков должен соответствовать первоначальному. Получим следующую таблицу разбиения текущего рабочего отрезка:
50

Рабочий отрезок [0,3; 0,9)
Символ
Частота использования
Отрезок a
0,3
[0,3; 0,3 + 0,06*3) =
[0,3; 0,48)
b
0,6
[0,48; 0,48 + 0,06*6) =
[0,48; 0,84)
!
0,1
[0,84; 0,84 + 0,06*1) =
[0,84; 0,9)
Далее в сообщении S расположен символ «a». Сейчас ему соответствует отрезок [0,3; 0,48). Выбираем этот отрезок в качестве рабочего и, согласно алгоритму, проведем его деление на части (общая длина отрезка 0,18, значит длина 1/10 части будет 0,018, для буквы «а» нужно три таких части, для «b» - шесть, для «!» - одна часть):
Рабочий отрезок [0,3;0,48)
Символ
Частота использования
Отрезок a
0,3
[0,3; 0,3 + 0,018*3) =
[0,3; 0,354)
b
0,6
[0,354; 0,354 + 0,018*6)
= [0,354; 0,462)
!
0,1
[0,462; 0,462 + 0,018*1)
= [0,462; 0,48)
На следующем этапе рабочим отрезком будет [0,354; 0,462)
— именно он соответствует новой букве в сообщении S, букве
«b». Длина отрезка d = 0,462 — 0,354 = 0,108. Разделяем его на
10 частей длиной 0,0108. Букве «а» будет соответствовать часть
51

рассматриваемого рабочего отрезка длиной 3*0,0108 = 0,0324.
Далее расположится часть рабочего отрезка буквы «b». Ее длина будет 6*0,0108 = 0,0648. Оставшаяся часть рабочего отрезка длиной 0,0108 отводится символу «!». Рассмотрим таблицу деления нового рабочего отрезка:
Рабочий отрезок [0,354; 0,462)
Символ
Частота использования
Отрезок a
0,3
[0,354; 0,3864)
b
0,6
[0,3864; 0,4512)
!
0,1
[0,4512; 0,462)
Заканчиваем сообщение символом «!». Его рабочий отрезок на данном этапе [0,4512; 0,462). Выберем любое число из рабочего отрезка, например число 0,46. Переведем его в двоичную систему счисления: 46 10
= 0,0111011 2
. Биты этого числа вместе с длиной его битовой записи и есть результат арифметического кодирования использованных символов потока.
Видно, что после каждого обработанного символа текущий интервал становится все меньше, поэтому требуется все больше бит, чтобы выразить его, однако окончательным выходом алгоритма является единственное число, которое не является объединением индивидуальных кодов последовательности входных символов. Среднюю длину кода можно найти, разделив размер выхода (в битах) на размер входа (в символах).
Рассмотрим как происходит декодирование сообщения.
Декодировщик получает код сообщения 0,46. Ему известен первичный алфавит и вероятности использования его символов.
Он разбивает рабочий отрезок [0; 1) на отрезки согласно
52

вероятностям появления символов:
Полученный код принадлежит отрезку [0,3; 0,9) — это часть отрезка соответствующая букве «b». Значит первый символ закодированного сообщения это символ «b». Далее декодировщик рассматривает рабочий отрезок полученной буквы, делит его пропорционально известным вероятностям появления символов и определяет в какую часть нового рабочего отрезка попадает число 0,46 — код сообщения S.
Число 0,46 принадлежит той части рассматриваемого рабочего отрезка, которая соответствует букве «а». Это второй декодированный символ сообщения S.
Декодировщик продолжает указанное деление до тех пор, пока полученный код не попадет в рабочий отрезок символа «!», являющийся признаком конца сообщения.
Вопросы для самопроверки:
1.
Объясните алгоритм построения арифметического
кода.
2.
Постройте арифметический код сообщения S = «2+2!»
для символов первичного алфавита А={«+», «2», «!»} с
известными вероятностями появления символов Р={0,4; 0,5;
0,1} (символ «!» не несет смысловой нагрузки и является
признаком конца сообщения).
3.
Декодируйте сообщение S, составленное из символов
53 0
0,3 0,9 1 0,46
0,3
0,9
0,46
0,48
0,84

алфавита А={«1», «2», «3», «!»} с вероятностями Р={0,4; 0,3;
0,2; 0,1}, если известен его арифметический код, записываемый
в двоичной системе счисления как 0,1000101
2
Адаптивное арифметическое кодирование.
При ответе на данный вопрос необходимо дать понятие
«адаптивное арифметическое кодирование» и рассказать об
алгоритме построения такого кода.
Для арифметического кодирования, позволяющего закодировать сообщение единственным числом в диапазоне [0;
1), существует адаптивный алгоритм. Такой алгоритм при каждом сопоставлении символу кода, изменяет внутренний ход вычислений так, что в следующий раз этому же символу может быть сопоставлен другой код, т.е. происходит “адаптация” алгоритма к поступающим для кодирования символам. При декодировании происходит аналогичный процесс.
Необходимость применения адаптивного алгоритма возникает в том случае, если вероятностные оценки для символов сообщения неизвестны до начала работы алгоритма.
Рассмотрим на примере алгоритм адаптивного арифметического кодирования. Пусть требуется закодировать сообщение S = «bab!». Известен первичный алфавит символов
{a, b, !}, но неизвестны вероятности их использования.
Сопоставим каждому символу первичного алфавита его вес. Первоначально вес всех символов равен 1. Все символы располагаются в естественном порядке, например по возрастанию. Вероятность каждого символа устанавливается равной его весу, деленному на суммарный вес всех символов.
После получения очередного символа и постройки интервала для него, вес этого символа увеличивается на 1. Для того чтобы
54

обеспечить остановку алгоритма распаковки вначале сжимаемого сообщения, надо поставить его длину или ввести дополнительный символ — признак конца сообщения (в нашем случае это символ «!»). Затем, аналогичным простому арифметическому кодированию методом, выбирается число, описывающее кодирование.
Итак, на первом этапе вес символов «a», «b» и «!» одинаков и равен 1. Соответственно, вероятности использования каждого символа также одинаковы и равны 1/3. Разделим рабочий отрезок [0; 1) на три равные части длиной 1/3:
Первая часть соответствует букве «a», вторая букве «b», третья — символу «!». Первый символ сообщения S — буква
«b». Ей соответствует отрезок [1/3; 2/3). Теперь он будет новым рабочим отрезком.
Вес буквы «b» увеличивается на единицу, веса остальных символов не изменяются. Суммарный вес всех символов меняется (сейчас он равен 1 + 2 + 1 = 4). Соответственно изменяются и вероятности использования символов: символ «а» имеет вероятность 1/4, символ «b» - вероятность 2/4 или 1/2, символ «!» - вероятность 1/4. Отношение вероятностей 1:2:1.
Именно в этом отношении необходимо разделить новый рабочий отрезок (т. е. отрезок нужно разделить на 4 части длиной 1/12 каждая, по одной части отдать символам «а» и «!», две части отдать символу «b», сохранив при этом первоначальный порядок следования букв):
55