Every piece of information or file that is compressed sends a dictionary along with it. In the case of, say, many HTML or CSS files, this dictionary data is likely nearly completely redundant.
There's almost no added complexity since zstd already handles separate compression dictionaries quite well.
The standard compressed formats don't literally contain a dictionary. The decompressed data becomes its own dictionary while its being decompressed. This makes the first occurrence of any pattern less efficiently compressed (but usually it's still compressed thanks to entropy coding), and then it becomes cheap to repeat.
Brotli has a default dictionary with bits of HTML and scripts. This is built in into the decompressor, and not sent with the files.
The decompression dictionaries aren't magic. They're basically a prefix for decompressed files, so that a first occurrence of some pattern can be referenced from the dictionary instead of built from scratch. This helps only with the first occurrences of data near the start of the file, and for all the later repetitions the dictionary becomes irrelevant.
The dictionary needs to be downloaded too, and you're not going to have dictionaries all the way down, so you pay the cost of decompressing the data without a dictionary whether it's a dictionary + dictionary-using-file, or just the full file itself.
Of course, the Brotli default (built-in) dictionary is infamous for containing such strings like "Holy Roman Emperor", "Confederate States", "Dominican Republic", etc., due to the way it was created. One can see the whole dictionary in https://gist.github.com/duskwuff/8a75e1b5e5a06d768336c8c7c37....
Having a dictionary created by actual content to be compressed will end up with a very different dictionary.
Which is why the idea is to use a previous version of the same file, which you already have cached from a prior visit to the site. You pay the cost of decompressing without a dictionary, but only on the first visit. Basically it's a way to restore the benefits of caching for files that change often, but only a little bit each time.
show significant gain of using dictionary over compressed w/o dictionary.
It seems like instead of sites reducing bloat, they will just shift the bloat to your hard-drive. Some of the examples said dictionary of 1MB which doesn't seem big, but could add up if everyone is doing this.
That demonstrates how useless this is. It only shaves off kilobytes on extremely bloated sites that waste megabytes of data.
For example, take the CNN example:
> The JavaScript was 98% smaller using the previous version as a dictionary for the new version than if the new version was downloaded with brotli alone. Specifically, the 278kb JavaScript was 90kb with brotli alone and 2kb when using brotli and the previous version as a dictionary.
Oh wow! 98% savings! That's amazing! Except in absolute terms the difference between 90 KB and 2 KB is only 88 KB. Meanwhile, cnn.com pulls in 63.7 MB of data just on the first page load. So in reality, that 88 KB saved was less than 0.14% of the total data, which is negligible.
If you're shipping a JS bundle, for instance, that has small, frequent updates, this should be a good use case. There's a test site here that accompanies the explainer which looks interesting for estimates: https://use-as-dictionary.com/generate/
In some applications, there’s no “good enough,” even small gains help and can be significant when multiplied across a large system. It’s like the software version of American Airlines saving $40,000/year by removing one olive from their salads.
Interesting idea. I wonder if there would be a way to do steganography here. That is, changing the message by using a different dictionary but with the same delta / same set of compression rules.
Allowing for changing the message obviously means that things like malware become a possibility.
Why can’t browsers/servers just store a standard English dictionary and communicate via indexes?. Anything that isn’t in the dictionary can be sent raw. I’ve always had this thought but don’t see why it isn’t implemented. Might get a bit more involved with other languages but the principle remains the same.
Thinking about it a bit more, we are doing this at the character level- a Unicode table, so why can’t we lookup words or maybe even common sentences ?
Compression is limited by the pigeonhole principle. You can't get any compression for free.
There's every possible text in Pi, but on average it's going to cost the same or more to encode the location of the text than the text itself.
To get compression, you can only shift costs around, by making some things take fewer bits to represent, at the cost of making everything else take more bits to disambiguate (e.g. instead of all bytes taking 8 bits, you can make a specific byte take 1 bit, but all other bytes will need 9 bits).
To be able to reference words from an English dictionary, you will have to dedicate some sequences of bits to them in the compressed stream.
If you use your best and shortest sequences, you're wasting them on picking from an inflexible fixed dictionary, instead of representing data in some more sophisticated way that is more frequently useful (which decoders already do by building adaptive dictionaries on the fly and other dynamic techniques).
If you try to avoid hurting normal compression and assign less valuable longer sequences of bits to the dictionary words instead, these sequences will likely end up being longer than the words themselves.
Seems like this would result in quite a lot of increased server load.
Previously servers would cache compressed versions of your static resources.
Whereas now they either have to compress on-the-fly or have a massive cache of not only your most recent static JavaScript blob, but also all past blobs and versions compressed using different combinations of them as a dictionary.
This could easily 10x resources needed for serving static html/CSS/js.
Presumably you'd generate a standalone compressed form (or forms) as usual, and also compressed forms using several dictionaries.
Then the server is doing more work at request time, but it's not meaningfully more work --- just checking if the request path has a dictionary compressed form that matches the dictionary hash provided by the client.
The past versions stored clientside are the dictionaries. Serverside, just keep the diffs against, say, the last five versions around if storage is an issue, or whatever gets you some high percentage of returning clients, then rebuild when pushing a new release.
Cloudflare and similar services seem well positioned to take advantage of this.
Analyze the most common responses of a website on their platform, build an efficient dictionary from that data, and then automatically inject a link to that site-specific dictionary so future responses are optimally compressed and save on bandwidth. All transparent to the customers and end users.
Per-URL dictionaries (where a URL is its own dictionary) are great, because they allow updating to a new version of a resource incrementally, and an old version of the same resource is the best template, and there's no extra cost when you already have it.
However, I'm sceptical about usefulness of multi-page shared dictionaries (where you construct one for a site or group of pages). They're a gamble that can backfire.
The extra dictionary needs to be downloaded, so it starts as an extra overhead. It's not enough for it to just match something. It has to beat regular (per-page) compression to be better than nothing, and it must be useful enough to repay its own cost before it even starts being a net positive. This basically means everything in the dictionary must be useful to a user, and has to be used more than once, otherwise it's just an unnecessary upfront slowdown.
Standard (per-page) compression is already very good at removing simple repetitive patterns, and Brotli even comes with a default built-in dictionary of random HTML-like fragments. This further narrows down usefulness of the shared dictionaries, because generic page-like content is enough to be an advantage. They need to contain more specific content to beat standard compression, but the more specific the dictionary is, the lesser the chance of it fitting what the user browses.
It seems very odd to use a colon as starting and ending delimiter when the header name is already using a colon. Wouldn’t a comma or semicolon work better?
Oh, thanks, it looked like a string such as a hash or base64 encoded data, not binary. Don’t think I have ever seen a use case for binary data like this in a header before.
This seems like a lot of added complexity for limited gain. Are there cases where gzip and br at their highest compression levels aren’t good enough?
Every piece of information or file that is compressed sends a dictionary along with it. In the case of, say, many HTML or CSS files, this dictionary data is likely nearly completely redundant.
There's almost no added complexity since zstd already handles separate compression dictionaries quite well.
The standard compressed formats don't literally contain a dictionary. The decompressed data becomes its own dictionary while its being decompressed. This makes the first occurrence of any pattern less efficiently compressed (but usually it's still compressed thanks to entropy coding), and then it becomes cheap to repeat.
Brotli has a default dictionary with bits of HTML and scripts. This is built in into the decompressor, and not sent with the files.
The decompression dictionaries aren't magic. They're basically a prefix for decompressed files, so that a first occurrence of some pattern can be referenced from the dictionary instead of built from scratch. This helps only with the first occurrences of data near the start of the file, and for all the later repetitions the dictionary becomes irrelevant.
The dictionary needs to be downloaded too, and you're not going to have dictionaries all the way down, so you pay the cost of decompressing the data without a dictionary whether it's a dictionary + dictionary-using-file, or just the full file itself.
Of course, the Brotli default (built-in) dictionary is infamous for containing such strings like "Holy Roman Emperor", "Confederate States", "Dominican Republic", etc., due to the way it was created. One can see the whole dictionary in https://gist.github.com/duskwuff/8a75e1b5e5a06d768336c8c7c37....
Having a dictionary created by actual content to be compressed will end up with a very different dictionary.
> The dictionary needs to be downloaded too
Which is why the idea is to use a previous version of the same file, which you already have cached from a prior visit to the site. You pay the cost of decompressing without a dictionary, but only on the first visit. Basically it's a way to restore the benefits of caching for files that change often, but only a little bit each time.
Some examples here: https://github.com/WICG/compression-dictionary-transport/blo...
show significant gain of using dictionary over compressed w/o dictionary.
It seems like instead of sites reducing bloat, they will just shift the bloat to your hard-drive. Some of the examples said dictionary of 1MB which doesn't seem big, but could add up if everyone is doing this.
That demonstrates how useless this is. It only shaves off kilobytes on extremely bloated sites that waste megabytes of data.
For example, take the CNN example:
> The JavaScript was 98% smaller using the previous version as a dictionary for the new version than if the new version was downloaded with brotli alone. Specifically, the 278kb JavaScript was 90kb with brotli alone and 2kb when using brotli and the previous version as a dictionary.
Oh wow! 98% savings! That's amazing! Except in absolute terms the difference between 90 KB and 2 KB is only 88 KB. Meanwhile, cnn.com pulls in 63.7 MB of data just on the first page load. So in reality, that 88 KB saved was less than 0.14% of the total data, which is negligible.
What makes you think this would stop working if applied to 63.7 MB of JavaScript instead of just one file?
If you're shipping a JS bundle, for instance, that has small, frequent updates, this should be a good use case. There's a test site here that accompanies the explainer which looks interesting for estimates: https://use-as-dictionary.com/generate/
In some applications, there’s no “good enough,” even small gains help and can be significant when multiplied across a large system. It’s like the software version of American Airlines saving $40,000/year by removing one olive from their salads.
If this interests you, I highly recommend watching this talk by Pat Meenan.
https://www.youtube.com/watch?v=Gt0H2DxdAPY
Interesting idea. I wonder if there would be a way to do steganography here. That is, changing the message by using a different dictionary but with the same delta / same set of compression rules.
Allowing for changing the message obviously means that things like malware become a possibility.
https://en.wikipedia.org/wiki/Steganography
Why can’t browsers/servers just store a standard English dictionary and communicate via indexes?. Anything that isn’t in the dictionary can be sent raw. I’ve always had this thought but don’t see why it isn’t implemented. Might get a bit more involved with other languages but the principle remains the same.
Thinking about it a bit more, we are doing this at the character level- a Unicode table, so why can’t we lookup words or maybe even common sentences ?
Compression is limited by the pigeonhole principle. You can't get any compression for free.
There's every possible text in Pi, but on average it's going to cost the same or more to encode the location of the text than the text itself.
To get compression, you can only shift costs around, by making some things take fewer bits to represent, at the cost of making everything else take more bits to disambiguate (e.g. instead of all bytes taking 8 bits, you can make a specific byte take 1 bit, but all other bytes will need 9 bits).
To be able to reference words from an English dictionary, you will have to dedicate some sequences of bits to them in the compressed stream.
If you use your best and shortest sequences, you're wasting them on picking from an inflexible fixed dictionary, instead of representing data in some more sophisticated way that is more frequently useful (which decoders already do by building adaptive dictionaries on the fly and other dynamic techniques).
If you try to avoid hurting normal compression and assign less valuable longer sequences of bits to the dictionary words instead, these sequences will likely end up being longer than the words themselves.
Compression algorithms like Brotli already do this:
https://www.rfc-editor.org/rfc/rfc7932#page-28
Brotli has a built-in dictionary.
Seems like this would result in quite a lot of increased server load.
Previously servers would cache compressed versions of your static resources.
Whereas now they either have to compress on-the-fly or have a massive cache of not only your most recent static JavaScript blob, but also all past blobs and versions compressed using different combinations of them as a dictionary.
This could easily 10x resources needed for serving static html/CSS/js.
Presumably you'd generate a standalone compressed form (or forms) as usual, and also compressed forms using several dictionaries.
Then the server is doing more work at request time, but it's not meaningfully more work --- just checking if the request path has a dictionary compressed form that matches the dictionary hash provided by the client.
The past versions stored clientside are the dictionaries. Serverside, just keep the diffs against, say, the last five versions around if storage is an issue, or whatever gets you some high percentage of returning clients, then rebuild when pushing a new release.
Cloudflare and similar services seem well positioned to take advantage of this.
Analyze the most common responses of a website on their platform, build an efficient dictionary from that data, and then automatically inject a link to that site-specific dictionary so future responses are optimally compressed and save on bandwidth. All transparent to the customers and end users.
Per-URL dictionaries (where a URL is its own dictionary) are great, because they allow updating to a new version of a resource incrementally, and an old version of the same resource is the best template, and there's no extra cost when you already have it.
However, I'm sceptical about usefulness of multi-page shared dictionaries (where you construct one for a site or group of pages). They're a gamble that can backfire.
The extra dictionary needs to be downloaded, so it starts as an extra overhead. It's not enough for it to just match something. It has to beat regular (per-page) compression to be better than nothing, and it must be useful enough to repay its own cost before it even starts being a net positive. This basically means everything in the dictionary must be useful to a user, and has to be used more than once, otherwise it's just an unnecessary upfront slowdown.
Standard (per-page) compression is already very good at removing simple repetitive patterns, and Brotli even comes with a default built-in dictionary of random HTML-like fragments. This further narrows down usefulness of the shared dictionaries, because generic page-like content is enough to be an advantage. They need to contain more specific content to beat standard compression, but the more specific the dictionary is, the lesser the chance of it fitting what the user browses.
Excited to see access control mishaps where the training data includes random data from other users
It’s encoded using the spec that binary data in headers should be enclosed by colons: https://www.rfc-editor.org/rfc/rfc8941.html#name-byte-sequen...
Oh, thanks, it looked like a string such as a hash or base64 encoded data, not binary. Don’t think I have ever seen a use case for binary data like this in a header before.
This seems very interesting for APIs where clients have chatty and long lived connections. I’m thinking about the GitHub API, for example.
That `Link:` header broke my brain for a moment.
No doubt someone will figure out how to abuse this into yet another cookie/tracking technology.