4 ms·

Simply because indexes into a 1TB dictionary would require 40 bits just for the position, rather than the 15 bits for a 32kB sliding search window. You would al

Simply because indexes into a 1TB dictionary would require 40 bits just for the position, rather than the 15 bits for a 32kB sliding search window. You would also have to implement some sort of indexing system to improve the speed of compression. 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.

ck2 12y ago
40bits if you aren't thinking in offsets. Maybe 40bits for the starting point.
dspillett 12y ago
A single 1Tb dictionary would be nonsensical as would be far too large for many devices, and you wouldn't be able to use it as an "initial state" dictionary for the most commonly supported compression method (as this article is discussing), and if using it for some other compression method (so the 32Kb window limit is not significant) large chunks of it would be useless for most (if not all) content so the large indexing key size could be an issue. 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).
- marcosdumay 12y ago
  > 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. 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.
  - dspillett 12y ago
    Many symbols being longer only matters if they are common (and your encoding method doesn't allow you to leave affected sequences plain to avoid increasing their size), and if, moving away from UFT8-a-like encodings which might have been a bad example, you allow context beyond one symbol you can break them into pages making symbols after a page selection smaller (though the next one that requires a new page to be selected will necessarily be larger). 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.

ck2 12y ago

40bits if you aren't thinking in offsets. Maybe 40bits for the starting point.

dspillett 12y ago

A single 1Tb dictionary would be nonsensical as would be far too large for many devices, and you wouldn't be able to use it as an "initial state" dictionary for the most commonly supported compression method (as this article is discussing), and if using it for some other compression method (so the 32Kb window limit is not significant) large chunks of it would be useless for most (if not all) content so the large indexing key size could be an issue. 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).

marcosdumay 12y ago
> 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. 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.
- dspillett 12y ago
  Many symbols being longer only matters if they are common (and your encoding method doesn't allow you to leave affected sequences plain to avoid increasing their size), and if, moving away from UFT8-a-like encodings which might have been a bad example, you allow context beyond one symbol you can break them into pages making symbols after a page selection smaller (though the next one that requires a new page to be selected will necessarily be larger). 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.