Задание №4. Короткий конспект
Условие Фано, выбор кратчайшего кода, место для всех букв и подсчёт длины сообщения с учётом повторений.
Условие Фано
Код одной буквы не является началом кода другой. Проверка пары идёт в обе стороны: новое слово не начинается с готового, а готовое — с нового. Совпадающие коды для разных букв недопустимы.
Если занят \mathtt{10}, запрещены и \mathtt{1}, и \mathtt{101}. В дереве кодов буквы стоят только в листьях.
Что требуется найти
| Вопрос | Что учитывается |
|---|---|
| Кратчайшее кодовое слово | Сначала минимум длины; затем наименьшее или наибольшее значение среди равных по длине вариантов |
| Сумма длин кодов | Каждый запрошенный код один раз. Условие может требовать только неизвестные коды или все коды алфавита |
| Длина сообщения | Длина кода каждой буквы умножается на число её повторений; результаты складываются |
Порядок подбора
- Готовые коды фиксируются: менять их нельзя.
- Исключаются их продолжения и начала. Выделяются свободные начала новых слов.
- Для всех неизвестных букв выбираются совместимые коды. Если одного свободного начала мало, оно делится на два продолжения.
- Сравниваются допустимые варианты по тому показателю, который требуется в вопросе.
- Проверяется полный набор, затем формат ответа: кодовое слово или число битов.
При нескольких неизвестных буквах короткий код одной из них не должен занимать всё свободное место. Буквы, которых нет в конкретном сообщении, тоже получают коды, если входят в заданный алфавит.
Длина сообщения
L=\sum_i n_i\ell_i, где n_i — число повторений буквы, а \ell_i — длина её кода. Для чаще встречающейся буквы полезен более короткий код, если его выбор позволяет закодировать весь алфавит.
В EGE-04-0028 ↗ для слова КАЧАЛКА подходит А — \mathtt{00}, К — \mathtt{0100}, З — \mathtt{0101}; заданы Ч — \mathtt{1}, Л — \mathtt{011}. Длина сообщения: 3\cdot2+2\cdot4+1+3=18 битов.
Возможные ловушки
- Не осталось места для другой буквы. В EGE-04-0044 ↗ свободное начало \mathtt{11} делится на \mathtt{110} и \mathtt{111}, поскольку код нужен двум буквам.
- Пропущен готовый код при подсчёте всех длин. В EGE-04-0049 ↗ к четырём трёхбитным кодам добавляется заданный однобитный: 12+1=13.
- Перепутан выбор среди кратчайших. В EGE-04-0025 ↗ подходят \mathtt{100} и \mathtt{111}, но требуется наибольшее — 111.
- Код заменён числом. Начальные нули — часть кодового слова: \mathtt{010} и \mathtt{10} — разные цепочки. В ответе на вопрос о коде сохраняются все его биты.