3 Что надо знать для решения

Что надо знать для решения

Неравномерный двоичный код — простыми словами

Каждой букве сопоставили слово из нулей и единиц — это её код. Слово «АБ» кодируется так: берём код буквы А, сразу за ним код буквы Б, без пробелов и разделителей. Например, если А = 0, Б = 10, то «АБ» → 010.

Проблема: когда коды разной длины и записаны подряд без разделителей, приёмник должен как-то понять, где кончается одна буква и начинается другая. Если коды подобраны неудачно, расшифровка получится неоднозначной. Спасает от этого условие Фано.

Условие Фано — сердце всего задания

Условие Фано: ни один код не является началом (префиксом) другого кода.

Проще: если код буквы А — это 0, то ни у одной другой буквы код не может начинаться с `0` (нельзя 01, 00, 011 и так далее). Ветка, начинающаяся с 0, целиком «забронирована» буквой А.

Посмотри на два дерева. Слева условие Фано нарушено: код А = 0 является началом кода Б = 01. Приёмник, увидев 0, не поймёт — это уже буква А или только начало буквы Б. Справа всё хорошо: коды 0, 10, 11 сидят в разных «тупиках», и ни один не начинается с другого.

Иллюстрация к заданию 4, рисунок 1Иллюстрация к заданию 4, рисунок 2

📌 Как проверить условие одним взглядом

Код удовлетворяет условию Фано ⟺ на дереве все коды сидят в листьях (в самых кончиках веток), и ни один код не стоит «по дороге» к другому. Если хоть один код оказался промежуточным узлом, через который проходит путь к другому коду, — условие нарушено.

Дерево кода — главный инструмент

Дерево кода — это картинка, на которой любой двоичный код превращается в путь от корня:

  • спуск влево — это бит `0`,

  • спуск вправо — это бит `1`.

Путь от корня до кружка, читаемый по битам, и есть код. Например, чтобы попасть в код 10, идём вправо (1), потом влево (0).

Иллюстрация к заданию 4, рисунок 3

Кружки на дереве бывают трёх видов, и по цвету сразу видно, что происходит:

  • Тёмно-фиолетовый кружок — занятый код. Это лист, дальше ветка не растёт (условие Фано запрещает вешать что-то ниже).

  • Зелёный кружок — свободная ветка. Сюда можно поместить код новой буквы.

  • Золотая обводка — код, который мы выбрали в ответ.

  • Маленькие серые точки — промежуточные узлы, просто часть пути.

⚠️ Занятая ветка закрывает всё под собой

Как только код занял какой-то узел, вся ветка ниже него исчезает — туда больше нельзя ставить коды. Поэтому короткие коды «дорогие»: код длины 1 (0) забирает сразу половину всего дерева. Это ключ к задачам на минимальную длину.