Пример
2. Закодируем буквы алфавита из примера 1 в
коде Шеннона-Фано.
Все
буквы записываются в порядке убывания их
вероятностей, затем делятся на
равновероятные группы, которые
обозначаются 0 и 1, затем вновь делятся на
равновероятные группы и т.д. (см.табл.4.1)
Таблица
4.1.
| X |
P |
|
|
|
|
Коды |
| x1 |
1/4 |
0 |
0 |
------- |
------- |
00 |
| x2 |
1/4 |
1 |
------- |
------- |
01 |
|
| x3, |
1/8 |
|
0 |
0 |
------- |
100 |
| x4 |
1/8 |
1 |
------- |
101 |
||
| x5 |
1/16 |
1 |
0 |
0 |
1100 |
|
| x6 |
1/16 |
1 |
1101 |
|||
| x7 |
1/16 |
1 |
0 |
1110 |
||
| x8 |
1/16 |
1 |
1111 |
Средняя длина полученного кода будет равна
Итак, мы получили
оптимальный код. Длина этого кода совпала с
энтропией. Данный код оказался удачным, так
как величины вероятностей точно делились
на равновероятные группы.
Пример 3.
Возьмем 32 две буквы русского алфавита. Частоты этих букв известны. В алфавит включен и пробел, частота которого составляет 0,145. Метод кодирования представлен в таблице 4.2.
Таблица
4.2.
| Буква |
Рi |
1 |
2 |
3 |
4 |
Код |
| ب |
0.145 |
|
0 |
0 |
- |
000 |
| о |
0.095 |
1 |
- |
001 |
||
| е |
0.074 |
1 |
0 |
0 |
0100 |
|
| а |
0.064 |
1 |
0101 |
|||
| и |
0.064 |
1 |
0 |
0110 |
||
| н |
0.056 |
1 |
0111 |
|||
| т |
0.056 |
1 |
0 |
0 |
- |
|
| с |
0.047 |
1 … |
0 … |
|
||
| ... |
… |
|||||
| ф |
0.03 |
Средняя
длина данного кода будет равна,
бит/букву;
Энтропия
H=4.42
бит/буква.
Эффективность полученного кода можно
определить как отношение энтропии к
средней длине кода. Она равна 0,994. При
значении равном единице код является
оптимальным. Если бы мы кодировали кодом
равномерной длины
, то эффективность была бы значительно ниже.
