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

Алгоритм Фано — способ построения кода, близкого к оптимальному. iordanskyma.wordpress.com Он использует коды переменной длины: часто встречающийся символ кодируется кодом меньшей длины, редко встречающийся — кодом большей длины. ru.ruwiki.ru ru.wikipedia.org

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

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

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