Архиватор PUSHK. Часть 3. Трансформация деревьев Хаффмана

PUSHK Compression Algorithm (C++) архиватор PUSHK data compression C++ алгоритм сжатия данных Алгоритм PUSHK расширяет классический подход к деревьям Хаффмана, добавляя поверх него слой геометрической трансформации, за счёт которого дерево перестаёт быть фиксированным результатом частотного анализа и превращается в управляемую структуру, адаптируемую под требования кодирования и декомпрессии. https://telegra.ph/Arhivator-PUSH-CHast-2-Rezultat-kompressii-grafiki-Obzor-processa-i-log-fajly-03-23 https://telegra.ph/PUSH-Archiver-representation-first-compression-03-23 На первом этапе всё происходит строго по классике: на основе частотной выборки строится стандартное дерево Хаффмана снизу вверх, где редкие элементы оказываются на длинных ветках, а часто встречающиеся — ближе к корню, формируя исходную структуру, которая далее используется как заготовка для последующих преобразований. Далее начинается ключевая часть алгоритма, в которой дерево рассматривается не как финальный результат, а как промежуточная форма, и подвергается серии целенаправленных изменений, включающих рекурсивные развороты ветвей, добавление узлов через врезки и удаление промежуточных или «фантомных» элементов через стяжки, причём все эти операции направлены на изменение геометрии дерева без потери его логической связности. Ключевым механизмом здесь является контейнер (escape-узел), который фактически создаёт дополнительную структуру — «параллельную плоскость», в которую можно сбрасывать части веток, если они оказываются слишком глубокими или неэффективными, благодаря чему основное дерево не перегружается длинными путями, а сложные участки выносятся отдельно и обрабатываются через этот контейнер по мере необходимости. После того как геометрия дерева приведена к целевому виду, выполняется финальный этап — построение префиксного дерева сверху вниз, которое уже напрямую используется декомпрессором, однако из-за изменений структуры исходные позиции элементов перестают совпадать, поэтому дополнительно формируется таблица реиндексации, позволяющая восстановить точное соответствие между исходными символами и их новыми индексами. В результате в битстрим записывается не частотная модель, а только геометрия дерева и таблица реиндексации, что делает представление более компактным и при этом даёт полный контроль над структурой декодирования. Если суммировать различия между этапами, то переход от первого дерева ко второму означает изменение геометрии при сохранении структурного подобия, переход ко третьему — сохранение геометрии при изменении внутренней организации, а сравнение первого и третьего состояний показывает полную перестройку структуры при сохранении точного соответствия символов за счёт реиндексации. Главный инженерный смысл PUSH заключается в том, что он отделяет статистическую оптимизацию (задачу Хаффмана) от структурной оптимизации (собственно PUSH), позволяя не просто использовать полученное дерево, а целенаправленно формировать его геометрию, в том числе за счёт вынесения неудачных участков в контейнер, что особенно важно в задачах работы с графикой, бинарными потоками и другими структурами, где форма дерева влияет на эффективность не меньше, чем сами вероятности. C++ , data compression , Optimized Huffman based algorithm, Data Compression