6.2. Кодирование с минимальной избыточностью

Для практики важно, чтобы коды сообщений имели по возможности наименьшую длину. Алфавитное кодирование пригодно для любых сообщений, то есть S=A^*. Если больше про множествоSничего не известно, то точно сформулировать задачу оптимизации затруднительно. Однако на практике часто доступна дополнительная информация. Например, для текстов на естественных языках известно распределение вероятности появления букв в сообщении. Использование такой информации позволяет строго поставить и решить задачу построения оптимального алфавитного кодирования.

6.2.1. Минимизация длины кода сообщения

Если задана разделимая схема алфавитного кодирования , то любая схема, гдеявляется перестановкой, также будет разделимой. Если длины элементарных кодов равны, то перестановка элементарных кодов в схеме не влияет на длину кода сообщения. Но если длины элементарных кодов различны то длина кода сообщения зависит от состава букв в сообщении и от того, какие элементарные коды каким буквам назначены.

Если заданы конкретное сообщение и конкретная схема кодирования, то нетрудно подобрать такую перестановку элементарных кодов, при которой длина кода сообщения будет минимальна.

Пусть k₁,…,k_n– количества вхождений буквa_1,...,a_nв сообщениеS,аl₁,…,l_n– длины элементарных кодов, соответственно. Тогда, еслии, то. Действительно, пустьk_j=k+a,k_i=kиl_j=l,l_i=l+b, гдеa,b0. Тогда

Отсюда вытекает алгоритм назначения элементарных кодов, при котором длина кода конкретного сообщения Sбудет минимальна: нужно отсортировать буквы в порядке убывания количества вхождений, элементарные коды отсортировать в порядке возрастания длины и назначить коды буквам в этом порядке.

ЗАМЕЧАНИЕ

Этот простой метод решает задачу минимизации длины кода только для фиксированного сообщения Sи фиксированной схемы.

6.2.2. Цена кодирвания

Пусть заданы алфавит и вероятности появления букв в сообщении(p_i– вероятность появления буквыa_i). Не ограничивая общности, можно считать, чтоp_i+…+p_n=1 и(то есть можно сразу исключить буквы, которые не могут появиться в сообщении, и упорядочить буквы по убыванию вероятности их появления).

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

, где

и называется средней ценой (илидлиной) кодированияпри распределении вероятностейP.

Пример

Для разделимой схемы А={a,b},B={0,1}, при распределении вероятностейцена кодирования составляет 0.5*1+0.5*2=1.5, а при распределении вероятностейона равна 0.9*1+0.1*2=1.1.

Обозначим

Очевидно, что всегда существует разделимая схема , такая что. Такая схема называется схемойравномерного кодироваия. Следовательно,и достаточно учитывать только такие схемы, для которых, гдеl_iцелое и. Таким образом, имеется лишь конечное число схем, для которых. Следовательно, существует схема, на которой инфимум достигается:

Алфавитное (разделимое) кодирование , для которого, называется кодированием сминимальной избыточностью, или оптимальным кодированием, для распределения вероятностейP.

6.2.3. Алгоритм Фано

Следующий рекурсивный алгоритм строит разделимую префиксную схему алфавитного кодирования, близкого к оптимальному.

Алгоритм 6.1. Построение кодирования, близкого к оптимальному

Вход:P:array[1..n]ofreal– массив вероятностей появления УКВ в сообщении, упорядоченный по невозрастанию;.

Выход:C:array[1..n, 1..L]of0..1 – массив элементархых кодов.

Fano(1,n, 0) { вызов рекурсивной процедурыFano}

Основная работа по построению элементарных кодов выполняется следующей рекурсивной процедурой Fano.

Вход:b– индекс начала обрабатываемой части массиваP, е – индекс конца обрабатываемой части массиваP, к – длина уже построенных кодов в обрабатываемой части массива С.

Выход: заполненный массив С.

ife>bthen

k:=k+1 { место для очередного разряда в коде }

m:=Med(b,e) { деление массива на две части }

for I from b to e do

C[i,k] :=I>m{ в первой части добавляем 0, во второй - 1 }

endfor

Fano(b,m,k) { обработка первой части }

Fano(m+1,e,k) { обработка второй части }

end if

Функция Medнаходитмедиану указанной части массиваP[b..e], то есть определяет такой индексm(), что сумма элементовP[b..m] наиболее близка к сумме элементовP[m+1..e].

Вход: b– индекс начала обрабатываемой части массиваP,e– индекс концап обрабатываемой части массиваP.

Выход: m– индекс медианы, то есть

S_b:= {сумма элементов первой части }

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:=m-1 { сдвигаем границу медианы вниз }

S_b:=S_b-P[m];

S_e:=S_e+P[m]

until |S_b-S_e|d

return m

Обоснование

При каждом удлинении кодов в одной части коды удлиняются нулями, а в другой – единицами. Таким образом, коды одной части не могут быть префиксами другой. Удлинение кода заканчивается тогда и только тогда, когда длина части равна 1, то есть остается единственный код. Таким образом, схема по построению префиксная, а потому разделимая.

Пример

Коды, построенные алгоритмом Фано для заданного распределения (n=7).

pi	C[i]	li
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
		2.80