Най-великите програмисти на века: Юрки Алакуйяла – геният на компресията

Наскоро се спряхме на тезата, че компресията без загуби е всъщност главната концепция в нашия реален живот. Нека сега да обърнем малко повече внимание на един много ярък представител на именно тази индустрия. Той е човек, който вижда света през призмата на теорията на информацията, ентропията, хаоса и закономерностите.

Съвсем малко хора са чували за финландеца Юрки Алакуйяла (Jyrki Alakuijala), но буквално всички използваме неговите алгоритми и гениални софтуерни разработки. Изображенията във формат JPEG често се генерират от модерния енкодер JPEG guetzli с помощта на психовизуални модели, а HTTP трафикът в интернет се компресира от кодека brotli, който също е най-добрият в своя клас.

Д-р Юрки Алакуяла е един от най-великите програмисти на нашия век, активен член на open source общността и неуморен изследовател, който обаче не обича много много да се показва пред камерите и фотоапаратите, а предпочита да работи върху най-съвременните алгоритми за силна компресия на данните със и без загуби. Той е технологичен експерт в Google Research Europe (Швейцария). Най-новите му разработки включват алгоритмите за компресия JPEG XL, WebP lossless и др.

Кариерата

Преди да се присъедини към Google, той разработва софтуер за неврохирургията и планирането на лъчетерапията (1990-1995 г.), а след това в продължение на десетилетие усъвършенства енджините за изкуствен интелект на различните игри, включително Mephisto Chess Mobile Edition и Deep Pocket Chess. Това е интересен пример за универсален експерт с научно образование, който винаги и навсякъде ще бъде търсен. В крайна сметка той е поканен в Google, а такива предложения трудно се отказват.

Проектите

Юрки Алакуяла е автори и съавтор на няколко добре познати формати и алгоритми за компресия, хеширане и PRNG – генератори на псевдослучайни числа със свойства, които го правят подходящ за използване в криптографията. Основните му разработки включват:

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

  

  Компресията без загуби WebP е напълно независим кодек, който не е свързан с оригиналния WebP, базиран на VP8. Този алгоритъм използва най-съвременни техники, включително специални ентропийни кодове за различните цветови канали, двуизмерна локалност на обратните референтни разстояния и цветови кеш на наскоро използваните цветове. Това е в допълнение към основните техники като речниково кодиране, кодиране по Хъфман и преобразуване на цветовия индекс. В този формат се използва рекурсия. Изображенията с по-ниска разделителна способност с обслужваща и контролна информация (ентропийни кодове, пространствени предсказатели, преобразувания на цветовото пространство и цветови таблици) се вграждат рекурсивно в основното изображение, което означава, че се кодира, като се използва същата контролна информация, съдържаща се в тези базови изображения с ниска резолюция.

• Zopfli (2013 г.) е безплатна библиотека за компресиране на данни, която кодира данните във форматите DEFLATE, gzip и zlib. Тя компресира данни с по-висока степен на компресия от другите имплементации на DEFLATE и zlib, но архивирането ѝ отнема на порядък повече време. Поради тази причина обикновено се използва за единично статично компресиране, а не за компресиране в реално време. Разработена е съвместно с Lode Vandevenne, също служител на 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 GHz, компресията на тестовото PNG изображение с резолюция 1560×1032 пиксела отнема почти четири минути (3:56), за да се кодира в JPEG. Но Guetzli превъзхожда всички други JPEG енкодери по отношение на размера на изходния файл и качеството на компресията.

• Butteraugli (2017 г.) е гореспоменатата метрика за възприемане на разстоянието за Guetzli, т.е. основата, по която се оценява качеството на компресията. В крайна сметка колкото по-ефективна е метриката, толкова по-ефективен е резултатът

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

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

Освен това, важно е, че няма лицензионни такси.

Новият кодек включва инструменти за кодиране, които намаляват разходите (системните ресурси) за пренос и съхранение на JPEG с 22%, като същевременно позволяват възстановяване на оригиналния JPEG с точност байт по байт. Кодекът е проектиран по такъв начин, че да се възползва от предимствата на многоядрените процесори и SIMD и дори декодира по-бързо от стандартния JPEG.

• CityHash (2011 г.) е фамилия хеш функции на Google.
• HighwayHash (2016 г.) е нов бърз алгоритъм за хеширане, базиран на инструкциите за умножение и пермутация на AVX2. набора  процесорни команди. Както се казва в описанието, той просто реализира нов начин за смесване на входните данни със SIMD инструкциите. Накратко, използват се необратими 32×32 -> 64-битови умножения, а пермутацията изравнява разпределението на получените байтове. Вътрешното състояние на функцията е доста голямо (1024 бита), но се побира в SIMD регистрите. Поради ограниченията на набора от AVX2 инструкциите, регистрите са разделени на две 512-битови половини, които остават независими до фазата на редуцирането. Алгоритъмът извежда 64-битови извлечения или до 256 бита без допълнителни разходи.

В допълнение към високата пропускателна способност, алгоритъмът не изисква големи системни ресурси. Резултатът е повече от два пъти по-бърза работа от SipTreeHash.

Съществува версия за SSE4.1 (80% скорост за големи входни данни и 95% за малки входни данни), реализация за VSX на POWER и портативна версия (10 процентна скорост). Съществува реализация на трета страна за ARM архитектурата.

Тестовете показват, че HighwayHash алгоритъмът е 5,2 пъти по-бърз от SipHash при входни данни, в които преобладават блокове от по 1 KB. Бенчмарковете за работата с малки блокове във входните данни са показани по-долу:

• Randen е бърз генератор на псевдослучайни числа със защита срещу обратно проследяване от външен наблюдател, който се опитва да предскаже поведението на генератора

Научни работи

Те са толкова много, че ще се ограничим с по-важните.

• „Brotli. Алгоритъм за компресия на данни с общо предназначение“ (2019). В статията за научната общност авторите описват обстойно формата, представят експериментален анализ на основните алгоритмични блокове в настоящата реализация на кодера и правят сравнение с другите алгоритми за компресия от различни семейства, като повдигат редица нови въпроси, свързани с алгоритмичния и софтуерния инженеринг на дизайна, които заслужават допълнително внимание от страна на научната общност

По-долу е дадена сравнителната таблица от тази научна работа, където се прави сравнение на алгоритъма Brotli с най-добрите кодеци от това време (2019 г.). Използвани са четири големи текстови бази:

В таблицата са указани коефициента на компресия (съотношението на изходния компресиран файл към входния), скоростта на компресия и декомпресия

• „Тестове на JPEG XL – стандарт за компресиране на изображения със загуби/без загуби“ (2020). Според субективните сравнителни тестове JPEG XL дава 60% намаление на размера на файла в сравнение с JPEG при еквивалентно визуално качество. За да се възпроизведат резултатите, публикувани в този документ, изходният код на JPEG XL бе отворен през 2019 г.
• „Времево кодирани шиповидни невронни автоенкодери“ (2021). Шиповидният автоенкодер се представя подобно на конвенционалните автоенкодери и ги превъзхожда по отношение на ефективността на реконструкция на изображения с инвертирана яркост. Резултатите показват потенциала на шиповидните автоенкодери като градивни елементи за по-сложни компютърни архитектури, базирани на биологични принципи. С други думи, бъдещето на графичната компресия е в по-усъвършенстваните невронни мрежи.

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