Лекция: Алгоритм Шэннона-Фано.

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.

 

еще рефераты
Еще работы по информатике