Решение задачи 559: ОРАНГУТАН - кодирование по условию Фано

Задача № 559 Условие: Для кодирования последовательности из букв А, Г, Н, О, Р, Т, У используется неравномерный двоичный код, удовлетворяющий условию Фано (однозначное декодирование). Известны коды для букв: Г — 10 Р — 01 О — 001 Т — 11 Нужно найти наименьшую возможную длину кодовой последовательности для слова ОРАНГУТАН. Решение: 1. Выпишем количество вхождений каждой буквы в слове ОРАНГУТАН: А — 2 раза Н — 2 раза О — 1 раз (код 001, длина 3) Р — 1 раз (код 01, длина 2) Г — 1 раз (код 10, длина 2) У — 1 раз Т — 1 раз (код 11, длина 2) 2. Для обеспечения однозначного декодирования построим дерево кодов и определим свободные ветви для оставшихся букв (А, Н, У). Уже занятые коды: 01 (Р) 10 (Г) 11 (Т) 001 (О) Проверим свободные узлы: Узел 0: ветвь 01 занята (Р), ветвь 00 занята частично. В узле 00: ветвь 001 занята (О), ветвь 000 свободна. Узел 1: ветви 10 (Г) и 11 (Т) заняты. Таким образом, у нас есть одна свободная ветвь 000. Чтобы закодировать три оставшиеся буквы (А, Н, У), нам нужно разветвить этот узел. Разветвляем 000: — 0000 (свободно) — 0001 (свободно) Разветвляем 0000: — 00000 (свободно) — 00001 (свободно) Теперь у нас есть три свободных кода: 0001 (длина 4), 00000 (длина 5) и 00001 (длина 5). Чтобы минимизировать общую длину слова, присвоим более короткие коды буквам, которые встречаются чаще (А и Н). А — 4 символа (код 0001) Н — 5 символов (код 00000) У — 5 символов (код 00001) (Или наоборот для Н и А, результат будет тот же). 3. Вычислим общую длину слова ОРАНГУТАН: Длина = \( L(О) + L(Р) + L(А) + L(Н) + L(Г) + L(У) + L(Т) + L(А) + L(Н) \) Подставим длины: О: 3 Р: 2 А: 4 Н: 5 Г: 2 У: 5 Т: 2 А: 4 Н: 5 Суммируем: \[ 3 + 2 + 4 + 5 + 2 + 5 + 2 + 4 + 5 = 32 \] Ответ: 32