Для кодирования последовательности, состоящей из букв слова ШKOЛKOВО решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Ш использовали кодовое слово 00, для буквы К — 1. Укажите, какова наименьшая длина всех символов заданного слова.
Построим дерево для решения задачи. Для букв Ш и К есть кодовые слова 00 и 1 соответственно. В слове ШКОЛКОВО самая частовстречаемая буква — О, следовательно, её нужно закодировать минимальновозможным количеством символов.
Минимально возможная длина кодового слова для буквы состоит из трёх битов, то есть О закодируем с помощью 010.
Буквы Л и В встречаются всего один раз, закодируем их минимально возможным количеством символов.
Самая маленькая длина кодовых слов для них \(=4\): 0110 и 0111.
Посчитаем сумму длин кодовых слов:
Ш, Л и В встречаются один раз,
К — 2 раза,
О — 3 раза.
\(3\cdot3+2\cdot1+1\cdot2+2\cdot4=21\)
Ответ: 21