Question

По каналу связи передаются сообщения, содержащие только буквы: А, З, К, Н, Ч. Для передачи используется двоичный код, удовлетворяющий условию Фано (никакое кодовое слово не является началом другого). Известны коды: Н — 1111, З — 110. Для букв А, К, Ч коды неизвестны. Какое количество двоичных знаков потребуется для кодирования слова КАЗАЧКА, если оно закодировано минимально возможным количеством двоичных знаков?

Accepted Answer

14

Answer

Идея решения: найти кратчайшие коды для оставшихся букв, соблюдая условие Фано, затем подсчитать общую длину кодирования слова с учётом частоты каждой буквы.

Проанализируем занятые коды в префиксном дереве:
- Н = 1111 (занимает ветку длины 4)
- З = 110 (занимает ветку длины 3)

Свободные ветки:
- Длины 1: `0`
- Длины 2: `10`, `11`
- Длины 3: `0...` (под `0`), `100`, `101`

Для минимизации общей длины кодирования нужно назначить кратчайшие коды буквам с наибольшей частотой в слове КАЗАЧКА.

Подсчитаем частоты букв в слове КАЗАЧКА:
- А встречается 3 раза
- К встречается 2 раза
- Ч встречается 1 раз

Назначим коды в порядке убывания частоты:
- А (3 раза) → `0` (длина 1)
- К (2 раза) → `10` (длина 2)
- Ч (1 раз) → `1110` (длина 4)

Проверим условие Фано: коды `0`, `10`, `1110`, `110`, `1111` не пересекаются по префиксам. ✓

Вычислим общую длину кодирования слова КАЗАЧКА:
- К: 2 раза × 2 знака = 4
- А: 3 раза × 1 знак = 3
- З: 1 раз × 3 знака = 3
- Ч: 1 раз × 4 знака = 4

Итого: 4 + 3 + 3 + 4 = **14** двоичных знаков.

Задание №4Представление информацииЕГЭ по информатике