Как работает кодирование сообщений с использованием кода Фано?

Кодирование сообщений с использованием кода Фано (также известно как алгоритм Шеннона — Фано) основано на использовании кодов переменной длины: часто встречающийся символ кодируется кодом меньшей длины, редко встречающийся — кодом большей длины. 24

Алгоритм включает следующие этапы: 2

1. Символы первичного алфавита выписывают по убыванию вероятностей. 24
2. Полученный алфавит делят на две части, суммарные вероятности символов которых максимально близки друг другу. 24
3. Для первой части алфавита присваивается двоичная цифра «0», второй части — «1». 24
4. Полученные части рекурсивно делятся, и их частям назначаются соответствующие двоичные цифры в префиксном коде. 24
5. Когда размер подалфавита становится равен нулю или единице, то дальнейшего удлинения префиксного кода для соответствующих ему символов первичного алфавита не происходит. 24

Код строится с помощью дерева. 24 Всё множество кодируемых элементов соответствует корню дерева (вершине первого уровня). 24 Оно разбивается на два подмножества с примерно одинаковыми суммарными вероятностями. 24 Эти подмножества соответствуют двум вершинам второго уровня, которые соединяются с корнем. 24 Далее каждое из этих подмножеств разбивается на два подмножества с примерно одинаковыми суммарными вероятностями. 24 Им соответствуют вершины третьего уровня. 24

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

Ветви кодового дерева размечают символами 1 и 0. 24

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