Задание 4: Кодирование и декодирование информации

Типовая формулировка: «По каналу связи передаются сообщения, содержащие только N букв. Для передачи используется двоичный код, удовлетворяющий условию Фано. Известны кодовые слова для нескольких букв. Какое наименьшее количество двоичных знаков потребуется для кодирования слова …?» В конце обычно даётся примечание: условие Фано означает, что ни одно кодовое слово не является началом (префиксом) другого. Задание оценивается в 1 первичный балл, относится к базовому уровню сложности, но требует аккуратной работы с деревом кодов и внимательного подсчёта — обычно на него уходит 3–5 минут.

• Условие Фано (префиксность): код называется удовлетворяющим условию Фано, если ни одно кодовое слово не является началом другого кодового слова. Это гарантирует, что закодированное сообщение можно однозначно разбить на буквы без разделителей.
• Кодовое дерево: множество всех двоичных слов длины $k$ удобно представлять как вершины двоичного дерева на глубине $k$; всего таких вершин $2^k$.
• Если вершина стала «листом» (кодовым словом), то все вершины на пути от неё к корню не могут быть отдельными кодовыми словами, и всё поддерево под ней недоступно для новых кодовых слов.
• Неравенство Крафта: для префиксного кода с длинами слов $l_1, l_2, \dots, l_n$ должно выполняться $\sum_{i=1}^{n} 2^{-l_i} \le 1$. Если распределить коды так, что сумма превышает 1, дерево «не вмещает» такие длины и нужно увеличивать глубину.
• Длина сообщения: если буква $i$ встречается в кодируемом слове $n_i$ раз и имеет код длиной $l_i$, то общая длина сообщения $L = \sum_i n_i \cdot l_i$.
• Чтобы длина $L$ была минимальной, самые короткие из доступных кодов нужно отдавать буквам, которые встречаются в слове чаще всего (а лучше — которые встречаются вообще, в отличие от букв, отсутствующих в слове).

1. Выписать полный алфавит и известные кодовые слова с их длинами.
2. Построить (хотя бы мысленно) кодовое дерево до глубины, равной максимальной длине среди известных кодов.
3. Отметить все вершины этой и меньших глубин, которые заняты известными кодами или являются их предками — эти вершины недоступны.
4. Найти все свободные вершины (не заняты и не являются предками занятых), начиная с самой малой глубины — это кандидаты на новые самые короткие коды.
5. Сравнить количество свободных вершин с количеством ещё не закодированных букв. Если не хватает, расщепить часть свободных вершин на следующую глубину (одна вершина глубины $k$ даёт две вершины глубины $k+1$), повторять до точного совпадения количества.
6. Определить частоту каждой ранее незакодированной буквы в целевом слове (сколько раз она встречается). …