ГДЗ по информатике, 10 класс, Босова, номер 4.10: Обработка информации

Для того чтобы код можно было однозначно декодировать (обычно подразумевается мгновенное декодирование или отсутствие неоднозначности при потоковом чтении), код должен быть префиксным . Это означает, что ни одно кодовое слово не должно являться началом (префиксом) другого кодового слова.

• Слово A (0): является ли оно префиксом других слов? Нет, все остальные слова начинаются с 1 или 2.
• Слово B (11): является ли оно префиксом других слов? Нет, другие слова начинаются с 2 или 0.
• Слово V (20): является ли оно префиксом других слов? Нет, другие слова начинаются с 1 или 0.
• Слово G (21): является ли оно префиксом других слов? Нет.
• Слово D (22): является ли оно префиксом других слов? Нет.

Текущий набор кодов является префиксным и однозначно декодируемым.

Рассмотрим каждую букву по очереди и попробуем сократить её код на один символ, проверяя, не нарушится ли условие префиксности относительно неизмененных кодов.

Вариант 1: Сокращение кода буквы A (0)

Код A имеет длину 1. Сократить его невозможно (минимальная длина кода — 1 символ).

Вариант 2: Сокращение кода буквы B (11)

Если мы сократим код B до 1, то новый код будет 1. Проверим, не является ли он префиксом других слов:

• Слово V начинается с 2 — ок.
• Слово G начинается с 2 — ок.
• Слово D начинается с 2 — ок.
• Слово A равно 0 — ок.

Однако, нужно проверить, не является ли какое-то другое слово префиксом нового слова B=1? Нет, все остальные имеют длину ≠1 или другой первый символ. Но важно проверить обратное: не является ли новое слово 1 префиксом существующих слов? Существующие слова 20,21,22 начинаются с 2, слово 0 начинается с 0. Значит, код 1 не является префиксом ни одного из них. И ни одно из них не является префиксом кода 1 (так как они длиннее или начинаются иначе). Таким образом, замена 11→1 сохраняет префиксность.

Вариант 3: Сокращение кода буквы V (20)

Попробуем сократить 20 до 2. Новый код V=2.

• Проверяем, не является ли 2 префиксом других слов. Слово G имеет код 21. Код 2 является префиксом кода 21.
• Это нарушает условие префиксности. При получении последовательности 21... декодер не сможет сразу понять, это буква V (2) за которой следует что-то, или буква G (21).

Следовательно, сокращать код V нельзя.

Вариант 4: Сокращение кода буквы G (21)

Попробуем сократить 21 до 2. Аналогично предыдущему пункту, код 2 становится префиксом кода V=20 (или D=22, если бы мы меняли их, но здесь сравниваем с неизменными). Если G=2, то G является префиксом V(20) и D(22). Декодирование станет неоднозначным.

Следовательно, сокращать код G нельзя.

Вариант 5: Сокращение кода буквы D (22)

Попробуем сократить 22 до 2. Код 2 является префиксом кодов V(20) и G(21). Нарушается префиксность.

Следовательно, сокращать код D нельзя.

Единственная возможность сократить длину кодового слова без нарушения однозначности декодирования (сохранения свойства префиксного кода) — это изменить код буквы B с 11 на 1.

Проверим итоговый набор: A=0,B=1,V=20,G=21,D=22.

• 0 не является префиксом 1,20,21,22.
• 1 не является префиксом 0,20,21,22.
• 20 не является префиксом 0,1,21,22.
• 21 не является префиксом 0,1,20,22.
• 22 не является префиксом 0,1,20,21.

Все условия выполнены.