Дэн Рута

Первоначальной мотивацией этого побочного проекта был поиск лучшего способа хранения и загрузки весов, обученных нейронной сетью на основе браузера, при разработке jsNet. Чтобы сохранить весы, как у JSON, мне пришлось бы выйти из содержимого, на консоли или на странице, и, как вы можете представить себе, это стало очень плохо, когда сети стали большими и появилось много данных.

Решение, которое я нашел, заключалось в том, чтобы закодировать данные как изображения, которые обрабатываются гораздо лучше, чем обычный текст JSON. Случайно алгоритм, который я использовал для этого, кажется, не только сработал достаточно хорошо, но конечный размер файла был столь же мал, как сжатие gzip, даже фактически превосходя его в большинстве случаев.

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

Алгоритм

Без лишних слов, краткий, высокоуровневый обзор преобразования массива в изображение выглядит следующим образом:

• Числа преобразуются в базу 15, где несколько первых символов являются метаданными
• Результаты объединены
• Затем каждая пара шестнадцатеричных символов преобразуется в значение Uint8Clamped
• Наконец это рисуется на холсте, затем либо возвращается (браузер), либо хранится в файл (nodejs)

Что касается преобразования изображения обратно в данные массива:

• Изображение считывается либо из файла, Uint8ClampedArray, либо из элемента HTML img
• Каждое значение в Uint8ClampedArray преобразуется в базу 16
• После объединения в строку исходные данные разделяются по символу метаданных f.
• Каждая шестнадцатеричная строка затем анализируется обратно в число

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

Мета-данные

Если бы числа были преобразованы по основанию 16 (от 0 до f), используемому на изображениях, не было бы способа различить отдельные значения после объединения. Поэтому они преобразуются в основание 15 (от 0 до e), а символ f используется как разделитель для разделения значений.

Отсюда может потребоваться несколько больше метаданных для других вещей. Но теперь это может быть представлено как база 15, как это в начале, то есть нам больше не нужны только метасимволы.

Положительный или отрицательный
Первый дополнительный нужный бит метаданных – это число положительное или отрицательное. Однако было бы пустой тратой использования всего символа только для двоичного значения, поэтому это объединяется с метаданными для того, сколько базовых 15 символов сохраняет левая часть числа (слева от десятичного знака).

См. Конфигурации раздел ниже, но по умолчанию один символ используется для кодирования обоих, например:

Значения 7 или ниже представляют отрицательное число, в то время как остальные представляют положительное число.

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

Так, например, 3 представляет отрицательное число с 4 цифрами слева, например -1234.xyz. И a представляет положительное число с 3 цифрами слева, например 123.xyz.

Количество начальных десятичных нулей
Наконец, по умолчанию сохраняется количество начальных нулей в десятичном смысле. Снова см. Конфигурации раздел ниже, но по умолчанию используется 1 символ, разрешающий 15 десятичных нулей в начале, например 0,00000000000000001.

Итак, с конфигурациями по умолчанию значение 1430,01623 будет преобразовано в следующее:

‘Ф«является разделителем,»a‘ представляет положительное значение с 3 символами (655), представляющими левую часть десятичного знака, ‘1’ представляет 1 начальный нуль, в 1430 году.01623, а остальные представляют фактическую стоимость. Первые 3 символа, ‘655′ превращаются из основы 15 в 1430, а остальные, ‘733′преобразуется в 1623. Результат объединяется с добавлением начального нуля.

Конфигурации

По умолчанию только один метасимвол используется для кодирования количества шестнадцатеричных символов, используемых для представления левой части десятичного знака (655 => 1430, в примере выше). Это устанавливает ограничение на максимальное шестнадцатеричное значение eeeeeee, равное 170859374 в десятичной системе. Хотя этого должно быть достаточно для большинства случаев, все равно можно представить больше, просто используя 2 символа.

В этом сценарии положительные числа сохраняются как любые значения выше 112, а отрицательные числа как любые значения ниже. This means there’s a theoretical maximum of 113 hex characters that can represent the left side of the number, aka 7912473587054163204202262246064660222224606482062446620828868288862844044480028440444220620006824802826420808608284080640028606608644. Though, in practice, parseInt округление становится смешным после 15 символов, поэтому 9999999999999999 должно быть точкой остановки.

Но, чтобы сэкономить еще больше места, вместо этого эту конфигурацию можно установить на 0, чтобы полностью игнорировать эти метаданные, если вы точно знаете, что числа положительны и в пределах 0–1 (вы всегда можете нормализовать/отменить нормализацию с помощью включенных вспомогательных функций ). Поэтому, 0,123 будет превращено в:

где ‘83‘ является шестнадцатеричной преобразованием 123. Для левой части десятичного знака не сохраняется символ, поскольку считается, что число равно 0.

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

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

Эталонные показатели

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

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

Формат PNG выполняет свою работу, но WebP действительно превосходит gzip! Приблизительно… на 98,5% размера, согласно этим 3 тестам. Использование альфа-канала не помогло уменьшить размер файла, но уменьшило размер изображения в пикселях, поэтому оставили его как конфигурацию с возможностью переключения.

Следующий набор тестов касается конфигурации емкости. Для этого и следующего набора тестов я создал случайный массив чисел в диапазоне от 0 до 1 с 1 десятичным знаком, например: 0,1, 0,4, 0,7, 0,2, и так далее, чтобы убедиться, что данные действительны для любой конфигурации, и проверил варианты PNG и WebP по выводу браузера. Для теста было использовано 80 000 номеров.

WebP довольно легко победил формат PNG и даже gzip, когда емкость была установлена ​​на 0, равнялась ей, когда установлена ​​на 1, и немного больше, когда установлена ​​на 2.

Наконец, размеры сравнивались для конфигурации с десятичными нулями в начале для каждой конфигурации емкости для формата WebP. На этот раз был использован набор из 500 000 чисел того же типа, что и выше.

Кажется, эта конкретная конфигурация действительно хуже для конфигурации с наименьшей емкостью, но лучше для остальных.

Я заключил из этих тестов: если данные нормализуются на этапе предварительной обработки, и вы можете использовать формат WebP, есть потенциал для гораздо лучшего сжатия. Вы также получаете несколько хороших изображений:

Файлы тестов можно найти в хранилище GitHub.

Так что дальше?

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

Другие вещи, которые следует добавить, могут быть автоматическими конфигурациями, чтобы автоматически определять все конфигурации, сначала циклически просматривая данные, чтобы увидеть, что на самом деле нужно.

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

Но пока, чтобы завершить, вот изображение весов для нейронной сети, обученной распознавать рукописные цифры (MNIST). Если предположить, что Medium не использует собственного сжатия, вы должны иметь возможность загрузить его с помощью jsNet в структуре 784–100–10 и иметь обученную модель с изображения PNG!

Страница GitHub для этого здесь, а мой Twitter — @Dan_Ruta.