ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 9357
Скачиваний: 24
91
составляет 0.5 * 1 + 0.5 * 2 = 1.5, а при распределении вероятно-
стей <0.9, 0.1> она равна 0.9 * 1 + 0.1 * 2 = 1.1.
Обозначим
)
(
inf
:
)
(
*
P
l
P
l
σ
σ
=
,
i
p
i
n
p
1
min
*
−
=
,
(
)
[
]
1
1
log
:
2
+
−
=
n
L
.
Очевидно, что всегда существует разделимая схема
n
i
i
i
a
1
=
→
=
β
σ
, такая что
∀ i |β
i
| = L. Такая схема называется
схемой
равномерного
кодирования. Следовательно, 1
≤ l
*
(P)
≤ L и
достаточно учитывать только такие схемы, для которых
∀i p
i
l
i
.
≤ L,
где l
i
– целое и l
i
≤ L/p
*
. Таким образом, имеется лишь конечное
число схем
σ
, для которых l
*
(P)
≤
l
σ
(P)
≤ L. Следовательно, суще-
ствует схема
σ
*
, на которой инфимум достигается: 1
σ
*
(
Р
) =
=1
*
(
Р
).
Алфавитное (разделимое) кодирование и
σ
*
, для которого
l
σ
*
(P) = l
*
(P), называется кодированием с
минимальной
избыточ
-
ностью
, или
оптимальным
кодированием, для распределения ве-
роятностей
Р
.
Алгоритм Фано
Следующий рекурсивный алгоритм строит разделимую
префиксную схему алфавитного кодирования, близкого к опти-
мальному.
Алгоритм 1. Построение кодирования, близкого к опти-
мальному
Вход:
Р
:
array
[l..n]
of real
– массив вероятностей появле-
ния букв в сообщении, упорядоченный по невозрастанию;
1
≥ Р[1] ≥ …≥ Р[n] > 0, Р[1] +…+ Р[п] = 1.
Выход:
С
:
array
[l..n, 1..L]
of
0..1 – массив элементарных
кодов.
Fano(l,n, 0) { вызов рекурсивной процедуры Рано }
Основная работа по построению элементарных кодов вы-
полняется следующей рекурсивной процедурой Fano.
92
Вход: b – индекс начала обрабатываемой части массива
Р
,
е
–
индекс конца обрабатываемой части массива
Р
, k – длина уже по-
строенных кодов в обрабатываемой части массива
С
.
Выход: заполненный массив
С
.
if
е
> b
then
k: = k + 1 { место для очередного разряда в коде }
т
: = Med(b,
е
) { деление массива на две части }
for
i
from
b
to
e
do
С
[i,k]: =i >
т
{ в первой части добавляем 0, во второй – 1 }
end for
Fano(b,
т
, k) { обработка первой части }
Fano (m + 1,
е
, k) { обработка второй части }
end if
Функция Med находит
медиану
указанной части массива
Р
[b..
е
], то есть определяет такой индекс
т
(b
≤
т
<
е
), что сумма
элементов
Р
[b..
т
] наиболее близка к сумме элементов P[m + 1..e].
Вход: b – индекс начала обрабатываемой части массива
Р
,
е
–
индекс конца обрабатываемой части массива Р.
Выход: m – индекс медианы, то есть
[ ]
[ ]
∑
∑
+
=
=
−
∈
−
e
m
i
m
b
i
e
b
m
i
P
i
P
1
1
..
min
.
S
b
: = 0 { сумма элементов первой части }
for
i
from
b
to
e – 1
do
S
b
: = S
b
+ P[i] { вначале все, кроме последнего }
end for
S
e
: = P[e] { сумма элементов второй части }
m: = e { начинаем искать медиану с конца }
repeat
d: = S
b
– S
e
{ разность сумм первой и второй части }
m : =
т
– 1 { сдвигаем границу медианы вниз }
S
b
: = S
b
– P[m]; S
e
: = Se + P[m]
until
|S
b
–S
e
|
≥ d
return
m.
Обоснование
При каждом удлинении кодов в одной части коды удлиня-
ются нулями, а в другой – единицами. Таким образом, коды од-
93
ной части не могут быть префиксами другой. Удлинение кода за-
канчивается тогда и только тогда, когда длина части равна 1, то
есть остается единственный код. Таким образом, схема по по-
строению префиксная, а потому разделимая.
Пример
Коды, построенные алгоритмом Фано для заданного распре-
деления вероятностей (
п
= 7).
p
i
C[i] l
i
0.20 00
2
0.20 010 3
0.19 011 3
0.12 100 3
0.11 101 3
0.09 110 3
0.09 111 3
l
σ
(P)
2.80
Оптимальное кодирование
Оптимальное кодирование обладает определенными свойст-
вами, которые можно использовать для его построения.
ЛЕММА. Пусть
n
i
i
i
a
1
=
→
=
β
σ
–
схема
оптимального
ко
-
дирования
для
распределения
вероятностей
Р
=
р
1
≥ …≥
р
п
> 0.
Тогда
,
если
р
i
> p
j
,
то
l
i
≤ l
j
.
Таким образом, не ограничивая общности, можно считать,
что l
1
≤ … ≤1
п
.
ЛЕММА.
Если
n
i
i
i
a
1
=
→
=
β
σ
–
схема
оптимального
пре
-
фиксного
кодирования
для
распределения
вероятностей
Р
=
=
р
1
≥ …≥
р
п
> 0,
то
среди
элементарных
кодов
,
имеющих
мак
-
симальную
длину
,
имеются
два
,
которые
различаются
только
в
последнем
разряде
.
94
ТЕОРЕМА. Если
1
1
1
−
=
−
→
=
n
i
i
i
n
a
β
σ
–
схема
оптимального
префиксного
кодирования
для
распределения
вероятностей
Р
=
=
р
1
≥ …≥
р
п–1
> 0.
и
p
j
= q’+ q’’,
причем
р
1
≥ …≥
р
j–1
≥
р
j+1
≥ …≥
р
п–1
≥ q’≥ q’’ > 0,
то
кодирование
со
схемой
1
,
0
,
,...,
,
,...,
1
1
1
1
1
1
1
1
j
n
j
j
n
n
j
j
j
j
n
a
a
a
a
a
a
β
β
β
β
β
β
σ
→
→
→
→
→
→
=
−
−
=
=
−
−
является
оптимальным
префиксным
кодированием
для
распреде
-
ления
вероятностей
P
n
=p
1
,...,p
j–1
, p
j+1
,...,p
n–1
, q’,q’.’
Алгоритм Хаффмена
Следующий рекурсивный алгоритм строит схему оптималь-
ного префиксного алфавитного кодирования для заданного рас-
пределения вероятностей появления букв.
Алгоритм 2.
Построение оптимальной схемы – рекурсивная
процедура Huffman.
Вход: п
– количество букв,
Р
:
array
[l..n]
of real
– массив
вероятностей букв, упорядоченный по убыванию.
Выход: С
:
array
[l..n, 1..L]
of
0..1 – массив элементарных
кодов, d :
array
[l..n] of 1..L – массив длин элементарных кодов
схемы оптимального префиксного кодирования.
if п
= 2
then
С
[1,1]: = 0; d[1]: = 1{ первый элемент }
С
[2, 1]: = 1; d[2]: = 1{ второй элемент }
else
q: =
Р
[
п
– 1] +
Р
[
п
] { сумма двух последних вероятностей }
j : = Up(n, q) { поиск места и вставка суммы }
Huffman (P, n – 1) { рекурсивный вызов }
Down (n, j) { достраивание кодов }
end if
Функция Up находит в массиве
Р
место, в котором должно
находиться число q (см. предыдущий алгоритм) и вставляет это
число, сдвигая вниз остальные элементы.
Вход: n – длина обрабатываемой части массива
Р
, q – встав-
ляемая сумма.
Выход: измененный массив
Р
.
95
for
i
from
n – 1
downto
2
do
if
P[i – 1]
≤ q
then
P[i]: = P[i – 1]{ сдвиг элемента массива }
else
j : =i – l { определение места вставляемого элемента }
exit for
i { все сделано – цикл не нужно продолжать }
end if
end for
P[j] := q { запись вставляемого элемента }
return
j
Процедура Down строит оптимальный код для
п
букв на ос-
нове построенного оптимального кода для
п
– 1 буквы. Для этого
код буквы с номером j временно исключается из массива
С
путем
сдвига вверх кодов букв с номерами, большими j, а затем в конец
обрабатываемой части массива
С
добавляется пара кодов, полу-
ченных из кода буквы с номером j удлинением на 0 и 1, соответ-
ственно. Здесь С [i,*] означает вырезку из массива, то есть i-ю
строку массива
С
.
Вход:
п
– длина обрабатываемой части массива
Р
, j – номер
«разделяемой» буквы.
Выход: оптимальные коды в первых n элементах массивов
С
и d.
с
: = C[j, *]{ запоминание кода буквы j }
l: = d[j] { и длины этого кода }
for
г
from
j
to
n – 2
do
C [i, *]: = C[i + 1, *]{ сдвиг кода }
d [i] := d [i + 1] { и его длины }
end for
C[n – 1, *]: = c; C[n, *]: = c { копирование кода буквы j }
C[n – 1,l + 1]: = 0; C[n, l + 1]: = 1{ наращивание кодов }
d[n – 1]: = / + 1; d[n] : = l + 1{ и увеличение длин }
Обоснование
Для пары букв при любом распределении вероятностей оп-
тимальное кодирование очевидно: первой букве нужно назначить
код 0, а второй – 1. Именно это и делается в первой части опера-