Чтобы закодировать сообщение, замените каждый символ его кодовым словом и соедините слова без разделителей. При декодировании нужно восстановить границы слов: в префиксном коде это можно делать слева направо.

В практикуме четыре задачи разобраны по шагам, ещё восемь предложены для самостоятельного решения. Вертикальные черты в разборах показывают границы кодовых слов и не входят в передаваемую строку.
Правила для работы со строками
Префиксный код устроен так, что ни одно его кодовое слово не является началом другого. При чтении можно накапливать биты до полного кодового слова, затем начинать следующее. Это свойство описано в лекции Корнеллского университета о префиксных кодах.
| Задача | Действие |
|---|---|
| Закодировать | Подставить коды по порядку и убрать разделители |
| Расшифровать префиксный код | Читать слева до полного слова, затем продолжить |
| Проверить условие Фано | Сравнить каждое слово с началом остальных |
| Доказать неоднозначность строки | Найти два разных сообщения с одной полной строкой |
Нарушение префиксного условия само по себе ещё не доказывает неоднозначность любого кода. Для конкретной строки надёжнее показать две её полные расшифровки.
Четыре задачи с решением
1. Кодирование последовательности
Учебный код: А = 0, Б = 10, В = 110, Г = 111. Закодируйте последовательность АБВГА. Между кодами нет пробелов или разделителей; пробел в записи условия не является частью сообщения.
- Заменяем каждую букву её кодом: 0 | 10 | 110 | 111 | 0.
- Убираем разделители и соединяем группы.
- Проверяем длину: 1 + 2 + 3 + 3 + 1 = 10 бит.
Ответ: 0101101110.
2. Расшифровка строки
Учебный код: А = 0, Б = 10, В = 110, Г = 111. Расшифруйте полную битовую строку 11011110010, без пропущенных и добавленных битов.
- Первое полное слово — 110, это В.
- Далее идут 111 и 10: это Г и Б.
- Остаются 0 и 10: это А и Б.
Разделение всей строки: 110 | 111 | 10 | 0 | 10.
Ответ: ВГБАБ.
3. Две расшифровки
Даны коды А = 0, Б = 01, В = 1. Найдите две разные расшифровки полной строки 01. Поясните, почему именно эта строка неоднозначна.
- Вся строка 01 — код буквы Б.
- Её также можно разделить как 0 | 1, то есть АВ.
- Оба сообщения допустимы и различаются, но дают одну строку.
Ответ: Б и АВ. Неоднозначность здесь подтверждается совпадением полных кодировок.
4. Выбор кода
Три символа кодируются так: Д = 00, Е = 01, Ж = 10. Выберите для З код из вариантов 0, 1, 11, 000, чтобы ни одно кодовое слово не было началом другого. Покажите, какие конфликты возникают у остальных вариантов.
- Вариант 0 — начало уже занятых 00 и 01.
- Вариант 1 — начало занятого 10.
- Вариант 000 начинается с занятого 00.
- Вариант 11 не совпадает с началом ни одного из занятых слов, и они не являются его началом.
Ответ: 11.
Восемь задач для самостоятельной работы
5. Учебный код: А = 00, Б = 01, В = 10, Г = 11. Закодируйте последовательность ГВАБВ. Между кодами нет пробелов или разделителей; пробел в записи условия не является частью сообщения.
6. Учебный код: А = 00, Б = 01, В = 10, Г = 11. Расшифруйте полную битовую строку 0010110111, без пропущенных и добавленных битов.
7. Даны коды А = 1, Б = 10, В = 0. Найдите две разные расшифровки полной строки 10. Обоснуйте совпадение кодировок.
8. Три символа кодируются так: К = 0, Л = 10, М = 110. Выберите для Н код из вариантов 0, 11, 111, 1100, чтобы ни одно кодовое слово не было началом другого. Укажите конфликты у остальных вариантов.
9. Учебный код: А = 1, Б = 00, В = 010, Г = 011. Закодируйте последовательность БАГВБ. Между кодами нет пробелов или разделителей; пробел в записи условия не является частью сообщения.
10. Учебный код: А = 1, Б = 00, В = 010, Г = 011. Расшифруйте полную битовую строку 011100010011, без пропущенных и добавленных битов.
11. Даны коды А = 00, Б = 000, В = 0. Найдите две разные расшифровки полной строки 00. Обоснуйте совпадение кодировок.
12. Три символа кодируются так: П = 00, Р = 10, С = 110. Для Т предложены 0, 1, 01, 1110. Выберите кратчайший из вариантов, который не создаёт префиксного конфликта со старыми кодами.
Ответы и объяснения
5. 1110000110. Подставляем коды: 11 | 10 | 00 | 01 | 10. После соединения получается строка из 10 бит.
6. АВГБГ. Все кодовые слова имеют длину два бита, поэтому разделяем строку так: 00 | 10 | 11 | 01 | 11. По таблице это А | В | Г | Б | Г.
7. Б и АВ. Для Б код равен 10. Для АВ получаем 1 | 0, то есть ту же полную строку 10. Других разбиений этой строки на данные кодовые слова нет.
8. 111. Вариант 0 уже занят; 11 является началом 110; 1100 начинается с занятого 110. Код 111 не создаёт конфликта ни с одним из трёх старых кодов.
9. 00101101000. Разделение по буквам: 00 | 1 | 011 | 010 | 00. Соединяем группы; длина строки равна 2 + 1 + 3 + 3 + 2 = 11 бит.
10. ГАБВГ. Разделение строки: 011 | 1 | 00 | 010 | 011. Каждое слово найдено в таблице, а неиспользованных битов не осталось.
11. А и ВВ. Буква А кодируется как 00. Две буквы В дают 0 | 0 = 00. Код Б длиннее строки, поэтому в её расшифровку не входит.
12. 01. Вариант 0 — начало 00, а 1 — начало 10 и 110. Варианты 01 и 1110 допустимы: ни один из старых кодов не является их началом и наоборот. Из них 01 короче: два бита вместо четырёх.
Типичные ошибки
- Делят строку на равные части без основания. В задаче 10 длины слов различаются, поэтому границы определяются таблицей.
- Оставляют бит без расшифровки. После чтения проверьте, что использована вся строка и каждая группа соответствует коду.
- Проверяют префикс только в одном направлении. Новый код может быть началом старого, а старый — началом нового: сравнивайте оба случая.
- Считают совпадение первых битов конфликтом. Например, 00 и 01 начинаются одинаково, но ни одно слово не является началом другого.
- Забывают сравнить длины допустимых вариантов. В задаче 12 недостаточно найти любой подходящий код: требуется кратчайший из предложенных.
Если вы готовитесь к экзамену, продолжить работу можно с материалом «Подготовка к ОГЭ по информатике: теория и практика за компьютером».