Как работает алгоритм Фано для построения оптимального префиксного кода?

Алгоритм Фано — способ построения кода, близкого к оптимальному. 1 Он использует коды переменной длины: часто встречающийся символ кодируется кодом меньшей длины, редко встречающийся — кодом большей длины. 23

Алгоритм состоит из следующих шагов: 1

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

Код, построенный по алгоритму Фано, не является оптимальным в общем смысле, хотя и даёт оптимальные результаты при некоторых распределениях вероятностей. 24