Improving compression with a preset DEFLATE dictionary
blog.cloudflare.com
blog.cloudflare.com
For our game, this consists of the normal communication going back and forth between server and client, where individual messages are normally <100b.
By sampling some user sessions we built a dictionary, fed it into deflateSetDictionary/inflateSetDictionary, and use that in both Node modules for the server, as well as throughout the ecosystem of Android and iOS.
It's very simple to do; we base all communication on standard JSON (for ease of portability and debugging) but then have the preset-dictionary fed into zip (a simple large string!) to counter the weight of JSON.
Needless to say, binary packing the protocol would give additional gains; but the productivity gains with using dictionaries to get good compression of pure JSON was a great choice for us. And it's really supersimple to do.
One nice benefit is that the protocol is extendable by any developer without worrying about the wire-transport; the compression won't break is someone decides to add a parameter to a message, it just most likely won't be compressed as well as the rest of the message.
It was patented in the context of headers for text messages, which are sent for every message, are generally larger than the message but appear exactly once in each text so never end up in the compression table. Each side of the conversation runs the zip algorithm on the header strings, discards the output up to that point, then compress the text message from that point. On receive they preload the algorithm with the checkpointed data structures from the preload-compression.
This Google technique is probably different enough to be off their radar. But who knows.
I think its the guys who do DirectPC
I wonder: how many folks have Little Bunny Foo Foo stuck in their heads after reading this?
Back in the late 80s I read an interview with Phil Katz who mentioned them to possibly improve PKZIP so I looked them up in the library. That's when it dawned on me there were people far, far more intelligent and clever in this world than I would ever be.
On the other hand Huffman is somewhat less easy to grasp intuitively, but some aspects of its principle of reducing bits/symbol based on their frequency shows up in natural languages: the more common a word is, the shorter it tends to be. It's also a bit more difficult to implement.
Eg see the evolution from phone / mobile phone, to landline / phone.
The output from the DEFLATE stream is not standalone, which makes it really hard to use - a more ideal approach would've been to provide training to the Huffman tree & guess best window sizing from a sample.
But SDCH solves that problem by storing an external named dictionary - clients will read it off a common HTTP location if it's missing in the cache.
Within that, there's a pretty neat standard which SDCH uses - RFC 3284.
I ran into it trying to optimize holding a few billion serialized blogs within an in-memory store with transactional updates - the issue was mostly the in-memory sizes of serialized objects.
I ended up using a versioned external dictionary for compression, which was an extension to VCDIFF with 1 additional instruction in its streams - COPY_DICT.
That concept can be pushed further, to get to something more generic like femtozip - https://github.com/gtoubassi/femtozip/wiki/How-femtozip-work...
Pre-seeding the dictionary could have a better effect in an LZ78 scheme where there is an actual dictionary built and stored in memory as opposed to a moving lookbehind window.
This also makes me wonder how the dictionary is delivered to the end client. If it's sent with each page request, then it hardly makes any sense as you are hauling an extra 16 KB or 32 KB of the dictionary just to have a better chance of compressing the page's first 32 KB.
I wonder if the size of the dictionary itself is factored in the compression benchmarks provided in the article.
That's not to say it isn't possible - rsync does it when updating the contents of a file. I wrote (about five years ago) a program that does it too. What you get is a file that can reconstruct the original file assuming an exact copy of a reference file is present. I use it for my incremental backup system.
Maybe 40bits for the starting point.
You could use variable length indexing method to minimise that third point though, much like UTF8 for text - the vast majority of references need not require close to the 40 bits.
A large (up to 1Gb - 32Kb of 32Kb) collection pre-made dictionaries might be more practical though, and you wouldn't have to pre-load the entire data-set on every device/client. Content expecting the dictionary would need to be labelled as such anyway, so ad a dictionary number to that label. If the client didn't already have that dictionary then it would be an extra HTTP request to get it that once but it would always have it for future use (or for smaller devices you might only hold a portion of the collection in a round-robin manner).
Of course someone would have to make the dictionaries, and everyone and his dog would prefer a different set so standardising could be an issue (if there were several "standards" the footprint would grow significantly). You would want a selection optimised for HTML, a selection for CSS, a selection for Javascript, some for English text, and some for other common languages (natural or technical). When compressing you would either need to pick one of the options arbitrarily (for HTML always use dictionary 3, for instance) or try with several and pick the best (which would be CPU intensive for dynamic content though the results could be cached for static). Clients would need to state they supported the new format, and servers would need to be able to serve content not requiring it as needed, servers would also need to host the dictionaries as you don't want to be adding an extra external point of failure. Oh, and now you have the global presets on each host there would need to be some way of protecting against pollution due to reasons of accidental damage (simple on-disk or in-transit corruption), malicious intent (a DoS attempt), or stupidity (some one deciding it'll be fine to use an as yet unallocated standard preset ID for something more local).
To get around the "standard set" issue in some cases you could perhaps support local standards (so the server could ask for "prime the dictionary with local block 5" instead of "prime the dictionary with standard block 123" and have these preset dictionaries cached and expired just like any other other object read over HTTP)
So while fraught with potential problems it is not an idea without merit - something practical could be gained, though there is debate to be had on whether the effort is worth while. I suspect it wouldn't be, but if I won a lottery and had free time on my hands I might be interested to play with the idea further!
EDIT:
Having actually read the article, the local dictionaries method is very similar to what Google do with SDCH. I wonder if other browsers will ever bother to support it... For dynamically loaded content you could implement it yourself in javascript but that would kill external indexing so would be a problem for content you care about SEO and similar regarding (it could be useful for page/site 3rd party comment services though, and others that that already load all their content that way).
It's the other way around. If you used variable length indexes, most of your symbols will be much larger than 40 bits.
Take as an example a set of 256 byte long symbols. If you shorten one of them to a "1" bit, you just used half of the symbols you could represent with that byte, and almost half of them will need to grow at least one bit.
There are various ways you could arrange the symbol encoding and how deal with those parts of the input that can't be encoded effectively (where the encoding would increase size overall instead of decreasing it). I'm pretty sure it would work, though whether it would be truly practical (in terms of the return from making the effort) rather than just being an interesting little thought experiment is definitely a valid discussion point! The idea of a collection of preset initial dictionaries for LZ77 and similar feels much more practical than the single large reference dictionary for some other scheme.
Just treat your bits as the binary representation of a Natural number and you're done. No computation required for encoding/decoding, and you only need to store one number :)
There's already some work being done in that general direction: http://www.w3.org/TR/SRI/
https://github.com/nmrugg/LZMA-JS
But nothing beats native code for decompression speed and also if it is native it can happen asynchronously outside of the JavaScript's limited threading model (although it is always getting better) and most importantly, it can also happen outside of the JavaScript memory space.