ЛЕКЦИЯ 22
МЕТОДЫ ЭФФЕКТИВНОГО КОДИРОВАНИЯ
22.1 Префиксные коды
Код Хаффмена
22.3 Код Шеннона-Фано
22.4. Неравномерное кодирование для последовательности сообщений
22.5. Арифметическое кодирование
22.6 Словарные методы сжатия
22.1 Префиксные коды
Простейшими кодами, на основе которых может выполняться сжатие данных, являются коды без памяти. В коде без памяти
каждый символ в кодируемом векторе данных заменяется кодовым словом из префиксного множества двоичных
последовательностей или слов.
Префиксным множеством двоичных последовательностей
S
называется конечное множество двоичных последовательностей,
таких, что ни одна последовательность в этом множестве не является префиксом, или началом, никакой другой
последовательности в
S
.
К примеру, множество двоичных слов
S1 = {00, 01, 100, 110, 1010, 1011 }
является префиксным множеством двоичных
последовательностей, поскольку, если проверить любую из возможных совместных комбинаций (
wi wj
) из
S1,
то видно, что
wi
никогда не явится префиксом (или началом)
wj
. С другой стороны, множество
S2 = { 00, 001, 1110 }
не является префиксным
множеством двоичных последовательностей, так как последовательность 00 является префиксом (началом) другой
последовательности из этого множества - 001.
Таким образом, если необходимо закодировать некоторый вектор данных
X
=
( x1, x2,… xn )
с алфавитом данных А размера
N
,
то кодирование кодом без памяти осуществляется следующим образом:
-
составляют полный список символов
a1, a2, aj ... ,aN
алфавита А, в котором
aj
-
j
-й по частоте появления в
X
символ,
то есть первым в списке будет стоять наиболее часто встречающийся в алфавите символ, вторым – реже встречающийся и
т.д.;
-
каждому символу
aj
назначают кодовое слово
wj
из префиксного множества двоичных последовательностей
S
;
-
выход кодера получают объединением в одну последовательность всех полученных двоичных слов.
Формирование префиксных множеств и работа с ними – это отдельная серьезная тема из теории множеств, выходящая за
рамки нашего курса, но несколько необходимых замечаний все-таки придется сделать.
Если
S
= {
w1, w2, ... , wN
} - префиксное множество, то можно определить некоторый вектор
(
)
N
m
m
m
S
,...,
,
)
(
2
1
=
n
,
состоящий из чисел, являющихся длинами соответствующих префиксных последовательностей (
mi
- длина
wi
).
Вектор
(
)
N
m
m
m
S
,...,
,
)
(
2
1
=
n
, состоящий из неуменьшающихся положительных целых чисел, называется вектором
Крафта. Для него выполняется неравенство
1
2
2
...
2
2
1
2
1
Ј
=
-
+
+
-
+
-
е
=
-
N
i
m
i
N
m
m
m
.
(22.1)
Это неравенство называется неравенством Крафта. Для него справедливо следующее утверждение: если
S
- какое-либо
префиксное множество, то
v(S)
- вектор Крафта.
Иными словами, длины двоичных последовательностей в префиксном множестве удовлетворяют неравенству Крафта
.
Если неравенство (22.1) переходит в строгое равенство, то такой код называется компактным и обладает наименьшей среди
кодов с данным алфавитом длиной, то есть является оптимальным.
Ниже приведены примеры простейших префиксных множеств и соответствующие им векторы Крафта:
S1
= {0, 10, 11}
и v(S1)
= ( 1, 2, 2 );
S2 =
{0, 10, 110, 111}
и
v(S2)
= ( 1, 2, 3, 3
);
S3 =
{0, 10, 110, 1110, 1111}
и
v(S3)
= ( 1, 2, 3, 4, 4 )
;
S4
= {0, 10, 1100, 1101, 1110, 1111}
и
v(S4)
= ( 1, 2, 4, 4, 4, 4 );
S5 =
{0, 10, 1100, 1101, 1110, 11110, 11111}
и
v(S5) =
( 1, 2, 4, 4, 4, 5, 5 );
S6 =
{0, 10, 1100, 1101, 1110, 11110, 111110, 111111}
и
v(S6) =
(1,2,4,4,4,5,6,6).
Допустим мы хотим разработать код без памяти для сжатия вектора данных
X = ( x1, x2,… xN )
с алфавитом
А
размером в
N
символов. Введем в рассмотрение так называемый вектор вероятностей
(
)
N
p
p
p
P
,...,
,
2
1
=
, где
i
P
- вероятность
появления
i
-го символа из
А
в
X
или вектор
частот
F = ( f1, f2, ... , fN ),
где
fi
- количество появлений
i
-го символа из
А
в
X
.
Закодируем
X
кодом без памяти.
Длина двоичной кодовой последовательности на выходе кодера составит
е
=
=
+
+
+
=
N
i
i
i
N
N
f
m
f
m
f
m
f
m
m
1
2
2
1
1
...
,
(22.2)
а средняя длина двоичной кодовой последовательности на выходе кодера составит
. (22.3)
Лучшим кодом без памяти был бы код, для которого средняя длина
- минимальна. Для разработки такого кода нам нужно
найти вектор Крафта
,
для которого
m
была бы минимальной.
Простой перебор возможных вариантов - вообще-то, не самый лучший способ найти такой вектор Крафта, особенно для
большого
N
.
Прямая теорема неравномерного кодирования
Теорема 22.1.
Для ансамбля
{
}
)
(
,
x
P
x
X
=
с энтропией
(
)
X
H
существует побуквенный неравномерный префиксный код
со средней длиной кодовых слов
(
)
1
+
Ј
X
H
m
.
(22.4)
Обсудим полученную оценку длины кодовых слов. Мы знаем, что дости­жимая скорость кодирования примерно равна энтропии.
Теорема гарантирует, что средняя длина слов хорошего кода отличается от энтропии не более чем на 1. Ес­ли энтропия велика,
то проигрыш по сравнению с минимально достижимой ско­ростью можно считать небольшим. Но предположим, что
(
)
1
,
0
=
X
H
. Теорема га­рантирует, что существует код со средней длиной кодовых слов не более 1,1 бита. Но нам хотелось
бы затрачивать на передачу одного сообщение примерно в 10 раз меньше бит. Этот пример показывает, что либо теорема дает
неточную оценку, либо побуквенное кодирование в этом случае не эффективно.
На этом же примере мы убедимся в том, что теорема достаточно точна и ее результат не может быть улучшен, если не
использовать никакой дополнительной информации об источнике. Действительно, предположим, что дан двоичный ис­точник
Х=
{0,1} с вероятностями букв
{
}
e
e
-
1
,
. Минимально достижимая длина кодовых слов наилучшего кода, очевидно, равна 1.
Теорема говорит, что средняя длина кодовых слов не больше
(
)
1
+
e
H
, т. е. стремится к 1 при
0
®
e
. Таким обра­зом, для
данного примера двоичного источника теорема верна.
Достижение скоростей (затрат на передачу одной буквы источника), мень­ших 1, невозможно при побуквенном кодировании,
поскольку длина кодового слова не может быть меньше 1. Однако переход к кодированию блоков сообще­ний решает эту
проблему и позволяет сколь угодно близко подойти к теоретическому пределу, равному энтропии
(
)
X
H
.
Конструктивным
ре­шением данной задачи является арифметическое кодирование.
Обратная теорема неравномерного кодирования
Обратная теорема неравномерного кодирования устанавливает нижнюю границу средней длины кодовых слов любого
однозначно декодируемого кода.
Теорема 22.2.
Для любого однозначно декодируемого кода дискретного источника
{
}
)
(
,
x
P
x
X
=
с
энтропией
(
)
X
H
средняя длина кодовых слов
m
соответст­вует неравенству
(
)
X
H
m
і
.
(22.5)
Иными словами, не существует кода со средней длиной кодовых слов меньше
(
)
X
H
и обладающего свойством
однозначной декодируемости.
Рассмотрим вопрос о том, при каких условиях возможно равенство в обратной теореме. Перепишем неравенство (22.5):
е
е
=
=
-
=
N
i
i
i
N
i
i
i
p
p
m
p
1
1
log
.
Для этого при каждом
x
должно выполняться соотношение
(
)
i
m
i
x
p
-
=
2
.
В то же время для такого распределения вероятностей существует полный префиксный код с длинами кодовых слов
)
(
log
i
i
x
p
m
-
=
.
Для этого кода неравен­ство Крафта преобразуется в равенство
)
(
X
H
m
=
.
Таким образом, мы установили справедливость следующего утверждения.
Следствие.
Для существования кода со средней длиной кодовых слов
)
(
X
H
m
=
необходимо, чтобы все вероятности
сообщений
X
x
i
О
имели вид
(
)
i
m
i
x
p
-
=
2
,
где
i
m
— целые положительные числа.
Код Хаффмена
Алгоритм Хаффмена, названный в честь его изобретателя - Дэвида Хаффмена, - дает нам эффективный способ поиска
оптимального вектора Крафта
для которого
– минимальна. Код, полученный с
использованием оптимального
, называют кодом Хаффмена.
Алгоритм Хаффмена
Алгоритм Хаффмена изящно реализует общую идею статистического кодирования с использованием префиксных множеств и
работает следующим образом:
1. Выписываем в ряд все символы алфавита в порядке убывания вероятности их появления в тексте.
2. Последовательно объединяем два символа с наименьшими вероятностями появления в новый составной символ. Каждому
символу из составного символа приписываем: одному «0», а второму «1». Вероятность появления составного символа
полагаем равной сумме вероятностей составляющих его символов. Составной символ переставляем в ряде в соответствии с
новой суммарной вероятностью. В конце концов построим дерево, каждый узел которого имеет суммарную вероятность всех
узлов, находящихся ниже него.
3. Прослеживаем путь к каждому листу дерева, помечая направление к каждому узлу (например, направо - 1, налево - 0) .
Полученная последовательность дает кодовое слово, соответствующее каждому символу.
Построим кодовое дерево для сообщения со следующим алфавитом табл 22.1:
Табл.22.1
объединяем Е и F как символы с наименьшими вероятностями и приписываем символу Е – «0», а F – «1». Суммарная
вероятность двух символов 0,2. Составной символ Е F переставляем в ряде в соответствии с новой суммарной вероятностью.
Продолжение табл.22.1
2) объединяем С и D как символы с наименьшими вероятностями на данном шаге и приписываем символу С – «0», а D – «1».
Суммарная вероятность двух символов 0,25. Составной символ С D переставляем в ряде в соответствии с новой суммарной
вероятностью.
Продолжение табл.22.1
3) объединяем В и Е F как символы с наименьшими вероятностями на данном шаге и приписываем символу В – «0», а Е F –
«1». Суммарная вероятность символов 0,4. Составной символ В Е F переставляем в ряде в соответствии с новой суммарной
вероятностью.
Продолжение табл.22.1
4) объединяем А и С D как символы с наименьшими вероятностями на данном шаге и приписываем символу A – «0», а С D –
«1». Суммарная вероятность символов 0,6. Составной символ А С D переставляем в ряде в соответствии с новой суммарной
вероятностью.
Продолжение табл.22.1
5) на последнем шаге объединяем А С D и B E F и приписываем символу А С D – «0», а B E F – «1». Суммарная вероятность
символов 1.
На рис.22.1 представлено дерево кода Хаффмена.
Рис. 22.1 Дерево кода Хаффмена
Избыточность кода Хаффмена
Из теоремы 22.1 следует, что для построенных по алгоритму Хаффмана кодов средняя длина кодовых слов удовлетворяет
неравенству
(
)
1
+
Ј
X
H
m
,
(22.6)
где
(
)
X
H
— энтропия ансамбля.
Разность
(
)
X
H
m
r
-
=
называется
избыточностью неравномерного кода.
При кодировании с избыточностью
r
на
каждое сообщение затрачивается на
r
бит больше, чем в принципе можно было бы потратить, если использовать теоретичес­ки
наилучший (возможно, нереализуемый) способ кодирования.
Итак, из (22.6) следует, что для кода Хаффмана избыточность г < 1. Хоте­лось бы получить более точную оценку средней длины
кодовых слов. Гораздо бо­лее точную оценку избыточности получил Р. Галлагер, наложив ограничение на максимальную из
вероятностей сообщений.
Теорема 22.3.
Пусть
1
p
— наибольшая из вероятностей сообщений конечно­го дискретного ансамбля. Тогда избыточность
кода Хаффмана для этого ансамбля удовлетворяет неравенствам:
п
о
п
н
м
і
-
-
<
+
Ј
,
2
1
)
(
2
,
2
1
1
1
1
1
1
p
при
p
p
H
p
при
p
r
s
где
)
1
log(
)
1
(
log
)
(
1
1
1
1
1
p
p
p
p
p
H
-
-
-
-
=
— энтропия двоичного ансамбля;
08607
,
0
log
log
log
1
»
-
-
=
e
e
s
.
22.3 Код Шеннона-Фано
Алгоритм Шеннона-Фано заключается в следующем.
Символы алфавита источника (первичного или укрупненного) записываются в порядке не возрас­тающих вероятностей.
Затем они разделяются на две части так, чтобы суммы вероятностей символов, входящих в каждую из таких частей, были
примерно одинаковыми. Всем символам первой части приписывается в качестве первого символа комбинации неравномерного
кода ноль, а символам второй части — единица.
Затем каждая из этих частей (если она содержит более одного сооб­щения) делится в свою очередь на две, по возможности
равновероятные части и к ним применяется то же самое правило кодирования.
Этот процесс повторя­ется до тех пор, пока в каждой из полученных частей не останется по одному сообщению.
Таблица 22.2
Буква
рi
I
II
III
IV
V
VI
Kод
mi
mi Ч pi
А
0.6
1
1
1
0.6
Б
0.2
0
1
1
011
3
0.6
В
0.1
0
010
3
0.3
Г
0.04
0
1
001
3
0.12
Д
0.025
0
1
0001
4
0.1
Е
0.015
0
1
00001
5
0.075
Ж
0.01
0
1
000001
6
0.06
З
0.01
0
000000
6
0.06
Пример
. Пусть алфавит
А
источника состоит из 8 символов
А, Б, В, Г, Д, Е,
Ж, З
с ве­роятностями
р
(
А
) = 0,6;
р
(
Б
)
=
0,2;
р
(
В
) =
0,1;
р
(
Г
) = 0,04;
р
(
Д
)=0,025;
р
(
Е
)
=
0,015,
р
(
Ж
)=0,01;
р
(
З
)
=
0,01. Про­цедура построения неравномерного кода Шеннона-Фано
задаётся в таблице 22.2.
На первом этапе производится деление на два множества
А,
и
Б, В, Г, Д, Е,
Ж, З
, так как вероятность р(А)=0,6 и сумма
вероятностей
4
,
0
01
,
0
01
,
0
015
,
0
025
,
0
04
,
0
1
,
0
2
,
0
)
(
)
(
)
(
)
(
)
(
)
(
)
(
=
+
+
+
+
+
+
+
=
+
+
+
+
+
+
З
р
Ж
р
Е
р
Д
р
Г
p
В
р
Б
p
примерно одинаковы. При этом символу
А
присваивается «1», а всем остальным
Б, В, Г, Д, Е,
Ж, З
присваивается «0».
На втором этапе производится деление второго множества на два множества
Б, В,
и
Г, Д, Е,
Ж, З
. Множеству
Б, В
присваивается «1», а множеству
Г, Д, Е,
Ж, З
присваивается «0».
Hа третьем этапе производится деление множества
Б, В,
на два множества (уже символа)
Б и В.
Символу
Б
присваивается
«1», а символу В
присваивается «0». Множество
Г, Д, Е,
Ж, З
делится на множества
Г
и
Д, Е,
Ж, З.
Символу
Г
присваивается
«1», а множеству
Д, Е,
Ж, З
присваивается «0».
На четвёртом этапе производится деление множества
Д, Е,
Ж, З
на два множества
Д
и
Е,
Ж, З.
Символу
Д
присваивается «1»,
а множеству
Е,
Ж, З
присваивается «0».
На пятом этапе производится деление множества
Е,
Ж, З
на два множества
Е
и
Ж, З.
Символу
Е
присваивается «1», а
множеству
Ж, З
присваивается «0».
На шестом этапе производится деление множества
Ж, З
на два множества
Ж
и
З.
Символу
Ж
присваивается «1», а символу
З
присваивается «0».
Легко проверить, что данный код оказывается префиксным и средняя длина кодовой комбинации
»
=
е
=
8
0
i
i
i
m
p
m
1,915, что
менее чем на 7 % превышает энтропию данного источника, равную 1,7813. A избыточность кода составит
0689
.
0
915
.
1
7813
.
1
1
»
-
=
k
r
.
Отметим, что хотя, деление на части с "примерно равными вероятностями" не является однозначной процедурой, но при
увеличении длин блоков
m
укрупнённого источника сообщений эти погрешности бу­дут сглаживаться, а средняя длина
m
m
при­ближаться к предельному значению.
22.4. Неравномерное кодирование для последовательности сообщений
Разумеется, если мы рассматриваем стационарный источ­ник и его распределение вероятностей на буквах не меняется от
буквы к букве, то любой из описанных выше способов может быть использован для кодирования отдельных сообщений
источника. Во многих случаях именно такой подход ис­пользуется на практике как самый простой и достаточно эффективный.
В то же время, можно выделить класс ситуаций, когда побуквенное кодиро­вание заведомо неоптимально. Во-первых, из
теоремы об энтропии на сообщение стационарного источника следует, что учет памяти источника потенциально мо­жет
значительно повысить эффективность кодирования. Во-вторых, побуквенные методы затрачивают как минимум 1 бит на
сообщение, тогда как энтропия на со­общение может быть значительно меньше 1.
Итак, рассмотрим последовательность
i
x
x
x
,...,
,
2
1
наблюдаемую на выходе дискретного стационарного источника, для
которого известно вероятностное описание, т.е. можно вычислить все многомерные распределения вероят­ностей и по ним —
энтропию
)
(
X
H
.
Пусть указан некий способ кодирования, который для любых
п
для каждой последовательности
n
X
x
=
r
на выходе источника
строит кодовое слово
)
(
x
c
r
r
с
длиной
)
(
x
m
r
. Тогда