Условие:
Реши задачу по дискретной математике: для распределения вероятностей P = (0,45 , 0,1 , 0,1 , 0,2 , 0,1 , 0,05) построить оптимальный префиксный код в алфавите А = {0,1,2}. Посчитать стоимость кодирования
Решение:
Ниже приведём пошаговое решение задачи. 1. Задача состоит в построении оптимального префиксного кода (в терминах дерева Хаффмана) для шести символов с вероятностями 0.45, 0.1, 0.1, 0.2, 0.1 и 0.05, если кодируем по алфавиту из трех символов {0, 1, 2}. 2. Для алгоритма Хаффмана в D-ичной (здесь D = 3) форме необходимо, чтобы число листов удовлетворяло условию: (n – 1) mod (D – 1) = 0. Здесь n = 6, а (6 – 1) = 5, и 5 mod 2 = 1. Поэтому добавляем дополнительный фиктивный символ (dummy) с вероятностью 0, так чтобы общее число стало n = 7 (так как (7 – 1) = 6, и 6 mod 2 = 0). 3. Итак, набор веро...