Алгоритм квазиоптимального кодирования Фано

Известны два метода построения кодов, близких к оптимальному, принадлежащие Фано и Шеннону. Рекурсивный алгоритм Фано отличается чрезвычайной простотой конструкции и строит разделимую префиксную схему алфавитного кодирования, близкого к оптимальному. Метод Фано заключается в следующем: упорядоченный в порядке убывания вероятностей список букв делится на две последовательные части так, чтобы суммы вероятностей входящих в них букв как можно меньше отличались друг от друга. Буквам из первой части приписывается символ 0, а буквам из второй части – символ 1. Далее точно также поступают с каждой из вновь полученных частей, если она содержит, по крайней мере, две буквы. Процесс продолжается до тех пор, пока весь список не разобьется на части, содержащие по одной букве. Каждой букве ставится в соответствие последовательность символов, приписанных в результате этого процесса данной букве. Легко видеть, что полученный в результате код является префиксным.

В таблице 4.3 приведен пример построения схемы кодирования с использованием алгоритма Фано для алфавита, включающего 7 букв. Буквы встречаются в сообщениях с вероятностями . На первом этапе список букв был разделен на две части. В первую часть вошли буквы с вероятностями . Во вторую – с вероятностями . Общая сумма вероятностей первой часть – 0,59, второй – 0,41. Принятое разбиение обеспечивает минимальную разницу суммарных вероятностей двух частей, равную 0,18. Если принять иное разбиение, например, и , то разница будет равной 0,20. В результате, первым символом в кодах трех первых букв принимается 0, а оставшихся четырех – 1.

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

Таблица 4.3.

	Метод Фано	Метод Хаффмена
Коды		Коды
0.20
0.20
0.19
0.12
0.11
0.09
0.09
Цена кодирования	2.80		2.78