Лекция: Алгоритм Шэннона-Фано.
1. Будем считать список из разновидности символов встречаемых в тексте «группой символов».
2. Подсчитаем частоту появления Fi для каждого из символов, входящего в группу символов.
3. Ранжируем символы по частоте: от самых частых в начале списка к самым редким в конце списка.
4. Подсчитаем сумму частот F символов в группе.
5. Подсчитаем половину суммы частот F/2 символов в группе.
6. Разобьем группу на 2 подгруппы:
— подгруппу нулей, куда будут включены более частые символы, их коды начинаются с 0,
— подгруппу единиц, куда будем включать коды более редких символов.
Разбивать будем так, чтобы сумма частот Fi символов в обеих подгруппах — оказалась по возможности одинаковой. Для этого:
а) начинаем включать символы в подгруппу единиц, начиная с самого редкого;
б) после включения каждого символа подсчитывается текущая сумма частот Fi в подгруппе единиц;
в) включаем символы в подгруппу нулей до тех пор, пока текущая сумма частот Fi в подгруппе единиц, не окажется равной или не привысит F/2;
г) оставшиеся символы включим в подгруппу нулей;
д) проверим, остались ли символы в подгруппе единиц, если нет, то один из символов подгруппы нулей, последний из внесённых подгруппу единиц, перенесем в подгруппу нулей.
7. Результат выполнения пунктов 1-6 — получили первый бита кода для каждого из символов.
8. Определяем второй бит. Для этого:
а) каждую из получившихся в пункте 6 подгрупп назовем группой;
б) если в группе оказывается всего один символ, других бит в коде этого символа уже не будет – код символа определён;
б) каждую группу, в которой более 1 символа, разобьем на подгруппы точно так же, как мы это делали в пунктах 1-7.
9. Процесс разбиения групп на подгруппы, и определения новых бит — будет продолжаться до тех пор, пока в каждой группе — не останется по одному символу.
Задача.
Составить кодовую таблицу для сжатия фразы «мама мыла раму».
Решение.
Оформим решение в виде таблицы:
Символ | Fi | Бит 1 | Бит 2 | Бит 3 | Бит 4 | Бит 5 |
м | ||||||
а | ||||||
_ | ||||||
ы | ||||||
л | ||||||
р | ||||||
у |
Ответ: получим следующие коды символов: М = 0; А = 10; _ = 1100; Ы = 1101; Л = 1110; Р = 00001; У = 11111.