Конспект: RLE, Хаффман, LZ77, арифметическое кодирование

Понятия

Сжатие без потерь - запись короче исходной, по которой данные восстанавливаются точно.

RLE - замена серии одинаковых символов парой «длина, символ».

Энтропия - H = Σ p · log₂(1/p) бит на символ, где p - доля символа в тексте. Предел для способов, которые кодируют символы по отдельности и знают только их частоты.

LZ77 - замена повторяющегося куска ссылкой «назад, длина» на его прошлое вхождение. Окно - участок уже обработанного текста, в котором ищутся повторы. Литерал - символ, записанный как есть.

Арифметическое кодирование - кодирование всего сообщения одним числом из отрезка, ширина которого равна произведению долей символов.

Кодирование диапазона - арифметическое кодирование на машинных словах вместо длинных чисел.

Канонический код Хаффмана - коды подряд по сортировке (длина, символ); передают только длины.

Коды целых для разностей отсортированных номеров: гамма Элиаса (2·log₂ x + 1 бит), Голомб-Райс (2^k ≈ 0.69 · среднее), varint (по 7 бит в байт).

Что унести

ПОЧЕМУ НЕЛЬЗЯ СЖАТЬ ВСЁ
файлов длины n бит:        2ⁿ
записей короче n бит:      2ⁿ − 1          одной не хватает
сжатие - ставка на закономерность; на данных без неё метод ПРОИГРЫВАЕТ

ЭНТРОПИЯ: почему логарифм
символ с долей 1/8 = «один из восьми» → три вопроса «да или нет» → log₂ 8 = 3 бита
символ с долей p   = «один из 1/p»    → log₂(1/p) бит
H = среднее по позициям текста = Σ p · log₂(1/p)

abracadabra:  H = 2,040 бита на символ;  11 · H = 22,4;  Хаффман 23;  три бита на символ - 33

Энтропия - предел для МОДЕЛИ, а не для данных. "ab" * 500: по частотам 1000 бит, а LZ77 пишет два литерала и ссылку. Журнал из 826 символов: по частотам 3578 бит, LZ77 - около 900.

LZ77: распаковка
литерал              → дописать
ссылка (назад, дл.)  → дл. раз: взять символ на «назад» позиций ОТ КОНЦА и дописать
                       ПО ОДНОМУ СИМВОЛУ - дописанное сразу становится источником

a, (1, 9)            → aaaaaaaaaa          серия без отдельного правила
a, b, (2, 6)         → abababab

АРИФМЕТИЧЕСКОЕ КОДИРОВАНИЕ
отрезок [0, 1) делится по долям; символ выбирает свою часть, дальше делится она
ширина итога = произведение долей
бит = log₂(1/ширина) + до двух = энтропия · n + 2 НА ВСЁ СООБЩЕНИЕ

aba, доли a = 3/4, b = 1/4:   [0, 1) → [0, 3/4) → [9/16, 3/4) → [9/16, 45/64);   число 5/8 = 0,101

ЧТО ВНУТРИ ФОРМАТОВ
gzip, zip, PNG     LZ77 (окно 32 КБ) + Хаффман        = deflate
xz                 LZ77 (большое окно) + кодирование диапазона
zstd               LZ77 + асимметричные системы счисления (ANS, 2009)
H.264, H.265       двоичное арифметическое кодирование на последней ступени

Ловушки джокера

RLE на данных без серий. Вдвое длиннее. Формат должен уметь записать кусок как есть.

Счётчик серии не помещается в отведённое поле. Серию режут; забытая проверка теряет символы.

Счётчик цифрами в общем потоке. 311a - это «три единицы и a» или «311 букв a»?

Сжатие сжатого и сжатие зашифрованного. Закономерностей не осталось. Сжимать до шифрования.

Копирование ссылки срезом. a, (1, 9) даёт aa вместо десяти a. Ломается на самых сжимаемых данных.

Расстояние от начала текста. «Назад» отсчитывается от текущего конца.

Повтор дальше окна. Два одинаковых файла по мегабайту при окне 32 КБ сжимаются как разные.

Распаковка без предела размера. Несколько килобайт разворачиваются в гигабайты.

Склейка строк в распаковщике. Квадратичное время: 4,5 миллиона шагов вместо 12 тысяч на замере.

Дроби с плавающей точкой в арифметическом кодировании. Отрезок быстро становится уже их точности.

Доли у упаковщика и распаковщика разошлись. Мусор с первого же расхождения до конца.

Конец сообщения не обозначен. Нужна длина или символ конца.

Куда это ведёт

У всех трёх методов модель простая: серии, частоты, повторы в окне. Следующая глава - про модели посложнее. Словарные методы строят словарь на ходу и ссылаются на его номера. Контекстные модели предсказывают символ по предыдущим и отдают предсказание арифметическому кодировщику. А преобразование Барроуза-Уилера ничего не сжимает само: оно переставляет символы так, что после него простые методы этой главы начинают работать намного лучше.