Лабораторная работа №4 1 Теоретические сведения

Упорядоченный в порядке невозрастания вероятностей список букв
делится на две последовательные части так, чтобы суммы вероятностей
входящих в них букв как можно меньше отличались друг от друга.
Буквам из первой части приписываем символ 0, а буквам из второй
части – символ 1. Далее точно так же поступаем с каждой из 
полученных частей, если она содержит хотя бы две буквы.
Построенный код является префиксным, и ему соответствует насыщенное 
кодовое дерево.
В алгоритме Фэно кодовое дерево строится от корня, а в
алгоритме Хаффмана – начиная с листьев. Это отличие позволяет в
алгоритме Хаффмана полнее использовать специфику данного
распределения вероятностей и строить оптимальный код. Алгоритм Фэно 
строит код, близкий к оптимальному. 
Метод Шеннона-Фэно соответствует требованию оптимального 
кодирования. Алгоритм построения кода Шеннона-Фэно состоит в том, что
кодируемые символы (буквы) разделяются на две равновероятные
подгруппы: для символов 1-й подгруппы на втором месте ставится 0, а для
2-й подгруппы – 1 и т.д. 

жүктеу/скачать 349,84 Kb.

Достарыңызбен бөлісу: