6.7. Насколько плохим является кодирование Шеннона — Фано?

Поскольку кодирование Хаффмена оптимально и мы временно перешли к неоптимальному (в смысле затрат времени) кодированию Шеннона — Фано, естественно задать вопрос: «Насколько плохим является кодирование Шеннона — Фано?».

Рассмотрим следующие примеры. Для источника с алфавитом и вероятностями получает Поэтому Однако для имеем

Итак, в этом случае код Хаффмена. состоит из двух двоичных слов длины 1, а код Шеннона — Фано — из слова длины дла и слова длины

Прежде чем огорчаться из-за. малой эффективности, найдем среднюю длину кодового слова. Ясно, что для кода Хаффмена Для кода Шеннона — Фано имеем

В качестве другого примера потери эффективности рассмотрим случай, в котором все кодовые символы имеют одинаковую вероятность Код Шеннона — Фано дает Если не есть степень то некоторые слова будут укорочены в коде Хаффмена и не будут в коде Шеннона — Фано.

Имеем таблицу (см. скан)

Увеличение средней длины кодового слова при использовании, кода Шеннона — Фано невелико; позже будет показано, что для теории это несущественно; код Хаффмена лучше кода Шеннона — Фано только в практических приложениях.