Величайшие программисты XXI века. Юрки Алакуйяла — гений сжатия

Пару дней назад на Хабре обсуждали, что сжатие информации — главная концепция нашей жизни. И вот перед нами представитель этой самой индустрии. Человек, который видит мир через призму теории информации, энтропии, хаоса и закономерностей.

Мало кто слышал имя Юрки Алакуйяла (@jyzg), но все мы используем его разработки. Картинки JPEG частенько генерируются фантастическим JPEG-энкодером guetzli с применением психовизуальных моделей, а HTTP-трафик в интернете жмётся кодеком brotli, тоже лучшим в своём классе.

Д-р Юрки Алакуйяла — активный член опенсорсного сообщества и исследователь. Работает техлидом Google Research Europe (Швейцария). Среди последних разработок — алгоритмы сжатия JPEG XL, WebP lossless и др.

▍ Карьера

До работы в Google он разрабатывал софт для нейрохирургии и планирования лучевой терапии (1990–1995 гг.), а потом десять лет точил AI-движки мобильных настольных игр, включая Mephisto Chess Mobile Edition и Deep Pocket Chess. Это интересный пример универсального инженера с научным бэкграундом, который будет востребован всегда и везде. В итоге его пригласили в Google, а от таких предложений трудно отказаться.

▍ Проекты

Юрки Алакуйяла является (со-)автором нескольких известных форматов и алгоритмов сжатия, хеширования и ГПСЧ. Среди основных разработок:

• WebP lossless (2012). Формат сжатия без потерь, который по тестам значительно лучше PNG с кодеком Zopfli и немного превосходит FLIF.

  Сжатие без потерь WebP — абсолютно независимый кодек, не связанный с оригинальным WebP, который базируется на VP8. Этот алгоритм использует самые передовые методы, в том числе специальные энтропийные коды для различных цветовых каналов, двумерную локальность обратных опорных расстояний и цветовой кэш недавно использованных цветов. Это вдобавок к базовым техникам типа кодирования по словарю, кодирования Хаффмана и преобразования цветовых индексов. В этом формате применяется рекурсия. Изображения меньшего разрешения со служебной и управляющей информацией (коды энтропии, пространственные предикторы, преобразование цветового пространства и таблица цветов) рекурсивно внедряются внутрь основного изображения, то есть закодированы с применением той же управляющей информации, которая содержится внутри них.

• Zopfli (2013) — свободная библиотека для сжатия данных, кодирующая данные в форматы DEFLATE, gzip и zlib. Сжимает данные с бóльшим коэффициентом, чем другие реализации DEFLATE и zlib, но требует на порядок больше времени для архивации. По этой причине обычно используется для однократного сжатия статики, а не для компрессии в реальном времени. Разработана в соавторстве с Лоде Вандевенне, тоже работником Google. Первая публичная версия вышла в феврале 2013 года.
• Brotli (2013) — опенсорсный универсальный компрессор общего назначения, представленный Google, используемый в большинстве браузеров и веб-серверов. Он находится в открытом доступе на GitHub, а в июле 2016 года формат данных оформлен в виде RFC 7932. Сам алгоритм использует комбинацию современного варианта алгоритма LZ77, кодирования Хаффмана и контекстного моделирования 2-го порядка с довольно высоким коэффициентом компрессии. По скорости схож с deflate, но обеспечивает лучшее сжатие.

  По статистике Web Almanac 2021, треть всего сжатого контента в интернете обработано кодеком Brotli.

• Guetzli (2017). Перцептивный JPEG-энкодер, о котором на Хабре рассказывали в фундаментальной статье «Оптимизация графики для веба: самое важное».

  Guetzli оптимизирует глобальные таблицы квантования JPEG и значения коэффициентов DCT в каждом блоке JPEG с помощью оптимизатора с замкнутым контуром. В научной статье объясняется, что в процессе оптимизации в качестве источника обратной связи Guetzli использует специальную метрику перцептивного расстояния Butteraugli, за счёт которой достигается уменьшение объёма данных на 29–45% для данного перцептивного расстояния (по оценке Butteraugli) по сравнению с другими компрессорами.

  
  Визуализация двух деталей в изображении, оригинал в левой колонке, Guetzli в средней, libjpeg в правой. В версии libjpeg больше кольцевых артефактов, чем у Guetzli

  
  Слева пейзаж разложен на три YUV-плоскости в JPEG. Каждый квадрат 8×8 преобразуется в пространство DCT, а значения DCT квантуются. Кроме квантования, Guetzli агрессивно обнуляет малые значения

  Синтаксис энкодера:

  guetzli --quality 90 01.png 01.jpg

  Правда, вычисления довольно медленные. Например, на компьютере Core i5-4460 3,2 ГГц тестовая картинка PNG размером 1560×1032 кодировалась в JPEG почти четыре минуты (3:56). Но зато по размеру/качеству сжатия Guetzli превосходит все остальные JPEG-кодировщики.

• Butteraugli (2017) — упомянутая выше метрика перцептивного расстояния для Guetzli, то есть основа, по которой оценивается качество сжатия. Ведь чем эффективнее метрика, тем эффективнее получается результат.

  Образно говоря, если учёные обнаружили новые паттерны работы человеческого мозга (новые психовизуальные модели, когнитивные искажения и др.), то мы получаем возможность сжимать картинки в файлы меньшего размера. Дополнительное знание — лучшее сжатие.

• JPEG XL (2017) — кодек нового поколения, ориентированный на масштабное применение в интернете, эффективное сжатие высококачественных изображений и в конечном итоге замену существующего проприетарного формата JPEG. Обеспечивает различные преимущества по сравнению с существующими форматами изображений:
  • меньший размер при эквивалентном субъективном качестве;
  • быстрые параллелизуемые конфигурации декодирования и кодирования;
  • прогрессивное сжатие, сжатие без потерь, анимация и обратимое перекодирование существующего JPEG;
  • поддержка высококачественных изображений: широкая гамма, более высокое разрешение, битовая глубина, динамический диапазон, кодирование без визуальных потерь.

  Кроме того, важной целью является отсутствие роялти.

  Новый кодек включает инструменты кодирования, позволяющие снизить затраты на передачу и хранение JPEG на 22%, при этом позволяя байт за байтом точно восстановить исходный JPEG. Кодек был разработан с учётом преимуществ многоядерности и SIMD, и даже декодирование у него осуществляется быстрее, чем у стандартного JPEG.

• CityHash (2011) — семейство хеш-функций от Google.
• HighwayHash (2016) — новый алгоритм быстрого хеширования, основанный на инструкциях умножения и перестановки AVX2. Как сказано в описании, здесь просто реализован новый способ смешивания входных данных с SIMD-инструкциями. Если вкратце, то используются необратимые умножения 32x32 -> 64 бита, а перестановка выравнивает распределение результирующих байтов. Внутреннее состояние функции довольно велико (1024 бита), но помещается в SIMD-регистры. Из-за ограничений набора инструкций AVX2 регистры разделены на две 512-битные половины, которые остаются независимыми до фазы уменьшения. Алгоритм выдаёт 64-битные дайджесты или до 256 бит без дополнительных затрат.

  В дополнение к высокой пропускной способности алгоритм рассчитан на низкую стоимость финализации. Результат более чем в два раза быстрее, чем SipTreeHash.

  Есть версия для SSE4.1 (80% скорости для больших входов и 95% для малых), реализация для VSX на POWER и портативная версия (10% скорости). Есть сторонняя реализация под ARM.

  Согласно тестам, HighwayHash в 5,2 раза быстрее SipHash для входных блоков данных размером 1 КБ. Бенчмарки для малых блоков показаны ниже.

  

• Randen — быстрый ГСПЧ с защитой от бэктрекинга со стороны внешнего наблюдателя, который пытается предсказать поведение генератора.

▍ Научные статьи

Список научных работ любого исследователя показывает главные инновации, которые он привнёс в этот мир. По сути, это вклад человека в развитие опенсорса, науки и всего человечества. Будущие кирпичики цивилизации лягут поверх слоёв, которые укладываются нами прямо сейчас.

Юрки Алакуйяла указан соавтором восьми работ, в том числе ведущим автором четырёх:

1. «Быстрая хеш-функция с ключом/псевдослучайная функция с использованием SIMD-умножения и перестановки» (2016). Научная статья с описанием вышеупомянутого алгоритма HighwayHash. В статье объясняется выбор дизайна функции, представлен статистический анализ, бенчмарки и предварительный криптоанализ. Предполагается, что если сообщество по инфобезу не найдёт уязвимостей, то эту функцию можно внедрить в массовое использование, а её «усиленные» варианты могут существенно ускорить вычисление контрольных сумм файлов и потоковые шифры.

   Контрольные суммы и хеши вычисляются практически повсеместно — в файловых системах, архивах, бэкапах, стримах, различных криптосистемах и так далее. В отличие от реально сильных хешей, функция HighwayHash очень быстрая, поэтому её можно рекомендовать как более безопасную альтернативу слабым хешам во многих приложениях.

2. «Guetzli: JPEG-кодировщик с перцептивным управлением» (2017), описанный выше. Сейчас алгоритм Guetzli подходит только для сжатия статического контента и служит просто доказательством, что теоретически можно достичь значительного уменьшения размера файлов, сочетая продвинутые психовизуальные модели и сжатие с потерями.
3. «Randen — быстрый генератор случайных чисел, устойчивый к бэктрекингу, с использованием AES+Feistel+Reverie» (2018). Алгоритмы с ГСПЧ часто теряют смысл, когда противник может предсказать поведение генератора. Для защиты приложений от таких атак разработан «сильный» ГПСЧ с двумя свойствами:
   1. Числа, вычислительно неотличимые от случайных.
   2. Устойчивость к бэктрекингу (backtracking).

   Некоторые существующие криптографически безопасные генераторы также отвечают этим критериям, но они слишком медленные, чтобы быть принятыми для общего использования. Как и ранее упомянутый хеш-алгоритм HighwayHash, опенсорсный ГСПЧ Randen может считаться сильным и одновременно превосходит «слабых» конкурентов по производительности (в данном случае имеются в виду Mersenne Twister, PCG, ChaCha8, ISAAC и Philox) благодаря аппаратному ускорению.

   На самом деле Randen представляет собой видоизменённую версию недавно опубликованного надёжного генератора Reverie с новой перестановкой (Permute на иллюстрации ниже), построенной на основе улучшенной обобщённой структуры Фейстеля с 16-ю ветвями: «Мы предоставляем новые границы активных s-боксов для 24-х раундов этой конструкции, что стало возможным благодаря алгоритму поиска, экономящему память», — сказано в научной работе.

   

4. «Временнóе кодирование в спайковых нейросетях с альфа-синаптической функцией» (2019). Спайковые (импульсные) нейросети — это третье поколение искусственных нейронок, в котором нейроны обмениваются короткими (у биологических нейронов это 1–2 мс) импульсами одинаковой амплитуды.
   

   Импульсная нейронная сеть с одним скрытым слоем, источник

   Временны́е характеристики нейронной активности необходимы биологическому мозгу для быстрой реакции на сенсорные стимулы. Однако искусственным нейросетям не хватает присущего биологическим сетям тайминга временного сигнала. В данной работе представлена новая модель нейронной сети со спайками, которая кодирует информацию по времени импульсов. В дальнейшем такую архитектуру применят для создания более продвинутых алгоритмов сжатия изображений.

5. «Архитектура сжатия изображений следующего поколения JPEG XL и инструменты кодирования» (2019). Архитектура JPEG XL представляет собой традиционное блочно-трансформационное кодирование с эффективной модернизацией каждого компонента. В научной статье описаны эти компоненты и анализируется качество декодированного изображения.

   

6. «Brotli. Компрессор данных общего назначения» (2019). В статье для научного сообщества авторы тщательно описывают формат, представляют экспериментальный анализ основных алгоритмических блоков в текущей реализации кодера и сравнение с компрессорами различных семейств, поднимая «ряд новых проблем разработки алгоритмической и программной инженерии, которые заслуживают дальнейшего внимания со стороны научного сообщества».

   Сравнение Brotli с лучшими кодеками на четырёх текстовых базах (полные результаты):

   
   Указаны коэффициент сжатия (отношение размера архива к оригинальному размеру базы), скорости кодирования и декодирования

7. «Тесты JPEG XL, стандарта сжатия изображений с потерями/без потерь» (2020). По результатам субъективных бенчмарков, JPEG XL даёт выигрыш 60% в размере файлов по сравнению с JPEG при эквивалентном визуальном качестве. Для воспроизведения результатов, опубликованных в этой работе, исходный код JPEG XL был открыт в 2019 году.
8. «Спайковые нейронные автоэнкодеры с временны́м кодированием» (2021). Спайковый автоэнкодер работает аналогично обычным автоэнкодерам и превосходит их по производительности реконструкции изображений с инвертированной яркостью. Результаты исследования показали потенциальные возможности спайковых автоэнкодеров как строительных блоков для более сложных компьютерных архитектур на биологических принципах. Другими словами, будущее сжатия графики — за более продвинутыми нейросетями.

Как видим, для разработки алгоритмов сжатия в последнее время начали активно применять нейросети. Перейдя на работу в Google, д-р Юрки Алакуйяла в каком-то смысле возвращается к истокам, ведь его изначальная специализация — софт для нейрохирургии. И вот теперь оказалось, что компьютерный софт становится всё больше похож на биологический мозг с нейронами, синапсами, обучением, адаптацией и психовизуальными моделями. С другой стороны, в медицине тоже применяется всё больше компьютерных технологий. В диагностике заболеваний (по снимкам) применяют схожие методы обработки изображений, что и в графических кодеках.