Решение задач по кодированию: Условие Фано и оптимальная длина кода

Ниже представлены решения задач, оформленные для удобного переписывания в тетрадь. Задача 1. Условие Фано означает, что ни одно кодовое слово не является началом другого. Дано: А = 11, Б = 101. Нужно закодировать В и Г так, чтобы длина слова БАГ была минимальной. Свободные ветви дерева: 1. Коды, начинающиеся на 0 (0, 00, 01 и т.д.). 2. Код 100 (так как 101 занято, а 11 занято). Для слова БАГ нам нужна буква Г. Чтобы минимизировать длину, выберем для Г самый короткий свободный код. Самый короткий свободный код — это 0. Проверим: А(11), Б(101), Г(0). Условие Фано соблюдается. Длина слова БАГ: \[ L = L(Б) + L(А) + L(Г) = 3 + 2 + 1 = 6 \] Ответ: 6. Задача 2. Слово: ПАРАЛЛЕЛЬ. Буквы: П(1), А(2), Р(1), Л(3), Е(1), Ь(1). В скобках указано количество повторений. Дано: Л = 0. Так как Л = 0, все остальные коды должны начинаться с 1. Строим дерево от узла 1: - 10 - 11 Разветвляем дальше, чтобы хватило на 5 оставшихся букв (П, А, Р, Е, Ь): - 110 - 111 - 100 - 1010 - 1011 Самая частая буква после Л — это А (2 раза). Дадим ей код покороче, например, 110 (длина 3). Остальным буквам (П, Р, Е, Ь) дадим коды: 111 (3), 100 (3), 1010 (4), 1011 (4). Считаем общую длину: \[ L = 3 \cdot L(Л) + 2 \cdot L(А) + 1 \cdot L(П) + 1 \cdot L(Р) + 1 \cdot L(Е) + 1 \cdot L(Ь) \] \[ L = 3 \cdot 1 + 2 \cdot 3 + 1 \cdot 3 + 1 \cdot 3 + 1 \cdot 4 + 1 \cdot 4 = 3 + 6 + 3 + 3 + 4 + 4 = 23 \] Ответ: 23. Задача 3. Слово: ИНИЦИАЛИЗАЦИЯ. Буквы: И(4), Н(1), Ц(2), А(3), Л(1), З(1), Я(1). Известны: А=000, З=101, Л=0011, Н=0010, Ц=11. Нужно найти коды для И и Я. Свободные коды: 01, 100, 101 (занято), 11 (занято). Проверим дерево: 000 (А), 0010 (Н), 0011 (Л) — ветка 00 занята. 11 (Ц), 101 (З) — ветки заняты. Свободны: 01 и 100. Буква И встречается 4 раза, Я — 1 раз. Присвоим И самый короткий код: И = 01 (длина 2), тогда Я = 100 (длина 3). Считаем длину: И(4*2) + Н(1*4) + Ц(2*2) + А(3*3) + Л(1*4) + З(1*3) + Я(1*3) \[ L = 8 + 4 + 4 + 9 + 4 + 3 + 3 = 35 \] Ответ: 35. Задача 4. Слово: ИНТЕЛЛЕКТ. Буквы: И(1), Н(1), Т(2), Е(2), Л(2), К(1). Всего 7 разных букв. Дано: Л=100, Н=110. Свободные ветви: 0, 101, 111. Разветвим 0 на 00 и 01. Разветвим 111 на 1110 и 1111. Частые буквы (Т, Е, Л) должны иметь короткие коды. Л уже 3 знака. Пусть Т=00 (2), Е=01 (2). Остались И, К, Г (буква Г есть в алфавите, ей тоже нужен код). Свободны: 101, 1110, 1111. И=101 (3), К=1110 (4), Г=1111 (4). Считаем длину ИНТЕЛЛЕКТ: И(3) + Н(3) + Т(2*2) + Е(2*2) + Л(2*3) + К(4) = 3 + 3 + 4 + 4 + 6 + 4 = 24. Ответ: 24. Задача 5. Даны коды для 7 букв из 8. Нужно найти код для Й. Я: 001, Ы: 110, Ш: 101, Т: 000, А: 010, В: 0110, М: 0111. Проверим префиксы: 000 (Т), 001 (Я), 010 (А), 0110 (В), 0111 (М), 101 (Ш), 110 (Ы). Свободные ветви: Коды на 111 свободны. Коды на 100 свободны. Кратчайшие коды: 100 и 111. Оба имеют длину 3. По условию нужно выбрать код с наименьшим числовым значением. 100 < 111. Ответ: 100.