Кодирование Шеннона — Фано — это способ кодирования информации, который представляет собой

технику создания префиксного кода, основанного на наборе символов и их вероятностей (оценочных или измеренных).

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

Метод Шеннона — Фано не всегда даёт оптимального префиксного кода. По этой причине он почти никогда не используется.

Алгоритм метода Шеннона-Фано — один из первых алгоритмов сжатия, который впервые сформулировали американские учёные Шеннон и Фано, и он имеет большое сходство с алгоритмом Хаффмана. Алгоритм основан на частоте повторения. Так, часто встречающийся символ кодируется кодом меньшей длины, а редко встречающийся — кодом большей длины.
В свою очередь, коды, полученные при кодировании, префиксные. Это и позволяет однозначно декодировать любую последовательность кодовых слов. Но все это вступление.

Для работы оба алгоритма должны иметь таблицу частот элементов алфавита.

Итак, алгоритм Хаффмана работает следующим образом:
1. На вход приходят упорядоченные по невозрастанию частот данные.
2. Выбираются две наименьших по частоте буквы алфавита, и создается родитель (сумма двух частот этих «листков»).
3. Потомки удаляются и вместо них записывается родитель, «ветви» родителя нумеруются: левой ветви ставится в соответствие «1», правой «0».
4. Шаг два повторяется до тех пор, пока не будет найден главный родитель — «корень».