Метод Шеннона-Фано

Этот метод требует упорядочения исходного множества символов по не возрастанию их частот. Затем выполняются следующие шаги:

а) список символов делится на две части (назовем их первой и второй частями) так, чтобы суммы частот обеих частей (назовем их Σ₁ и Σ₂) были точно или примерно равны. В случае, когда точного равенства достичь не удается, разница между суммами должна быть минимальна;

б)  кодовым комбинациям первой части дописывается 1, кодовым комбинациям второй части дописывается 0;

в) анализируют первую часть: если она содержит только один символ, работа с ней заканчивается, – считается, что код для ее символов построен, и выполняется переход к шагу г) для построения кода второй части. Если символов больше одного, переходят к шагу а) и процедура повторяется с первой частью как с самостоятельным упорядоченным списком;

г) анализируют вторую часть: если она содержит только один символ, работа с ней заканчивается и выполняется обращение к оставшемуся списку (шаг д). Если символов больше одного, переходят к шагу а) и процедура повторяется со второй частью как с самостоятельным списком;

д) анализируется оставшийся список: если он пуст – код построен, работа заканчивается. Если нет, – выполняется шаг а).

Пример 1. Даны символы a, b, c, d с частотами f_a = 0,5;  f_b = 0,25;  f_c = 0,125;  f_d = 0,125. Построить эффективный код методом Шеннона-Фано.

Сведем исходные данные в таблицу, упорядочив их по невозрастанию частот:

Исходные символы	Частоты символов
a	0,5
b	0,25
c	0,125
d	0,125

Первая линия деления проходит под символом a: соответствующие суммы Σ₁ и Σ₂ равны между собой и равны 0,5. Тогда формируемым кодовым комбинациям дописывается 1 для верхней  (первой) части и 0 для нижней (второй) части. Поскольку это первый шаг формирования кода, двоичные цифры не дописываются, а только начинают формировать код:

Исходные символы	Частоты символов	Формируемый код
a	0,5	1
b	0,25	0
c	0,125	0
d	0,125	0

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

Второе деление выполняется под символом b: суммы частот Σ₁ и Σ₂ вновь равны между собой и равны 0,25. Тогда кодовой комбинации символов верхней части дописывается 1, а нижней части – 0. Таким образом, к полученным на первом шаге фрагментам кода, равным 0, добавляются новые символы:

Исходные символы	Частоты символов	Формируемый код
a	0,5	1
b	0,25	01
c	0,125	00
d	0,125	00

Поскольку верхняя часть нового списка содержит только один символ (b), формирование кода для него закончено (соответствующая строка таблицы вновь выделена заливкой).

Третье деление проходит между символами c и d: к кодовой комбинации символа c приписывается 1, коду символа d приписывается 0:

Исходные символы	Частоты символов	Формируемый код
a	0,5	1
b	0,25	01
c	0,125	001
d	0,125	000

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

Таким образом, получили коды:

a        -        1,

b        -        01,

c        -        001,

d        -        000.

Определим эффективность построенного кода по формуле:

l_ср = 0,5*1 + 0,25*01 + 0,125*3 + 0,125*3 = 1,75.

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