В лекции из образовательного цикла Стэнфордского университета подробно рассматривается семейство алгоритмов сжатия данных под названием асимметричные числовые системы (Asymmetric Numeral Systems, ANS). Преподаватель объясняет теоретические основы и практические преимущества этих кодов, которые объединяют в себе высокую скорость декодирования алгоритмов Хаффмана и близкую к теоретическому оптимуму эффективность арифметического кодирования. В центре внимания лекции оказывается детальный разбор математического аппарата разновидностей rANS и tANS, совершивших революцию в современных практических утилитах сжатия.
📝 Тестирование знаний: разбор задач на арифметическое кодирование 0:05
Лекция традиционно начинается с разбора вопросов квиза по материалам прошлого занятия, посвященного арифметическому кодированию. Студентам предлагалось рассмотреть бернуллиевскую случайную переменную, где вероятность появления символа $A$ равна $p$, а символа $B$ равна $1-p$. Основной вопрос заключался в том, будут ли кодовые слова для последовательностей символов $AB$ и $BA$ иметь одинаковую длину при использовании арифметического кодирования. Преподаватель подтверждает правильность догадки студентов: в идеализированной модели кодера длины кодовых слов действительно совпадают. Это объясняется тем, что вероятности обеих строк равны $p(1-p)$, а длина кода напрямую зависит от длины получившегося интервала.
Однако преподаватель делает важное замечание, ссылаясь на комментарий своего коллеги Шубхама Чандака: в реальных, неидеализированных арифметических кодерах длины этих последовательностей могут различаться в пределах двух бит. Именно поэтому в текст задания была добавлена формулировка об «идеализированной версии» алгоритма. Ответ на второй вопрос теста — выводят ли эти две разные последовательности абсолютно одинаковое кодовое слово — отрицательный. Если представить отрезок от 0 до 1, то комбинации $AB$ и $BA$ будут проецироваться на совершенно разные непересекающиеся подобласти, порождая уникальные двоичные коды.
Вторая часть квиза включала стандартную задачу на декодирование входящего битового потока, который соответствовал вещественному числу $0.609375$, при заданной длине сообщения в три символа. Используя распределение вероятностей (масса символа $A$ составляет $0.5$, а символов $B$ и $C$ — по $0.25$), лектор пошагово демонстрирует процедуру сужения интервалов. На первом шаге число попадает в область символа $B$, после чего масштаб увеличивается для повторения итерации. В результате последовательного выполнения алгоритма на доске восстанавливается исходная строка символов — $BAC$.
⏱️ Проблема скорости: компромисс между эффективностью и производительностью 4:35
Переходя к основной теме лекции, преподаватель напоминает о фундаментальном свойстве арифметического кодирования: оно позволяет полностью отделить построение вероятностной модели данных от самого процесса энтропийного кодирования. Это открывает огромные возможности для создания адаптивных алгоритмов, способных динамически подстраиваться под изменяющееся распределение данных прямо на лету. Существует множество практических вариантов арифметических кодеров, различающихся способами округления интервалов и оптимизацией вычислений, и они повсеместно применяются в ИТ-индустрии.
Тем не менее перед разработчиками встает закономерный вопрос: можно ли считать задачу сжатия данных без потерь полностью решенной? Ответ оказывается отрицательным из-за серьезного практического недостатка технологии. Анализируя статистические графики, лектор отмечает, что арифметическое кодирование существенно опережает классическое кодирование Хаффмана по степени сжатия, измеряемой в битах на символ. Но если обратить внимание на производительность вычислений, ситуация кардинально меняется: скорость работы арифметического кодера — как при кодировании, так и при декодировании — оказывается значительно ниже.
В реальных сценариях инженерам зачастую приходится обрабатывать колоссальные объемы информации на высокой скорости, жертвуя долями процента эффективности сжатия ради экономии процессорного времени. Согласно приведенным в лекции данным из популярного блога Чарльза Блума, разница в скорости декомпрессии между алгоритмами может быть критичной для инфраструктурных проектов. Именно этот вызов послужил катализатором для поиска принципиально новых подходов, которые смогли бы объединить преимущества обоих миров.
🧮 Идея асимметричных числовых систем на простом примере 7:31
Решением описанной дилеммы стало открытие в районе 2014 года асимметричных числовых систем (ANS). По словам лектора, ANS представляет собой не один конкретный архиватор, а целый класс энтропийных компрессоров. Двумя крайними полюсами этого семейства выступают алгоритмы rANS (интервальный) и tANS (табличный). Модификация rANS позиционируется как прямая замена арифметического кодирования, сохраняющая его высокую эффективность, но выигрывающая в скорости. В свою очередь, tANS заменяет коды Хаффмана, работая практически с той же скоростью декодирования, но обеспечивая гораздо более плотное сжатие информации.
Чтобы объяснить внутреннее устройство этой системы с весьма экзотическим названием, преподаватель предлагает аналогию, с которой каждый человек сталкивается в повседневной жизни. Представим, что у нас есть поток данных, состоящий из обычных десятичных цифр от 0 до 9, например: 3, 2, 4, 1, 5. Задача состоит в том, чтобы упаковать эту последовательность в одно-единственное число $x$, отражающее состояние всей системы. Решение очевидно — записать эти цифры последовательно, сформировав число 32415.
С точки зрения теории сжатия, этот процесс представляет собой потоковый кодер, работающий в системе счисления с основанием 10. Алгоритм функционирует по следующему принципу:
- Кодер инициализируется базовым состоянием $x = 0$.
- При получении первой цифры (3) предыдущее состояние умножается на 10 и к нему прибавляется новое значение, давая $x = 3$.
- При поступлении цифры 2 операция повторяется: $3 \times 10 + 2 = 32$.
- Для последующих символов шаги идентичны: состояние последовательно переходит в 324, затем в 3241 и, наконец, достигает финального значения 32415.
Для восстановления исходного сообщения принимающей стороне достаточно выполнить строго обратные математические действия. Финальное число делится на 10 нацело для получения предыдущего состояния системы, а остаток от деления (операция modulo) возвращает декодированный символ. Единственная специфическая особенность такого декодера заключается в том, что символы извлекаются в обратном порядке: сначала 5, затем 4, 1, 2 и 3. Процесс останавливается, когда система возвращается к исходному нулевому состоянию или исчерпывает известный счетчик символов.
📉 Математика rANS: масштабирование под неравномерные вероятности 23:03
Описанный выше симметричный числовой кодер работает идеально и не теряет информацию, однако он оптимален только в одном специфическом случае — когда все символы алфавита имеют строго одинаковую вероятность, равную $0.1$. При равномерном распределении состояние $x$ на каждом шаге увеличивается ровно в 10 раз. Это означает, что для упаковки каждого нового символа мы тратим ровно $\log_2 10$ дополнительных бит, что в точности соответствует энтропии источника.
В реальном мире символы распределены неравномерно. По словам преподавателя, главным правилом сжатия данных является обеспечение длины кода, близкой к величине $\log_2 (1/p)$ для каждого символа с вероятностью $p$. Следовательно, вместо фиксированного умножения состояния на 10, в асимметричных системах число $x$ должно масштабироваться на величину, обратно пропорциональную вероятности конкретного пришедшего символа $s$, то есть примерно в $1/p_s$ раз.
Для реализации этой идеи в алгоритме rANS вводятся специальные целочисленные нотации:
- Вероятности символов представляются в виде дробей $f_s / M$, где $f_s$ — индивидуальная целочисленная частота символа, а $M$ — общий нормализующий знаменатель.
- Для примера рассматривается алфавит из трех символов (0, 1, 2) с вероятностями $3/8, 3/8$ и $2/8$ соответственно. Частоты запишутся как список
[3, 3, 2], а константа $M = 8$. - Параллельно рассчитывается массив кумулятивных (накопленных) частот $cumul_s$, который для данного примера примет вид
[0, 3, 6]путем последовательного суммирования.
Базовый шаг кодирования rANS заменяет простое выражение $x \times 10 + s$ на более сложную математическую конструкцию. Формула разделяет новое состояние на две составляющие — идентификатор блока (block ID) и внутреннее смещение, называемое слотом (slot):
$$x_{next} = \lfloor x_{prev} / f_s \rfloor \cdot M + cumul_s + (x_{prev} \pmod{f_s})$$
Здесь член $\lfloor x_{prev} / f_s \rfloor$ отвечает за глобальное увеличение значения переменной в соответствии с редкостью символа, а кумулятивная частота вместе с остатком от деления аккуратно упаковывают информацию внутрь отведенного числового диапазона.
🔄 Декодирование и интерактивная визуализация алгоритма 37:38
Процесс извлечения данных из полученного значения $x$ в rANS опирается на строгое математическое свойство сформированного слота. Поскольку значение остатка от деления $x_{prev} \pmod{f_s}$ по определению строго меньше частоты $f_s$, величина слота гарантированно зажата в жестких пределах: она всегда больше или равна кумулятивной частоте текущего символа $cumul_s$ и строго меньше кумулятивной частоты следующего по порядку символа $cumul_{s+1}$.
Благодаря этому, декодирование разделяется на три прозрачных этапа:
- Вычисление текущего слота и идентификатора блока с помощью деления нацело и взятия остатка от общего знаменателя $M$: $slot = x \pmod M$ и $block_ID = \lfloor x / M \rfloor$.
- Поиск исходного символа $s$. Поскольку массив кумулятивных частот отсортирован по возрастанию, задача сводится к быстрому бинарному поиску диапазона, в который попадает вычисленный $slot$. Это гарантирует абсолютную уникальность восстановленного знака.
- Реконструкция предыдущего состояния системы по формуле: $x_{prev} = block_ID \cdot f_s + slot - cumul_s$.
Во время лекции демонстрируется пошаговый ручной разбор декодирования числа 101 для упомянутого алфавита с кумулятивными частотами [0, 3, 6]. На первой итерации деление 101 на $M=8$ дает $block_ID = 12$ и $slot = 5$. Значение слота 5 находится между значениями 3 and 6, что однозначно указывает на символ «1». Подстановка чисел в финальное уравнение восстанавливает предыдущее состояние, равное 38.
Преподаватель обращает внимание аудитории на интерактивный веб-инструмент, разработанный создателями курса. Эта утилита, доступная по ссылке в учебных материалах, позволяет визуализировать расширение и сужение числовых состояний в реальном времени, помогая студентам перепроверить свои расчеты при выполнении домашних заданий.
🚧 Потоковый режим и преодоление проблемы бесконечного роста состояния 58:57
Теоретическая схема rANS выглядит безупречно: средняя длина кода на один символ в точности стремится к энтропии источника, поскольку финальное состояние кодируется минимально возможным числом бит $\lceil \log_2 x_{final} \rceil$. Тем не менее при переносе алгоритма на практику инженеры мгновенно сталкиваются с серьезным аппаратным ограничением. Поскольку состояние $x$ множится на величину порядка $1/p_s$ при обработке каждого знака, значение переменной растет экспоненциально. Буквально через 20–40 закодированных символов число превысит разрядность стандартных регистров процессора и произойдет критическое переполнение.
Простое обнуление или сброс состояния при достижении лимита недопустимы, поскольку это уничтожит весь выигрыш от блочного сжатия и лишит алгоритм его оптимальности. Практическое решение заключается в удержании переменной состояния в строго заданном числовом окне от $L$ до $H$. Чтобы реализовать это, в схему кодирования внедряется дополнительный промежуточный шаг, называемый «сжатием состояния» (shrink state):
- Перед тем как вызвать базовую функцию кодирования, текущее состояние проверяется на предмет выхода за верхнюю границу.
- Если число слишком велико, оно последовательно делится на 2 (сдвигается вправо), а отсекаемые младшие биты немедленно отправляются наружу, в итоговый двоичный поток.
- Процесс деления продолжается до тех пор, пока оставшаяся часть $x$ не окажется внутри безопасного диапазона $[L, H]$.
Аналогичным образом перестраивается и декодер. Получив управление, он сначала извлекает символ и базовое состояние, а затем выполняет фазу «расширения» (expand state), считывая ранее сохраненные биты из входного потока и восстанавливая исходную масштабную величину. Путем грамотного выбора границ интервала $[L, H]$, предложенного в оригинальной научной работе по ANS, математически гарантируется абсолютная однозначность и обратимость сквозного потокового процесса.
🏎️ Табличный метод tANS и аппаратные оптимизации 1:15:16
В финальной части лекции поднимается вопрос о максимальном ускорении работы кодеров семейства ANS. Хотя rANS значительно опережает классическое арифметическое кодирование за счет отказа от дорогостоящих операций с плавающей запятой, в его теле все еще присутствуют целочисленное деление и вычисление остатка. Преподаватель озвучивает фундаментальное правило промышленного программирования: если вы хотите кардинально ускорить вычисления, избавьтесь от динамических расчетов и замените их предварительно вычисленными таблицами поиска (lookup tables).
Именно эта концепция легла в основу табличной модификации алгоритма — tANS (Table ANS). Поскольку в потоковом режиме состояние кодера всегда удерживается внутри фиксированного и относительно небольшого окна $[L, H]$, все возможные переходы из текущего состояния для каждого символа алфавита можно рассчитать заранее на этапе инициализации программы. В результате процесс кодирования и декодирования сводится к мгновенному чтению готовых значений из кэша процессора, полностью исключая любые математические операции.
Плата за экстремальную скорость — незначительное ухудшение плотности сжатия из-за неизбежных погрешностей округления при дискретизации таблиц вероятностей. Тем не менее на практике декомпрессия tANS демонстрирует быстродействие, идентичное коду Хаффмана, превосходя его по качеству упаковки информации. По этой причине семейство ANS практически полностью вытеснило старые алгоритмы из современных индустриальных стандартов сжатия.
В заключение лектор анонсирует смену парадигмы курса на следующих занятиях. До текущего момента во всех моделях предполагалось, что символы данных независимы и одинаково распределены (IID). Однако реальная информация — будь то тексты, изображения или код — обладает колоссальным уровнем внутренней корреляции. Предстоящие лекции будут посвящены контекстному моделированию, адаптивному сжатию и тому, как современные большие языковые модели (LLM) используются для достижения рекордных результатов в компрессии данных.
