В чем заключается принцип работы кодирования по методу Фано?

Принцип работы кодирования по методу Фано заключается в использовании кодов переменной длины: часто встречающийся символ кодируется кодом меньшей длины, редко встречающийся — кодом большей длины. 14

Алгоритм использует избыточность сообщения, заключённую в неоднородном распределении частот символов его алфавита, то есть заменяет коды более частых символов короткими двоичными последовательностями, а коды более редких символов — более длинными двоичными последовательностями. 1

Основные этапы алгоритма: 1

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