Решение задачи: Минимальная длина кодового слова БАГ (условие Фано)

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