Small data compression – theory and practice

[SolidComp]

Hi all – Are there any good write-ups on small data compression, on the theoretical challenges and optimal approaches? I wonder what the best approaches are to small message compression. I mean sizes of about 300 bytes to 3 KB. Does small message compression present any interesting problems or opportunities? I've been looking at data serialization formats like MessagePack, Protocol Buffers, FlatBuffers, JSON, CBOR, Amazon Ion, and so forth. Most are binary, and some are compact, but none are designed specifically for compression. There are two senses in which I mean this:

• They weren't co-developed with a compression codec tailored for them.
• They weren't developed with preprocessing in mind – preprocessing with respect to subsequent compression by an existing codec like gzip, brotli, Zstd, LZMA, etc.

By contrast, I think WebAssembly (Wasm) was developed with compression in mind, with maybe two tiers – tailored compression followed by general compression – but I don't know much about it.

Do you think there should be a lot of headroom still for compressing small binary messages with tailored codecs? I was very impressed with some of the XML-specific codecs like XMill and XGrind (which is homomorphic). Which approaches do you think would work well on already-compact binary messages? What I'm getting at is whether there's a theoretical framework that pops out here, an approach to small payload compression. Something like JSON compresses well because there are lots of chunky and wasteful repeated strings. Compact binary formats are more challenging, but I don't know if things like CM, RANS, FSE, etc. have any particularly interesting properties for small payloads.

Thanks.

Links:

Amazon Ion: http://amzn.github.io/ion-docs/

Apache Arrow: https://arrow.apache.org/

CBOR: https://cbor.io/

FlatBuffers: https://google.github.io/flatbuffers/

JSON: https://www.json.org

MessagePack: https://msgpack.org

Protocol Buffers: https://developers.google.com/protocol-buffers

[ivan2k2]

Hi. Look at https://github.com/antirez/smaz and https://ed-von-schleck.github.io/shoco/ these are compressors designed for short strings\data.

[Shelwien]

https://encode.su/threads/3025-Achie...-short-strings
https://encode.su/threads/3385-Compr...-random-access

[SolidComp]

Hi. Look at https://github.com/antirez/smaz and https://ed-von-schleck.github.io/shoco/ these are compressors designed for short strings\data.

Thanks, shoco looks very interesting. I wonder how it does with binary data. I'm surprised that neither of these projects seem to be maintained.

[SolidComp]

Hi. Look at https://github.com/antirez/smaz and https://ed-von-schleck.github.io/shoco/ these are compressors designed for short strings\data.

It looks like shoco is only good for strings up to 100 bytes or so. That's much smaller than I was thinking of, which was 300 bytes to 3 KB. I wonder if I could just compress 100 byte chunks at a time, and how the performance and ratios would compared to SLZ.

[Jyrki Alakuijala]

An earlier (pre-zopflication) version of brotli was pretty good at small files (<300 bytes). While zopflication improves things in general it can add 20+ bytes in the shortest data.

[Bulat Ziganshin]

What is zopflication? How one can find pre-zoplification versions of Brotli?

[SolidComp]

An earlier (pre-zopflication) version of brotli was pretty good at small files (<300 bytes). While zopflication improves things in general it can add 20+ bytes in the shortest data.

Interesting. Brotli has performed very well in tests so far, beating everything else by a wide margin. This surprised me because I don't think the dictionary is going to have any significant matches with the JSON payments payloads I've tested.

[Shelwien]

> Brotli has performed very well in tests so far, beating everything else by a wide margin.

Brotli does have some advanced parts in statistical model which other LZs lack - like o2-ish models for utf8 and 16-bit audio.
But in the end it still uses huffman coding, so actual compression improvement is not that significant.

> This surprised me because I don't think the dictionary is going to have any significant matches with the JSON payments payloads I've tested.

You can download this file: https://github.com/google/brotli/blo...dictionary.bin
And test it with zstd (and other codecs if you want - by subtracting compressed size of dictionary from compressed size of your file with prepended dictionary).

[SolidComp]

Brotli does have some advanced parts in statistical model which other LZs lack - like o2-ish models for utf8 and 16-bit audio.
But in the end it still uses huffman coding, so actual compression improvement is not that significant.

> This surprised me because I don't think the dictionary is going to have any significant matches with the JSON payments payloads I've tested.

You can download this file: https://github.com/google/brotli/blo...dictionary.bin
And test it with zstd (and other codecs if you want - by subtracting compressed size of dictionary from compressed size of your file with prepended dictionary).

That brotli dictionary file will work with Zstd? How?

What do you mean that compression improvement is not significant? But it is in my testing. Brotli even beats Pavlov's gzip by a wide margin, and Pavlov's gzip has been incredible on other files.

[Shelwien]

> That brotli dictionary file will work with Zstd? How?

zstd.exe --ultra -22 -fo book1.zst book1
zstd.exe -D dictionary.bin --ultra -22 -fo book1d.zst book1
zstd.exe --patch-from=dictionary.bin --ultra -22 -fo book1p.zst book1

> What do you mean that compression improvement is not significant?

768,771 book1
768,771 book1r          // reorder.exe forward.xlt book1 book1r
256,361 book1.bro       // brotli_gc82.exe -q 11 -fo book1.bro book1 
263,455 book1r.bro      // brotli_gc82.exe -q 11 -fo book1r.bro book1r 
261,092 book1.lzma      // lzma.exe e book1 book1.lzma
262,109 book1r.lzma     // lzma.exe e book1r book1r.lzma
264,731 book1.zst       // zstd.exe --ultra -22 -fo book1.zst book1
264,800 book1r.zst      // zstd.exe --ultra -22 -fo book1r.zst book1r

I mean that most of brotli gains come from integrated dictionary rather
than entropy model improvements.
Well, usually - there could be significant differences if we'd try compressing 16-bit wavs
or chinese text in utf8.

> But it is in my testing. Brotli even beats Pavlov's gzip by a wide margin,
> and Pavlov's gzip has been incredible on other files.

Does it really?

32,768 book1r
13,753 book1r.bro
13,823 book1r.gz
13,844 book1r.lzma
13,879 book1r.zst

You have to take into account that deflate only supports 32k window size,
so for files longer than 32k its usually inferior to any new codecs, Pavlov or not.

Also deflate doesn't have integrated dictionary either.

[SolidComp]

Are there any innovative theories for small data compression? It seems like there should be theories and strategies tailored to it. I found the Shoco or Unishox compressor you posted a while back. I think they were hand Huffman coding letters or something.

Small data might end up being best served by dictionaries, I guess. Maybe the technique they use in brotli where you can permute dictionary entries.

[xezz]

shorty.js
https://github.com/enkimute/shorty.js
P5, P6, P12a
http://mattmahoney.net/dc/p5.cpp
http://mattmahoney.net/dc/p6.cpp
http://mattmahoney.net/dc/p12a.cpp
HA
https://www.sac.sk/download/pack/ha0999.zip
MR-RePair
https://github.com/izflare/MR-RePair
GCIS
https://github.com/danielsaad/GCIS

[Dresdenboy]

Here's my bunch of findings (as I'm researching compression of small binary files for a while now -> also check the tiny decompressors thread by introspec):

Lossless Message Compression:
https://www.diva-portal.org/smash/ge...FULLTEXT01.pdf

The Hitchhiker's guide to choosing the compression algorithm for your smart meter data:
https://ieeexplore.ieee.org/document/6348285 (PDF freely available)
Slides:
https://www.ti5.tuhh.de/publications..._energycon.pdf

A Review of IP Packet Compression Techniques:
http://citeseerx.ist.psu.edu/viewdoc...0.1.1.111.6448

Automatic message compression with overload protection:
https://www.sciencedirect.com/scienc...64121216300267

Also feel free to send me compressor executables (Win32/64) and test sets. So I can include them in my test bench (see example plots here and here in the already mentioned thread).

[Jyrki Alakuijala]

What is zopflication? How one can find pre-zoplification versions of Brotli?

Zopflification (an attempt on optimal parsing) was added somewhere around early 2015. So a version from 2014 would likely work. IIRC, we opensource the first version in October 2013. The first version is not file-format compatible with the standardized brotli, but can give ideas on how well it can work for very short files. The first version only includes quality 11.

Brotli's optimal parsing could be greatly improved -- it is still ignoring the context modeling, thus overestimating final literal cost. I suspect another 2 % in density could be possible by doing this more thoroughly.

Before zopflification brotli would often outperform gzip with the smallest files (in 500 byte category) by 40-50 % in compression. After zopflification it got 10-20 % worse in the smallest category. This is likely because zopfli lead to more entropy codes to be used and that is not accounted for in optimal parsing.

[Jyrki Alakuijala]

Brotli does have some advanced parts in statistical model which other LZs lack - like o2-ish models for utf8 and 16-bit audio.
But in the end it still uses huffman coding, so actual compression improvement is not that significant.

Brotli uses my own prefix coding that is different from (length limited) Huffman coding. In my coding I optimize not only for the code length (like Huffman), but also for the complexity of the resulting entropy code representation. That gives an 0.15 % improvement roughly over Huffman coding.

In early 2014 Zoltan Szabadka compared our coding against ANS for our reference test corpora (web and fonts), and a simple ANS implementation was slightly less dense due to more overhead in entropy code description.

In typical use the prefix code that we use is within 1 % of pure arithmetic coding, and simpler and faster (less shadowing of data because no reversals are needed).

(Arithmetic coding gives about 10 % improvement over Huffman in practical implementations. 1 % of that is because of arithmetic coding being more efficient. The 9 % is because of context modeling that arithmetic coding allows. In Brotli we take much of that 9 % by using context modeling that is compatible with prefix coding, but none of the 1 % improvement.)

[Dresdenboy]

Here's another paper describing an LZSS variant for small sensor data packets (so IoT, sensor mesh, SMS, network message compression related works look promising):
An Improving Data Compression Capability in Sensor Node to Support SensorML-Compatible for Internet-of-Things [sic]
http://bit.kuas.edu.tw/~jni/2018/vol3/JNI_2018_vol3_n2_001.pdf

[compgt]

Here's another paper describing an LZSS variant for small sensor data packets (so IoT, sensor mesh, SMS, network message compression related works look promising):
An Improving Data Compression Capability in Sensor Node to Support SensorML-Compatible for Internet-of-Things [sic]
http://bit.kuas.edu.tw/~jni/2018/vol3/JNI_2018_vol3_n2_001.pdf

Dresdenboy, if you're interested in LZSS coding, search for my "RLLZ" in this forum for my remarks on it.

RLLZ doesn't need literal/match prefix bit, no match_len for succeeding similar strings past the initially encoded string, and no literal_len. It was my idea in high school (1988-1992), but i was forgetting computer programming then and we didn't have access to a computer. I remembered it in 2018, so it's here again, straightened out, better explained.

https://encode.su/threads/3013-Reduc...highlight=RLLZ

[compgt]

Brotli uses my own prefix coding that is different from (length limited) Huffman coding. In my coding I optimize not only for the code length (like Huffman), but also for the complexity of the resulting entropy code representation. That gives an 0.15 % improvement roughly over Huffman coding.

In early 2014 Zoltan Szabadka compared our coding against ANS for our reference test corpora (web and fonts), and a simple ANS implementation was slightly less dense due to more overhead in entropy code description.

In typical use the prefix code that we use is within 1 % of pure arithmetic coding, and simpler and faster (less shadowing of data because no reversals are needed).

(Arithmetic coding gives about 10 % improvement over Huffman in practical implementations. 1 % of that is because of arithmetic coding being more efficient. The 9 % is because of context modeling that arithmetic coding allows. In Brotli we take much of that 9 % by using context modeling that is compatible with prefix coding, but none of the 1 % improvement.)

Maybe Jyrki and Google (with all their expertise) can implement RLLZ into an actual compressor and see actual gains for LZ77 and LZSS...

Since the write buffer is imposed in the decoding algorithm, it should be very fast like byte-aligned LZ.

[Dresdenboy]

Dresdenboy, if you're interested in LZSS coding, search for my "RLLZ" in this forum for my remarks on it.

RLLZ doesn't need literal/match prefix bit, no match_len for succeeding similar strings past the initially encoded string, and no literal_len. It was my idea in high school (1988-1992), but i was forgetting computer programming then and we didn't have access to a computer. I remembered it in 2018, so it's here again, straightened out, better explained.

https://encode.su/threads/3013-Reduc...highlight=RLLZ

I already found this thread a few weeks ago. Your algo is very interesting. I think this might also work well with small files which don't have so many matches (covering ~15-50% of total bytes for binary data).

The decompressor code might even be very small.

My literal encoding needs roughly half a bit per literal or more, depending on other parameters, and 0 bits for no literals between matches. Matches (starting from length 2) need more than one bit ofc. This roughly fits the probabilities.

[Dresdenboy]

Christian Steinruecken looked at several compression methods in an interesting way. He scaled the actually compressed window. So we can see compression ratios at each partial file size:

Source: https://q4.github.io/thesis.html