1. Принцип Дирихле: почему не существует универсального архиватора, способного уменьшить любой файл

Когда мы ежедневно используем zip, gzip, zstd, 7z или PNG, уменьшая документы, исходный код или изображения в несколько раз и при распаковке восстанавливая их бит в бит (сжатие без потерь / обратимое сжатие), возникает естественный вопрос: если архиватор уменьшает файл, почему бы не сжать полученный .zip-архив еще десять раз подряд, пока огромный фильм или база данных не сожмется до одного байта?

Ответ категоричен: это математически невозможно. Доказательство не требует даже сложной теории информации и следует напрямую из принципа Дирихле (принципа голубятен / Pigeonhole Principle) элементарной комбинаторики.

Пусть $E: \{0,1\}^* \to \{0,1\}^*$ — функция кодирования без потерь, а $D: \{0,1\}^* \to \{0,1\}^*$ — функция декодирования. Чтобы гарантировать безошибочное восстановление $D(E(x)) = x$ для любого входного файла $x$, отображение $E$ обязано быть инъективным (взаимно-однозначным): если два разных файла $x_1 \ne x_2$ сожмутся в одну и ту же короткую битовую строку $y = E(x_1) = E(x_2)$, декодер никогда не узнает, должен ли он выдать $x_1$ или $x_2$!

Существует ровно $2^N$ различных двоичных файлов длины $N$ бит. В то же время общее число всех двоичных строк строго короче $N$ бит (длины от $0$ до $N-1$) равно:

Поскольку входных файлов длины $N$ («голубей») $2^N$, а более коротких кодовых строк («голубятен») всего $2^N - 1$, любой алгоритм сжатия без потерь, который уменьшает хотя бы один файл, ОБЯЗАН увеличивать (раздувать) другие файлы! Более того, доля файлов длины $N$, которые можно сжать хотя бы на $c$ бит, строго ограничена сверху величиной:

Подавляющее большинство случайных битовых строк алгоритмически несжимаемы (по Колмогорову). Наши архиваторы успешно сжимают реальные файлы лишь потому, что человеческие тексты, программы и фотографии занимают ничтожно малое, высокоструктурированное низкоэнтропийное подмножество в пространстве $\{0,1\}^N$.

2. Теорема Шеннона о кодировании источника и информационная энтропия

В 1948 году Клод Шеннон в работе «Математическая теория связи» установил фундаментальный предел обратимого сжатия. Для дискретного источника без памяти с алфавитом $\mathcal{A} = \{s_1, \dots, s_m\}$ и распределением вероятностей $P = (p_1, \dots, p_m)$ собственная информация (Surprisal) символа $s_i$ и её математическое ожидание — энтропия Шеннона $H(X)$ — определяются как:

Любой префиксный (мгновенно декодируемый) код с длинами кодовых слов $\ell_1, \dots, \ell_m$ обязан удовлетворять неравенству Крафта — Макмиллана:

Используя неотрицательность дивергенции Кульбака — Лейблера $D_{\text{KL}}(P \,\|\, Q) \ge 0$ для $q_i = 2^{-\ell_i}/Z$ ($Z = \sum 2^{-\ell_i} \le 1$), получаем теорему Шеннона о кодировании источника без шума для средней длины кодового слова $L = \sum_{i=1}^m p_i \ell_i$:

  flowchart TD
    A["Исходный поток данных (Текст / Изображение / Бинарный код)"] --> B["Этап 1: Преобразование и словарное моделирование (BWT / LZ77)"]
    B --> C["Распределение вероятностей P(s) символов и пар (смещение, длина)"]
    C --> D["Этап 2: Статистическое энтропийное кодирование (Huffman / Арифметическое / ANS)"]
    D --> E["Компактный битовый поток вблизи предела Шеннона N·H(X)"]

3. Три поколения энтропийного кодирования: Хаффман, арифметическое кодирование и ANS

3.1 Кодирование Хаффмана (1952): оптимальные целочисленные префиксные деревья

Жадный алгоритм Дэвида Хаффмана за время $O(m \log m)$ строит префиксное дерево с минимальной средней длиной, последовательно объединяя два наименее вероятных узла. Однако у кода Хаффмана есть фундаментальное ограничение: каждое кодовое слово должно иметь целое число бит ($\ell_i \ge 1$). Символ с вероятностью $p_1 = 0{,}99$ несет лишь $-\log_2(0{,}99) \approx 0{,}0145\,\text{бита}$ информации, но тратит минимум $1\,\text{целый бит}$.

3.2 Арифметическое кодирование (Arithmetic / Range Coding): дробное число бит

Арифметическое кодирование (Риссанен, Паско, Уиттен и др.) преодолевает целочисленный барьер, отображая всю последовательность сообщения $x_1 x_2 \dots x_N$ в единый подинтервал $[L_{\text{low}}, H_{\text{high}}) \subset [0, 1)$ ширины $\Delta = \prod_{t=1}^N P(x_t)$, для записи которого требуется $\lceil -\log_2 \Delta \rceil + 1 \approx N \cdot H(X)$ бит. Это позволяет тратить дробное число бит на символ, но требует ресурсоемких операций умножения и ренормализации.

3.3 Асимметричные системы счисления (ANS, Ярек Дуда, 2009–2014)

Польский физик и математик Ярек Дуда изобрел Asymmetric Numeral Systems (tANS и rANS), объединив степень сжатия арифметического кодирования со скоростью табличного декодирования Хаффмана. При кодировании символа $s$ с вероятностью $p_s$ целочисленное состояние автомата $x \in \mathbb{N}$ преобразуется по правилу:

Сегодня ANS лежит в основе Zstandard (zstd) от Meta, LZFSE от Apple и JPEG XL от Google.

4. Словарное сжатие и преобразования: LZ77, DEFLATE, BWT и «Сжатие как предсказание»

Чтобы устранить контекстную избыточность и повторы строк, современные архиваторы объединяют словарные методы с энтропийными кодерами:

• LZ77 (Лемпель и Зив, 1977): заменяет повторяющиеся подстроки в скользящем окне обратными ссылками (distance, length). В паре с кодом Хаффмана это образует DEFLATE (gzip, zip, PNG), а в паре с ANS — Zstandard (zstd).
• Преобразование Барроуза — Уилера (BWT, 1994, bzip2): лексикографически сортирует все циклические сдвиги блока данных и берет последний столбец $L$, группируя одинаковые символы с общим правым контекстом для последующего сжатия методами Move-To-Front (MTF) и RLE.

  flowchart TD
    A["Входной поток байтов"] --> B["Поиск длиннейшего совпадения в скользящем окне (LZ77)"]
    B --> C{"Длина совпадения >= 3?"}
    C -- "Да" --> D["Вывод обратной ссылки (distance, length)"]
    C -- "Нет" --> E["Вывод исходного байта (Literal)"]
    D --> F["Энтропийное кодирование через Huffman (DEFLATE) или ANS (Zstandard)"]
    E --> F

В фундаментальном смысле сжатие математически эквивалентно предсказанию: любая вероятностная модель (включая современные большие языковые модели Transformer), минимизирующая кросс-энтропию $-\sum \log_2 P_\theta(x_t \mid x_{