Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н, решили использовать неравномерный двоичный код,
Вопрос от пользователя
Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Н использовали кодовое слово 0, для буквы К — кодовое слово 110. Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?
1)7
2)8
3)9
4) 10
Ответ от эксперта
Для анализа соблюдения условия однозначного декодирования (условия Фано) изобразим коды в виде дерева. Тогда однозначность выполняется, если каждая буква является листом дерева:
Легко заметить, что ближайшие от корня свободные листы (т.е. свободные коды с наименьшей длиной) — это 10 и 111. Таким образом, наименьшая возможная суммарная длина всех четырёх кодовых слов будет 1 + 3 + 2 + 3 = 9.
Правильный ответ указан под номером 3.
Ответ: 3.
