Теория информации

Для этого два последних символа «укрупняются» в некоторый вспомогательный символ с вероятностью, которая равняется сумме вероятностей символов, которые были «укрупнены». 3 шаг) Образовавшаяся новая последовательность вновь сортируется в порядке убывания вероятностей с учетом вновь образованного за счет «укрупнения» символа. 4 шаг) Процедура повторяется до тех пор, пока не получится один «укрупненный» символ, вероятность которого равна 1. Пример 1.25. Покажем процесс построения кодов Хаффмана для алфавита сообщений: X = ( x 1 , x 2 , x 3 , x 4 , x 5 , x 6 , x 7 , x 8 ). с распределением вероятностей появления символов:        16 1 , 16 1 , 16 1 , 16 1 , 8 1 , 8 1 , 4 1 , 4 1 P . 1. Исходный список букв X = { x 1 , x 2 , x 3 , x 4 , x 5 , x 6 , x 7 , x 8 } уже упорядочен, так как        16 1 , 16 1 , 16 1 , 16 1 , 8 1 , 8 1 , 4 1 , 4 1 P . 2. Объединим буквы x 7 и x 8 в одну букву x 1 с вероятностью 8 1 и переупорядочим список:        16 1 , 16 1 , 8 1 , 8 1 , 8 1 , 4 1 , 4 1 1 P , X 1 = { x 1 , x 2 , x 3 , x 4 , x 1 , x 5 , x 6 }. 3. Повторим шаг 2 до тех пор, пока не останется одна буква в списке:        8 1 , 8 1 , 8 1 , 8 1 , 4 1 , 4 1 2 P , X 2 = { x 1 , x 2 , x 3 , x 4 , x 1 , x 2 };        8 1 , 8 1 , 4 1 , 4 1 , 4 1 3 P , X 3 = { x 1 , x 2 , x 3 , x 3 , x 4 };        4 1 , 4 1 , 4 1 , 4 1 4 P , X 4 = { x 1 , x 2 , x 3 , x 4 };