Префиксный код Шеннона – Фано

Данный вариант кодирования был предложен в 1948 – 49 гг. независимо Р. Фано и К. Шенноном. Рассмотрим его на примере.

Пусть имеется первичный алфавит А, состоящий из 6 знаков (а1, … а6) с вероятностями появления (0.30, 0.20, 0.20, 0.15, 0.10, 0.05) соответственно. Расположим эти знаки в таблице в порядке уменьшения вероятностей. Разделим на 2 группы таким образом, чтобы суммы вероятностей в каждой из них были примерно равными (таблица 4.2), шаг 1.

Таблица 4.2 Код Шеннона-Фано

В нашем примере в первую группу попадут а1, а2 (сумма вероятностей 0.5), во вторую – все остальные символы. Первый знак кода для 1-ой группы будет «0», для второй – «1».

Продолжим деление каждой из групп на подгруппы по этой же схеме (т.е., чтобы суммы вероятностей на каждом шаге в соседних подгруппах были бы возможно более близкими). Окончательные коды приведены в таблице 3.1 в последнем столбце.

Из процедуры построения кодов легко видеть, что они удовлетворяют условию Фано, и код является префиксным.

Средняя длина кода равна:

2*(0.30+0.20+0.20)+3*0.15+4*(0.10+0.05)=2.45.

Среднее количество информации на знак

I = - =2.390.

Избыточность данного кода:

= =0.0249 (всего 2.5%!).

Применительно к русскому языку такой код дает избыточность 0.0147%!

Однако данный код не является оптимальным, так как вероятности знаков (0 и 1) не одинаковы - и соответственно.