LZ77 и LZW

Платон Каратаев перед сном молится, и в переводе Мод молитва повторена дважды подряд: «Lord Jesus Christ, holy Saint Nicholas, Frola and Lavra! Lord Jesus Christ, holy Saint Nicholas, Frola and Lavra!» Упаковщик LZ77 записывает её так: Lord Jesus Christ, holy Saint Nic<14,3>as, Fr<8,3> and Lavra! <57,56>. Первая половина — буквы как есть, с двумя короткими ссылками назад. Вся вторая половина — одна ссылка: вернись на 57 байт и скопируй 56. Повтор стоит почти ничего, а новая буква — восемь-девять бит. Ниже это видно на первой части «Войны и мира»: каждая буква окрашена по тому, сколько бит она стоит в настоящем блоке DEFLATE.

Без подсветки — почти даром. Имена, обращения, слова, которые уже были на прошлой странице, стоят по одному-два бита на букву: они попадают в длинные ссылки. Ярче всего — русская буква, записанная буквально: два байта UTF-8 по восемь-девять бит, около 17 бит на букву. Полоса внизу показывает весь текст: в начале он дорогой — в окне ещё ничего нет, ссылаться не на что, — а дальше дешевеет. Переключите уровень и окно. С окном в 4 КиБ первая часть стоит 5,78 бита на букву, с окном DEFLATE в 32 КиБ — 4,67, с окном в 256 КиБ — 4,11: дальние повторы тоже повторы, но маленькое окно их не видит.

Идея

Если кусок данных уже встречался, вместо него можно записать ссылку: на сколько байт вернуться и сколько скопировать. Распаковщик просто копирует, ему думать не нужно. Вся работа — у упаковщика: в каждой позиции найти самый длинный повтор в окне — последних нескольких десятках килобайт. Искать перебором дорого, поэтому настоящие упаковщики держат указатель по первым трём байтам и проверяют только места, которые начинаются так же. Сколько таких мест проверять — это и есть «уровень сжатия».

Ссылки, тройки «назад, сколько, следующий знак» и простой поиск по словарю троек разбирает глава курса о сжатии. Здесь — как устроен поиск в zlib, библиотеке, которая стоит за gzip, PNG и сжатием веб-страниц, почему уровни сжатия ведут себя так, как ведут, и что делать словарю LZW, когда он переполнен.

Хеш-цепочки

zlib хранит два массива. head[h] — последнее место, где начиналась тройка байтов с хешем h. prev[i] — предыдущее место с тем же хешем, что у позиции i. Вместе они образуют для каждой тройки хеш-цепочку: от самого свежего вхождения к более старым. Вставка — две записи в массивы на каждый байт, без всякого удаления: позиции, которые ушли за окно, просто перестают проверяться. Хеш считается скользящим, как у Рабина и Карпа — комментарий в исходнике zlib так и говорит, — и по умолчанию занимает 15 бит.

В листинге ниже хеш-таблица — словарь по точным трём байтам, без коллизий; у zlib тройка сворачивается в 15 бит, и в цепочку изредка попадают чужие тройки, которые потом отсеивает сравнение. Нажмите на букву:

У «Antichrist» во втором упоминании цепочка короткая, и лучший кандидат — первое упоминание тремя десятками байтов раньше. Теперь переключите на ДНК. Разных троек в четырёх буквах всего 64, и каждая встречается в среднем каждые 64 байта: цепочки в окне из 32 КиБ вырастают до сотен звеньев. Совпадения при этом короткие, потому что ДНК почти не повторяется. Уровень 9 честно проходит до 4096 звеньев и почти ничего не выигрывает. Замер ниже это подтвердит: на геноме фага уровень 9 работает в десятки раз дольше уровня 1.

Ленивое сопоставление и уровни

Жадный упаковщик берёт самый длинный повтор в текущей позиции. Но бывает, что он находит, скажем, три байта, а с соседней позиции начинается повтор в двадцать: взяв короткую ссылку, он его проглотит. Ленивое сопоставление откладывает решение на шаг: нашли повтор в позиции i — посмотрим, что даёт i + 1. Если там длиннее, в i выдаётся одна буква, и всё повторяется. В исходнике zlib сказано, что идея принадлежит Яну-Марку Вамсу и что авторы нашли её в упаковщике freeze Леонида Брукхиса.

Уровень сжатия в zlib — это четыре числа из таблицы configuration_table в deflate.c:

Есть и мелкие правила: на ленивых уровнях повтор из трёх байтов дальше 4096 байт назад отбрасывается — ссылка на него стоит дороже трёх букв. Листинг ниже повторяет эту логику для уровней 1, 6 и 9.

Код

Упаковщик LZ77 с хеш-цепочками и ленивым разбором, распаковщик и подсчёт размера блока DEFLATE с фиксированными кодами Хаффмана — теми, что заданы в стандарте раз и навсегда, без таблиц в начале блока. Настоящий zlib строит для каждого блока свои коды по частотам, как в статье о коде Хаффмана, и выходит ещё меньше; разбор на буквы и ссылки у него такой же.

На первых тридцати тысячах букв романа (51 749 байт) уровень 1 прошёл по цепочкам 33 575 звеньев и выдал 26 024 байта. Уровень 6 прошёл в 18 раз больше звеньев и сжал на 27 % сильнее: ссылки в среднем стали длиннее — 8,4 байта вместо 5,1, — и их понадобилось меньше. Уровень 9 удвоил работу ещё раз и выиграл ещё полтора процента. Это обычная картина: первые шаги поиска окупаются, дальше каждый следующий приносит всё меньше.

Окно

Ссылка в DEFLATE дотягивается не дальше чем на 32 КиБ назад: так задан формат, расстояние кодируется числом до 32 768. zlib оставляет запас под буфер чтения и ссылается не дальше чем на 32 506 байт. Всё, что дальше, для упаковщика как будто не встречалось. Сцена в начале статьи показывает, сколько это стоит на первой части романа: с окном 4 КиБ — 5,78 бита на букву, с окном DEFLATE — 4,67, с окном 256 КиБ — 4,11. Имена героев и обороты повторяются на расстоянии глав, а не абзацев.

Поэтому потомки DEFLATE первым делом расширили окно: в Brotli оно до 16 МиБ (RFC 7932), zstd и xz позволяют мегабайты и больше. Платить за большое окно приходится памятью упаковщика и распаковщика и более длинными цепочками; это ещё одна ручка, которую поворачивает уровень сжатия.

Сколько это стоит

Вставка в цепочку — O(1) на байт. Поиск в позиции — не больше chain звеньев, и в каждом сравнение до 258 байт, поэтому худший случай — O(n · chain · 258), а на обычных данных сравнение почти всегда обрывается на первом же байте: zlib, как и листинг, сначала проверяет байт, который сделал бы совпадение длиннее найденного. Распаковка — O(n) и не зависит от уровня: распаковщик ничего не ищет. Замер — настоящий zlib в Python и собственный DEFLATE стандартной библиотеки в Go на четырёх видах данных: первой части романа, исходниках сцен этого каталога, таблице землетрясений и геноме фага лямбда.

На прозе уровень 9 в Python в двенадцать раз медленнее уровня 1 и даёт 28,6 % от исходного размера вместо 38,9 %. Почти весь выигрыш набран к уровню 6, а последние уровни стоят дорого. На ДНК картина хуже: уровень 9 медленнее уровня 1 в тридцать раз и сжимает лишь с 33,0 до 29,6 %, а уровень 6 на этом геноме даже чуть лучше девятого. Причина — цепочки: в четырёх буквах всего 64 тройки, цепочки длинные, совпадения короткие, и уровень 9 добросовестно проходит до 4096 звеньев впустую. Go устроен иначе — у него своя реализация и свои параметры уровней, — но общая форма та же.

LZW: словарь вместо окна

LZW не ссылается назад. Он держит словарь фраз: в начале — 256 одиночных байтов, дальше каждая выданная фраза, продлённая на следующий байт, становится новой фразой с новым номером. Распаковщик строит такой же словарь сам, поэтому передавать его не нужно. Номера пишутся сначала 9 битами, потом 10, 11 и так до предела: 12 бит в GIF, по умолчанию 16 в программе compress. Как растёт словарь на скороговорке и чем кончилась история с патентом на LZW, рассказывает глава курса. Здесь — что делать, когда словарь полон.

Вариантов три. Можно заморозить словарь и дальше пользоваться тем, что есть: спецификация GIF требует от распаковщика не менять полный словарь, пока не придёт код сброса. Можно сбрасывать его сразу, как только он заполнился. А можно, как compress, оставить полный словарь, но каждые 10 000 байт проверять степень сжатия и сбрасывать словарь, если она упала. Разница видна на файле, который меняется посередине, — например, архиве, где за геномом лежит текст:

Двенадцатибитный словарь, замёрзший на геноме, превращает весь русский текст в коды по одному байту: каждый байт становится 12-битным кодом, и файл выходит больше исходного — почти 11 бит на байт. Сброс при заполнении спасает положение: 3,19 бита на байт. Сброс по падению степени сжатия, как в compress, ещё лучше — 3,01: словарь живёт, пока он полезен. На 16 битах словарь вмещает почти всю первую часть, и сжатие 2,63 бита на байт.

История

Якоб Зив и Абрахам Лемпель опубликовали LZ77 в 1977 году, а через год — LZ78, со словарём фраз вместо окна. В 1982 году Джеймс Сторер и Томас Шимански заметили, что не обязательно дописывать к каждой ссылке следующий знак, достаточно флага «буква или ссылка», — так устроены почти все потомки LZ77. В 1984 году Терри Уэлч упростил LZ78 до LZW, и вскоре на его основе появилась программа compress; среди её авторов в исходниках — Спенсер Томас, Джеймс Вудс и Джо Орост. DEFLATE придумал Фил Кац для PKZIP, а в 1996 году Питер Дойч описал его в RFC 1951. Его самую распространённую реализацию, zlib, написали Жан-лу Гайи и Марк Адлер. В комментарии к коду zlib сказано, что прежняя версия этого файла искала повторы более сложным алгоритмом Фиалы и Грина — линейным, но более медленным в среднем, прожорливым и запатентованным; от него отказались в пользу хеш-цепочек.

Задачи

В первой задаче нужно распаковать LZW со сбросами словаря и не споткнуться на номере, которого ещё нет. Во второй — посчитать сложность строки по Лемпелю и Зиву: ту самую меру 1976 года, из которой вырос LZ77, — быстро, с помощью суффиксного массива.