Question

Для кодирования некоторой последовательности, состоящей из букв я, К, Л, А, С, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы С использовали кодовое слово О, для буквы К — кодовое слово 11. Какова наименьшая возможная суммарная длина всех пяти кодовых слов? (Напечатай в ответе только число.)​

Answer 1

Для решения задачи нужно построить дерево Фано. На первом шаге можно объединить буквы К и Л, так как они имеют одинаковую частоту встречаемости. Получится следующее дерево:

        /  \

      /      \

     /         \

  КЛ       САЯ

  /               \

 К               ЛАЯ

Для буквы С используется кодовое слово О, а для буквы К — кодовое слово 11. Значит, для буквы ЛАЯ используется кодовое слово 0, а для буквы КЛАЯ — кодовое слово 10. Для буквы Я используется кодовое слово 11. Таким образом, суммарная длина всех пяти кодовых слов равна:

1 (буква С) + 2 (буква К) + 2 (буква ЛАЯ) + 2 (буква КЛАЯ) + 2 (буква Я) = 9

Ответ: 9.