Задание 4 · Кодирование и декодирование информации
Практика и итог
Вся тема на одной странице: как решилась задача темы, главное из подтем, порядок решения и частые ошибки.
Одна задача — вся тема
Задача темы — кратчайший код Г при кодах А 0, Б 10, В 110, если код Д тоже должен существовать, — решается одним деревом, и каждая подтема добавляла к нему новый шаг. Пролистай решение: в подписи каждого шага — подтема, откуда приём.
- Подтема 1. Коды А — 0, Б — 10, В — 110 удовлетворяют условию Фано: ни один не совпадает с началом другого.
- Подтема 2. На дереве видно свободное место: кратчайший свободный код — 111. Но если отдать его Г, для Д места не останется.
- Подтема 3. Место нужно каждой букве: вершину 111 делят на две, Г — 1110, Д — 1111. Ответ задачи темы — 1110.
Подтема 4 добавляет к тому же дереву частоты: когда спрашивают длину сообщения, частым буквам отдают короткие свободные места, а длину считают как сумму «частота × длина кода».
Карта темы
Каждая подтема дала несколько правил, и любое решение собирается из них. Сверху — путь от условия к ответу, ниже — по блоку на подтему. Заголовок блока ведёт на подтему.
- Алфавитвсе буквы и известные коды
- Деревозанятые и свободные ветви
- Ответкод, сумма длин или длина слова
1Код и условие Фано
- условие Фанони один код не совпадает с началом другого
- проверкав обе стороны: короткий в длинном и наоборот
- ведущие нуличасть кода: 01 и 1 — разные коды
- 2ᵏразных кодов длины k
2Кодовое дерево и кратчайший код
- длина кодаглубина вершины дерева
- буквалист: ниже неё ветвей нет
- свободная ветвьзанять одной буквой или разделить
- кратчайший кодсначала короче, при равной длине — меньше
3Место для всех букв и сумма длин
- последняя ветвьне занимать, пока остались буквы
- резерводна свободная ветвь вмещает сколько угодно букв
- сумма длинделить самую короткую свободную вершину
4Длина закодированного слова
- длина словасумма «частота × длина кода»
- частые буквына короткие места; сравни два дерева
- буквы вне словатоже в алфавите — им нужно место
Как решать
Любое задание 4 решается одним порядком из пяти шагов. Каждому шагу ты уже учился — под ним номера подтем:
Перед ответом перечитай последнюю фразу условия: спрашивают код, сумму длин, длину сообщения или что-то ещё — это разные числа на одном и том же дереве.
Частые ошибки
Восемь ошибок встречаются чаще других, и каждую ловит один вопрос к себе. Выбери ошибку — увидишь, как её исправить, и вопрос, который её ловит:
- разные — значит верно
- коды 0 и 01 разные — значит, подходят → 0 — начало 01, условие Фано нарушено. Спроси себя: не начинается ли один код другим?подтема 1
- одно направление
- новый код проверили только как начало старых → проверяют в обе стороны. Спроси себя: а старый код не начало нового?подтема 1
- ведущие нули
- код 010 записан как 10 → нули в начале — часть кода. Спроси себя: сохранилась ли длина кода?подтема 1
- последняя ветвь
- Г занял последнюю свободную вершину 111 → вершину делят: Г — 1110, Д — 1111. Спроси себя: остались ли буквы без кода?подтема 3
- длинное место
- для суммы длин делят глубокую вершину → делят самую короткую свободную. Спроси себя: какая свободная вершина ближе к корню?подтема 3
- буквы вне слова
- забыты буквы, которых нет в слове → им тоже нужно место. Спроси себя: все ли буквы алфавита получили код?подтема 4
- без повторов
- длину слова считают по разным буквам → каждую букву столько раз, сколько встречается. Спроси себя: сколько раз эта буква в слове?подтема 4
- частой — кратчайший
- самой частой букве сразу отдан кратчайший код → сравнивают два варианта дерева. Спроси себя: не выгоднее ли разделить эту ветвь?подтема 4
Итог
Тема пройдена: задача темы решена одним деревом до кода 1110. Вот что взять с собой.
- ПорядокДерево, свободные места, распределение, выбор, проверка.
- Условие ФаноНи один код не начало другого — в обе стороны.
- МестоПоследнюю свободную ветвь делят, пока есть буквы.
- ОтветКод, сумма длин и длина слова — разные числа.
- Задача темыВершину 111 делят: Г — 1110, Д — 1111.
Проверьте себя
Ответь сначала сам, потом открой ответ.
Коды А — 10, Б — 101. Удовлетворяют ли они условию Фано?
ОтветСкрыть ответ
Нет: 10 — начало 101. На дереве Б лежала бы ниже листа А.
Свободна одна вершина, а без кода остались три буквы. Что делать?
ОтветСкрыть ответ
Делить её: под одной свободной вершиной помещается сколько угодно букв, например 0, 10, 11 от неё вниз.
Какая из свободных вершин даёт кратчайший код: 011 или 10?
ОтветСкрыть ответ
10: она ближе к корню, код короче. Из кодов одной длины берут меньший.
В слове ТАРАКАН буква А встречается три раза, код А — 01. Сколько бит даёт буква А в длине слова?
ОтветСкрыть ответ
3 · 2 = 6: частота умножается на длину кода.
Практика
Для проверки ответов нужен JavaScript. Условия, подсказки и решения доступны ниже.
Кратчайший код П с местом для Р
Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н, П, Р, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв К, Л, М, Н использовали соответственно кодовые слова 00, 01, 101, 11. Для букв П и Р кодовые слова неизвестны. Укажи кратчайшее возможное кодовое слово для буквы П. Если таких кодов несколько, укажи код с наименьшим числовым значением.
Введите кодовое слово (последовательность из 0 и 1).
Подсказка
Код П не должен занять последнюю свободную ветвь.
Решение
Свободна только ветвь 100; код 100 не оставил бы места Р.
Ответ: 1000
Три оставшиеся буквы
По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж, З. Используется двоичный код, удовлетворяющий условию Фано. Известны коды: А — 000, Б — 01, В — 100, Г — 11, Д — 1010. Какое наименьшее количество двоичных знаков потребуется для кодирования трёх оставшихся букв? В ответе запишите суммарную длину кодовых слов для букв Е, Ж, З.
Введите число.
Подсказка
Делят самую короткую свободную ветвь.
Решение
Свободны 001 и 1011; делим более короткую 001 — места 0010, 0011, 1011, 4 + 4 + 4 = 12.
Ответ: 12
Слово ЛОПАТА
По каналу связи передаются сообщения, содержащие только буквы А, Л, О, П, Т. Используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Л — 0, О — 10. Какое наименьшее количество двоичных знаков потребуется для кодирования слова ЛОПАТА?
Введите число.
Подсказка
Л и О заданы; А встречается дважды.
Решение
Свободна ветвь 11; А встречается дважды и получает 110, П и Т — 1110 и 1111; 1 + 2 + 4 + 3 + 4 + 3 = 17.
Ответ: 17
Слово ТАРАКАН
По каналу связи передаются сообщения, содержащие только буквы А, К, Н, Р, Т, Я. Используется двоичный код, удовлетворяющий условию Фано. Известен код буквы Р — 011. Какое наименьшее количество двоичных знаков потребуется для кодирования слова ТАРАКАН?
Введите число.
Подсказка
Сравни два варианта дерева; букве Я нужна резервная ветвь.
Решение
Свободны 00, 010 и 1; А встречается трижды и получает 1. Если Т взять кратчайший свободный 00, то К, Н и резерв для Я уйдут в ветвь 010… — 17. Лучше разделить 00: Т — 000, К — 001, Н — 0100, резерв — 0101; Т | А | Р | А | К | А | Н — 3 + 1 + 3 + 1 + 3 + 1 + 4 = 16.
Ответ: 16
Слово КОРОВА
Все заглавные буквы русского алфавита закодированы неравномерным двоичным кодом, в котором никакое кодовое слово не является началом другого кодового слова. Известен код буквы Р — 11. Какое наименьшее число двоичных знаков может содержать код слова КОРОВА?
Введите число.
Подсказка
Все буквы алфавита — резервная ветвь с частотой 0.
Решение
Свободны 0 и 10; О встречается дважды. Код 0 для О заставляет К, В, А и резерв уйти в ветвь 10… — 16. Лучше разделить 0: К — 00, О — 01, В — 100, А — 1010, резерв — 1011; К | О | Р | О | В | А — 2 + 2 + 2 + 2 + 3 + 4 = 15.
Ответ: 15