Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 0, для буквы Б – кодовое слово 110. Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?

Предыдущий
вопрос Следующий
вопрос

Для решения данной задачи, можно воспользоваться алгоритмом Фано.

Нам известно, что частота встречаемости букв в последовательности равна:
A - 1, B - 1, В - 1, Г - 1.

Упорядочим буквы по убыванию частоты встречаемости:
(A, B, В, Г).

Далее рекурсивно делим буквы на две группы с приблизительно одинаковыми суммарными частотами. Получаем следующее дерево кодирования:

3
/ \
A 2
/ \
B 1
/ \
В Г

Кодовые слова для каждой буквы:
A - 0
B - 10
В - 110
Г - 111

Суммарная длина всех четырех кодовых слов:
11 + 12 + 13 + 13 = 1 + 2 + 3 + 3 = 9.

Таким образом, наименьшая возможная суммарная длина всех четырех кодовых слов равна 9.