Имеется источник, генерирующий случайные символы со следующими вероятностями: Символ Вероятность A 0,32 B 0,21 C 0,34 D 0,13 Построить кодовое

Имеется источник, генерирующий случайные символы со следующими вероятностями: Символ Вероятность A 0,32 B 0,21 C 0,34 D 0,13 Построить кодовое дерево по алгоритму Хаффмана и найти коды, соответствующие каждой букве. Определить среднюю длину кодовой комбинации и вероятности обнаружения нуля и единицы в полученном коде. Декодировать с использованием полученного кода поток: 01011111111001101100111100000100110001110111011001 Ответ записать буквами.

Построение дерева начинаем со списка листьев:
На первом шаге из листьев дерева выбираются два с наименьшим весом - B и D. Они присоединяются к узлу-родителю, вес которого устанавливается в 0,21+0,13=0,34. Затем узлы B и D удаляются из списка свободных. Узел B соответствует ветви 0 родителя, узел D - ветви 1. Дерево кодирования после первого шага:
На втором шаге «наилегчайшей» парой оказывается лист A и свободный узел (B + D) . Для них создастся родитель с весом 0,66, узел A с меньшей вероятностью соответствует ветви 1 (Возможно также соединение узлов A и C – оба варианта будут обладать одинаковой эффективностью для заданного распределения вероятностей). Получаем:
И последний шаг:
На основании построенного дерева буквы представляются кодами, отражающими путь от корневого узла до листа, соответствующего нужному символу (в третьей строке укажем также частоты символов):
A B C D
01 000 1 001
0,32 0,21 0,34 0,13
Определяем среднюю длину кодовой комбинации как среднее количество символов, требуемых для кодирования одного символа с учетом вероятностей генерации случайных символов:
lкод=0,32∙2+0,21∙3+0,34∙1+0,13∙3=2
Определим вероятность обнаружения единицы в кодах, соответствующих символам как отношение числа единиц к длине кода:
P1|HA=12;P1|HB=0;P1|HC=1;P1|HD=13
Тогда вероятность обнаружения единицы в полученном коде:
P1=0,32∙12+0,21∙0+0,34∙1+0,13∙13≈0,543
А вероятность обнаружения нуля:
P0=1-P1=1-0,543=0,457
Декодируем с использованием полученного кода поток:
01011111111001101100111100000100110001110111011001
Получаем:
AACCCCCCCDCACDCCCBDDCBCCCACCACD

. Для них создастся родитель с весом 0,66, узел A с меньшей вероятностью соответствует ветви 1 (Возможно также соединение узлов A и C – оба варианта будут обладать одинаковой эффективностью для заданного распределения вероятностей). Получаем:
И последний шаг:
На основании построенного дерева буквы представляются кодами, отражающими путь от корневого узла до листа, соответствующего нужному символу (в третьей строке укажем также частоты символов):
A B C D
01 000 1 001
0,32 0,21 0,34 0,13
Определяем среднюю длину кодовой комбинации как среднее количество символов, требуемых для кодирования одного символа с учетом вероятностей генерации случайных символов:
lкод=0,32∙2+0,21∙3+0,34∙1+0,13∙3=2
Определим вероятность обнаружения единицы в кодах, соответствующих символам как отношение числа единиц к длине кода:
P1|HA=12;P1|HB=0;P1|HC=1;P1|HD=13
Тогда вероятность обнаружения единицы в полученном коде:
P1=0,32∙12+0,21∙0+0,34∙1+0,13∙13≈0,543
А вероятность обнаружения нуля:
P0=1-P1=1-0,543=0,457
Декодируем с использованием полученного кода поток:
01011111111001101100111100000100110001110111011001
Получаем:
AACCCCCCCDCACDCCCBDDCBCCCACCACD