3 Что надо знать для решения
Что надо знать для решения
Неравномерный двоичный код — простыми словами
Каждой букве сопоставили слово из нулей и единиц — это её код. Слово «АБ» кодируется так: берём код буквы А, сразу за ним код буквы Б, без пробелов и разделителей. Например, если А = 0, Б = 10, то «АБ» → 010.
Проблема: когда коды разной длины и записаны подряд без разделителей, приёмник должен как-то понять, где кончается одна буква и начинается другая. Если коды подобраны неудачно, расшифровка получится неоднозначной. Спасает от этого условие Фано.
Условие Фано — сердце всего задания
Условие Фано: ни один код не является началом (префиксом) другого кода. |
Проще: если код буквы А — это 0, то ни у одной другой буквы код не может начинаться с `0` (нельзя 01, 00, 011 и так далее). Ветка, начинающаяся с 0, целиком «забронирована» буквой А.
Посмотри на два дерева. Слева условие Фано нарушено: код А = 0 является началом кода Б = 01. Приёмник, увидев 0, не поймёт — это уже буква А или только начало буквы Б. Справа всё хорошо: коды 0, 10, 11 сидят в разных «тупиках», и ни один не начинается с другого.
📌 Как проверить условие одним взглядом Код удовлетворяет условию Фано ⟺ на дереве все коды сидят в листьях (в самых кончиках веток), и ни один код не стоит «по дороге» к другому. Если хоть один код оказался промежуточным узлом, через который проходит путь к другому коду, — условие нарушено. |
Дерево кода — главный инструмент
Дерево кода — это картинка, на которой любой двоичный код превращается в путь от корня:
спуск влево — это бит `0`,
спуск вправо — это бит `1`.
Путь от корня до кружка, читаемый по битам, и есть код. Например, чтобы попасть в код 10, идём вправо (1), потом влево (0).
Кружки на дереве бывают трёх видов, и по цвету сразу видно, что происходит:
Тёмно-фиолетовый кружок — занятый код. Это лист, дальше ветка не растёт (условие Фано запрещает вешать что-то ниже).
Зелёный кружок — свободная ветка. Сюда можно поместить код новой буквы.
Золотая обводка — код, который мы выбрали в ответ.
Маленькие серые точки — промежуточные узлы, просто часть пути.
⚠️ Занятая ветка закрывает всё под собой Как только код занял какой-то узел, вся ветка ниже него исчезает — туда больше нельзя ставить коды. Поэтому короткие коды «дорогие»: код длины 1 ( |