Алгоритм Фано для префиксного кодирования.

Пусть кодируемое сообщения таково, что известны вероятности вхождения каждого символа, причем   ( 1), причем =1         (2)

То есть прежде чем производить кодирование, необходимо расположить буквы алфавита А так, чтобы удовлетворялось условие (1). Затем проверить равенство (2), после чего назначать коды.

Итак, имеем

 = 0,…

 = 0,…

….

= 0,….

….

 

=1

Алгоритм.

Разобьем вероятности на две части так, чтобы суммы вероятностей каждой из частей были примерно равны. Пусть это будет после  вероятности: . Назначим коды: в верхней части 0, а в нижней 1. Теперь разбиваем верхнюю часть на две части, с примерно равными суммами вероятности: . И вновь делаем то же самое: для данного деления: к имеющимся кодам добавляем в верхней части 0, а в нижней 1 и так далее до тех пор, пока в верхней части не останется одна строка. Добавим в нее 0, а в нижнюю часть 1. Последнюю нижнюю часть опять разбиваем на две части (если она содержит более одной строки) и так далее, пока в нижней части не останется одна строка. После этого переходим к делению предыдущей нижней части.

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

Пример: пусть заданы вероятности

0,25 0,15 0,112 0,11   0,08 0,06 0,06 0,06 0,06 0,05.   

После первого разбиения получим

   вероят-

   ности коды

     0,25 0   

      0,15 0   

0,12 0    

     0,11 1    

     0,08 1    

     0,06 1    

      0,06 1          

      0,06 1

      0,06 1    

      0,05 1  

после второго разбиения

    вероят

   ности ти коды

0,25 0 00 код назначен

      0,15 0 01    

0,12 0 01    

     0,11 1           

     0,08 1          

     0,06 1          

     0,06 1          

     0,06 1    

     0,06 1    

     0,05 1    

 

После третьего разбиения

0,25 0 00    

0,15 0 01 010 код назначен

0,12 0 01 011 код назначен

     0,11 1                

      0,08 1          

     0,06 1          

     0,06 1          

     0,06 1      

     0,06 1    

     0,05 1        

После четвертого разбиения

 

0,25 0 00 00       

 0,15 0 01 010     

0,12 0 01 011     

     0,11 1 1  10           

     0,08 1 1  10         

0,06 1 1  10     

     0,06 1 1  11       

       0,06 1 1  11             

     0,06 1 1  11             

     0,05 1 1  11       

 

Окончательно получим:

0,25 0 00     

0,15 0 01 010      

0,12 0    01 011            

0,11 1 1  10   100             

0,08 1 1  10   101 1010    

0,06 1 1  10   101 1011    

0,06 1 1  11   11   11      110   1100      

0,06 1 1  11   11   11     110   1101      

0,06 1 1  11   11   11     111   111     1110

     0,05 1 1  11   11    11      111  111      1111

 

Если кодирование равномерное, то цена кодирования по формуле Хартли равна:       = log 10 4. По алгоритму Фано: = =3,12, что меньше 4, а значит, общая длина кода будет меньше.

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

При использовании кодирования по алгоритму Фано мы получаем некоторую цену кодирования. Так как разбиение на две части неоднозначно, то цена кодирования может меняться, то есть является некоторой функцией длины элементарных кодов. А так как эта цена кодирования конечна, то она имеет наименьшее значение. Кодирование, при котором цена кодирования имеет наименьшее значение, называется оптимальным. Т.к. число вариантов кодирования конечно, то оптимальное кодирование существует.

Таким образом, алгоритм Фано дает кодирование близкое к оптимальному.

 Рассмотрим несколько вопросов, относящихся к оптимальному кодированию.

Лемма 1. Пусть имеется распределение вероятностей   1) и оптимальная схема кодирования ={ }| .     (2)

Тогда для любого j>i имеем: .

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

Пусть существует такое j, что > , а < . Тогда < . Взяв = , получим, что

={ ;… ;… } и С <C , что противоречит оптимальности кодирования. Значит наше предположение неверно и .

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

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

Допустим, что код максимальной длины один. По лемме 1 = 0 или = 1. Если  - префикс, то найдется такое j, что = . Это значит, что  - префикс . А это невозможно, так как кодирование префиксное.  - не префикс, следовательно, оно может быть включено в схему кодирования:

={ ;… ;… }. Так как | |< , то | |< . Следовательно, С <C . А это противоречит оптимальности.

Докажем теперь, что два кода наибольшей  длины отличны только лишь в последнем разряде:

Пусть = , = , . Ни один из элементарных кодов не может быть префиксом , и так как он не префикс, то его можно выбрать в качестве элементарного кода: | |<  и тогда , совпадающая с  до (n-1) кода, и в которой n – ый код равен  Получим: ={ ;…, ; }. Эта схема имеет цену кодирования С <C , так как | |< . А это противоречит оптимальности. Значит наше предположение неверно и два кода наибольшей длины отличны только лишь в последнем разряде.