Недавно на Хабре была опубликована статья Разбираем самый маленький PNG в мире. Интересно, а какой самый маленький файл JPEG? В ответах на StackOverflow и Reddit можно встретить размеры 107, 119, 125, 134, 141, 160 байтов. Все они представляют серый прямоугольник 1 на 1. И кто прав? Все правы, просто такая разница объясняется различными режимами кодирования и степенью строгости соответствия стандарту. Описание всех нюансов разрослось до целой статьи cо всеми необходимыми подробностями для более-менее хорошего знакомства с самыми маленькими jpeg-ами. После краткой теории разберем 159-байтный файл на КДПВ, а затем рассмотрим способы его уменьшения.
Сжатие данных *
Упаковываем и распаковываем информацию
Новости
Разбираем самый маленький PNG в мире
Самый миниатюрный PNG в мире весит 67 байт и представляет собой один чёрный пиксель. Выше вы видите его в 200-кратном увеличении.
Красота, не так ли?
Состоит этот файл из четырёх частей:
- Сигнатура PNG, одинаковая во всех файлах этого формата: 8 байт.
- Метаданные изображения, включая его размеры: 25 байт.
- Данные пикселя: 22 байта.
- Маркер «конец изображения»: 12 байт.
Далее я опишу этот файл подробнее и постараюсь объяснить принцип работы формата PNG.
В качестве небольшой затравки скажу, что в конце предстоит неожиданный поворот. Хотя, надеюсь, вам и без того интересно побольше узнать о PNG.
Сжатие целых чисел
Цель статьи осветить state of the art методы сжатия целых чисел, чтобы сэкономить в будущем время исследования алгоритмов и терминологии. При этом описание части алгоритмов может быть упрощено для понимания. Сравнение алгоритмов тоже находится вне рамках этой статьи. Подробнее можно почитать в ссылках.
Многие из упомянутых ниже алгоритмов используются в прикладных задачах: сжатие битмап, обратных индексов, просто массивов данных.
Распаковываем файл gzip вручную. Часть 2
В этой части мы, как и в первой, распакуем файл gzip вручную, но теперь ещё и декодируем коды Хаффмана.
Для начала запишем данные на диск:
$ echo "hector the frantic father on an anchor or a rare fat cat sat on the ranch" > test-huff.txt
$ xxd test-huff.txt
00000000: 6865 6374 6f72 2074 6865 2066 7261 6e74 hector the frant
00000010: 6963 2066 6174 6865 7220 6f6e 2061 6e20 ic father on an
00000020: 616e 6368 6f72 206f 7220 6120 7261 7265 anchor or a rare
00000030: 2066 6174 2063 6174 2073 6174 206f 6e20 fat cat sat on
00000040: 7468 6520 7261 6e63 680a the ranch.
На этот раз файл получился размером 74 байта и содержит 13 символов:
a, c, e, f, h, i, n, o, r, s, t; пробел (0x20) и перевод каретки (0x0a).
В этой строке есть много повторений. Надеюсь, gzip это учтёт. Поскольку я работаю под Windows, то для распаковки использовал 7zip-zstd.
$ 7z a -mx9 test-huff.txt.gz .\test-huff.txt
$ xxd test-huff.txt.gz
00000000: 1f8b 0808 d76f 6565 0200 7465 7374 2d68 .....oee..test-h
00000010: 7566 662e 7478 7400 158b 410a 0031 0c02 uff.txt...A..1..
00000020: effb 0abf 2621 257b 69c1 e6ff d480 1e64 ....&!%{i......d
00000030: c6ca e823 7425 96b8 fb0f 2c7a 0967 8393 ...#t%....,z.g..
00000040: 2873 8710 9543 11ee 75ad cc51 237d 0fc7 (s...C..u..Q#}..
00000050: 9797 d64a 0000 00 ...J...
Чтобы вы лучше поняли, как будет выглядеть декодирование, покажу первую строку декодированного потока gzip:
0101 1001 0001 1101 00111 010 000 1101 0101 1001 000
h e c t o r ' ' t h e ' '
Ну а подробности читайте далее.
Распаковываем файл gzip вручную
В этой небольшой статье мы создадим файл gzip, после чего разберём его внутренние составляющие и просмотрим начинку. Избегая лишней сложности, в качестве содержимого для сжатия мы просто запишем в изначальный файл 8 символов
a
.$ echo "aaaaaaaa" > test.out
$ xxd test.out
00000000: 6161 6161 6161 6161 0a aaaaaaaa.
Файл получился размером 9 байт — 8 символов
a
плюс перевод каретки в конце.Теперь упакуем его. Сделаем это командой
gzip -1
, поскольку так мы задействуем самый быстрый метод сжатия, который позволит нам лучше разобрать процесс. $ gzip -1 test.out
$ xxd test.out.gz
00000000: 1f8b 0808 bf35 6a61 0403 7465 7374 2e6f .....5ja..test.o
00000010: 7574 004b 4c84 002e 00b6 66d7 ad09 0000 ut.KL.....f.....
00000020: 00
Дисклеймер: эту статью я писал в целях обучения, так что мог допустить некоторые ошибки. Мне нравится заниматься низкоуровневым программированием, но моя основная деятельность сосредоточена на веб-разработке для Microsoft Teams.
Генеративный ИИ — это просто «замыленный JPEG интернета», который убедительно косит под интеллект
ИИ чат‑боты любят ловить глюки и выдавать всякую чушь. Так массово, что словом 2023 года признали «галлюционировать». В чем причина такого явления? Является ли генеративный ИИ интеллектом (спойлер — и да, и нет)? И что общего у ChatGPT и копировального аппарата Xerox? Разбираемся, осмысляя неочевидный нюанс в логике работы больших языковых моделей.
Ещё раз про алгоритм сжатия Хаффмана
К написанию этой заметки меня сподвигло почти полное отсутствие информации на русском языке относительно эффективной реализации алгоритма оптимального префиксного кодирования алфавита с минимальной избыточностью, известного по имени своего создателя как алгоритм Хаффмана. Этот алгоритм в том или ином виде используется во многих стандартах и программах сжатия разнообразных данных.
Наполняем до краев: влияние порядка столбцов в таблицах на размеры баз данных PostgresQL
При оценке требований базы данных к оборудованию требуется учет многих факторов. И здесь у Postgres есть одна интересная особенность, которая почти всегда ускользает от внимания разработчиков, потому что она искусно спрятана между столбцами таблиц.
Кодеки новой эпохи: HEVC, AV1, VVC и нейросети
Хотя новые стандарты кодеков появляются каждые десять лет, все они основаны на пиксельной математике — манипулировании значениями отдельных пикселей в видеокадре для удаления информации, не важной для восприятия. Другие математические операции уменьшают объём данных после первоначального кодирования.
В новом поколении кодеков алгоритмы машинного обучения используются для анализа и понимания визуального содержания видео, выявления избыточных данных и более эффективного сжатия. Вместо написанных вручную алгоритмов, тут применяют методы Software 2.0, основанные на обучении. Данная область развивается на протяжении десятилетий, но в последние годы получила сильный толчок. Все знают, что в 2017 году произошёл прорыв в разработке ИИ благодаря изобретению трансформеров. В свою очередь, они основаны на концепции внимания, которую придумали в 90-е. Эта техника впервые позволила соотносить друг с другом отдельные части текста или видеокадра.
Как стажировка в большой компании может преобразить студенческий проект
Добрый день! Меня зовут Дмитрий Грязнов, я студент УрФу и начинающий разработчик.
Вместе с товарищами мы подумали, что всем студентам и школьникам, которые ищут в интернете информацию, был бы полезен сервис, который может делать смысловую выжимку из текста любого объёма. Мы решили разработать именно такое приложение и выступить с этой идеей на конкурсе «Большие вызовы для студентов». Собрали ансамбль моделей, изучили, много чего переработали.
Коротко: мы используем пайплайн из сжимающих T5, Pegasus, экстракции TextRank, парафразер Bart. Сначала один алгоритм определяет вес каждого предложения и передаёт на вход абстрактивной модели 20% самых значимых предложений. А затем второй перефразирует полученный текст, чтобы сделать его более связанным. Очень много интеграционного кода и тюнинга, чтобы это всё заработало нормально. Сейчас расскажу, как дело было.
RSync на стероидах с поддержкой Windows
На Хабре периодически рассказывают о новых инструментах для синхронизации данных. Это интересная тема. Такие программы используются:
- для синхронизации файлов на разных устройствах,
- дедупликации,
- резервного копирования,
- сжатия.
Малейшая оптимизация даёт экономию трафика, места, ускоряет синхронизацию и общую производительность любых систем. Всё, везде и сразу. В эпоху веб-приложений и клиент-серверной архитектуры со множеством девайсов, которые работают в единой инфраструктуре, синхронизация — Святой Грааль, одна из базовых технологий в компьютерной области.
Кроме того, инструменты синхронизации интересны с алгоритмической точки зрения. Любопытно, как люди умудряются оптимизировать базовые алгоритмы типа
rsync
, которые вроде бы работают идеально. Но нет, всегда можно придумать что-то получше.Как мы создаём корпоративную почтовую систему нового поколения Mailion. Оптимизация стоимости хранения данных
Каждый из нас сталкивался с необходимостью настройки сложного ПО, интенсивно потребляющего ресурсы компьютера. Как правило, у такого софта довольно объёмная конфигурация, и из-за этого бывает трудно подобрать комбинацию параметров, при которой этот софт демонстрировал бы высокую производительность при минимальной утилизации железа.
Одна из наиболее ресурсоемких категорий софта сегодня — это системы хранения данных. К ним можно отнести как классические СУБД, так и хранилища различного назначения. В корпоративной почтовой системе Mailion мы используем объектное хранилище собственной разработки — Dispersed Object Store (DOS). Mailion поддерживает одновременную работу до миллиона пользователей, и подобный уровень нагрузки выдвигает существенные требования к производительности и экономической эффективности системы.
Под катом рассказываем, как мы искали оптимальную конфигурацию нашего объектного хранилища, и какие уроки извлекли из этого поиска.
Величайшие программисты XXI века. Юрки Алакуйяла — гений сжатия
Мало кто слышал имя Юрки Алакуйяла (@jyzg), но все мы используем его разработки. Картинки JPEG частенько генерируются фантастическим JPEG-энкодером guetzli с применением психовизуальных моделей, а HTTP-трафик в интернете жмётся кодеком brotli, тоже лучшим в своём классе.
Д-р Юрки Алакуйяла — активный член опенсорсного сообщества и исследователь. Работает техлидом Google Research Europe (Швейцария). Среди последних разработок — алгоритмы сжатия JPEG XL, WebP lossless и др.
Ближайшие события
Революционный метод сжатия изображений
Всем привет! Курс компьютерной графики в том или ином виде присутствует в образовательной программе любой ИТ-специальности. В числе прочего там обязательно проходят форматы графических файлов и затрагивают алгоритмы сжатия изображений. Сегодня я расскажу о новом, современном методе сжатия изображений, который ещё не вошёл ни в один учебник.
Сжатие без потерь — главная концепция в нашей жизни
Бывало так, что из долгой поездки вы помните только несколько моментов? А все отпуска за много лет сливаются в единое целое? А из школьного класса помните фамилии только нескольких человек? Это вовсе не потеря памяти, как может показаться. Наоборот, это признак крайне развитого интеллекта, который научился эффективно сжимать данные.
На самом деле воспоминания из памяти можно вытянуть (разархивировать) через регрессивный гипноз. Просто в данный момент они не нужны, поэтому хранятся в сжатом виде
Все мы знаем и используем компьютерные архиваторы: ZIP, RAR, Brotli и т. д. Но мало кто видит в них модель интеллекта. Это даже как-то странно на первый взгляд. Хотя если подумать, то идеальное сжатие — это синоним понимания.
Как смотрели нюдсы на древних компьютерах?
Формат JPEG представили в 1993 году, а GIF — в 1987-м. Но тогда непонятно, как смотрели фотографии девушек на этой прекрасной машине образца 1983 года?
Такой вопрос пришёл мне от читателя обзора портативного компьютера Compaq Portable. Ответ оказался сложнее, чем мы думали. Давайте разберёмся.
Хакинг метрик качества видео или как с приходом ИИ все становится намного сложнее
Сейчас модно писать, что ML пришел туда и все стало отлично, DL пришел сюда и все стало замечательно. А к кому-то пришел сам AI, и там все стало просто сказочно! Возможна ли ситуация, когда к нам пришел волшебный ML/DL и все стало сложнее, тяжелее и на порядок запутаннее? Безусловно! Разберем такой пример.
Десятки лет при сравнении кодеков и алгоритмов обработки видео исследователи использовали старые добрые метрики PSNR и SSIM с довольно простыми формулами и были счастливы. Но прогресс невозможно остановить! На их место пришли новые метрики и… тут выяснилось, что они взламываются.
— Погодите, погодите… — скажет взволнованный читатель, — А как это вообще выглядит, взломать метрику???
— Добро пожаловать в 21 век, дорогой товарищ! Благодаря неудержимому прогрессу, сегодня можно хакнуть не только утюг, колонку, автопилот машины и домашний пылесос, но и метрику качества видео.
В этот момент собеседники обычно дружно спрашивают, кому это надо? О, поверьте, есть люди, которым не просто надо, а сильно надо! Представьте себе, что вы руководитель подразделения и у вас жесткие KPI (маркетинг требует обогнать конкурентов, от этого зависят нехилые годовые бонусы у всех сотрудников и особенно у вас). Чтобы улучшить видеокодек на условные 4%, требуются десятки человеко-месяцев труда весьма высокооплачиваемых инженеров, причем, бывает, получается, а бывает, не очень. И тут выясняется, что можно за пару недель работы одного зеленого стажера подшаманить метрику на 7%. Ваши действия? Вспоминается жизненный анекдот «тут-то мне карта и поперла»…
Далее мы популярно затронем взлом методом черного ящика, белого ящика, взлом недифференцируемых метрик (привет дистилляция!) и цирк с дифференцируемыми.
Впрочем обо всем по порядку…
Кому интересен цирк с конями взлом метрик — го под кат.
Сжатие изображений при помощи модели Stable Diffusion
Введение
На сегодняшний день Stable Diffusion является источником вдохновения для сообщества любителей опенсорсного машинного обучения и в то же время источником расстройства для художников всего мира. Мне стало любопытно, что ещё может сделать эта важная технология кроме того, как подвергать угрозе рабочие места профессиональных художников и дизайнеров.
В процессе экспериментов с моделью я обнаружил, что она подходит в качестве чрезвычайно эффективного кодека сжатия изображений с потерями. Прежде чем приступать к описанию своей методики и демонстрации кода, вот несколько результатов модели по сравнению с JPG и WebP с высокой степенью сжатия. Все изображения имеют разрешение 512x512 пикселей:
Сжимаем изображения без потерь: какой формат выбрать?
Одна из тестовых фотографий, сжатие без потерь на 41%
Для сжатия изображений без потерь принято использовать PNG. Его обычно применяют для логотипов, скриншотов, диаграмм, где есть сплошные области с одинаковым цветом. Такие области сжимаются лучше всего: все lossless-кодеки используют классический RLE, то есть кодирование повторов. В некоторых случаях это обеспечивает даже лучший коэффициент сжатия, чем JPEG. И никаких искажений.
Но PNG не используют для фотографий — файлы слишком большие. Однако сейчас, с появлением кодеков нового поколения, ситуация должна измениться. Фотографии будут кодировать без потерь в файлы меньшего размера, а PNG наконец-то уйдёт на покой (см. результаты тестирования в конце статьи).
Кто круче rsync? Интересные алгоритмы для синхронизации данных
Тридж, автор rsync
Что может быть приятнее, чем минимизировать объём бэкапа или апдейта? Это не просто экономия ресурсов, а чистая победа интеллекта над энтропией Вселенной. Исключительно силой разума мы уменьшаем размер файла, сохраняя прежний объём информации в нём, тем самым уменьшая поток фотонов в оптоволокне и снижая температуру CPU. Реальное изменение физического мира силой мысли.
Если без шуток, то все знают rsync — инструмент для быстрой синхронизации файлов и каталогов с минимальным трафиком, который пришёл на замену
rcp
и scp
. В нём используется алгоритм со скользящим хешем, разработанный австралийским учёным, программистом и хакером Эндрю Триджеллом по кличке Тридж (на фото).Алгоритм эффективный, но не оптимальный.