LZJB-2 compression algorithm

Анатолий Георгиевский, 2021-2025

Разработка алгоритма сжатия и декомпрессии для файловой системы. За основу взят алгоритм LZJB, используемый в файловой системе ZFS. Разработан новый алгоритм сжатия на том же принципе, более эффективный.

Алгоритм предназначен для работы в составе файловой системы и для упаковки пакетов данных при отсылке по сети. Принцип упаковки, в отличие от других алгоритмов, таких как LZ4 и LZO, использует не только байтовый поток данных, но и битовый поток выбора форматов, как в LZJB. В LZ4 и LZJB может применяться только два формата кодирования, в LZJB-2 используется три формата кодирования.

Описание по ссылке: https://project-george.blogspot.com/2021/07/lzo-vs-lzjb.html

Сравнение степени сжатия LZ4 vs LZJB-2, размер блока ограничен 4кБайт. Дистанция поиска для алгоритма LZJB-2 =2кБайта. Примеры:

сам себя пакует, исполняемый код x86_64

$ lz4 --best -v -B4096 lzjb2.exe  test.lz4
using blocks of size 4 KB
*** LZ4 command line interface 64-bits v1.9.3, by Yann Collet ***
Compressed 314731 bytes into 157673 bytes ==> 50.10%
$ lzjb2.exe lzjb2.exe
==> 43.14%

небольшой текстовый файл на русском языке в кодировке UTF-8

$ lz4 --best -v -B4096 test.utf8.txt  test.lz4
Compressed 5126 bytes into 2895 bytes ==> 56.48%
$ lzjb2.exe test.utf8.txt
==> 47.37%

файл в кодировке base64

$ lz4 --best -v -B4096 test.b64 test.lz4
Compressed 466669 bytes into 266322 bytes ==> 57.07%
$ lzjb2.exe test.b64
==> 52.29%

файл векторной графики в формате SVG

$ lz4 --best -v -B4096 test.svg test.lz4
Compressed 622684 bytes into 167499 bytes ==> 26.90%
$ lzjb2.exe test.svg
==> 24.59%

Состав пакета

В составе проекта представлена векторная реализация алгоритмов Adler-32, CRC-32, xxh32 и xxh64. Представлены алгоритмы декомпрессии deflate [RFC1951] и gzip [RFC1952]. В составе графического формата PNG используется сжатие методом deflate [RFC2083]. В проекте представлена распаковка изображений PNG. Для анализа и упаковки используется метод сжатия Хаффмана со статической таблицей. Методы компрессии разделены на два этапа: поиск подстрок и сжатие.

Упаковка тензорных данных

Сжатие метаданных в формате JSON, XML. Сжатие изображений на основе формата PNG.

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

1. Применить два типа фильтров: SCAN-XOR, SCAN-ADD по группе из 32 значений.
2. Для каждого типа квантизованных данных {MXINT8, MXFP8; F16, BF16, HF8, BF8, F32, Q8_1} подобрать свой фильтр, основанный на кластеризации и разнице SCAN-ADD.
3. Кластеризацию f32 рассматривать как {1}{2,3}{4} или {1},{2},{3,4}. BF16 рассматривать как {1},{2}.
4. F32 представить, как два числа: разница {BF16,F16, MXFP8, MXINT8} и градиент {BF16}. метод convert_f32_to_bf16_rne() возвращает значение и позволяет вычислить градиент в формате BF16. Компилятор GCC>13 поддерживает тип __bf16.
5. Режим анализа данных. Добавить оценку энтропии, среднеквадратичную ошибку, среднего по группе MEAN ERR, максимальной относительной ошибки, вывести квантовую ошибку QSNR.
6. Для изображений применить предикаты движения по плитке 4x4 8x8 16x16. Корреляция, ошибка для lossy. PSNR.
7. Предикаты Lorenzo 1st и 2nd order для тензорных данных.

Предварительные результаты по упаковке тензорных данных в формате BF16, на примере весовых коэффициентов визуальной модели InternViT:

1. Потоковое сжатие без не дает результата.
2. Матрицы весов BF16 не содержат значения NaN и INF. Значения как правило содержат только нормализованные числа.
3. Квантизация одновременно удовлетворяет требованиям формата f16 и bf16. Для представления экспоненты достаточно 4-5 бит. Без потери точности можно представить в одном из двух форматов.
4. Использование предиката и сегментации с данными Bfloat16 позволяет снизить разрядность экспоненты на 50%, которая укладывается в 4 бита. Сегментация выполняется: {(uint8_t)(v>>7), (uint8_t)(v>>15|v<<1)};
5. Аналогичный результат с минимизацией ошибки можно получить используя квантизацию eXm7 c общей экспонентой, Q8_1 или MXINT8 (целый тип с общей экспонентой). Использование потокового сжатия после этого не дает результата.

Декомпрессия BF16 использует следующие примитивы: RLE декодирование, SEGMENT-READ-ROTATE, PREDICT-ADD, общая экспонента по группе.

• P. Ratanaworabhan, Jian Ke and M. Burtscher, "Fast lossless compression of scientific floating-point data," Data Compression Conference (DCC'06), Snowbird, UT, USA, 2006, pp. 133-142, doi: 10.1109/DCC.2006.35.
• P. Lindstrom and M. Isenburg, "Fast and Efficient Compression of Floating-Point Data," in IEEE Transactions on Visualization and Computer Graphics, vol. 12, no. 5, pp. 1245-1250, Sept.-Oct. 2006, doi: 10.1109/TVCG.2006.143.
• P. Lindstrom, "Fixed-Rate Compressed Floating-Point Arrays," in IEEE Transactions on Visualization and Computer Graphics, vol. 20, no. 12, pp. 2674-2683, 31 Dec. 2014, doi: 10.1109/TVCG.2014.2346458.
• [2506.18062] Floating-Point Data Transformation for Lossless Compression, 2025
• (https://github.com/LLNL/zfp)
• (https://github.com/LLNL/fpzip)
• (https://github.com/inikep/lzbench)