По каналу связи передается 20 букв Е, 16 букв И, 6 букв К, 4 буквы (других букв нет). Все буквы кодируются неравномерным двоичным кодом, удовлетворяющим условию Фано, и общая длина кодового сообщения наименьшая. Для одной из букв использовали код 10. Найдите кратчайшее кодовое слово для буквы К, если таких кодов несколько, то укажите код с наименьшим числовым значением.
1. Выписываем все буквы, для которых нам дано количество, в порядке убывания их количества: Е (20), И (16), К (6).
2. Делим этот список пополам с суммой количества букв в каждой половине максимально близкой друг к другу: Е (20), И (16), К (6) → Е (20), И (22) | К (6).
3. Рекурсивно повторяем шаг 2 для каждой половины, пока не получим по одной букве в каждой ветви.
- Для левой ветви Е (20), И (22):
- Делим список пополам: Е (20) | И (22).
- Создаем кодовое слово для левой ветви: 0.
- Создаем кодовое слово для правой ветви: 1.
- Для правой ветви К (6):
- Создаем кодовое слово: 10.
4. Теперь можем записать полное дерево кодирования:
.
|
---
| |
E ---
|
I
.
|
К
5. Наше кратчайшее кодовое слово для буквы К будет "10".
Обратите внимание, что в этом случае нет других кодовых слов с таким же числовым значением.