Кодирование Шеннона — Фано — это способ кодирования информации, который представляет собой технику создания префиксного кода, основанного на наборе символов и их вероятностей (оценочных или измеренных).
Алгоритм кодирования:
1. Символы распределяются в порядке от наиболее вероятных к наименее вероятным.
2. Затем они разделяются на два набора, чьи суммарные вероятности максимально приближены друг к другу.
3. Далее формируется первый разряд кода всех символов: символы из первого набора получают двоичный «0», символы из второго — «1».
4. Процесс деления на две части и получения следующих разрядов повторяется для полученных наборов аналогичным образом, пока в полученном наборе не останется по одному символу.
5. Когда набор уменьшается до одного символа, код символа полностью сформирован.
Метод Шеннона — Фано не всегда даёт оптимального префиксного кода. По этой причине он почти никогда не используется.