Page 42 - 6151
P. 42
Другим кроком виробляємо кодування, "проходячи" по таблиці справа
наліво (зазвичай це проробляється в одній таблиці):\
Побудова кодового дерева починається з кореня. Двом походить із
нього ребрах приписується в якості ваг ймовірності 0,6 і 0,4, які стоять в
останньому стовпчику. Утворився при цьому вершин дерева приписуються
кодові символи 0 і 1. Далі "йдемо" по таблиці справа наліво. Оскільки
ймовірність 0,6 є результатом складання двох ймовірностей 0,4 і 0,2, з
вершини 0 виходять два ребра з вагами 0,4 і 0,2 відповідно, що призводить
до утворення двох нових вершин з кодовими символами 00 і 01. Процедура
триває до тих пір, поки в таблиці залишаються ймовірності, отримані в
результаті підсумовування. Побудова кодового дерева закінчується
утворенням семи листя, які відповідають даним повідомленням з
присвоєними їм кодами. Дерево, отримане в результаті кодування по
Хаффману, має такий вигляд:
43