По каналу связи передаются сообщения, содержащие только русские буквы. Для передачи используется двоичный код, удовлетворяющий условию Фано (никакое кодовое слово не может быть началом другого кодового слова). Кодовые слова для некоторых букв известны: К – 10, Р – 011, С – 11. Какое наименьшее количество двоичных знаков потребуется для кодирования слова ФОКСФОРД?
1. Первым делом в дереве нужно учесть кодовое слово К – 10. Создадим вершину с этим кодом.
10
2. Следующее кодовое слово – Р – 011. Добавим его в дерево. Для этого нужно начать от вершины с кодом 10, добавить новую вершину 0 и установить кодовое слово Р на этой вершине.
10
\
0 - Р
3. Третье кодовое слово – С – 11. В дереве нужно создать новую вершину 1 от вершины с кодом 10 и установить на ней кодовое слово С.
10
\
0 - Р
/
1 - С
4. Теперь дерево готово, и мы можем закодировать слово ФОКСФОРД. Для этого нужно пройти по дереву, соответствуя каждой букве кодовое слово.
Ф – 0
О – 10
К – 10
С – 11
Ф – 0
О – 10
Р – 011
Д – неизвестно (буквы "Д" в задаче нет)
5. Наименьшее количество двоичных знаков потребуется для кодирования слова ФОКСФОРД, если применить кодирование по Фано, равно 21. Для этого слова потребуется использовать последовательность из 21 двоичного знака.
Обоснование: В данной задаче использовано кодирование по Фано, которое гарантирует отсутствие начала одного кодового слова внутри другого. Количество двоичных знаков для кодирования каждой буквы определено исходя из дерева кодовых слов. Количество двоичных знаков для слова ФОКСФОРД определено путем пройденя по дереву и кодирования каждой буквы.