Условие: № 8462 (Уровень: Базовый)
(В. Рыбальченко) По каналу связи передаются сообщения, содержащие только буквы В, И, Д, О, С, К, Ю. Для передачи используют двоичный код, удовлетворяющий условию Фано.
Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: В – 01, Д – 11.
Необходимо определить кратчайшее кодовое слово для буквы К, такое чтобы последовательность ВИДОСИКИ была закодирована наименьшим количеством двоичных знаков.
Если существует несколько подходящих кодовых слов, необходимо выбрать код с наименьшим числовым значением. В ответ укажите найденное кодовое слово.
1. Строим бинарное (двоичное) дерево
В любом прототипе задания №4 построение бинарного дерева - это наш первый шаг.
В большинстве задач нам хватит дерева глубины 3-4.
2. Вчитываемся в условие задачи
Нам известен алфавит: В, И, Д, О, С, К, Ю.
Также нам известно, что буква В закодирована как 01, а буква Д - как 11.
По условию Фано, никакой код не может быть началом другого кода.
Например, мы не можем закодировать какую-либо букву как 110, т.к. буква Д имеет код 11. Для удобства советую сразу зачеркивать те ветки, которые мы не сможем использовать из-за условия Фано.
Переносим данные из условия на наше дерево и зачеркиваем ненужные нам ветки:
3. Снова возвращаемся к условию
Нам нужно подобрать и записать в ответ код для буквы К с наименьшим числовым значением, используя который слово ВИДОСИКИ будет закодировано наименьшим количеством двоичных знаков (0 и 1).
Для этого нам сначала нужно посчитать сколько раз каждая из букв встречается в слове ВИДОСИКИ:
Как мы можем заметить, буква Ю ни разу не встречается в нашем слове. Но это не отменяет того факта, что все буквы алфавита должны быть закодированы, поэтому в будущем оставим свободное место для нее.
Также стоит обратить внимание на букву И, которая встречается целых три раза в нашем слове! Это значит, что ее код должен быть минимальной длины.
4. Решаем задачу
Обращаем внимание на предыдущее замечание и кодируем букву И.
Нам нужно использовать наименьшее кол-во двоичных знаков, а значит у нас лишь два варианта: 10 и 00.
Предлагаю использовать код 10, потому что этот код имеет большее числовое значение (10 > 0).
Так или иначе, нас впоследствии будут интересовать коды с наименьшим числовым значением, поэтому сразу “закроем” ветки, начинающиеся с единицы.
На следующем этапе опций у нас немного.
Среди всех возможных вариантов, код 000 является подходящим для буквы К, т.к. он имеет наименьшую длину, в нашем случае 3, и имеет минимальное числовое значение.
Кодируем!
А сейчас перед нами самый ошибкоопасный шаг. Казалось бы, для нашего слова осталось закодировать две буквы, и у нас есть ровно два варианта: 0010 и 0011.
Но не стоит торопиться. Помните что я говорил вам про букву Ю? Да, ее нет в нашем слове, но ее обязательно нужно закодировать.
А сделаем мы это путем расширения нашего дерева.
Теперь со спокойной душой кодируем оставшиеся буквы.
В нашем случае все буквы встречаются в слове ровно один раз, и нам не придется отдавать какой-то из них код с минимальной длиной.
Все получилось! И теперь проверяем еще раз, что нам нужно вписать в ответ: “кратчайшее кодовое слово для буквы К”.