Краткое сравнение для потоковой передачи с меняющимся распределением символов — ключевые компромиссы: скорость, степень сжатия, сложность реализации, память.

Основные формулы:
[H = -\sum_i p_i \log_2 p_i]
Для статического Хаффмана средняя длина кода (L) удовлетворяет
[H \le L < H + 1,]
избыточность (\mathrm{red} = L - H). Арифметическое кодирование при больших блоках стремится к (H) (избыточность ~ (O(1/n)) для блока длины (n)).

1) Статический код Хаффмана

Как работает: строится таблица кодов по оценённым частотам (обычно в двух проходах или с предварительной передачей частот).Скорость: быстрая кодировка/декодировка — обычно таблица и прямой доступ, читается/пишется по символу: примерно (O(1)) на символ.Сжатие: хорошее для стационарных распределений; верхняя граница (L < H+1). При часто меняющем распределении — теряется эффективность, если модель не обновляется.Сложность реализации: низкая — простая постройка дерева, таблицы.Память: (O(|A|)) для таблиц/дерева, где (|A|) — размер алфавита.Потоковая специфика: не адаптируется автоматически; требует периодической пересборки модели (скользящие окна/блоки) или передачи таблиц, что даёт задержки и доп. трафик.

2) Адаптивный Хаффман (FGK, Vitter)

Как работает: дерево обновляется онлайн по мере поступления символов, кодируются символы без предварительного знания частот.Скорость: кодирование/декодирование + обновление дерева; обычно чуть медленнее статического, типично (O(1))–(O(\log |A|)) на символ в зависимости от реализации; алгоритм Vitter оптимизирован для лучшего поведения.Сжатие: лучше для меняющихся распределений, но в ранней фазе (начальная инициализация) и при резких сменах остаётся отставание от оптимума; обычно уступает адаптивному арифметическому.Сложность реализации: средняя — сложнее статического (правильные операции обмена/номера узлов).Память: (O(|A|)) для дерева и счётчиков.Потоковая специфика: нативно потоковый (без двух проходов и без передачи таблиц); чувствителен к ошибкам — рассинхронизация модели при битовых ошибках.

3) Арифметическое кодирование (и его практичная реализация — range/range coder)

Как работает: кодирует последовательность как дробь в интервале [0,1) по накопленным вероятностям; в адаптивной версии модель (счётчики или контекст) обновляется онлайн.Скорость: медленнее статического Хаффмана; практичные реализации (range coder, целочисленные версии) достигают близкой к (O(1)) амортизированной работы, но константы выше (многократные целочисленные операции, нормализация, перенос битов).Сжатие: близко к энтропии (H), лучше Хаффмана особенно при дробных частотах и сложных моделях; с контекстными моделями (PPM, n-gram) даёт существенно лучшее сжатие для сложных данных.Сложность реализации: выше — требуется аккуратная работа с точностью/ренормализацией; range coder проще в реализации, чем “реальная” арифметика с плавающей запятой.Память: модель требует (O(|A|)) для простого порядка‑0; контекстные модели требуют значительно больше (зависит от порядка/структуры).Потоковая специфика: хорошо подходит для адаптивного потокового кодирования; однако побайтная/битовая природа требует аккуратного буферирования/флашинга при пакетной передаче; чувствителен к ошибкам — ошибки могут вести к большой рассинхронизации.

Сравнительные точки принятия решений

Скорость (быстрее → медленнее): статический Хаффман > адаптивный Хаффман ≈ range coder (на практике range coder медленнее, но константы реализации значимы).
(в KaTeX) ( \text{скорость: Huff{stat}} > Huff{adapt} \gtrsim RangeCoder ).Сжатие (лучше → хуже): арифметическое/range (с адаптивной/контекстной моделью) > адаптивный Хаффман > статический Хаффман (при меняющемся распределении).
( \text{сжатие: Range/Arithmetic} > Huff{adapt} > Huff{stat}) (если статический не обновляется).Сложность реализации: статический Хаффман (низкая) < адаптивный Хаффман (средняя) < арифметическое/range + сложные модели (высокая).Память: все три базово требуют (O(|A|)); при использовании контекстных моделей арифметикa требует значительно больше памяти.
(\text{память: } O(|A|)) для простых моделей; контексты → существенно выше.Адаптация к меняющемуся распределению: адаптация встроена в адаптивный Хаффман и адаптивный арифметик; статический — только при рефрешах/блоках.Надёжность/синхронизация: Хаффман устойчивее к локальным ошибкам (символ границы), арифметик чувствителен — ошибка может разрушить дальнейшее декодирование; адаптивные схемы добавляют риск рассинхронизации при ошибках.

Рекомендации практические

Нужна простота и очень высокая скорость, небольшие ресурсы, и распределение меняется не слишком резко → статический Хаффман с периодической пересборкой/скользящим окном.Стрим с ограниченными ресурсами и без возможности пересылать/согласовывать частоты, приемлемая компромиссная компрессия → адаптивный Хаффман (алгоритм Vitter для лучшей эффективности).Приоритет — максимальное сжатие при адаптивности к быстро меняющимся или сложным распределениям (включая контексты) и можно потерять немного скорости/памяти → адаптивное арифметическое/range кодирование с подходящей моделью (range coder обычно практичнее).Если есть требования по устойчивости к ошибкам/простому восстановлению — выбирать схемы с явными символными границами (Хаффман) или добавить маркеры/срезы и повторную синхронизацию при использовании арифметики.

Если нужно — могу коротко предложить конкретную схему (параметры окна, модель, выбор range coder vs Huffman) под ваши ограничения: скорость, ОЗУ, латентность и ожидаемая скорость смены распределения.