Код Шеннона-Фано

Примерами префиксных кодов являются коды Шеннона-Фано и Хаффмана.

Рис. Кодовое слово непрефиксного кода

Сообщения алфавита источника выписывают в порядке убывания вероятностей их появления. Далее разделяют их на две части так, чтобы суммарные вероятности сообщений в каждой из этих частей были по возможности почти одинаковыми. Припишем сообщениям первой части в качестве первого символа – 0, а второй – 1 (можно наоборот). Затем каждая из этих частей (если она содержит более одного сообщения) делится на две по возможности равновероятные части, и в качестве второго символа для первой из них берется 0, а для второй – 1. Этот процесс повторяется, пока в каждой из полученных частей не останется по одному сообщению.

Пример:

Р(а₁)=0,1 Р(а₂)=0,15 Р(а₃)=0,15 Р(а₄)=0,1 Р(а₅)=0,05

Р(а₆)=0,05 Р(а₇)=0,2 Р(а₈)=0,07 Р(а₉)=0,09 Р(а₁₀)=0,04

Рис. Кодовое дерево кода Шеннона – Фано

Методика Шеннона – Фано не всегда приводит к однозначному построе­нию кода, поскольку при разбиении на части можно сделать больше по веро­ятности как верхнюю, так и нижнюю части. Кроме того, методика не обеспе­чивает отыскания оптимального множества кодовых слов для кодирования данного множества сообщений. (Под оптимальностью подразумевается то, что никакое другое однозначно декодируемое множество кодовых слов не имеет меньшую среднюю длину кодового слова, чем заданное множество.) Предложенная Хаффманом конструктивная методика свободна от отмечен­ных недостатков.