Compressing small packets

[cbloom]

Say you need to compress some small packets for sending over a network. Not actually TCP packets but app data packets, of size 1-64k, average size around 16k.

The channel is not persistent, so you can't use any information from previous packets.

Compressor speed is important, so any compressor that has to initialize a large model is not okay. Mem use has to be under 256k.

How would you do it?

The obvious answer is a small-hash-table LZ77, with or without entropy coding on the back end, but is there something better that I'm not seeing?

[encode]

It's funny, but these days I'm toying with such idea exactly. Apart from LZ77/LZRW, I'd say Predictor algorithm (RFC 1987), or sort of simplified Symbol Ranking. I have found a few ideas on how to improve Predictor compression with no speed loss. I even wrote an ASM-driven version. Will release it soon!

[Cyan]

For small packets, having a pre-set dictionary to "warm up" the LZ reference table can get you a pretty significant win.

[cbloom]

It's funny, but these days I'm toying with such idea exactly. Apart from LZ77/LZRW, I'd say Predictor algorithm (RFC 1987), or sort of simplified Symbol Ranking. I have found a few ideas on how to improve Predictor compression with no speed loss. I even wrote an ASM-driven version. Will release it soon!

Cool, looking forward to that.

I've been thinking a bit along those lines. LZP1 was originally made to beat Predictor in this context. I find them hard to make faster than LZ77 these days though, because the cost of a branch is so high now. They can still be good if what you care about is MAX(encode_time,decode_time) because they're so symmetric, but not so awesome if you are measuring the sum (encode_time+decode_time).

It seems you could store the last 4 or 8 symbols in each context packed into a U32 or U64. Then adding a symbol is just shift and or. Maybe do some kind of fast scan for a byte in a U32 or U64. Hmm I might try this.

With SSE4 you could do a super fast symbol-ranker. The new string instructions look great for maintaining MTF lists.

[encode]

Well, that Predictor is just LZP with MIN_MATCH=MAX_MATCH=1. Unfortunately, LZP with simplest byte-aligned coding not really strikes - i.e. it has poor compression performance, unlike LZSS/LZRW. In other words, for LZP we need sort of Huffman-like bit codes for a match length coding - since we must able to compress that 1-byte match to achieve some compression. Predictor scores here.
Also, it should be noted that LZSS has some branches too - literal (literal run) or match, in simplest case. The thing is, LZSS' decompressor never maintain hash-tables of any kind. It performs just guided copy/paste.
At the same time LZP/Predictor must maintain a hash table of pointers/symbols (plus, compute a hash). Memory access is a big bottleneck, and for large hash tables it's even bigger than branches.
Anyway, my Predictor definitely is not slow and it beats my LZSS implementations in terms of Comp.Time+Decomp.Time due to its lightning fast compression (Even if we talking about pure C++ compile)