Кодирование Хаффмана

Кодирование Хаффмана — жадный алгоритм, который многократно объединяет два узла с наименьшей частотой, поэтому первое структурное решение — как эффективно поддерживать этот порядок. Наивный подход сортирует после каждого слияния с ценой O(n² log n); min-heap хранит минимум в корне и восстанавливает свойство кучи за O(log n) на операцию, давая O(n log n) в целом. До написания дерева реализуй обобщённый MinHeap<T>, параметризованный компаратором — это вынуждает разделить политику приоритета и тип узла, и делает кучу переиспользуемой для любого будущего жадного алгоритма. Считай частоты символов из строки одним проходом (O(n)); инициализируй один узел кучи на каждый уникальный символ; проверь, что куча корректно возвращает узел с наименьшей частотой при каждом извлечении. Думай о разрешении равенства уже сейчас: если два узла имеют одинаковые частоты, порядок извлечения определяет форму дерева и, следовательно, строки кодов. Выбери стабильное, детерминированное правило — например, предпочитай узел с лексикографически меньшим символом или предпочитай лист перед внутренним узлом — и задокументируй его, потому что тест round-trip будет от него зависеть.

Когда min-heap готов, реализуй классическое построение Хаффмана: извлекай два узла с наименьшими частотами, создавай внутренний узел с частотой, равной их сумме, возвращай этот внутренний узел в кучу и повторяй, пока не останется один узел — это корень. Алгоритм чисто жадный и доказуемо оптимален по аргументу обмена: если бы какое-то другое дерево было лучше, можно было бы поменять два самых глубоких листа-сестры с двумя символами наименьшей частоты и уменьшить ожидаемую длину кода, что противоречит предположению. Граничный случай, который пропускают большинство реализаций, — алфавит с одним уникальным символом (например, 'aaaa'): цикл никогда не срабатывает, потому что изначально существует только один узел, поэтому корень является листом, и ему нужно явно назначить код (по соглашению '0'), чтобы кодирование и декодирование всё равно работали. Ещё один тонкий момент: внутренние узлы не несут символа — только листья. Сделай это строгим типовым инвариантом сейчас, потому что обход при декодировании опирается на него.

Преврати дерево в таблицу кодов через DFS: влево → добавляй '0', вправо → добавляй '1', выдавай (символ, накопленные биты) на каждом листе. Полученные коды prefix-free по построению — ни один код не является префиксом другого, потому что коды живут только на листьях, а любой префикс пути к листу — это внутренний узел. Докажи это себе: если код A является префиксом кода B, можно пройти A в дереве и достичь листа, но тогда оставшиеся биты B должны спускаться от листа, у которого нет потомков — противоречие. Напиши тест свойств, который исчерпывающе проверяет все пары в таблице кодов: для каждой пары (a, b), где a ≠ b, проверяй, что ни a.startsWith(b), ни b.startsWith(a). Это важнейший инвариант корректности во всём проекте. Также проверь, что более короткие коды достаются символам с более высокой частотой: гарантия оптимальности Хаффмана утверждает, что назначение длины кода монотонно не возрастает с частотой, поэтому если freq(x) > freq(y), то len(code(x)) ≤ len(code(y)). Это второй тест свойств, и он обнаруживает ошибки построения дерева, которые round-trip в одиночку пропустил бы.

Кодирование — простая половина: ищи каждый символ в таблице кодов, конкатенируй битовые строки и возвращай результат. Интересные вопросы возникают, когда ты интегрируешь это в реальный компрессор. Во-первых, битовая строка, которую ты производишь, концептуальна — каждый символ это '0' или '1', а не упакованный бит, — что означает, что твой вывод в 8× больше сырых байт до упаковки. Для этого проекта представление строкой символов нормально, потому что позволяет сосредоточиться на алгоритме, но задокументируй разрыв: производственный кодировщик упаковывал бы биты в байты, управлял бы последним частичным байтом со счётчиком дополняющих битов и добавлял бы таблицу кодов (или её каноническую форму) в заголовок, чтобы декодер мог восстановить без внеполосных знаний. Во-вторых, твоя функция encode принимает заранее построенную таблицу кодов, а не исходное дерево — это намеренно, потому что декодирование нуждается в дереве (для обхода ветвей), а кодированию нужна только карта метка-листа-к-битам. Держи два интерфейса разделёнными. В-третьих, измерь сжатие: подсчитай общую длину в битах закодированного вывода и сравни с базовым значением фиксированной ширины ceil(log2(размер_алфавита)) бит на символ. Для любого ввода с искажённым частотным распределением вывод Хаффмана должен быть строго короче — если нет, твоё дерево неверно.

Декодирование — обратная операция: начинай с корня, читай один бит, спускайся влево на '0' или вправо на '1', и выдавай символ листа всякий раз при достижении листа, затем сбрасывайся обратно в корень. Этот обход O(длина_вывода × средняя_длина_кода) и не требует хэш-поиска, поэтому дерево — правильная структура данных для декодирования, даже если карта правильна для кодирования. Корректность декодирования гарантируется свойством prefix-free: поскольку ни один код не является префиксом другого, первый лист, на который ты попадаешь, всегда однозначно является целевым символом. Если тест prefix-free из предыдущего этапа проходит, декодирование тривиально корректно при правильной реализации обхода. Интересный режим отказа — снова случай одного уникального символа: корень — лист без потомков, поэтому цикл 'спускаться по биту' никогда не срабатывает — нужно обрабатывать это особо, выдавая символ для каждого бита во вводе. Напиши тест round-trip: для любой строки s, построенной из известного алфавита, decode(encode(s, codes), tree) === s. Это твой интеграционный тест, и он перекрывает юнит-тесты для encode и decode по отдельности.

Теперь, когда encode/decode работает, порассуждай о том, что на самом деле означает 'оптимальность' и как сделать таблицу кодов передаваемой без дерева. Алгоритм Хаффмана минимизирует ожидаемую длину кода E[L] = Σ freq(x) × len(code(x)), что равно взвешенной длине пути от корня до всех листьев. Аргумент обмена доказывает это: в оптимальном дереве два символа с наименьшей частотой должны быть братьями-сёстрами на самом глубоком уровне — если бы это было не так, можно было бы поменять их с фактическими самыми глубокими братьями-сёстрами и уменьшить E[L], что противоречит оптимальности. Энтропия H(X) = -Σ p(x) × log₂(p(x)) — нижняя граница: ни один однозначно декодируемый код не может достичь ожидаемой длины ниже H(X) бит на символ. Вычисли E[L] и H(X) для 'abracadabra' и сравни — Хаффман укладывается в несколько процентов. Далее, канонические коды Хаффмана: переназначь коды так, чтобы (а) коды одинаковой длины были смежными и (б) в группе одинаковой длины символы были отсортированы алфавитно, а сами коды назначались как последовательные целые числа в двоичном виде. Каноническая форма кодирует те же длины, что и исходное дерево, но с более короткими кодами в среднем для передачи — нужно только передавать отображение символ→длина (а не дерево), и любой декодер может восстановить канонические коды из него. Реализуй codes_canonical(tree), возвращающую канонические битовые строки.