В октябре прошлого года я опубликовал статью «О талантах, деньгах и алгоритмах сжатия данных», где с юмором описал, как «изобретают» новые алгоритмы сжатия люди, не имеющие достаточно навыков для реализации своих идей. А заодно рассказал про существующие конкурсы по новым алгоритмам, в том числе двигавшийся тогда к завершению конкурс алгоритмов сжатия с призовым фондом 50 тысяч евро.
Пост набрал 206 «плюсов», вышел на 2 место топа недели и вызвал оживленную дискуссию, в которой мне больше всего понравился комментарий: «Коммерческого интереса эффективность по сжатию алгоритмов сжатия без потерь сегодня не представляет, в силу отсутствия принципиально более эффективных алгоритмов. Деньги сегодня — в сжатии аудио-видео. И там и алгоритмы другие. Тема сжатия без потерь удобна именно лёгкостью верификации алгоритма, и не слегка устарела. Лет на 20.»
Поскольку я сам уже 20 лет в области сжатия видео, с ее бурным развитием мне спорить сложно. А вот что сжатие без потерь развиваться перестало… Хотя логика тут понятна каждому. Я до сих пор пользуюсь ZIP, все мои друзья пользуются ZIP с 1989 года — значит, ничего нового не появляется. Так ведь? Похоже рассуждают сторонники плоской земли. ))) Я не видел, знакомые не видели, и даже некоторые авторитеты утверждают, значит, это так!
О том, как Intel просили меня не прекращать читать курс по сжатию, ибо людей нет новые алгоритмы делать, я в прошлый раз писал. Но тут и Huawei в ту же дуду дует! Вместо того, чтобы раздать призы и должности победителям, а затем успокоиться, поскольку развитие давно встало, эти эксцентричные люди посчитали конкурс крайне успешным и запустили новый с призовым фондом 200 тысяч EUR.
Развивались ли алгоритмы сжатия без потерь в последние 20 лет? Чем закончился прошлый конкурс и на сколько опередили baseline? Сколько денег получили русские таланты, а сколько зарубежные? И есть ли вообще жизнь на Марсе в сжатии без потерь?
Кому интересно — добро пожаловать под кат!
Про развитие алгоритмов сжатия
Арифметик
Давайте посмотрим, что произошло за последние 20 лет. Для начала — истек срок действия 5 патентов на арифметическое сжатие от IBM (которая их никому не лицензировала), и его теперь можно легально использовать повсеместно. Объясняю на пальцах, почему это важно. Большинство представляет сжатие без потерь как-то так:
Наиболее частые символы кодируем короткими цепочками, наиболее редкие — длинными. Примитивная магия префиксного кодирования позволяет разобраться, где в потоке бит начинаются и заканчиваются символы. Profit!
Когда я говорю студентам, что арифметическое сжатие позволяет сжать символ, например, в 3.5 бита, или в 1.273 бита, или даже, страшно сказать, в 0.0001 бита, у них происходит разрыв шаблона, ведь в рамках их безнадежно устаревших представлений каждый символ можно закодировать только целым числом бит и вообще «бит на части не делится». Бит, может, и не делится, но как гарантированно упаковать символ в 1.5 бита известно уже более 40 лет, и пора бы уже к этой мысли привыкнуть: этот прием заметно степень сжатия поднимает. Заметим, что мы пока НИКАК не используем знание о последовательности символов (какой за каким идет), а только их вероятности, т.е. размер сжатого файла не зависит от порядка символов в потоке. По опыту, даже умные студенты не сразу понимают, как магия арифметического сжатия работает. Впрочем, про это много где написано. Для нас главное, что арифметическое сжатие с точностью до округлений реализации (например, мы не можем файл оборвать на полбита, и даже на полбайта не можем) приближается на больших файлах к теоретическому пределу сжатия для символов с заданной вероятностью появления. Особенно широкие просторы открываются при приближении к правой границе интервала вероятностей (когда разница в эффективности с алгоритмом Хаффмана наиболее велика):
Источник: ветхие лекции 20-летней давности начинающего седеть автора
На реальных примерах смена Хаффмана на арифметик дает примерно +15% к сжатию при том же качестве, что позволило использовать его в JPEG-2000 и сказалось на популярности H.264 (2003) по сравнению с MPEG-4 (1998), да и в целом он удачно получился (о новых кодеках, надеюсь, сделаю отдельный большой пост, там тоже много нового интересного прямо сейчас происходит, о чем газеты не пишут).
Источник: Market share of top online video codecs and containers
А примерно 10 лет назад ([1], [2]) появились методы Asymmetric numeral systems (ANS), позволившие достичь степени сжатия арифметика при скорости и вычислительных затратах быстрого алгоритма Хаффмана, что с 2013 года привело к маленькой революции в быстрых практичных алгоритмах. Заметим, потребовалось 30 лет для создания быстрой версии эффективного алгоритма. Сейчас ANS используется в библиотеках Facebook Zstandard, Google Draco, JPEG XL и многих других свежих разработках. Замечу, что автор ANS Ярек Дуда входит в состав экспертного совета нового конкурса по сжатию, о котором будет ниже.
Контекстное моделирование
Но дальше интереснее. Чистый арифметик с безусловными вероятностями по сути никто не использует, популярны варианты так называемого контекстного моделирования (Context Modeling или CM), которое использовалось с Хаффманом, а с арифметическим сжатием заиграло новыми красками.
Основная идея CM — в ПРЕДСКАЗАНИИ следующего символа. Чем более точное предсказание дает наша модель для следующего символа (чем больше его вероятность, т.е. мы чаще его угадываем), тем сильнее сжатие (тем правее мы находимся на графике оптимального сжатия выше). Context Modeling уже в полный рост использует межсимвольные зависимости в потоке, и на довольно простом коде хорошо видно, как модель недообучается и переобучается (плавно увеличивается-уменьшается размер файла, сжатого без потерь, в зависимости от объема статистики модели). Казалось бы, при чем тут нейросети…
«Стоимость», или вычислительная сложность моделирования, для сравнительно медленных, но хорошо сжимающих компрессоров минимум на порядок выше стоимости собственного сжатия (так называемого энтропийного кодирования). А для топовых по степени сжатия компрессоров — на несколько порядков, что сильно влияет на практичность алгоритмов, и позднее мы на этом еще отдельно остановимся.
Интересно, что долгое время, примерно 4–5 лет c 2009 по 2013, в топе известного рейтинга архиваторов Large Text Compression Benchmark Мэтта Махони был архиватор с прекрасным названием durilca kingsize, не без юмора названный так нашим замечательным соотечественником Дмитрием Шкариным. У него и до сих пор 8-е место в топе (для сравнения: у pkzip — 150-е место, у gzip — 148, у знакомого линуксоидам bzip2 — 118, у 7-Zip Игоря Павлова — 46). Алгоритм Дурилки основан на разновидности контекстного моделирования — PPM (Prediction by Partial Matching) — явном предсказании следующего символа по строке (контексту) ограниченной длины.
LSTM
Дальше — еще интереснее, на 6-й строчке рейтинга видим tensorflow-compress v3 с указанным методом сжатия LSTM. «Да это же рекуррентная нейросеть!» — воскликнет догадливый читатель. «Прям в точку!» — скажу я. Этот компрессор в открытых исходниках появился летом 2020 года (когда развитие сжатия окончательно остановилось) и представляет из себя обычный Jupyter Notebook под TensorFlow, который можно загрузить, модифицировать, проводить эксперименты и т.д. Даже устанавливать никакой софт не надо, загружаешь в Google Collab — и вперед. Легкий старт для тех, кто не боится сложных алгоритмов!
LSTM хорошо показали себя в предсказании следующего символа, и интересно, что идущий на пару строчек выше в рейтинге CMIX (4 место) — и тоже, кстати, доступный в исходниках — также использует внутри LSTM. Заметим, что его более быстрая и удачная модификация cmix-hp (2 место) была выпущена 10 июня этого года, всего 1.5 месяца назад!
Трансформеры
Ну и наконец, самое интересное. Как известно, трансформеры были разработаны в Google AI и сначала раскатали всех в переводе текстов, потом в обработке текстов (их производные: BERT в 2018 и нашумевшая GPT-3 в 2020), также хорошие результаты были получены для распознавания образов (тоже 2020). В январе 2021 эта чума архитектура трансформер добралась и до сжатия текстов в компрессоре NNCP, версия v3 которого, работающая в 3 раза быстрее январской и требующая меньше памяти, была опубликована 24 апреля и с хорошим отрывом заняла 1 место в бенчмарке. Это происходит прямо сейчас, друзья!
В целом расклад по топ-30 выглядит так (даже до 7-Zip, простите, не дошел, чтобы названия лучше на графике читались):
По оси ординат — сжатый размер 1 Гб файла данных английской Википедии (enwik9) с учетом размера декодера, в мегабайтах. У лидера преимущество по сравнению с 7-Zip — в 1.62 раза (!), по сравнению с pkzip — в 2.92 раза (архив почти в 3 раза меньше), причем в топе хорошая ступенька идет как раз с tensorflow-compress (привет, LSTM!), три первых места — свежак 2021 года, а рывок с трансформерами вполне себе убедительный (около 3% — это очень много в сжатии без потерь). И развитие на этом не остановится, очевидно. По ощущениям, развлечение с участием трансформеров и других нейросетевых архитектур в области сжатия только начинается.
Кстати, обделенный выше вниманием starlit (3 место, тоже LSTM) — это свежая (май 2021) опенсорсная разработка выпускника Физтеха Артема Маргаритова, который закончил аспирантуру и работает в университете Эдинбурга в Англии.
По всем законам жанра где-то в этот момент должен нарисоваться злобный скептик и громко крикнуть: «Вы только посмотрите, сколько времени оно все работает!!!» Мой опыт учит относиться к таким аргументам с терпеливым юмором. Помнится, JPEG при его появлении требовал порядка 5 минут, чтобы распаковать файл, а для MP3 специально сделали облегченные версии (помимо Layer 3 — Layer 2 и Layer 1), поскольку даже на топовых компьютерах того времени слушать музыку в нем было невозможно — не хватало скорости. И кто сейчас об этом помнит? Правильно. Специалисты. Потому что эта история повторялась уже много раз. Последний раз, кстати, с появлением AV1 совсем недавно — буквально пару лет назад, когда даже просто погонять его на сжатии было большой проблемой. Спрос на ускорение трансформеров в ближайшие годы очень велик. Люди массово хотят классный real time переводчик на свой смартфон и чтобы при наборе текста подсказка продолжения работала еще лучше, поэтому работы над аппаратными ускорителями идут фантастическими темпами (кстати, новый пост про это — будет). А то, что сжатие данных на тот же ускоритель ляжет параллельно с улучшением сегментации фотографий — будет мелким приятным бонусом.
Стоит упомянуть о количестве исследователей, работающих сейчас в области сжатия без потерь. На запрос "lossless compression" с 2020 года (1.5 года) Google Scholar дает 4,2 тысяч статей, на "image compression" — 12,6 тысяч, а на "video compression" — 5,5 тысяч. Прикидка очень грубая, в частности, в топе выборки попалась статья «Lossless compression of deep neural networks», где речь идет об удалении слоев из глубокой сети, т.е. выборка заметно зашумлена. Более того, видно, что большинство статей по сжатию без потерь — это сжатие всевозможных специфичных видов данных, где действительно зачастую можно получить преимущество в несколько раз по сравнению с универсальными алгоритмами. И, кстати, работ по картинкам больше, поскольку с ними банально проще работать (отдельная интересная тема, как техническая сложность влияет на научную популярность области). Но в целом можно говорить о том, что чисто в области сжатия без потерь работает существенно меньше специалистов, чем в других областях. Примерно ту же картину можно наблюдать и в трудах наиболее известной и авторитетной в области Data Compression Conference, тем не менее свежих статей даже по энтропийному сжатию (еще более узкая область, чем просто сжатие без потерь!) довольно много.
При этом в лучших традициях современного информационного средневековья (когда в паре кликов — ответ на любой вопрос, но информационный шум забил каналы) существует параллельная вселенная массового сознания, в которой на вопрос о том, какой алгоритм лучше всего жмет, старший заслуженный инженер с 20-летним стажем в единственном (!) ответе Quora дает ссылку на примитивный алгоритм середины прошлого века (популярный в Windows 3.x, кстати!):
Источник: What is the compression algorithm with highest compression ratio you know?
Этот ответ достоин лучших финансовых консультантов — абсолютно точный и абсолютно бесполезный (поскольку верен только для огромных файлов жестко определенного размера, состоящих из одинаковых байт, например, нулей). С другой стороны, он прав в том плане, что характер данных не был указан. Хотел привести еще несколько сравнений вида «Best compression tool in 2020», которые «технические журналисты» и блоггеры делают на основе пресс-релизов продавцов архиваторов, даже не попытавшись включить , но не стал. Всё с ними понятно… Так люди и не находят мучающий их ответ на вопрос о лучшем сжимающем алгоритме! И кто же таки лучший?
Пара слов про сравнение алгоритмов сжатия без потерь
Качественное сравнение от массового отличает как минимум анализ времени работы. Большинство серьезных алгоритмов имеют ручку скорости, которая иногда может варьироваться в весьма значительных пределах (изменение степени сжатия в 2 раза при изменении скорости работы почти в 1000 раз):
Источник: Compression Comparison Benchmarks: zstd vs brotli vs pigz vs bzip2 vs xz etc
Как правило, на графике степень сжатия/скорость получаются полукруглые кривые (часто зависимость близка к логарифмической), но на графике выше по горизонтали идет логарифмическая шкала, поэтому кривые вытягиваются почти в прямые и становится очень хорошо видно, как неравномерно они идут. При интерпретации таких графиков надо хорошо понимать, что результаты зависят от методов оптимизации конкретных реализаций алгоритмов, скорости памяти тестовой машины, размера памяти, размера кэша, характера данных и т.д. (то есть на разных компьютерах график будет разным!) У некоторых алгоритмов есть многопоточные реализации, и результат начинает зависеть от количества ядер. Чтобы жизнь медом не казалась, у современных алгоритмов появляется зависимость от наличия и мощности GPU, далее можно прогнозировать появление зависимости от TPU и т.д. В общем, чем дальше, тем такие бенчмарки становятся все сложнее в корректной интерпретации и интереснее.
На практике эти соображения приводят к нескольким важным следствиям:
- Во-первых, имеющиеся бенчмарки по сути используются как референс. Люди ищут там, кого в принципе имеет смысл гонять на своей задаче, и дальше, исходя из своих требований к скорости (в том числе отдельно скорости упаковки и скорости распаковки) и результатов на своих данных, выбирают алгоритм.
- Во-вторых, доведенные до ума промышленные библиотечные версии алгоритмов серьезно отличаются от исследовательских авторских — в них реализовано много алгоритмов оптимизации, дающих лучшее сжатие (с расходом времени) или лучшую скорость (с просадкой качества) с большим количеством градаций, которые сбалансированы между собой и управление ими выведено в единую ручку скорости. Именно поэтому кривые выше идут столь неравномерно — под капотом работают разные алгоритмы. При этом большое количество положений ручки скорости дает, например, возможность в случае перегрузки CPU серверов понизить условно на 10% сжатие на трафике, но при этом сбалансировать перегрузку. Или наоборот, докупить серверов, закрутить ручку и получить экономию по трафику в зависимости от того, что важнее для компании сегодня.
Специально для очень суровых инженеров серьезных систем. Хорошая «промышленная» реализация и оптимизация нового алгоритма сжатия (с поддержкой работы в потоке и всеми видами оптимизации) иногда требует пары лет квалифицированной работы. В этом плане очень радует, что коммерческие компании (и в первую очередь Google) в последние 10 лет начали регулярно выкладывать годные реализации библиотек сжатия без потерь в open source (см. гугловые Snappy — 2011, Zopfli — 2013, brotli — 2013, PIK — 2017, Draco — 2017 и т.д.). Ты все еще пользуешься gzip (1992), старина? То есть развитие идет ступеньками, сначала появляется новая идея, дающая очередной рывок на бенчмарках, а потом постепенно подтягиваются ее промышленные реализации (чаще — закрытые, но иногда и открытые).
По факту алгоритм проходит через следующие стадии:
- Исследовательская версия: в ней течет память, ужасный код, и т.д. Его задача — не упасть на датасете бенчмарка, обогнав при этом всех. Под капот лицам с тонкой нервной организацией лучше не заглядывать, ибо чревато!
- Standalone архиватор: падает на 2-3 порядка реже, распакованный файл за редчайшим исключением совпадает с паковавшимся (ура!), сделаны какие-то оптимизации по скорости и вообще можно пользоваться, пусть не слишком удобно.
- Промышленная библиотека: отличный отдокументированный код, портированный под несколько архитектур, сжимает в потоке и командной строке, OpenMP и OpenCL реализации, много разных оптимизаций, удобные параметры, работает, как часы.
Многие суровые инженеры говорят — пока код не будет промышленного уровня, даже смотреть в его сторону не будем. А зря! Очень часто по более ранним версиям можно прикинуть экономический эффект (для кого-то он становится заметен с 20% экономии трафика или хранилища, а для кого-то и с 3%) и для крупных компаний — как минимум появляется о чем говорить с вендорами технологических решений (должен же их кто-то образовывать). Так что смотрите бенчмарки, измеряйте, пробуйте!
В качестве стартовых точек можно посмотреть:
- Squash Compression Benchmark — отличный бенчмарк с 46 участниками на 28 датасетах. Увы, не обновляется, но представление о ситуации трехлетней давности дает очень хорошее.
- Sequence Compression Benchmark — великолепно организованный специализированный бенчмарк сжатия ДНК данных. Сравнивает 19 универсальных и 31 специализированный компрессор на 27 наборах данных. Фактически этот бенчмарк породил отдельное направление исследований и позволил в разы сильнее сжать специфические данные геномов.
- Large Text Compression Benchmark — самый долго обновляемый и большой бенчмарк по сжатию без потерь (в мае ему стукнуло 15 лет!), он содержит 201 участника (!) и дает хорошее представление о лучших алгоритмах, ориентированных на сжатие англоязычных текстов. На нем интереснее всего смотреть тренды и появление новых направлений исследований (много решений в open source).
Также имеет смысл смотреть участников конкурсов, особенно с большими денежными призами:
- Это, например, Global Data Compression Competition — наш недавний конкурс на сжатие текстов, картинок, смешанных данных и блоков по 32 Кб c призовым фондом в 50 тысяч евро, о чем будет ниже.
- Hutter Prize — сжатие англоязычной википедии, в котором, кстати, в конце мая 9000 евро получил упоминавшийся выше бывший физтеховец Артем Маргаритов, а до этого 4 раза подряд выигрывал наш коллега и соавтор Александр Ратушняк.
- Sequence Squeeze Compression Competition — конкурс на сжатие ДНК данных с призовым фондом 15 тысяч долларов
- и свежий конкурс Global Data Compression Competition 2021 с призовым фондом 200 тысяч евро, результаты которого будут к концу года.
Легко заметить корреляцию между денежными конкурсами и популярными бенчмарками, они идут по сути на одних данных, для которых есть спрос. Специально для талантливых ребят замечу, что, судя по запросам компаний, спрос на сжатие специфичных данных есть заметный, но обычно компании не хотят заморачиваться новыми конкурсами, а просто стараются нанять победителей прошлых конкурсов (именно поэтому авторы топовых алгоритмов часто работают в Google, Facebook, Apple, Huawei и других интересных компаниях). Так что пробуйте и достигайте!
Итоги Global Data Compression Competition 2020
Что можно сказать про прошлогодний конкурс. Во-первых, он разбудил декабристов, а они разбудили Герцена привлек внимание к теме сжатия без потерь. В нем поучаствовали заслуженные авторы, которые не выкатывали новых версий своих архиваторов уже 10–20 лет. Во-вторых, удалось сжать данные на 10–25% сильнее неплохих baseline решений при тех же вычислительных затратах, причем в разных категориях, а это уже коммерчески интересно. Очень неплохие результаты были в самой практичной «быстрой» («Rapid») категории конкурса. Интересно, что Байрон Кнолл — автор CMIX, результаты которого можно наблюдать в топе бенчмарка выше, хотел, но не смог поучаствовать в конкурсе, потому что CMIX примерно в… 300 раз медленнее самого щадящего порога. Его время придет позже.
Итак, поехали! Test 1 — сжатие большого массива текстовых данных. Ниже приведены избранные графики, результаты в категории Rapid, т.е. самые быстрые решения (жирным обозначены участники, обычным — baseline):
По оси абсцисс — общее время кодирования и декодирования в секундах (чем меньше, тем лучше), по оси ординат — коэффициент сжатия, вычислявшийся как отношение суммы размеров сжатых данных и декомпрессора к размеру исходных данных (чем меньше, тем лучше).
Чтобы было понятнее, кто является соперниками: Zstd — это упоминавшаяся выше библиотека Facebook Zstandard, которая появилась в 2015 году, имеет очень неплохие характеристики (во многом благодаря появлению ANS) и в исходниках выложена на GitHub. А brotli — это библиотека сжатия в открытых исходниках, развиваемая с 2013 Google, и через 8 лет развития он поддерживается в браузерах у 95% пользователей интернета. Если кто-то еще жмет gzip-ом (данные или трафик), вот вам мотивационный график, вы можете наиграть 20–30%, просто сменив архиватор на что-то свежее модное гугловое:
И, вы знаете, в нашем бенчмарке получилось обогнать и Facebook, и Google, и имеющиеся популярные решения! Получилось настолько хорошо, что было неожиданно даже для нас, организаторов. Когда pglz (автор Peter Thamm) жмет на 20-30% сильнее Brotli при вчетверо лучшей скорости работы — это серьезнейший повод для новой промышленной библиотеки.
В категории изображений интересно посмотреть результаты на распаковке в средней скоростной категории (Balanced). Видно, как неплохо новые компрессоры обошли и JPEG-LS (2003), и, что особенно интересно, JPEG XL (2020), серьезную конкуренцию составил только PIK (2018), продвигаемый Google-ом (последние два — это ещё аргументы в копилку к вопросу об остановке развития):
В категории смешанных данных (Mixed data) борьба была очень ожесточенной и неплохо себя на Balanced показал даже старичок bzip2. Кстати, рекомендую полные графики посмотреть в лидерборде сайта (там в Mixed data тесте быстрые baseline решения были сильны, но в медленной категории High compression ratio удалось очень хорошо улучшить результат). Итак, результаты борьбы на Balanced:
И наконец, в четвертой номинации (независимое сжатие блоков данных по 32 Кб) из-за малого количества участников (новые таланты, это предельно прозрачный намек!) на парето-оптимальную кривую попал даже старичок zlib, но если есть вычислительные ресурсы, то новые подходы позволяют сильно уменьшить размер вашей базы данных или файловой системы:
Надо понимать, что многое зависит от задачи. Например, для случая резервного копирования может быть важно время упаковки и совсем не важно время распаковки, а для задачи распространения дистрибутивов, наоборот, не важно, как долго мы сжимаем, а важно, сколько ресурсов (время, память, GPU) тратится при распаковке. По графикам на сайте можно посмотреть соответствующие варианты, и лидеры на парето-оптимальной кривой могут существенно меняться.
Также важно учесть, как обстоят дела, если использовать разные параметры по скорости и качеству для наиболее популярных сегодня промышленных zstd и brotli. А вдруг, если им параметры покрутить, они будут сильно лучше? Ниже результаты лидеров для «Test 1, Rapid, 1 GB», хорошо видно, что они поддержали свое высокое реноме, уверенно обогнав топовые библиотеки от Google и Facebook:
Источник: материалы автора
Ну, и самое интересное! Кому сколько денег досталось? В каждой номинации (текст, картинки, смешанный текст и блочное сжатие (базы данных), разные категории скорости) подводились свои результаты, всего 12 списков. Например, вот списки лидеров для картинок (Test 2):
За 1 место было 3000 EUR, за второе 1000 EUR, за третье — большое спасибо сертификат. Суммарный расклад по всем категориям выглядит так:
Источник: сайт конкурса, расчеты автора
Максимально один участник выставлял до 7 разных компрессоров (!). В сумме 3 автора за 16 топовых компрессоров получили 41 тысячу евро, в т.ч. Дмитрий Шкарин — 8 тысяч. Также специальный приз судей 2 тысячи из резерва ставки получил Илья Муравьев, поскольку его компрессоры отлично отработали pacesetter’ами и хорошо показали себя в конкурсных забегах, в то время как многие хитрые товарищи с сильными результатами подавали компрессоры на самом флажке в последний момент, но 40000 EUR все равно пришлось отдать в дальнее зарубежье.
Про новый контест
По итогам прошлого проекта Marcio Pais (2 место «по медалям») писал: «It's been fun trying out some ideas that I kept postponing and seeing what worked and what didn't… If you are planning on continuing this project, I just hope that the format can be changed a bit to make things more interesting» (12 тысяч евро понравились, если будете продолжать, можно доработать правила, чтобы было интереснее). Yann Collet, автор lz4 и zstd, работает в Facebook, прислал очень теплые слова о конкурсе: «I applaud the existence as well as your leading of this Data Compression Competition, which I believe is very valuable for the field in general» («Я аплодирую появлению и проведению Data Compression Competition, который я полагаю очень ценным для этой области в целом»). Christian Martelock, автор референсных ccm, rzm, работает в Apple, писал: «I like your initiative and I hope that you will be successful in breathing some new life into the compression community» («Мне нравится ваша инициатива, и я надеюсь, что вам удастся вдохнуть новую жизнь в сообщество авторов алгоритмов сжатия»). Было много других положительных отзывов.
Естественно, при создании правил конкурса 2021 года постарались отзывы учесть, особенно замечания Marcio Pais. Суть там заключается в том, что, если заметная часть датасета открыта для участников и входит в финальный датасет, на котором производится сравнение, появляются не самые спортивные тонкие способы (толсто было нельзя — размер декомпрессора складывался с архивом) увеличить степень сжатия за счет того, что ты уже «знаешь» часть данных абсолютно точно. В условиях, когда не требуются исходники (да-да, в этом году ваши исходники снова не нужны), это становится особенно важно. В итоге в новом конкурсе все данные закрыты, есть только сэмплы (данные такого же типа), при этом можно участвовать в промежуточных прогонах и видеть свое место.
Интересно, что в прошлом году были письма типа «А если я не писал компрессоров, у меня есть шанс?» В прошлом году шансов по сути не было, а в этом введена специальная номинация для новичков, которая заключается в настройке имеющихся компрессоров:
Более подробно задача описана тут. По опыту, конкуренция со студентами из Юго-Восточной Азии простой не будет, но это не повод не попытаться!
Также в целом данные стали сложнее. Например, в тексте появились иероглифы, а изображения — это теперь не привычные RGB по байту на компоненту, а многоканальные 16 битные HDR и даже 32-битные floating point, хорошо известные профессионалам и очень специфичные по контенту (не фото, примеры скачать можно). К слову — как там сжимать в целом понятно, а область, в отличие от сжатия текстов, почти целина, что, на мой взгляд, заметно повышает шансы талантливых грамотных новичков.
Да, еще в этом году есть гран-при за быстрый блочный алгоритм и в каждой категории отдельно будет поощряться первое место, у которого будет заметный отрыв от второго (т.е. поощрение прорывных результатов). В целом все выглядит так:
Вместо заключения
Надеюсь, мне удалось показать, как интересно развиваются алгоритмы сжатия без потерь в последние 20 лет. После общения с компаниями понимаешь, что сегодня основная проблема области — количество нерешенных задач заметно превышает количество людей, которые хорошо разбираются в современных алгоритмах. Ровно за это сейчас Huawei платит деньги, причем подсвечивая таких людей не только для себя. Для компаний разница между «старыми» и «новыми» подходами легко может означать от 10% до 50% (а в узких случаях до 300%) «лишних» расходов на трафик или дисковое пространство и это часто кардинально бОльшие деньги, чем призовой фонд.
Как писали в свое время любимые Стругацкие: «Я вернулся на свой пост в приёмную директора, свалил бесполезные ключи в ящик и прочёл несколько страниц из классического труда Я.П. Невструева «Уравнения математической магии». Эта книга читалась как приключенческий роман, потому что была битком набита поставленными и нерешёнными проблемами. Мне жгуче захотелось работать...»
(с) АБС «Понедельник начинается в субботу»
В общем — основной аудитории этой статьи я искренне желаю успевать за прогрессом, мастерски владеть актуальными профессиональными знаниями и жгуче хотеть решать нерешенные проблемы!
А тем, кто чувствует в себе силы попробовать себя в алгоритмах сжатия, настоятельно желаю быть настойчивыми, глубоко копать и не сдаваться!
Дерзайте! И почаще занимайте первое место!
Читайте также:
- О талантах, деньгах и алгоритмах сжатия данных — подробный текст о зарабатывании денег на алгоритмах сжатия вообще и конкурсе прошлого года в частности.
- Уличная магия сравнения кодеков. Раскрываем секреты — как мы много лет свежие видеокодеки сравниваем и какие прикольные моменты там были (про одно из интересных направлений развития видеокодеков свежий прикольный материал лежит, надеюсь хватит времени пост сделать).
Благодарности
Хотелось бы сердечно поблагодарить:
- родную Лабораторию Компьютерной Графики и Мультимедиа ВМК МГУ им. М.В. Ломоносова за вклад в развитие сжатия медиа в России и не только,
- моих замечательных соавторов по книге «Методы сжатия данных», Максима Смирнова, Александра Ратушняка и примкнувшего к ним Евгения Шелвина, благодаря которым этот проект вообще стал возможным и нанес непоправимую пользу людям,
- компанию Huawei за смелость финансировать самый крупный в мире конкурс по алгоритмам сжатия без потерь,
- и, наконец, огромное спасибо Дмитрию Коновальчуку, Кириллу Малышеву, Ивану Молодецких, Егору Склярову, Анастасии Кирилловой, Андрею Москаленко, Евгению Зимину, Никите Алутису, Егору Чистову, Александру Яковенко, Екатерине Шумицкой и Дмитрию Клепикову за большое количество дельных замечаний и правок, сделавших этот текст намного лучше!
Автор: Dmitriy Vatolin
