DB·VII Хранить и находить Глава 47 из 65
Конкурс упаковки
Пять файлов и одна задача: сделать их как можно меньше и ничего не потерять. Сначала упаковывают ваши собственные хитрости, потом на сцену выходят RLE, Хаффман, LZ77, DEFLATE и перестановка Барроуза — Уилера, а в последнем раунде мы разрешим себе терять, но так, чтобы глаз не заметил. По дороге — архивная война 1988 года, патент, из-за которого появился PNG, и доказательство, что архиватора, сжимающего всё, не бывает.
Хранить и находить
- 45 Базы данных
- 46 Индексы
- 47 Сжатие вы здесь
- 48 Поисковик
Опирается на: 23 · Жадность и электричество 28 · Всё есть биты 07 · Собеседник из строк
Что вы унесёте из главы
- оценивать, сколько можно выжать из данных: избыточность, энтропия и почему случайные байты не сжимаются
- писать RLE и LZ77 и понимать, как устроены bzip2 и DEFLATE — тот, что внутри ZIP, gzip и PNG
- выбирать формат и качество картинки: что теряет JPEG, где его границы и когда нужен PNG
Прошлая глава закончилась опытом: «Война и мир» ужимается почти вчетверо, архив из главы 45 — в два с половиной раза, а три мегабайта случайных байтов — ни на байт. Значит, в тексте и таблицах есть что-то лишнее, что можно выбросить и потом точно восстановить. Что это за «лишнее»? И правда ли ZIP делает из четырёх гигабайт один? Начнём с крайностей.
Миллион нулевых байтов упаковывают тем же способом, что внутри ZIP. Во сколько раз уменьшится файл?
Примерно в тысячу: 991 байт. До миллиона далеко, потому что у этого способа есть потолок. Откуда он берётся, выяснится в раунде про DEFLATE.
Миллион нулей превратился в 991 байт. Скороговорка, повторённая двадцать тысяч раз, — мегабайт с лишним — ужалась в три сотни раз. Самое любопытное в третьей строке: те же байты, перемешанные, ужимаются всего вдвое. Буквы и их частоты прежние, а «лишнего» стало в полтораста раз меньше. Выходит, лишнее сидит в порядке — в том, что следующий знак можно угадать по предыдущим. Нули угадываются целиком, повторы почти целиком, перемешанные буквы — только по частотам, а случайные байты не угадываются вовсе.
С четырьмя гигабайтами то же самое: всё зависит от того, что в них лежит. Тексты, таблицы, программы, журналы сервера, бывает, ужимаются и вдесятеро. Фильм или архив фотографий почти не ужмётся: они уже сжаты, угадывать в них нечего. Всё, что умеет упаковщик, — найти в данных предсказуемое и не хранить его.
Глава устроена как конкурс. Пять файлов-лотов, на сцене упаковщики, табло считает байты. Сначала соревнуются ваши собственные хитрости. Потом один за другим выходят профессионалы — и каждый приносит идею, которую стоит украсть. В последнем раунде правила меняются: можно терять, лишь бы глаз не заметил.
Правила конкурса
Сжатие — это пара программ: упаковщик превращает байты в другие байты, обычно покороче, а распаковщик возвращает исходные. Первые четыре раунда идут по правилу сжатия без потерь: распакованное обязано совпасть с исходным бит в бит. Программа, в которой после упаковки поменялась одна запятая, может и не запуститься, а пропавшая цифра в банковской выписке — это чьи-то деньги. Табло проверяет это у каждого участника: упаковывает, распаковывает, сравнивает. Не совпало — снят с конкурса.
Лотов пять, и они нарочно разные:
- Толстой — первые сорок тысяч знаков «Войны и мира» в UTF-8, 68 536 байт;
- ДНК — геном фага лямбда в формате FASTA из главы 27: буквы A, C, G, T по 70 в строке, 49 254 байта;
- код — исходный текст модуля
randomиз стандартной библиотеки Python, 37 299 байт; - картинка — рисунок 240 × 160 точек в шестнадцать цветов, по байту на точку: номер цвета, строка за строкой, 38 400 байт;
- шум — 30 000 случайных байтов.
Очки — суммарный размер пяти упакованных файлов, чем меньше, тем лучше. Всё лежит в модуле cs.packing: lots() отдаёт лоты, contest(pack, unpack) проводит конкурс и печатает таблицу. Внутри модуля — те же упаковщики, что мы напишем по ходу главы, только собранные вместе.
Милуоки, 1988. Архивная война
Почти сорок лет спустя ZIP есть в каждом компьютере, а файлы .docx, .xlsx и .jar внутри — тоже ZIP-архивы. Способ сжатия, которым он пользуется сегодня, Кац придумал позже, для PKZIP 2.0 в 1993 году; до него конкурс дойдёт к середине.
Раунд 1. Ваши хитрости
Прежде чем смотреть, как сжимают профессионалы, попробуйте сами. Кто читал главу 28, первым делом вспомнит: в UTF-8 каждая русская буква занимает два байта, а в старой кодировке Windows-1251 — один. Перекодируем русский текст в однобайтную кодировку, и Толстой похудеет почти вдвое. Если перекодировать не вышло (скажем, пришла картинка), сохраним байты как есть. Чтобы распаковщик знал, что делать, поставим в начало букву-метку: T — текст, B — байты как есть.
Таблица отрезвляет. Наша хитрость не сжала ничего: все пять лотов стали на байт длиннее, и этот байт — метка. С картинкой, кодом и шумом понятно, в них нет русских букв. Толстого подвела первая же строка романа: «— Eh bien, mon prince. Gênes et Lucques…» «Война и мир» начинается по-французски, а буквы «ê» в Windows-1251 нет. Одной буквы хватило, чтобы хитрость сдалась на всём файле.
Первый урок конкурса: упаковщик рассчитан на какие-то данные, а всё непохожее на них должен пропускать, не ломаясь и не раздувая. Почините хитрость. Можно перекодировать текст по одной букве, а для редких букв, которых нет в Windows-1251, завести исключение: нулевой байт, а за ним буква в UTF-8. Можно пойти дальше: самые частые слова — «что», «который», «князь» — заменить однобайтными номерами. Правьте ячейку, запускайте её и следите за местом на табло.
pack и unpack из ячейки выше, упакует ими все пять лотов, распакует и сравнит, а рядом прогонит остальных участников. Длина полосы — размер после упаковки, пунктир — исходный размер. Переключатель «по лотам» показывает, кто на каком файле силён.Профессионалы на табло сильны каждый в своём. RLE ужимает картинку в двадцать шесть раз и вдвое раздувает текст, Хаффман лучше всех на ДНК, а на шуме не выигрывает никто. Каждому достанется свой раунд.
Раунд 2. Серии
Первый профессионал — самый простой. Если подряд идут одинаковые байты, запишем их одной парой: «сколько раз и какой». Строка ААААБББВ превращается в «4А 3Б 1В». Это кодирование длин серий, по-английски run-length encoding, RLE. Наш вариант хранит каждую серию двумя байтами: длину (до 255) и сам байт.
Сотая строка картинки — 240 точек — уложилась в шесть серий: небо, холм, дом, холм, небо, холм. Вся картинка — в 725 серий, то есть в 1450 байт вместо 38 400. А у Толстого серий почти столько же, сколько байтов: в обычном тексте одинаковые буквы подряд стоят редко, а каждая русская буква в UTF-8 к тому же начинается байтом 208 или 209, который тут же сменяется другим. Пара на каждый байт — и текст раздувается вдвое.
RLE хорош там, где есть большие ровные области: схемы, значки, чертежи, отсканированные документы. Факсы им и живут: строка листа — это чередование белых и чёрных серий, и аппарат передаёт длины серий, закодированные кодом Хаффмана. Для фотографий RLE бесполезен — соседние точки фотографии почти никогда не совпадают в точности. Но в последнем раунде он вернётся: JPEG сначала превращает фотографию в данные, где много нулей подряд, и только потом считает серии.
Судейская: сколько вообще можно выжать
Пора спросить судей: есть ли у сжатия предел? Для одного файла вопрос странный — любой файл можно «сжать» в один бит, если распаковщик заранее знает, что этот бит означает «Война и мир». Предел имеет смысл для источника — того, кто порождает файлы. Его в 1948 году нашёл Клод Шеннон, и эту историю подробно рассказывает глава об информации в «Царице наук». Нам хватит короткой версии.
Пусть источник выдаёт знаки независимо друг от друга, и знак $x$ выпадает с вероятностью $p(x)$. Редкий знак — это новость, частый — почти не новость. Шеннон измерил новость в битах: знак с вероятностью $p$ несёт $-\log_2 p$ бита. Буква, которая встречается в каждом втором знаке, — один бит, в каждом восьмом — три. Среднее по всем знакам называют энтропией:
$$H = -\sum_x p(x) \log_2 p(x) \ \text{бит на знак}.$$Теорема Шеннона об источнике говорит, что меньше $H$ бит на знак в среднем не потратит ни один код без потерь, а приблизиться к $H$ можно. Код Хаффмана из главы 23 отстаёт от энтропии меньше чем на бит: на «Войне и мире» — 4,86 бита на знак при энтропии 4,82. Разницу между числом хранимых битов и количеством информации в них называют избыточностью; её-то сжатие и удаляет.
Но у Толстого буквы не независимы. После «ч» почти наверняка идёт гласная, после «князь Андр» — «ей». Если учитывать, что было перед знаком, новость в нём становится меньше. Посчитаем энтропию следующего знака, когда известны $k$ предыдущих. Для этого из неопределённости пары «контекст плюс знак» вычтем неопределённость одного контекста: остаток — то новое, что приносит знак, когда контекст уже известен.
С каждым знаком контекста оценка падает: 4,82, потом 3,68, 2,96, 2,31, 1,85. Упаковщики, которые смотрят на контекст, и правда пробивают «потолок Хаффмана»: DEFLATE тратит 3,82 бита на знак, bzip2 — 2,48. Хаффман по буквам на том же романе не может опуститься ниже 4,82.
Но последние числа в таблице лукавят. При четырёх знаках контекста их разных вариантов почти девяносто пять тысяч, и многие встретились один-два раза. Такая «модель языка» попросту запомнила роман: после редкого контекста она уверенно знает следующую букву, потому что видела этот контекст единственный раз. Если тянуть $k$ дальше, оценка уйдёт к нулю, но модель придётся хранить вместе с файлом, и она окажется больше самого романа. Так что размер модели надо прибавлять к размеру архива; к этой мысли мы вернёмся, когда будем искать архиватор, который сжимает всё.
Раунд 3. «Смотри выше»
Хаффман смотрит на буквы по одной, а избыточность текста сидит прежде всего в повторах: слова, обороты, имена, целые фразы. «Князь Андрей» встречается в романе сотни раз. Вместо того чтобы снова писать повтор, можно сослаться на прошлый раз: «скопируй 12 знаков, которые были 3518 знаков назад». В 1977 году эту идею превратили в алгоритм Абрахам Лемпель и Яаков Зив из Техниона в Хайфе. Их статья называлась «Универсальный алгоритм последовательного сжатия данных», а сам алгоритм по первым буквам фамилий и году зовут LZ77.
Упаковщик идёт по тексту и держит перед глазами окно — последние несколько тысяч знаков. В каждой позиции он ищет в окне самое длинное совпадение с тем, что идёт дальше, и выдаёт тройку: на сколько назад вернуться, сколько знаков скопировать и какой знак идёт после копии. Если совпадения нет, тройка $(0, 0, \text{знак})$ передаёт один знак. Распаковщику думать не нужно: он копирует, что сказано.
В скороговорке первые восемь знаков новые, а дальше пошли ссылки: (10, 3, 'е') значит «вернись на 10 знаков, возьми 3 — это „рав“ — и допиши „е“». Вторая строка интереснее. Последняя тройка (3, 14, '!') велит вернуться на 3 знака и скопировать 14 — больше, чем было написано к этому моменту после точки возврата. Распаковщик копирует по одному знаку, и каждый скопированный тут же становится источником для следующих: «ла-» размножается само собой. Так LZ77 бесплатно умеет и то, что делал RLE: серия из тысячи нулей — это один ноль и ссылка «назад на 1, скопировать 999».
Вы уже встречали такую ссылку. В главе 43 мы разбирали ответ DNS, и там байт 0xC0 означал «остаток имени читай с такого-то места пакета выше»: имя legost.in в ответе пишется один раз, а дальше на него ссылаются — тот же «смотри выше», только для имён.
Как найти повтор быстро
У нашего упаковщика есть беда: для каждой позиции он перебирает все начала в окне — четыре тысячи сравнений на знак. На скороговорке это незаметно, на романе — мучительно. Профессионалы ищут иначе, и инструмент вам знаком по главе 16: хеш-таблица. Повтор короче трёх знаков всё равно невыгоден — ссылка стоит дороже двух букв. Значит, искать имеет смысл только среди тех мест окна, где начинаются те же три знака, что и сейчас. Заведём словарь «три знака → позиции, где они встречались» и будем проверять только их.
Оба упаковщика выдают одни и те же тройки, но второй уже на четырёх тысячах знаков быстрее больше чем в сто раз, а миллион знаков романа упаковывает за секунду-другую. Перебор возился бы с миллионом несколько минут: на каждую тройку у него тысячи сравнений.
Так ищет повторы и DEFLATE. Его описание, RFC 1951, прямо говорит о хеш-таблице с цепочками, где хеш считается по трём байтам, а комментарий в исходном коде библиотеки zlib признаётся, что поиск коротких строк вдохновлён алгоритмом Рабина и Карпа из главы 27. У популярных сочетаний вроде « на» цепочки выходят длинными, поэтому zlib проверяет только ближайшие места: на уровне сжатия 1 — четыре, на обычном уровне 6 — 128, на уровне 9 — до 4096. Этой длиной проверки и управляет ручка «быстрее или плотнее», которая есть в любом архиваторе.
Словарь, который растёт сам: LZW и патент
Через год Лемпель и Зив предложили второй способ, LZ78, а в 1984 году Терри Уэлч из фирмы Sperry упростил его до алгоритма, который назвали по трём фамилиям, LZW. Ссылок назад в нём нет. Вместо окна — словарь фраз, который упаковщик строит по ходу дела. Сначала в словаре только одиночные знаки. Упаковщик читает текст, пока фраза остаётся знакомой, выдаёт номер самой длинной знакомой фразы и добавляет в словарь её же, продлённую на следующий знак. Распаковщик, читая номера, строит точно такой же словарь, поэтому сам словарь передавать не нужно.
На коротком тексте словарь едва успевает чему-то научиться: к концу скороговорки в нём появились «река» и « рек», и семьдесят знаков превратились в 51 номер. На мегабайтах словарь вырастает до тысяч фраз и экономит всерьёз. LZW был быстрым и простым, его взяли в программу compress системы Unix и в формат картинок GIF, который фирма CompuServe выпустила в 1987 году. Через несколько лет GIF был на каждой веб-странице. И тут выяснилось, что у LZW есть хозяин.
DEFLATE: двое в одной упряжке
Способ, на котором стоят ZIP, PNG, gzip и сжатие веб-страниц, называется DEFLATE. Фил Кац придумал его для PKZIP 2.0, а в 1996 году Питер Дойч описал его в RFC 1951. Идея — запрячь вместе двух участников нашего конкурса. Сначала LZ77 с окном в 32 КиБ превращает текст в поток из одиночных знаков и ссылок «длина, расстояние»; повтор бывает длиной от 3 до 258 байт. Здесь и прячется потолок из первого опыта главы: одна ссылка покрывает не больше 258 байт и стоит хотя бы пару бит, поэтому даже миллион нулей DEFLATE не ужмёт сильнее чем примерно в тысячу раз.
Потом код Хаффмана сжимает сам этот поток: частым знакам и частым длинам — короткие коды. LZ77 убирает повторы, Хаффман — неравные частоты того, что осталось. Поодиночке оба проигрывают, а в упряжке на табло DEFLATE обходит и LZ77, и Хаффмана на всех лотах, кроме ДНК.
Здесь видна несимметричность, на которой держится сжатие в жизни. Уровень 9 работает в полтора-два десятка раз дольше уровня 1 и выигрывает больше четверти размера, а распаковка в любом случае занимает миллисекунды: распаковщику не нужно ничего искать, он только копирует. Поэтому файл, который упаковывают один раз, а распаковывают миллионы раз, — библиотеку, обновление, страницу сайта — стоит упаковать на максимуме. Модуль gzip даёт тот же DEFLATE с другим заголовком. Именно так сервер этого сайта отправляет вам страницы: браузер пишет в запросе заголовок Accept-Encoding — какие способы сжатия он понимает, — и сервер отвечает телом в gzip с пометкой Content-Encoding: gzip. О заголовках HTTP — глава 43.
На ДНК DEFLATE уступил Хаффману. Букв в геноме четыре, и Хаффман сразу даёт каждой два бита — вчетверо меньше байта. Длинных повторов в геноме фага мало, ссылки LZ77 почти не помогают, а платить за саму их возможность приходится. Поэтому для генома, звука и картинок пишут свои упаковщики.
Раунд 4. Перестановка Уилера
Вы помните Дэвида Уилера из главы 5: на заре 1950-х на EDSAC он научил подпрограммы возвращаться туда, откуда их позвали. Через тридцать с лишним лет, в 1983-м, ему пришла в голову идея совсем из другой области: переставить буквы текста так, чтобы одинаковые оказались рядом, причём так, чтобы перестановку можно было отменить. Опубликовал он её только в 1994 году вместе со своим бывшим аспирантом Майклом Барроузом, в отчёте исследовательского центра фирмы DEC. С тех пор её называют перестановкой Барроуза — Уилера.
Рецепт умещается в строку. Допишем в конец текста метку, которой в тексте нет, выпишем все циклические сдвиги — текст, начатый с каждой буквы по очереди, — отсортируем их по алфавиту и прочитаем последний столбец сверху вниз.
Из «банан» выходит «ннб$аа»: те же буквы, переставленные. На отрывке романа в полторы тысячи знаков видно, ради чего всё затевалось: «аааааааа», «яяяяяяяя», «рррр», «ьььь». Буквы слипаются потому, что сдвиги отсортированы по тому, что идёт после последнего столбца, — по продолжению. Все сдвиги, которые начинаются с «нязь», стоят в таблице рядом, а последняя буква у каждого из них — та, что стоит в тексте перед «нязь», то есть почти всегда «к». Перестановка собирает в серии буквы, у которых одинаковое продолжение. А такие серии, как мы видели, хорошо сжимают RLE и Хаффман.
Перестановка была бы бесполезна, если бы её нельзя было отменить. А по одному последнему столбцу восстанавливается весь текст. Отсортируем последний столбец — получим первый: в таблице это те же буквы, только по алфавиту. Пары «последний, первый» — это пары соседних букв текста. Сортируем пары — получаем первые два столбца, и так далее, пока таблица не восстановится целиком; строка с меткой на конце — исходный текст. Так и работает inverse_bwt в ячейке, только медленно: $n$ сортировок по $n$ строк. Есть способ обратить перестановку за линейное время, и его вы найдёте сами в задаче в конце главы. Попробуйте сначала руками.
На этой перестановке стоит bzip2, который Джулиан Сьюард выпустил в 1996 году. Он режет данные на блоки до 900 КБ и переставляет каждый. Потом перекодирует буквы так, что недавно встречавшаяся становится маленьким числом (после перестановки это часто ноль), сворачивает серии нулей, а остаток отдаёт Хаффману. На табло bzip2 — лучший на Толстом и на коде, а на всём романе он тратит 2,48 бита на знак против 3,82 у DEFLATE. Платит он скоростью и памятью: сортировать сотни тысяч сдвигов дороже, чем искать повторы в окне. Метки bzip2 не ставит: он сортирует сами циклические сдвиги блока, а чтобы распаковщик знал, с какой строки начинать, записывает её номер. В нашей ячейке метка есть, и тогда сдвиги стоят в том же порядке, что и суффиксы, — это суффиксный массив из главы 27, через который перестановку и строят быстро. Там же было обещано, что перестановка пригодится в генетике. На её основе построены индексы, с которыми программы вроде Bowtie и BWA прикладывают миллионы коротких прочтений к геному человека, держа его в памяти в сжатом виде.
Архиватор, который сжимает всё
Табло показывает упрямую строчку: на шуме проигрывают все. Может, подходящий способ ещё не придумали?
Фирма продаёт архиватор и обещает: любой файл длиной в мегабайт он сожмёт хотя бы на один байт, и распаковка вернёт его в точности. Что вы думаете?
Невозможно, и доказательство — подсчёт. Ниже.
Никакой упаковщик без потерь не может укоротить все файлы длиной $n$ бит. Более того, если он укорачивает хотя бы один файл, какой-то другой файл он удлиняет.
Файлов длиной ровно $n$ бит — $2^n$. Строк короче $n$ бит — $1 + 2 + 4 + \ldots + 2^{n-1} = 2^n - 1$: на одну меньше. Если бы упаковщик укорачивал каждый файл, он разложил бы $2^n$ файлов по $2^n - 1$ более коротким строкам, и по принципу Дирихле два разных файла получили бы одну и ту же упаковку. Распаковщик, получив её, не знает, какой из двух вернуть, — значит, без потерь такой упаковщик не работает. Второе — тот же подсчёт. Пусть упаковщик не удлиняет ни один файл, а файл $x$ длины $n$ укорачивает. Файлов короче $n$ бит ровно $2^n - 1$, и все они переходят в строки короче $n$ бит, которых тоже $2^n - 1$. Разные файлы получают разные упаковки, значит, заняты все короткие строки до одной. Упаковке файла $x$ места не осталось, хотя она короче $n$. Противоречие.
Второе сжатие уже ничего не даёт: после первого избыточности не осталось, и каждая следующая упаковка добавляет к файлу свои служебные байты. Случайные байты ведут себя так же с самого начала. Любое сжатие — обмен: упаковщик рассчитывает, что ему встретятся «типичные» файлы — текст с повторами, картинка с ровными местами, — и укорачивает их за счёт нетипичных, которых в жизни почти не бывает. Наша метка B из первого раунда — как раз такая плата: всё, что не умеем сжать, мы удлиняем, зато не больше чем на байт.
Лот «шум» в модуле cs.packing сделан одной строкой: random.Random(47).randbytes(30_000). Тридцать тысяч байтов, на которых сдался каждый архиватор, описывает программа в несколько десятков знаков. Длину кратчайшей программы, которая печатает данную строку, называют колмогоровской сложностью строки — Андрей Колмогоров предложил эту меру в 1965 году. Это идеальный предел сжатия: короче, чем кратчайшая программа, не скажешь. Но достичь его нельзя. Колмогоровскую сложность не вычисляет никакой алгоритм — это родственник неразрешимых задач из главы 56. Архиваторы ищут только те закономерности, на которые рассчитаны: повторы, частоты, серии. Закономерность «это выход генератора случайных чисел» им не по зубам.
Раунд 5. Можно терять
В последнем раунде правила меняются. С фотографией можно обойтись вольнее, чем с программой или банковской выпиской: если цвет одной точки из миллиона станет чуть другим, никто не заметит. Значит, вместо неё можно хранить другую, очень похожую картинку, которую гораздо легче сжать. Это сжатие с потерями. Вопрос раунда — что именно выбросить, чтобы глаз не заметил потери, а файл стал в десятки раз меньше.
Картинка 320 × 200 точек занимает 192 000 байт: по три байта на точку. Формат JPEG при качестве 90 сохраняет её в 17,5 тысячи байт — в одиннадцать раз меньше, и на глаз разницы нет. При качестве 50 — в двадцать семь раз меньше, и всё ещё прилично. Дальше начинается распад: проступают квадраты по восемь точек, вокруг букв появляется рябь, трава превращается в зелёные плитки. Откуда квадраты и рябь, становится понятно, если разобрать JPEG на части. Вы узнаете в нём почти всех участников конкурса.
Цвет хранится грубее яркости. Глаз хорошо видит мелкие детали яркости и плохо — мелкие детали цвета. Поэтому JPEG переводит каждую точку из красного, зелёного и синего в яркость и два «цветовых» канала, а цветовые обычно хранит с половинным разрешением по каждой оси: одно значение цвета на четыре точки. Половина данных уходит сразу, и почти никто этого не видит.
Квадраты 8 × 8 раскладываются по волнам. Каждый канал режется на квадраты по 64 точки, и каждый квадрат записывается как сумма 64 стандартных узоров — косинусных волн разной частоты по горизонтали и вертикали: ровный фон, плавный переход слева направо, сверху вниз, полоски чаще, клетки мельче. Это дискретное косинусное преобразование, ДКП. Его предложили Насир Ахмед, Т. Натараджан и К. Р. Рао в 1974 году, и это близкий родственник рядов Фурье из «Царицы наук». Само по себе ДКП ничего не теряет: из 64 коэффициентов точки восстанавливаются точно. Зато в природных картинках почти вся «энергия» сосредоточена в нескольких первых, медленных волнах, а быстрые, отвечающие за мельчайшие детали, малы.
Больше всего теряется при округлении. Каждый коэффициент делится на свой шаг и округляется до целого. Шаги для медленных волн маленькие, для быстрых — большие, и большинство быстрых коэффициентов после округления становятся нулями. Это квантование. Ползунок «качество» в распространённой библиотеке libjpeg меняет величину этих шагов: умножает на один множитель всю их таблицу. При качестве 90 они мелкие, при качестве 2 — такие, что от квадрата остаётся только средний цвет: отсюда плитки.
Дальше — без потерь, нашими средствами. 64 округлённых коэффициента выписываются змейкой, от медленных волн к быстрым, и в конце змейки выстраиваются длинные серии нулей. Их кодируют длинами серий, как в раунде 2, а всё вместе — кодом Хаффмана, как в главе 23. Рябь вокруг букв — звон Гиббса. Резкий край складывается из многих быстрых волн, и когда часть из них выброшена, оставшиеся звенят.
Тот же приём работает со звуком. В главе 28 мы записывали звук отсчётами: компакт-диск хранит 44 100 отсчётов в секунду по 16 бит на каждый из двух каналов — 1411,2 килобита в секунду. Песня в MP3 обычно занимает 128 килобит в секунду, в одиннадцать раз меньше. MP3 тоже раскладывает звук по частотам и квантует их, а грубее всего хранит то, чего ухо не услышит: тихие звуки рядом по частоте с громкими ухо пропускает, громкий звук их заглушает. Чем точнее модель восприятия, тем больше можно выбросить незаметно.
Практическое правило выходит такое. Фотографии — в JPEG с качеством около 75–85 (или в его современных наследников WebP и AVIF): меньше разница уже видна, больше — файл растёт, а глаз не замечает выигрыша. Схемы, скриншоты, текст, чертежи — в PNG: у них резкие края, на которых JPEG звенит, и ровные области, которые DEFLATE внутри PNG сжимает лучше любых волн. И не пересохраняйте JPEG после каждой правки: каждое сохранение квантует заново, и потери копятся.
Задачи
Четыре задачи: серии в факсе, LZ77 туда и обратно, энтропия с контекстом и обратная перестановка Барроуза — Уилера. В каждой есть большой тест с секундомером, а в трёх последних перебор не пройдёт.
Факс передаёт лист построчно. Строка — это строка из '0' (белая точка) и '1' (чёрная), а передаются длины серий: сколько белых подряд, потом сколько чёрных, потом снова белых и так далее. Первая серия всегда белая — если строка начинается с чёрной точки, первая серия равна нулю. Напишите rle_encode(row) — список длин серий и rle_decode(runs) — строку обратно. Например, rle_encode('0000011100000000001') — это [5, 3, 10, 1], rle_encode('110') — [0, 2, 1], а у пустой строки серий нет: []. Последний тест за секунду кодирует и раскодирует целый лист: 2000 строк по 1728 точек — столько точек в строке листа A4 у обычного факса.
Идите по строке и держите текущий цвет — сначала '0' — и счётчик. Знак того же цвета увеличивает счётчик. Знак другого цвета закрывает серию: счётчик уходит в список, цвет меняется, счётчик становится 1. Не забудьте последнюю серию после цикла.
Чёрная точка в самом начале при таком обходе сама закроет белую серию длины 0 — отдельный случай не нужен. А вот у пустой строки после цикла дописывать нечего.
Для обратного пути серии с чётным номером белые, с нечётным — чёрные: '01'[i % 2] * n. Склеивайте куски через "".join, а не прибавлением к строке в цикле.
Договор «первая серия белая» избавляет от необходимости передавать цвет: он чередуется сам. Стандарт факса идёт дальше и кодирует сами длины кодом Хаффмана, с готовыми таблицами для белых и чёрных серий: короткие чёрные серии (буквы) и длинные белые (поля) получают короткие коды. Это две идеи главы в одной машине.
Напишите lz77_encode(text, window=4096) — список троек (назад, длина, знак), как в главе, и lz77_decode(triples) — текст обратно. Правила тройки: назад не больше window и не больше числа уже написанных знаков; если длина равна нулю, то и назад — ноль; после копии всегда идёт один знак, поэтому повтор нельзя тянуть до самого конца текста. Повтор можно (и нужно) брать налезающим на себя: 'a' * 1000 — это две тройки. Упаковка должна быть не хуже жадной: в каждой позиции брать самый длинный повтор из окна, причём повторы короче трёх знаков можно не брать. Тесты распаковывают ваши тройки своим распаковщиком, считают их число и упаковывают 30 000 знаков романа с окном 4096 за две секунды.
Распаковщик — несколько строк: для каждой тройки скопировать длина знаков, стоящих назад позиций от конца, и дописать знак. Копируйте по одному знаку: тогда копия, которая налезает сама на себя, получится правильно.
Упаковщик из заготовки верен, но на каждый знак перебирает до 4096 начал. На 30 000 знаков это десятки миллионов сравнений. Вспомните раздел «Как найти повтор быстро»: словарь «три знака → позиции», и проверять только позиции с теми же тремя знаками, от ближних к дальним.
Не забудьте пополнять словарь позициями всех знаков, которые покрыла тройка, а не только первого: иначе повторы, начинающиеся внутри скопированного куска, потеряются, и троек станет больше.
Позиции в каждом списке идут по возрастанию, поэтому reversed перебирает их от ближних к дальним, и первая же позиция за окном останавливает поиск. В худшем случае — текст из одной буквы — цепочка тянется через всё окно, поэтому zlib ограничивает её длину. Асимметрия та же, что в ячейке про уровни DEFLATE: упаковщику нужны хеш-таблица и поиск, распаковщику — четыре строки, и распаковка всегда быстрая.
Напишите entropy(text, k=0) — энтропию следующего знака текста в битах, когда известны $k$ предыдущих знаков. Смотрим на все позиции $i$ от $k$ до конца: у каждой есть контекст text[i - k:i] и следующий знак text[i]. Для каждого контекста посчитайте энтропию распределения следующих за ним знаков и усредните по контекстам с весами — долями позиций, где контекст встретился. При k=0 контекст пустой, и получается обычная энтропия знаков: entropy('abab') — 1,0 бита, entropy('ab' * 50, 1) — 0, потому что после a всегда b и наоборот. Если в тексте не больше $k$ знаков, ответ 0. Последний тест считает энтропию всей «Войны и мира» с двумя знаками контекста и даёт на это десять секунд.
Сгруппируйте позиции по контексту, как в главе 8: словарь «контекст → Counter следующих знаков». Энтропия одного счётчика — $-\sum \frac{c}{n} \log_2 \frac{c}{n}$, где $n$ — сумма его значений.
Вес контекста — $n / (\text{len(text)} - k)$: доля позиций, где он встретился. Сумма весов равна единице.
Можно и без группировки, через формулу из главы: энтропия пар «контекст + знак» минус энтропия контекстов. Это одно и то же число — проверьте на маленьком примере.
Это условная энтропия: средняя неопределённость следующего знака, когда контекст известен. Две формулы — «среднее по контекстам» и «пары минус контексты» — совпадают по свойству логарифма: $\log \frac{c}{n} = \log c - \log n$. Помните о ловушке из раздела «Судейская»: с ростом $k$ оценка падает, но при больших $k$ она показывает лишь, что модель запомнила этот конкретный текст.
Напишите inverse_bwt(last): по последнему столбцу перестановки Барроуза — Уилера восстановите текст. Перестановка делалась, как в главе: к тексту дописан знак $, которого в нём больше нет, сдвиги отсортированы обычным сравнением строк Python. Верните текст без $: inverse_bwt('ннб$аа') — это 'банан', inverse_bwt('$') — пустая строка. Способ из главы — $n$ раз дописать столбец и отсортировать таблицу — тратит порядка $n^3$ времени (на каждом из $n$ шагов заново склеиваются $n$ строк длиной до $n$) и $n^2$ памяти, а последний тест даёт перестановку ста тысяч знаков романа и две секунды.
Первый столбец таблицы — это sorted(last). Возьмите строку таблицы номер $j$: её последняя буква last[j] стоит в тексте прямо перед её первой буквой. Значит, если знать, в какой строке таблицы буква last[j] стоит первой, можно идти по тексту от буквы к букве.
Всё держится на одном наблюдении: одинаковые буквы в последнем и в первом столбце идут в одном и том же порядке. Третья сверху «а» последнего столбца — это третья сверху «а» первого: обе строки, где эти «а» стоят, отсортированы по тому, что идёт после «а». Поэтому устойчивая сортировка номеров по буквам, sorted(range(n), key=lambda i: last[i]), сразу даёт соответствие.
С какой строки начать? Строка, которая кончается меткой, — это сам текст с $ на конце. Начните с i = last.index("$") и сделайте $n$ шагов i = order[i], выписывая last[i].
Одна сортировка — $O(n \log n)$ — и $n$ шагов по готовому соответствию; если вместо сортировки посчитать, сколько каких букв, получится $O(n)$. Это соответствие называют LF-отображением: last-to-first, «из последнего столбца в первый». На нём же держатся индексы геномов из главы 27: они хранят последний столбец, сжатый, с небольшими таблицами-подсказками и по нему умеют не только восстановить текст, но и искать в нём образцы.
Куда дальше
Конкурс кончился без общего победителя. Каждый профессионал выбрасывает своё предсказуемое — серии (RLE), неравные частоты (Хаффман), повторы (LZ77, LZW), одинаковые продолжения (перестановка Уилера), — и упаковщик выбирают под данные. Энтропия говорит, сколько останется, когда предсказуемое выброшено, принцип Дирихле запрещает сжимать всё подряд, а сжатие с потерями выбрасывает ещё и то, чего не заметит человек.
У сжатия есть и менее заметная работа. Когда Брин и Пейдж в 1998 году описывали свой поисковик, примерно половину всех его данных занимал архив скачанных веб-страниц, сжатый почти втрое. Сжатыми хранятся и указатели, по которым поисковик ищет слова. Но хранить страницы — полдела, в них надо ещё находить нужное. Страниц миллиарды, а ответ на ваш запрос приходит за доли секунды, раньше, чем вы успеете убрать палец с клавиши. Прочитать за это время весь интернет невозможно, значит, ответ готов заранее. Как он может быть готов, если вопрос ещё не задан? Об этом следующая глава, где мы построим поисковик по учебникам этого сайта.