6.2.4. Оптимальное кодирование

Оптимальное кодирование обладает определенными свойствами, которые можно использовать для его построения.

ЛЕММАПусть-схема оптимального кодирования для распределения вероятностей . Тогда еслиp_i>p_j, то .

Доказательство

От противного. Пусть i<j,p_i>p_jиl_i>l_j. Тогда рассмотрим

Имеем:

что противоречит тому, что оптимально.

Таким образом, не ограничивая общности, можно считать, что .

ЛЕММА

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

Доказательство

От противного

1. Пусть кодовое слово максимальной длины одно и имеет вид , гдеb=0Vb=1. Имеем:. Так как схема префиксная, то словане являются префиксами. С другой стороны,не является префиксом слов, иначе было бы, а значит,было бы префиксом. Тогда схематоже префиксная, причем, что противоречит оптимальности.

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

ТЕОРЕМА Если - схема оптимального префиксного кодирования для распределения вероятностейи, причем

,

то кодирование со схемой

является оптимальным префиксным кодированием для распределения вероятностей P_n=p₁,…,p_j-1,p_j+1,…,p_n-1,q’,q’’.

Доказательство

1. Если было префиксным, тотоже будет префиксным по построению.

2. 

3. Пусть схема оптимальна дляP_n. Тогда по предшествуюещй лемме. Положими рассмотрим схему, гдеj определено так, чтобы.

4. 

5. - префиксное, значит тоже префиксное.

6. - оптимально, значит,.

7. , но - оптимально, значит оптимально.

6.2.5. Алгоритм Хаффмана

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

Алгоритм 6.2. Построение оптимальной схемы – рекурсивная процедураHuffman

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

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

ifn=2then

C[1, 1] := 0;l[1] := 1; { первый элемент }

C [2, 1] := 1; l[2] := 1; { Второй элемент }

else

q:=P[n-1]+P[n] { сумма двух последних вероятностей }

j:=Up(n,q) { поиск места и вставка суммы }

Huffman(P,n-1) { рекурсивный вызов }

Down(n,j) { достраивание кодов }

Endif

Функция Upнаходит в массивеPместо, в котором должно находиться числоq(см. предыдущий алгоритм) и вставляет это число, сдвигая вниз остальные элементы.

Вход: n– длина обрабатываемой части массиваp,q– вставляемая сумма.

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

for I from n-1 downto 2 do

if P [i-1] <= q then

P[i] :=P[i-1] { сдвиг элемента массива }

else

j:=i-1 { определение места вставляемого элемента }

exitforI{ все сделано – цикл не нужно продолжать }

end if

end for

P[j] := q;

return j

Процедура Downстроит оптимальный код дляnбукв на основе построенного оптимального кода дляn-1 буквы. Для этого код буквы с номеромjвременно исключается из массиваCпутем сдвига вверх кодов букв с номерами, большимиj, а затем в конец обрабатываемой части массива С добавляется пара кодов, полученных из кода буквы с номеромjудлинением на 0 и 1, соответственно. ЗдесьC[I,*] означает вырезку из массива, то естьi-ю строку массива С.

Вход: n– длина обрабатываемой части массиваP,j– номер «разделяемой» буквы.

Выход: оптимальные коды в первыхnэлементах массивов С иl.

c:=C[j, *] { запоминание кода буквыj}

l:=l[j] { и длины этого кода }

for i from j to n-2 do

C[I,*]:=C[i+1,*] { сдвиг кода }

l[i] :=l[i+1] { и его длины }

endfor

C[n-1,*]:=c;C[n,*] :=c{ копирование кода буквыj}

C[n-1,l+1]:=0;C[n,l+1] := 1 { наращивание кодов }

L[n-1] :=l+1;l[n] :=l+1 { и увеличение длин }

Обоснование

Для пары букв при любом распределении вероятностей оптимальное кодирование очевидно: первой букве нужно назначить код 0, а второй – 1. Именно это и делается в первой части оператора ifосновной процедурыHuffman. Рекурсивная часть алгоритма в точности следует доказательству теоремы предыдущего подраздела. С помощью функцииUpв исходном упорядоченном массивеPотбрасываются две последние (наименьшие) вероятности, и их сумма вставляется в массивP, так чтобы массив (на единицу меньшей длины) остался упорядоченным. Заметим, что при этом место вставки сохраняется в локальной переменнойj. Так происходит до тех пор, пока не останется массив их двух элементов, для которого оптимальный код известен. После этого в обратном порядке строятся оптимальные коды для трех, четырех и т. д. элементов. Заметим, что при этом массив вероятностей Р уже не нужен – нужна только последовательность номеров кодов, которые должны быть изъяты из массива кодов и продублированы в конце с добавлением разряда. А эта последовательность храниться в экземплярах локальной переменнойj, соответствующих рекурсивным вызовам процедурыHuffman.