Як працює DEFLATE: наочно

1 Запишіть один раз, а потім посилайтеся назад

У тексті повторюються слова. Так само повторюються зображення: наприклад, рядок неба схожий на попередній. DEFLATE зберігає останні 32 КБ записаних даних. Коли фрагмент повторюється, замість байтів він записує два числа: наскільки далеко назад розташована попередня копія, і яка її довжина .

Копія може перекривати саму себе: команда «повернися на 1 байт, скопіюй 50» записує останній байт ще п’ятдесят разів. Так довгі послідовності однакового кольору стискаються майже до нуля.

2 Короткі коди для частих символів

Те, що залишилося — окремі літери та числа довжин копій, — записується кодом Гаффмана. Часті символи отримують короткі коди, рідкісні — довгі. У цьому тексті пробіл і літери e, a, o та t займають по 4 біти, а велика S — 8.

Коди є канонічними: спочатку їх упорядковано за довжиною, а потім за символом. Щоб відновити всю таблицю, декодеру достатньо знати довжину коду кожного символу. Він читає по одному біту, доки отриманий код не потрапить у діапазон для своєї довжини. Панель під плеєром показує цей процес.

3 Кожен блок має власні коди

Потік поділено на блоки. Блок можна зберегти без змін, використати для нього стандартний фіксований код або — зазвичай — побудувати власний код, пристосований до даних. Сама таблиця теж стискається: довжини кодів описуються коротким кодом, а довгі серії відсутніх символів — довжиною повтору.

4 Як це працює разом

Разом ці два принципи й утворюють весь алгоритм. Текст у плеєрі стискається менш ніж до половини початкового розміру.

5 Де ви з ним зустрічалися

У кожному PNG (у його блоках IDAT), ZIP-архіві — зокрема у файлах Word, Excel і PowerPoint, застосунках Android та електронних книжках, — у файлах gzip і в багатьох завантаженнях браузера. hexscope може покроково відтворити кожен із цих потоків.

Відкрити PNG або ZIP і натисніть Як це розпаковується.

Стандарт описано в документі RFC 1951, який має дев’ять сторінок. Декодер hexscope, що працює просто тут, має відкритий код.