Теорема об оптимальном кодировании.

Пусть имеется распределение вероятностей Р :

; =1.

И пусть имеется префиксная схема оптимального кодирования:

={ }| .      (4) И пусть существует

=q +q , такое что .      (5)

Тогда схема кодирования:

={ ;…; ; ;…; ; ; }    (6), где = 0, = 1, 

q  , q  ,

является префиксной и оптимальной.

    

Разъяснение:

Эта теорема позволяет из оптимального кодирования алфавита, имеющего n-1 букв, составить схему оптимального кодирования для другого алфавита, имеющего n букв, если выполнено условие (5). Смысл теоремы заключается в том, что для распределения вероятностей, состоящих из двух букв, мы можем произвести оптимальное кодирование. Например. =0,6 - код 0, =0,4 - код 1     

Разобьем : =0,3+0,3. каждое из слагаемых поместим в нижнюю часть распределения вероятностей, а имеющемуся коду первой буквы припишем 0 и 1. Получим оптимальную схему кодирования:.

                 =0,4 1

                 =0,3 00

                 =0,3 01.

Далее, продолжая разбивать вероятность р₁ = 0,25+0,15, получим новую схему оптимального кодирования

                 =0,3     00

             =0,3     01

                 =0,25   10

                  Р₄ =0,15  11. и т.д.

     Замечание:

Не всякая вероятность может быть разбита на два слагаемых, удовлетворяющих условию (5). Например:

=0,6; =0,2; =0,2;

 не разбивается на два слагаемых, каждое из которых < 0,2.

Доказательство теоремы:

Схема кодирования (4) – префиксная. Цена кодирования

C = l +…+ .

Схема (6) тоже будет префиксной по построению.

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

C = l +…+ + +…+ +q | |+q | | =

= l +…+ + q ( +1) + q ( +1) =

= l +…+ + (q +q ) +q +q =          = l +…+ + + =C + .

Рассмотрим теперь схему оптимального кодирования

={ }| = { ;…; }              (7),

 в которой = q , =q , = q +q .

 По лемме 2 = 0, = 1

={ ;…; ; ; ;…; }, следовательно, C = C +             (8), если

= q +q .               (9)

Так как схема C  - схема оптимального кодирования, то

 C  C       (10).

Получим C = C +  и в силу неравенства (10):

C = C + C + = C . Так как - оптимальна, то оптимальна и .

Что и требовалось доказать.

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

Пусть имеются распределения вероятностей

   (1),     =1,

 

Положим = +  и поместим  в соответствующее место (чтобы условие (1) выполнялось) распределения вероятностей и запомним позицию.

…….

…….                  (2)

Сложим последние две вероятности = +  и поместим его в соответствующее место распределения   и запомним это место. Получили новое распределение. Здесь складываем последние две вероятности и помещаем в соответствующее место, и так далее, пока не получим две вероятности. Назначаем первой букве код 0, а второй 1. Если первая вероятность является суммой, то исключаем ее из распределения, код ее опускаем на второе и третье место (подняв код второй вероятности на первое место) и приписываем 0 и1. Новая первая вероятность – сумма? Да. Все нижние вероятности сдвигаем вверх, вместе с кодами, а код являющейся суммой опускаем вниз на две последние строчки, приписав ему ноль в предпоследней строчке и 1 в последней.

 Если вероятность первой строки не является суммой, то код первой букве назначен, и мы переходим ко второй вероятности. Разбиваем её и переносим код вниз с приписыванием 0 и 1. И так до тех пор, пока не исчерпаем все суммы.  

Пример.

   вероятности   

 11  12  13 14   15  16   17 18        19   

0,25 0,25 0,25 0,25 0,25 0,25 0,290,460,64          

0,15 0,15 0,15 0,15 0,220,24 0,25 0,29 0,46     

0,12 0,12 0,120,14 0,15 0,22 0,24 025       

0,11 0,11   0,12 0,12 0,14 0,15 0,22       

0,08 0,11 0,11 0,12 0,12 0,14            

0,06 0,08 0,08 0,11 0,11                            

0,06    0,06 0,06 0,08      

0,06    0,06 0,06   

0,06 0,06        

0,05   

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

 Перейдем к назначению кодов. Столбец 19 содержит две вероятности, поэтому оптимальными будут коды длиной 1 (столбец 28).

Коды

28 27 26   25      24           23         22        21

0 1    00   01       01      01          01        01

1 00 01   10       11      11          11        11

  01 10   11       000    001        100      100

           11   000     001    100        101      0000

                        001     100    101         0000   0001

                                        101    0000       0001   0010

                                                        0001      0010   0011

                                                                           0011   1010

                                                                                           1011

В первой строке 19 столбца вероятность подчеркнута. Это значит, что она является суммой. Разбиваем ее на два слагаемых и получаем 18 столбец.

Первый код столбца 28 опускаем в две строчки, следующие за последней, и приписываем 0 в одной строке и 1 в другой. Поднимем все строки вверх. Получим  коды (столбец 27)  для распределения 18 столбца.

В первой строке 18 столбца вероятность подчеркнута. Это значит, что она является суммой. Разбиваем ее на два слагаемых и получаем 17 столбец.

Первый код столбца 27 опускаем в две строчки, следующие за последней, и приписываем 0 в одной строке и 1 в другой. Поднимем все строки вверх. Получим  коды (столбец 26)  для распределения 17 столбца.

В первой строке 17 столбца вероятность подчеркнута. Это значит, что она является суммой. Разбиваем ее на два слагаемых и получаем 17 столбец.

Первый код столбца 26 опускаем в две строчки, следующие за последней, и приписываем 0 в одной строке и 1 в другой. Поднимем все строки вверх. Получим  коды (столбец 25) для  распределения 16 столбца.

В 16 столбце подчеркнута вторая вероятность. Это значит, что она является суммой. Разбиваем  ее на  два  слагаемых и  получаем    15 столбец.

Первый код столбца 25 уже назначен, поэтому мы его не трогаем, а опускаем второй в две строчки, следующие за последней, и приписываем 0 в одной строке и 1 в другой. Поднимем все строки ниже первой вверх. Получим коды (столбец 24) для распределения 15 столбца.

Продолжая в том же духе, получим 21-ый столбец кодов, соответствующих распределению 11 столбца, т.е. исходному распределению.