Дельта-кодирование. Завершение проекта.
Ребята, это фантастика! Claude Opus 5.5 творит чудеса!
У меня были планы в отдалённом будущем немного пооптимизировать проект, чтобы он пошустрее работал. Но тут удачно подвернулся Claude Opus, который по сравнению с Sonnet'ом - натурально полноценный сотрудник разработки за $20 в месяц. Ну и всё заверте...
Отдельно порадовала его работа с документацией: поначалу он мне выдал только PDF-ку с презентацией математики, по которой я понял чуть менее, чем ничего. На, мол, кожаный мешок, разбирайся. Я, конечно, ниасилил и пришлось попросить его расписать более подробно. В итоге он мне вывел одну теорему и четыре леммы, прокомментировал всё более детально с примерами и ссылками на код (я ещё в некоторых местах попросил его объяснить, что называется, для тупых) и в итоге я всё-таки сдюжил.
Вообще, я думал, что теоретического максимума для этого алгоритма можно достичь либо каким-то сложным матаном, либо он недостижим в принципе. Но я ошибался, оказалось всё достаточно несложно. И даже немножко обидно что я сам не додумался до этого метода, тем более, что я думал в этом направлении. А именно, мне как-то смутно казалось, что кодировать надо в обратную сторону - начиная с конца файла. Но я так и не смог для себя сформулировать почему это могло бы быть лучше, чем сканирование в прямом направлении.
Смотрите, как это работает: формируется массив UInt32, содержащий длины наиболее оптимальных блоков для каждого из кадров файла (каждого пикселя, семпла и т.д. в зависимости от формата данных). Затем идёт сканирование для каждого кадра начиная с последнего и по направлению к началу файла. Вычисляется наиболее эффективный блок для каждой такой стартовой позиции (точно так же как и у меня, только гораздо более эффективно, о чём скажу чуть ниже). Блок кодируется нормально - по направлению к концу файла, т.е. сами блоки компрессируются и декомпрессируются в прямом направлении. Однако, при поиске наиболее эффективного блока учитывается не только "стоимость" самого блока (его размер в сжатом виде), но она дополнительно суммируется со стоимостью блока, который оказывается следующим за найденным. В свою очередь, его стоимость тоже посичтана с учётом предыдущего блока и так далее до конца файла.
Например: пусть файл содержит N кадров, мы сканируем все кадры начиная с N-1, затем N-2, N-3 и так до начала файла. На каком-то шаге мы ищем наиболее эффективный блок для некоторой позиции p где-то в теле файла. Предположим, что кандидаты на самый эффективный блок имеют длины 50, 67 и 85 кадров. Для выбора наиболее подходящего кандидата сравниваются не сами стоимости кандидатов, а суммы их стоимости со стоимостью следующих за ними (выбранных ранее) наиболее эффективных блоков. Т.е. для первого кандидата его стоимость складывается со стоимостью наиболее эффективного блока на позиции p+50, для второго его стоимость складывается со стоимостью блока на позиции p+76, а для третьего со стоимостью блока на позиции p+85. Получившиеся суммы сравниваются между собой и для наименьшей из них в результирующий массив длин блоков сохраняется длина победившего блока. И так происходит на каждом шаге сканирования исходного файла. Т.е. каждое последующее сканирование на предмет наиболее эффективного блока учитывает стоимости предыдущих цепочек до самого конца файла. В итоге, на нулевой позиции (первый кадр файла) оказывается блок, учитывающий стоимость наиболее эффективной цепочки до конца файла. А затем прямым сканированием от 0-го блока и до конца файла вся цепочка восстанавливается по массиву сохранённых длин блоков и компрессируется в результирующий файл.
Это же гениально! И достаточно просто. Более того, Клод настолько оптимизировал мои алгоритмы поиска наиболее эффективных блоков, что скорость сканирования выросла буквально на порядки. А это, в свою очередь, позволило ему запустить множество поисков с разными параметрами параллельно в разных потоках и таким образом автоматически подобрать наилучшие параметры компрессии. И, что интересно, само по себе применение наиболее эффективной цепочки блоков позволило сократить объём сжатых данных примерно на 1 п.п. по сравнению с моим алгоритмом, а вот автоматический поиск наилучших параметров сжатия повысил эффективность ещё на 2-3 п.п.
Кроме того, он перепёр интерфейс компрессора на мою любимую Avalonia, так что теперь это приложение кроссплатформенное. И дополнительно мы ещё добавили возможность ресемплинга картинок в меньшую сторону. Поскольку алгоритм разрабатывался по большей части для компактной графики для маленьких микроконтроллеров, это может быть более чем удобно.
И это пожалуй всё, что я хотел сделать по проекту дельта-кодирования.
Да, это всё ещё не совсем теоретический максимум, поскольку можно ещё поменять формат заголовков блоков, добавить в них вспомогательные флаги, можно для сжатия изображений работать не только в рамках отдельных цветовых каналов, но и сделать, например, так, чтобы красный канал в расчётах опирался на зелёный или наоборот. Всё это несколько усложнит декомпрессор, но вместе с тем, позволит поднять эффективность на какие-то дополнительные доли процента. Если у вас есть желание, то вы вполне можете вооружиться какой-нибудь продвинутой нейронкой и попробовать проделать такие эксперименты. Мне для моих нужд более чем достаточно того, что уже есть, поэтому я предпочту остановиться, тем более, что сделано было немало.
Полный проект можно найти тут: https://github.com/DmitryMuravyev/Delta-Compression
Если кому-то интересна математика, то полный документ со всеми выкладками можно почитать тут: https://github.com/DmitryMuravyev/Delta-Compression/blob/main/docs/Sprint_4_Full_Theory.pdf
Коллеги, спасибо за внимание и интерес к проекту, а я наконец-то запускаю новый проект, посты о котором в ближайшее время будут в телеге и тут.
Оставайтесь на связи!