Для кодирования последовательности, состоящей из букв К, О, Л, Б...

Задание: 

Для кодирования последовательности, состоящей из букв К, О, Л, Б, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Букве К соответствует двоичный код 0, букве О — код 10. Какова наименьшая суммарная длина кодовых слов для всех букв в слове КОЛОБОК?

Решение:

По условию Фано ни одно кодовое слово не является началом другого. Коды К = 0 и О = 10 уже заняты, поэтому для Л и Б остаются только ветви, начинающиеся с 11. Кратчайшие подходящие коды — Б = 110 и Л = 111:

Длины кодов: К — 1, О — 2, Б — 3, Л — 3. Для слова КОЛОБОК:

Ответ: 14