Алгоритм Шэннона-Фано

1. Будем считать список из разновидности символов встречаемых в тексте "группой символов".

2. Подсчитаем частоту появления F_i для каждого из символов, входящего в группу символов.

3. Ранжируем символы по частоте: от самых частых в начале списка к самым редким в конце списка.

4. Подсчитаем сумму частот F символов в группе.

5. Подсчитаем половину суммы частот F/2 символов в группе.

6. Разобьем группу на 2 подгруппы:

- подгруппу нулей, куда будут включены более частые символы, их коды начинаются с 0,

- подгруппу единиц, куда будем включать коды более редких символов.

Разбивать будем так, чтобы сумма частот F_i символов в обеих подгруппах - оказалась по возможности одинаковой. Для этого:

а) начинаем включать символы в подгруппу единиц, начиная с самого редкого;

б) после включения каждого символа подсчитывается текущая сумма частот F_i в подгруппе единиц;

в) включаем символы в подгруппу нулей до тех пор, пока текущая сумма частот F_i в подгруппе единиц, не окажется равной или не привысит F/2;

г) оставшиеся символы включим в подгруппу нулей;

д) проверим, остались ли символы в подгруппе единиц, если нет, то один из символов подгруппы нулей, последний из внесённых подгруппу единиц, перенесем в подгруппу нулей.

7. Результат выполнения пунктов 1-6 - получили первый бита кода для каждого из символов.

8. Определяем второй бит. Для этого:

а) каждую из получившихся в пункте 6 подгрупп назовем группой;

б) если в группе оказывается всего один символ, других бит в коде этого символа уже не будет – код символа определён;

б) каждую группу, в которой более 1 символа, разобьем на подгруппы точно так же, как мы это делали в пунктах 1-7.

9. Процесс разбиения групп на подгруппы, и определения новых бит - будет продолжаться до тех пор, пока в каждой группе - не останется по одному символу.

Задача.

Составить кодовую таблицу для сжатия фразы «мама мыла раму».

Решение.

Оформим решение в виде таблицы:

Символ	Fi	Бит 1	Бит 2	Бит 3	Бит 4	Бит 5
м
а
_
ы
л
р
у

Ответ: получим следующие коды символов: М = 0; А = 10; _ = 1100; Ы = 1101; Л = 1110; Р = 00001; У = 11111.