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



Pdf көрінісі
бет2/5
Дата29.03.2022
өлшемі349,84 Kb.
#137152
түріЛабораторная работа
1   2   3   4   5
Байланысты:
ОИС лаб4 2018

4.1.1 Метод Шеннона-Фэно 


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


Достарыңызбен бөлісу:
1   2   3   4   5




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет