Как стать автором
Обновить

Как развитие алгоритмов сжатия остановилось 20 лет назад, или о новом конкурсе на 200 тысяч евро

Время на прочтение 18 мин
Количество просмотров 70K
Всего голосов 259: ↑258 и ↓1 +257
Комментарии 134

Комментарии 134

Отличная познавательная статья! Спасибо автору за труд.

Спасибо) В черновиках разной степени готовности еще 6 статей, но где время взять вечный вопрос)

В последнее время все реже и реже статьи такого качества появляются на хабре!
Благодаря таким статьям остается надежда на то, что хабр все еще торт :)


Спасибо!

Буду стараться время найти, спасибо!)

Эээ, дело идет к тому чтобы обучать нейросеть (парочку трансформеров) под каждый архив?? Типа будем не видео кодировать, а выдавать сценарий и учить нейросеть по нему генерить кино «на лету» )))

Не секрет, что во многих массовых архиваторах (в том же RAR) была предобработка под разные типы данных (картинки, бинарники), которые благодаря ей получалось лучше сжать. Сейчас скорее в декодере будет несколько сеток лежать под разные типы данных.

С кино и видео - отдельная тема, но рендеринг без движка рендеринга на нейросетях очень прикольно и быстро развивается )

 рендеринг без движка рендеринга на нейросетях очень прикольно и быстро развивается

А можете накидать ключевых слов / ссылок, как на это глянуть?

НЛО прилетело и опубликовало эту надпись здесь

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

НЛО прилетело и опубликовало эту надпись здесь
Ну так случайные данные и не сжимаются. А неслучайные все специфичны.

а в сжатии коротких сообщений (сотня байт, например) прогресс есть?
я пробовал zlib/lz4/zstd/xz/bzip2, из-за коротких заголовков только zlib нормально себя показал

А зачем их жать? Думаю, что задача пожать массив таких сообщений? Тогда и жать их надо порциями с балансом размер порции / ратио

В telegram bot api есть Inline Keyboard, и размер поля callback_data (отправляемый в бота при нажатии той или иной кнопки пользователем) не более 64 байт. При разных вариациях кнопок бота отдельную таблицу для декодирования айдишников запросов в команду на стороне сервера городить не хочется (тут начинают вылезать проблемы с тем, где хранить, очисткой старых данных, и т.п.), а в 64 байта уместить команду очень надо. Я структурированную команду паковал в protobuf+голый DEFLATE (без заголовков). Для небольших ботов с функционалом поиска (типа поиска билетов, или справочник для онлайн-игр) этого хватало с лихвой. Но думаю, что специализированные компрессоры должны себя лучше показать.

Это тот случай, кода можно всё упаковать ID СУБД

Когда у тебя stateless-сервис, ради кнопочек тащить СУБД в проект - ну такое...

Я в подобном проекте сделал временное key:value хранилище в памяти с TTL для записей. А в callback_data отправлял key. Тоже не хотелось тащить полноценный persistence. Но у меня и не скалировался этот сервис правда.

Если пакуешь в callback_data данные, то защищен от рестарта сервиса, т.к. персистентное хранение перекладывается на плечи телеги. Плюс горизонтальное сканирование забесплатно. Надо только не забывать подписывать данные (генерить MAC), хотя бы с транком до одного байта, чтобы уберечь себя от перебора значений в этом поле. Хотя последнее актуально и для ID, если они генерятся секвентально.

Вы совершенно правы, но, блин, 64 байта - это чертовски мало :)

Что за команды такие, раньше в твитторе 140 символов все сообщение было ;-))

у меня были листалки поисковой выдачи вправо-влево, в команду паковались параметры поиска и номер следующей требуемой страницы

на самом деле там немножко меньше: 48, т.к. можно пользоваться только символами из UTF-8 диапазона, поэтому паковал еще в Base64

тоже используем protobuf, известный набор данных кодируется в enum'ы, на стороне сервиса свитчами разворачивается. да, код громоздкий, зато данные компактные

А зачем их жать? Думаю, что задача пожать массив таких сообщений? Тогда и жать их надо порциями с балансом размер порции / ратио

https://habr.com/ru/post/479044/
задача сразу сохранить сообщение, а не накапливать «пачку», удобную для сжатия

Конечно. Еще со словарными методами там можно было заметно наиграть.

Вот, например, на гитхабе старый специализированный компрессор:
https://github.com/antirez/smaz SMAZ - compression for very small strings
Вот поновее:
https://github.com/unixba/b64pack - B64pack compresses short text messages
https://ed-von-schleck.github.io/shoco/ - shoco: a fast compressor for short strings

Ну и если сколар посмотреть - работы вполне есть, в том числе свежие.

это текстовые сообщения, а мне бы бинарные.

Несколько лет назад переписал алгоритм сжатия одной старой игры. В ней как раз маленькие udp-пакеты сжимались. Если интересно, можно потыкать: go get github.com/koteyur/eimaster/cmd/lzevil (название алгоритма неофициальное).
Вот, например:


$ head -c 100 /usr/bin/gzip | ~/go/bin/lzevil | wc -c
54
$ head -c 100 /usr/bin/gzip | gzip -9 | wc -c
68
$ tail -c 100 /usr/bin/gzip | ~/go/bin/lzevil | wc -c
30
$ tail -c 100 /usr/bin/gzip | gzip -9 | wc -c
47

немного поигрался, разница больше из-за заголовков gzip (которых 18 байт), в которые завёрнут поток deflate.
а так сам алгоритм очень похож на deflate, на моих данных deflate ведёт себя чуть лучше.

zstd умеет делать словарь по большому набору различных коротких сообщений.
Потом имея этот словарь, использовать его для сжатия/расжатия.
Получается достаточно эффективно. Я использовал такое чтобы базу из многих коротких строк сжимать.

Заявляется, что brotli с этим хорошо справляется.

нет, попробовал — с частыми flush deflate выигрывает.

Тупой ленивый метод (так делать не надо, но для понимания возможностей сойдёт): берёте 100500 ваших сообщений (тренировочный набор), как образец. Сжимаете любым типовым методом.
Приписываете к тренировочному набору сообщение, которое надо передать, сжимаете. У вас получится новый архив, в котором добавилось сколько-то байт в конце. Только их и передаёте.
(на самом деле, конечно, не упаковываете/распаковываете каждый раз с начала большого файла, а просто откатываете упаковщик/распаковщик к состоянию после упаковки/распаковки тестового набора. Но оценить, насколько на самом деле сожмётся ваше сообщение, вы можете и так)

Ну, на самом деле есть методы попроще (не модифицировать состояние упаковщика в процессе упаковки/распаковки – для ppm-методов это довольно просто и ускоряет их работу).

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

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

Я таки нашёл время и будучи аспирантом сделал свой архиватор. Сжимал zip файлы ещё на 15% (максимум), но оказалось, что все запатентовано до нас.

И эта собака на сене и сама не выпускает архиватор и другим не даёт. Так и потерял интерес к этой теме.

Но у вас, возможно, всё получится.

(старички поймут иронию) Где-то икнулось Рыбинкину.

И наконец, в четвертой номинации (независимое сжатие блоков данных по 32 Кб) из-за малого количества участников (новые таланты, это предельно прозрачный намек!) на парето-оптимальную кривую попал даже старичок zlib

что-то странно, что zstd тут заметно медленнее zlib, ЕМНИП именно быстрым сжатием (при степени сжатия на уровне zlib) zstd и прославился.
или тут какая-то мега-степень сжатия, а нормальная плохо себя показала (и не попала на приведённую часть графка) из-за малых размеров блоков данных?


всё, сходил на страницу с результатами, разобрался.


ещё вопрос, бинарники не сжимали? или третий тест это оно и есть?


и это нашёл )))


и раз были zlib/bzip2/zstd, почему не было lzma2 (7z/xz)?

Это совершенно нормально. У zlib разбор проще. У zstd в зависимости от уровня сжатия (параметр) сложные стратегии разбора. Кроме того, если речь про этот год и реф данные этого года, у zlib, помнится, словарь вроде 32к (надо проверять), а в этом году в референсе по 64к блоки, т.е. картина скорее всего несколько поменяется.

Интересно, по какому принципу выбрали степень сжатия 17 для zstd?

lz4, lz5 как бы. Но они не очень.

7-zip - архиватор, а не алгоритм. Зачем вы трижды упоминаете архиватор, сравнивая его с алгоритмами? Это совсем разные вещи. Уточните, о каких конкретно алгоритмах идёт речь. LZMA/LZMA2?

Зачем же мешать в кучу алгоритмы сжатия с очень разными свойствами?

По определению, любой условный файл (или группу) можно всегда сжать до условного 1 байта. Значит, надо соревноваться надо не только по коэффициенту сжатия и скорости, но и по объему данных (модели) для разжатия, например. И тогда монстроподобные нейросети уже будут смотреться на равных с каким-нибудь lzss, которому вообще не нужна память для распаковки.

Или вот еще пример из практики, мне нужен был несимметричный алгоритм сжатия для экономии траффика и ресурса флэш: сжатие на хилом контроллере (мало памяти и времени), разжатие на мощном ПК (ресурсов на порядки больше). Много вы знаете подобных алгоритмов? 90% описанных тут не годятся для этой задачи вообще.

Так что даже для алгоритмов сжатия произвольных данных без потерь надо рассматривать несколько категорий (в каждой будут свои победители).
1. Условно неограниченный по ресурсам упаковщик и распаковщик (память + время + размер данных/модели для сжатия и разжатия).
2. Неограниченный упаковщик (время + память) и жестко лимитированный распаковщик (нет памяти + нет объема для модели).
3. Жестко лимитированный упаковщик и неограниченный распаковщик (редкий случай)
4. Оба компонента жестко лимитированы, в идеале вообще не используют память.

И в каждой категории могут быть свои подкатегории, условно говоря когда, скажем, скорость важнее памяти или наоборот.
Вот такую табличку было бы интересно увидеть.
И тогда может быть выяснится, что в отдельных категориях прогресса нет те самые 20 лет?..

По определению, любой условный файл (или группу) можно всегда сжать до условного 1 байта.

По какому именно определению?

Если мы говорим про конкретный алгоритм сжатия, то он, возможно, какой-то файл и сожмёт до одного байта или даже бита, но за счёт того, что другой файл окажется больше, чем он был в оригинале.

Задача алгоритмов как раз в том, чтобы более вероятные данные оказывались короче, а менее вероятные нам уже не так интересны.

Имеется ввиду, что если для разжатия требуется запустить нейросеть, весом 305 гигабайт, на компьютере с топовым GPU, то надо как-то оценить эти затраты. Допустим добавить эти 305 гигабайт к архиву.

Размер распаковщика обычно учитывается в весе архива. Так что здесь всё хорошо.

Все верно, у нас тоже учитывался.

А я вот согласен с @titbit, что во многих случаях требования к распаковщику и упаковщику могут быть "весьма специфичными" и многие случаи заслуживают отдельных конкурсов :)

Например:

  1. Любые асимметричные применения: инсталятор может упаковываться долго и при этом жрать все ресурсы билд-сервера/фермы билд-серверов, так как упаковывают его один раз. Распаковывать его будут тысячи клиентов, поэтому хорошо бы ему делать это быстро и с минимальными ресурсами. Сюда же IoT (сервер и микроконтроллеры), g-code для станков и т.д.

  2. тонкие каналы и мощные вычислители: неважно сколько ресурсов требует упаковщик и распаковщик снимков с марсохода (спутниковый интернет на северном полюсе, связь с подводными лодками и т.д.). Канал связи с ним довольно узкий, а вычислительных ресурсов у NASA более чем достаточно. Учитывать при этом объем распаковщика будет не очень логично;

  3. потоковое сжатие на магистральных каналах связи: ресурсы упаковщика/распаковщика условно-безграничные, но должно работать с минимальным latency и максимально параллелиться;

  4. можно рассмотреть эволюцию стоимости вычислительных ресурсов: стоимость 305 гигабайт на SSD примерно 1000р. Как быстро окупится постоянное хранение 305 гигабайт, если это позволит сэкономить 10% интернет трафика (поднять скорость на 10%), при стоимости интернета 500р/мес? А если считать в рамках крупной организации? Можно учесть, что производительность процессоров, количество ядер, объем/скорость оперативки, объем/скорость дисков и т.д. дешевеют не очень равномерно. Например, раньше быстро расла производительность ядра, а теперь растет их количество, т.е. теперь для алгоритмов важнее возможность распараллеливания.

  5. можно также рассмотреть: архивное хранение "холодных" данных; большие объемы сырых, но хорошо структурированных и повторяющихся данных в научных исследованиях; сжатие коротких пакетов/сообщений; гомоморфное сжатие (возможность проводить операции, не распаковывая); сжатие в условиях возможных потерь/искажений кусков данных (учет возможностей и особенностей алгоритмов, обеспечивающих избыточность); интеграцию сжатия с алгоритмами шифрования (сейчас жмут потом шифруют, но есть мнение, что сжатие может рассматриваться как кусок алгоритма шифрования, так как на выходе хорошего компрессора данные статистически приближены к "случайным") и т.д. на сколько хватит фантазии :)

В этом конкурсе и так 12 категорий, которые отличаюся в том числе приведенными вами критериями.

во многих случаях требования к распаковщику и упаковщику могут быть "весьма специфичными" и многие случаи заслуживают отдельных конкурсов :)

Однозначно так!)

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

Зачем же мешать в кучу алгоритмы сжатия с очень разными свойствами?

А кто мешает? ) Выше в тексте вот прям специально для вас сказано, что есть много разных случаев и бенчмарки обычно на практике используются, как страртовая точка для своих экспериментов. Плюс приведены примеры бенчмарков, где больше параметров можно использовать для более детального сравнения.

Текущие 12 категорий были взяты чтобы с одной стороны покрыть основные интересные компаниям кейсы, с другое - не сделать сравнение слишком узким, чтобы был смысл в нем участвовать (и так приз получился не слишком большим в каждой категории).

И тогда может быть выяснится, что в отдельных категориях прогресса нет те самые 20 лет?..

Т.е. 12 категорий GDCC 2020 никак не коррелируют с ответом на этот вопрос? ))))

Если я правильно понял статью, то подавляющее большинство алгоритмов можно отнести к пункту 1 моей классификации, что конечно здорово, но интересен прогресс и в других пунктах. Я не смог увидеть никаких улучшений по пунктам 3 и 4. Поправьте меня, если я что-то упустил.

Поправляю) Статью вы поняли правильно, но в ней речь идет о конкурсе, а не о бенчмарке. Главное отличие между ними в том, что в конкурсе платятся деньги. Прямое следствие - во-первых, попытки читерить разной степени продвинутости (про это было в предыдущей статье и такие попытки были) и на это уходит много усилий. Во-вторых, в конкурсе важно приз за номинацию побольше, иначе он станет неинтересен.

В прошлый раз "размазали" 50 тысяч по 12 номинациям (по 4 тысячи в каждой + 2 в резерве) и это в принципе немного. Понятно, что можно было подавать любое количество программ (что является нагрузкой на организаторов), за счет чего победители и получили заметные суммы, но членам жюри известны конкретные люди, которые могли бы дать хороший результат, но не стали напрягаться, в силу не слишком большой суммы. Именно поэтому в конкурсе этого года не стали увеличивать количество номинаций - те же 12 + студенческая, но уже на 200 тысяч (хотя нам тоже интересен прогресс в других областях). Но "разбудить" еще участников интереснее.

Можно предложить заинтересованным лицам сделать специализированный конкурс или бенчмарк, это было бы классно!

Размер декомпрессора включается в размер сжатых данных.

По хорошему надо еще размер используемой памяти включать. Очевидно, что при одинаковых размерах распаковщика и объема сжатых данных, алгоритм не требующий память намного круче алгоритма требующего гигабайты (это условный пример), и это надо учитывать. Потому что есть хилые железки, контроллеры (я вот писал сжатие для контроллера с 128 байтами (!) памяти всего — msp430f1132 кажется), и там 99.9% приведенных алгоритмов вообще не работоспособны.

"... поблагодарить: компанию Huawei за смелость финансировать самый крупный в мире конкурс по алгоритмам сжатия без потерь,"

а кроме Хуавея у остальных не нашлось даже таких, очень скромных сумм .

При том, что и они, и другие имеют с этого хоть и косвенные, но немалые бонусы.

Молодцы, что тут скажешь.

Кроме алгоритма, есть ещё то, как ты им пользуешься. Precomp использует тот же LZMA2, что и 7zip, но сжимает докуметны в 2-3 раза сильнее.

Есть очень большая тема препроцессинга, который может в некоторых случаях очень много дать (и в Precomp активно используется).

НЛО прилетело и опубликовало эту надпись здесь

)))) Воистину! Я (бессердечный человек) за отсутствие подписей осей могу (бедного) студента с предзащиты диплома выгнать. )))

А что, скажем, с упрощением самого языка и, например, сокращением алфавита (хотя не за пределы 16 < символов < 32), т.е., получается, некоторой подгонкой исходных данных.
Должен же быть выигрыш в разнице за счет более простого языка и его конструкций (я подразумеваю эсперанто), особенно для предсказания следующих символов.

Окажется ли достаточным 5, тире 8 битов для кодирования всех символов и знаков?

Все резко захотели стать (воодушевились) пионерами в благом деле)

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

По этому поводу есть https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%A8%D0%B5%D0%BD%D0%BD%D0%BE%D0%BD%D0%B0_%D0%BE%D0%B1_%D0%B8%D1%81%D1%82%D0%BE%D1%87%D0%BD%D0%B8%D0%BA%D0%B5_%D1%88%D0%B8%D1%84%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F

Разработчику ПО была бы очень полезна сводка по:

  • лицензия под которой код доступен

  • Поддерживаемые платформы (esp32? etc.) и сложность интеграции

  • Размер компрессора / декомпрессора в скомпилированном варианте

Всё это, так же важно, как и стандартные параметры: скорость сжатия/распаковки, потребление памяти, коэффициент сжатия для разных типов данных и разного размера данных, многопоточность.

Там в статье было же.

Это не промышленный код. Это соревновательные примеры. О платформах и лицензиях рано еще говорить.

Ровно так. Это не бенчмарк, это конкурс. Основная проблема конкурсов - за счет появления приза в нем появляется заметное количество махинаторов разной степени хитросделанности и основная задача (и трудозатраты) - их фильтрация. Про это подробнее в прошлом посте было. В этом конкурсе они тоже были, но поскольку стартован новый конкурс я не стал облегчать им задачу и про это рассазывать ))), тем более что в этом году их явно будет больше ) (надеюсь, что не в 4 раза).

Бенчмарки мы тоже делаем, например, многолетний - сравнение кодеков (кстати - из-за опыта в нем нам доверили этот международный конкурс), матирования, видеозаполнения, супер-резолюшена, смен сцены, деинтерлейсеров. И еще пару новых бенчмарков собираемся опубликовать в этом году (в т.ч. очень прикольные). Если бы каждая университетская лаборатория программистских факультетов в России делала столько бенчмарков, бенчмарки с русскими корнями встречались бы на три порядка чаще. )))

Увы, покрыть все темы наших возможностей физеологически не хватает. Помогайте! )

Вот бы конкурс не "архиваторов", но библиотек компрессоров: 7zip архиватор не так интересен, как LZMA, входящий в состав SDK. А то получается, что zlib - всё наше.

Кстати, есть множество узких ниш, где могли бы пригодиться, например, BMF или bCdr, но не как исполняемые файлы, а как исходники под MIT, скажем. Дмитрий Шкарин исходники не опубликовал к этим алгоритмам?

Конкурс - это условно "хакатон" - в нем главное - показать работоспособность идеи. А библиотека - это промышленное программирование и удел либо компаний, либо open source (либо и того, и того)). От компаний скорее можно ожидать спонсирования библиотеки под своим брендом.

На конкурс исходники принципиально не требовались - все вопросы к лауреатам (которых сейчас на части рвут компании))).

Не нашел в рейтингах древний КГБ-архивер.

Помню решил проверить легенду: специально нашел таки запакованный им в 1,44 Мб дистрибутив MS Office 2003, дождался распаковки, установил на чистую систему и проверил работоспособность.

Был сильно впечатлён. Дважды. Второй раз - временем распаковки - что-то около 4 часов.

Википедия пишет, там используется алгоритм PAQ, который в 2007 году сжимал википедию до 133 Мб. На третьем графике в данной статье (где про Large Text Compression Benchmark) он был бы на 9~10 месте, что, я так понимаю, достойно для over-10-летнего алгоритма.

лет 15 назад помню в универе, мы тоже придумывали - разные архиваторы, стремясь перехватить славу zip и rar. А потом, мы вышли в жизнь....

Может быть, подобные алгоритмы хороши для передачи фото Илона Маска в марсоход. На Марс.

Но, представьте, обычную организацию - несчастные промсервера G5\G6\G7 у них - задача хранить бухгалтерию, какую-нибудь базу эдак гигов на 500-600. все это сжимать, бакапить за приемлемое время , при этом, сохранять отклик... И алгоритм, должен был общеизвестен. Могу представить, в какой осадок выпадет весь Ит-отдел, если мы ему подсунем Durilka. :)

И алгоритм, должен был общеизвестен

ну пример zstd, brotli показывает, что ничего нереального в появлении нового стандартного алгоритма нет — несколько лет назад их не было, а сейчас они на каждой кофеварке.
ладно, за этими двумя стояли мега-корпорации, но xz тоже не так давно набрал популярность.

а я и не отрицаю.

может быть пройдет еще 20 лет, и на смену нынешним алг без потерь (словарных), или для видео - придет, что нибудь.

Ну так очевидно же, для тех кто ведет двойную бухгалтерию:

  • архиватором KGB (о котором вспомнили веткой выше) жмем "белую"

  • архиватором Durilka жмем "черную"

И тогда IT-отдел их точно никогда не перепутает!

Я не понимаю зачем это. Ну то есть это наверное круто — жать сильнее, чем ZIP. Но дело в том, что сейчас везде почти несжимаемые данные — видео, фото. Да и производители винтов и ssd вроде идут вперед семимильными шагами. Оперативка дешевеет. Сетки везде гигабитные и выше. 5G, 6G, WiFi6. Я понимаю, когда ходили друг к другу с пачками дискет. Вот тогда это было ой как критично. Искали самый лучший архиватор. И он по моему (не помню уже) был .ha. Жал лучше всех. Потом появился RAR, но он уже сильно долго жал на максимальной компрессии. Опять же, мало сжать. А если данные повредятся? Есть возможность восстановления?

фото и видео - это не сжимаемые данные???? "а, мужики-то не знают" (с)

Ну я лет 20 назад пробовал сжимать МП3, чёт не впечатлило. Ну попробуйте сжать H265, может быть вам повезет.

MP3, как и H265 - это и есть уже сжатые данные. И сжаты они как раз алгоритмами, которые появляются благодаря таким вот людям, которые занимаются разработкой новых алгоритмов. Вы и правда не понимаете, о чём говорите. Так что лучше воздержаться от обесценивающих высказываний и разобраться в теме, прежде чем высказываться по ней.

Так и я о том же. Большинство данных уже сжато. Но в данной статье идёт речь о сжатии без потерь, что об МП3 и остальных не скажешь.

пнг?

png — отличный формат для синтезированных изображений, но никак не для фото.

Пф, Ничем не отличается от BMP, сжатого на NTFS-разделе…
Изредка и GIF может меньше PNG весить, но вот многие «здоровенные» монохромные PNG жмутся всё-таки лучше!
Раз уж упомянули аудио, то вот. Меня удивило "парадоксальное" сжатие 96kHz в такие форматы, как .ogg, .aac и .m4a… А вынуждают сохранять записи в mp3 какие-нибудь у района "колоночки" или "муз.центры"… Странно: мой Symbian отказывается воспроизводить .OGG .MP2, но отлично воспроизводит 96-килогерцовые .m4a и .aac!
А вот с древнейшими "форматами без потерь" есть даже такое сравнение: https://www.firstpr.com.au/audiocomp/lossless/
(зачёркнутым привожу то, что не воспроизводит "на лету"): WaveZip (MUSICompress) | Shorten | Pegasus SPSjpg | SONARC | WavArc | LPAC | WavPack | AudioZip | Monkey's | RKAU | недотестированные FLAC с OptimFROG, ещё сказано про DAKX, а на 3/3 страницы идёт объяснение алгоритма Райса!

Но в данной статье идёт речь о сжатии без потерь, что об МП3 и остальных не скажешь.

Не поверите, но в прошлой статье как раз я рассказываю, как мы 17 лет назад делали компрессор MP3 (рабочее название проекта было MP3ZIP, коммерческое - SoundSlimmer) и достигли сжатия в 1.2 раза на большой коллекции файлов. Это была перепаковка, но без потерь. Если поискать, в сети даже программу можно найти, а в прошлой статье были ссылки на патенты с описанием метода))) Это кстати, непросто было, 6 человек 2 года работали. Основная головная боль была - работа с битыми MP3, которых довольно много к сожалению. AAC тоже тогда сжали, кстати, но слабее.

Я люблю про этот проект рассказывать, когда кто-то про несжимаемость медиафайлов говорит. И даже под настроение могу рассказать, как именно это можно сделать и за счет чего ;)))

Абсолютно с вами согласен. Да, можно. Но стоит ли 20% таких затраченных ресурсов?

Детали разглашать не уполномочен, но Sony считала, что однозначно да) (по их меркам затраты копеечные))

Это ключевая часть HTTP 2, например. Специальный алгоритм сжатия… и .zstd файлы очень классно сжаты.

О, и еще там же есть сжатие exe пакерами. Это заставляет быстрее грузануть в ОЗУ, а там раскпаковка дешевле.

Это заставляет быстрее грузануть в ОЗУ, а там раскпаковка дешевле.

И подложить свинью системе управления памятью, ага.

Опыт кликхауса показывает, что даже в случаях с использованием SSD сжатие не стоит отключать из-за просадки по производительности (не говоря уже про экономию места). Там, по-моему, по дефолту lz4 используется

Очень ждал в статье пасхалку в виде коэффициента Вайзмана

Да, лучше такой конкурс, чем никакой. Но, если учесть, что за многолетний труд программист получит 10-20к евро, то это просто хедхантинг талантливых аутистов корпорациями.
Ну зачем давать эту ссылку? Суть всё-равно такая же. На конкурсах/патентах денег не заработать.

Если хочется денег, нужно начинать с осознания их природы и смысла. Тогда элементарные начала статистики и анализа, дадут вам больше, чем решение каких-то фундаментальных проблем.

В атомарном обществе, скрипач не нужен. Сейчас корона подогрела интерес к некоторым областям, и что же, есть боянистый метод, есть современные публикации, но зачем решать проблему на корню, если итеративно тянуть резину гораздо выгоднее :-)

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

К ответу автора на вопрос «вы еще пользуетесь zip?» ответ простой - у меня уже лет 10 диск больше чем на 50% свободен :) Понятно что для пром.задач оно актуально, для дома же я последний раз игрался с ключами rar и 7zip наверно когда студентом был и на новый винт денег не хватало.

Вы в контексте ваша фирма. Где вы пишите софт или админите сервера.

И дисков там сотни или тысячи и за траффик платить надо. -10% размера всего, при той же загрузке ЦПУ, это солидный минус к расходам фирмы.

Спасибо за интересный обзор. (Сожалею, что не могу за него голосовать).
Одного не понял: как юмор заголовка " развитие алгоритмов сжатия остановилось 20 лет назад" сочетается с итоговой фразой в конце?:


Надеюсь, мне удалось показать, как интересно развиваются алгоритмы сжатия без потерь в последние 20 лет.

Развиваются или развитие остановилось??

По ощущениям, развлечение с участием трансформеров и других нейросетевых архитектур в области сжатия только начинается.
Несколько не в тему, но возможное интересное развитие темы сжатия с помощью нейросетей, для моделирования ментальных явлений, включая сознание. Лет десять назад группа авторов выдвинула идею, что компрессия лежит в основе функционирования сознания, см. одну из их публикаций Compressionism: A Theory of Mind Based on Data Compression, наряду с другими многочисленными объяснениями этого феномена. Они назвали свой подход компрессионизмом. Показалась эта идеи интересной с точки зрения когнитивных исследований. Почему? Потому как по мере обработки информации поступающей от органов чувств в вышележащие области мозга происходит ее пространственно-временное нелинейное сжатие. На эту тему существует масса исследований, см. напр., это. В ней авторы иллюстрируют идею этого сжатия такой схемой.
Схема компрессии
С помощью моделирования сверточными сетями можно объяснить такое поведение, благодаря суммативным способностям нейронов и их моделей, напр, для вентрального тракта зрительной системы. Однако в более высоких областях происходит обобщение (абстрагирование) этой информации, кот. также можно рассматривать как сжатие, и создание того, что можно назвать статистической моделью мира. Хотя в этом случае компрессия происходит с потерями. Возможно это как-то поможет объяснить так называемый разрыв в объяснении сознания, также называемой тяжелой проблемой объяснения сознания. Однако десять лет назад применение нейросетей и глубокого обучения только начинало раскручиваться, и авторы не могли привлечь подобное моделирование для проверки своих идей. Поэтому особого развития эта тема не получила. Сейчас нейросетевое моделирование весьма успешно применяется для решения различных когнитивных задач. Как например, оценка численности объектов, успешно моделирующая поведение биологического аналога, см. эту работу. Возможно работы по компрессии с помощью нейросетей вдохнут жизнь в компрессиониский подход к объяснению ментальных явлений. Вот тут автор развивает идеи в этом направлении.

Спасибо автору за статью, весьма информативно.

Спасибо за самый интересный комментарий к статье! )

Да, семантическое сжатие информации (в т.ч. аудиовизуальной) - это безумно интересная тема, которая очевидно будет активно развиваться, причем стартует лет через 5-10 (сейчас не хватает ни мощности датасетов, ни мощности акселераторов, чтобы развернуться в полный рост). Прикладная польза там будет в кардинальном улучшении поиска по картинкам, фрагментам видео, фрагментам песен и т.д. Революция будет (и уже начинается) в видеонаблюдении и т.д. Прикольная тема - автоматическое создание трейлеров и роликов (например, из видео, заснятых в путешествии) - тоже сжатие))) Мы последним даже побаловались, но пока отложили (многие блоки из которых надо собирать пока слишком слабы).

Иногда интересно сравнить старые файлы с новыми, и удивиться, как в одинаковом размере файла раньше умещался только звук не самого лучшего качества, а сейчас и звук и видео.

А исходники pglz есть в природе?

Мы принципиально не собирали исходники в конкурсе. В природе они конечно есть)

Ну просто их и в инете нигде нет, вроде алгоритм неплохой, но юзать без исходников никто ж его не будет :-)
Ну, хорошо, что наконец-то в ЛабКГММ занимаются алгоритмами сжатия. А не видеофильтрами для самсунга, бгг ))). // когда в 2005 выбирал кафедру — не пошёл на АСВК, потому что мне сообщили, что учиться мы не будем, а будем видеофильтры типа «мультфильм» для самсунга писать)

Сейчас от автора зависит, как решит. Хантить его уже начали, причем походу в несколько мест)

По поводу того, что не будете учиться - вас грязно обманули)

А вот давно хотел спросить у разбирающихся…
Существуют ли архиваторы с "внешним" словарем? Ну т.е. если грубо, в старых архиваторах при упаковке создавался словарь, который и использовался для сжатия (а там уже вопрос в алгоритмах, как именно словарь делаем/используем).
Так вот, вопрос в том, не пробовал ли кто-то сделать архиватор, который таскает со своим исполняемым файлом большой словарь и при сжатии по факту ссылается на него, а не в данные файла полученного архива. В принципе, можно же иметь такой "внешний" словарь довольно большого размера с разбивкой под разные типы данных и в итоге получить большое сжатие?

zstandard позволяет вести тренировки на данных и потом переиспользовать этот словарь для упаковки/распаковки новых данных

Интересная статья, давно ничего подобного не читал с таким интересном

Я понимаю что времени никогда не бывает много, но такой вопрос, а когда можно ожидать следующую статью?

))) В высокой степени готовности 2 статьи. До конца сентября хотел бы их выкатить (в тексте даже анонсы были), точнее я бы не обещал, ибо в августе будут разъезды.

Большое спасибо!
НЛО прилетело и опубликовало эту надпись здесь

Ты все еще пользуешься gzip (1992), старина?

зипом и гзипом, потому что нужно упаковать на сотнях и тысячах машин с одним корявым "русским" линуксом, распаковать на винде, упаковать и затем распаковать на линуксе. И чтобы везде всё работало. И допсофт ставить на все эти линуксы это для извращенцев и мазохистов.

Понятно, что консерватизм - наше все и использовать софт дедов наших - святое дело. И понятно, что когда человек высылает архив в xz коллегам - это пижонство (даже если коллеги занимают сжатием))).

Но вообще я наблюдаю в России очень низкую профессиональную культуру сжатия данных. Возможно, это связано с тем, что в Кремниевой долине все смотрели сериал "Кремниевая долина" (где главный герой изобрел новый алгоритм сжатия и для них новые алгоритмы - это нормально), а наши айтишники смотрели сериалы первого канала (и просто не в курсе, что нового есть), не знаю.

Можно интересный тест сделать - распарсить, какие российские сайты отдают brotli (о котором я пишу в предыдущем предложении перед вашей цитатой). Его ведь 95% броузеров поддерживают (все, кроме странных встроенных броузеров планшетов, и отдать каждому его поток не проблема). И какие западные сайты его отдают. И даже можно пережать отдачу и посмотреть, где какой наигрыш (он от данных зависит сильно). И тут (внезапно!) откроются тайны великие, почему сайт условного Тинькова работает шустрее сайта условного Альфа-банка, даже когда сложные скриптовые графики отдает. А если с людьми поговорить, будут те же выводы, которые нам западные компании озвучивают (жестко не хватает специалистов).

Можно интересный тест сделать — распарсить, какие российские сайты отдают brotli

это легко объяснить.
почти весь рунет отдаётся nginx'ом; сейчас проверил, собранные пакеты nginx как в debian, так и на nginx.org не включают поддержку brotli, а общее правило админа такое: если ты не уверен, что тебе это нужно и «из коробки» оно не включено — не включай )

Тем интереснее сравнить) Инициатива в подобных вопросах идет не от админов, а от архитекторов или (в небольших компаниях) CTO, т.е. напрямую зависит от их уровня подкованности.

Спасибо за статью.

Есть книженция некоторой давности. Но, думаю, для стартового погружения, может быть кому-то полезна: "Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. - М.: ДИАЛОГ-МИФИ, 2002. - 384 с. ". Читал ее еще в универе, весьма подробно описаны алгоритмы сжатия, вспомогательного преобразования и кодирования.

Я первый автор, а в жюри описанного выше конкурса первые трое ;)))

Полностью согласен с вами в оценке книжки ;)))))))))))) (сейчас уже много нового, но для старта - вполне)

хехе) а я стеснялся спросить имеете ли вы к ней отношение))

Раза 3 перечитывал книгу. С первого раза не удалось уложить все в голову.
Впечатления от книги сугубо положительные. Спасибо за труд.

сейчас уже много нового

нет мыслей выпустить новую редакцию?

Нереально по времени. Счастьем будет хотя бы посты сюда почаще делать)

Спасибо за статью. Представление о современных трендах в сжатии имею по форуму на encode.su, но здесь всё наглядно и понятно, со сравнением алгоритмов.

А какой пароль на архив с данными в задании для студентов?

Отлично! Если что - пишите на почту, указанную внизу каждой страницы сайта конкурса - так будет оперативнее.

очень интересно, а я думал, что в этой области движухи особо нет, конечно в новостях на хабре иногда мелькают сообщения о новых библиотеках, но потом это всё куда-то исчезает. Сжатие картинок у которых 16 бит на канал, кстати, востребовано фотографами, RAW файлы с камеры весят от 20 до 100 МБ за штуку и сжатие тоже хотелось бы иметь без потерь (ну или со специфическими малозначимыми), ведь иначе теряется весь смысл в RAW файле.

Спасибо за полезную статью. От меня немного комментариев:

1) С 1992 года попал на платформу IBM PC

2) Для архивов в основном пользовался LHA/ARJ, работа с pkzip/pkunzip мне никогда не нравилась

3) C 1996 стал пользоваться RAR

4) С 2009 перешёл на 7 Zip

5) С 2020 для долговременной архивации использую ZPAQ, для каждодневной продолжаю пользоваться 7 Zip

6) ZIP использую в редких случаях если не знаю есть ли на принимающей стороне что-то для распаковки

7) На флешках у меня уже 15 лет файловая система NTFS с включенным сжатием, на ПК куча папок с тоже включенным сжатием, на работе куча сетевых ресурсов тоже с сжатием.

8) Подавляющее большинство рядовых пользователей не пользуются никакими архиваторами никогда, поэтому например появление docx/xlsx форматов для обывателей стало куда более заметным нежели появление ZPAQ

9) До сих пор, непонятно почему, но на многих ПК стоит взломанный WinRAR при доступности бесплатного 7 Zip

За последние 20 лет мы получили rANS, ZPAQ, CMIX, проблема "отсутствия развития" связана ровно с тем что резко выросла доступная память, как оперативная так и на всех типах носителей.

Абсолютно согласен с наблюдениями!

Интересно, что сейчас спрос на алгоритмы сжатия сместился в корпоративный сегмент (сжатие специфических данных, сжатие баз данных и т.п.). К нам постоянно приходят компании (Intel, Huawei, Яндекс) поскольку они не могут найти специалистов по сжатию, а я читаю единственный спецкурс в России по сжатию и собираюсь его прибить, поскольку с точки зрения студентов в области тоже "никакого развития давно нет". А у компаний это реакцию ужаса вызывает. Но поддерживать пока не спешат (точнее низовые начальники очень хотят, а выше...). Так что возможно единственный курс по сжатию тоже прикажет долго жить. Я уже спокойно к этому отношусь. Записи лекций и слайды есть - компании своих людей их изучать могут направить.

Просьба прокомментировать новую разработку китайцев https://ieeexplore.ieee.org/document/8668771 , которая обещает lossless сжатие уже сжатого h264/h265 потока на 15-20%.

Очень интересно было бы найти готовый билд этого.
Я так понимаю это не просто пережатие CABVLC в CABAC, как было в Pied Piper у DropBox.

Также на глаза попалась ещё одна новинка 2022 года https://arxiv.org/pdf/2203.16357.pdf - losless пережатие Jpeg посильнее JpegXL/Lepton/PackJpg/CMIX/StuffIt, пережимает примерно в 1.5 раза лучше чем JpegXL, 29% против 19% . Не просто пережимают, используя арифметическое кодирование, как вышеперечисленные, а дополнительно с нейросеткой. И всё это за секунду.
Вот бы тоже найти код/билд в открытом доступе.

Кстати, этот подход тоже бы хорошо применить для lossless пережатия видео, сделав сжатие ещё сильнее чем по ссылке выше.

Посмотреть бы картинку на градиентах. Меня модные алгоритмы не устроили "ступеньками" цветов, которые возникают на градиентах. А так если смотреть стрим на Twitch, то это не важно.

Если это lossless, как они говорят, и декодирование идёт бит в бит, то изменений быть не должно.

Обратил внимание на этот эффект на видео, где при кодировании использовалось ускорение видеокартой. Насколько оно в этом случае lossless незнаю.

Вы великолепно копнули!

Просьба прокомментировать новую разработку китайцев https://ieeexplore.ieee.org/document/8668771 , которая обещает lossless сжатие уже сжатого h264/h265 потока на 15-20%.

Перегружен, смотрел бегло. Из плюсов:
* Очень интересно, что этим кто-то плотно занимается!

Из минусов:
* Публикация не в профильном, а в междисциплинарном месте
* Это Rapid review - с такими публикациями более частые приколы
* RD кривые приведены, но почему-то не сравнительные (что напрашивается) - т.е. нормальных ревьюверов у статьи не было.
* То, что выглядит как сжатие - похоже не сжатие, а соотношение NAL units. И в выигрыш по сжатию тоже замаскировали - похоже это на самом деле то, что написано, т.е. сколько бит на фрейм сэкономили. Т.е. экономия копеечная. А фраза "that our approachcan considerably reduce the bit rate of streaming video" - по сути реклама.

А вот https://arxiv.org/pdf/2203.16357.pdf - крайне интересная работа! Прикрутили сеточку и увеличили эффективность сжатия коэффициентов - абсолютно реально и вполне реальные цифры. Ключевой минус статьи - тестировали на Кодаке. Он смешного размера. И код не выложен. Может не воспроизвестись) (сегодня это сплошь и рядом)

Ну и я руководил подобным проектом когда-то - про это есть тут https://habr.com/ru/post/525664/ Там ключевая проблема - если меняется стандарт - это становится крайне сложно продать. Мы РЕАЛЬНО на 20% без потерь MP3 жали (в том числе битые и в том числе при потоковом вещании) и были большие проблемы с продажей технологии.

Интересно, что мы тогда экспериментировали с JPEG и тоже около 20% был прогноз, в этом плане что сейчас с сеточками больше наиграли - вполне реально, но проверять надо.

Кстати, спасибо за Sound Slimmer. Те же принципы сжатия коэффециентов DCT в StuffIt, я так понимаю вы тоже приложили туда руку?
Интересно, нейросеть для звука тоже могла бы улучшить сжатие этих MDCT?

PackMP3/PackJpg тоже сделал кто-то из ваших учеников? PackRaw тоже оказалась неплохая, -25% на ARW от Sony.

StuffIt - это параллельная разработка, а PackMP3/PackJpg - это Matthias Stirner, который в свое поселился на http://packjpg.encode.su/?page_id=17 у наших коллег.

Да, современными методами улучшить сжатие MDCT, конечно, можно.

Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

Публикации

Истории