5 ms·

Really enjoyed reading this, I think I'd like to look more closely at an implementation to understand it further. Reading the article, I was reminded of a nagg

by sebular 10y ago

Really enjoyed reading this, I think I'd like to look more closely at an implementation to understand it further. Reading the article, I was reminded of a nagging question I've had in the back of my mind for a bit. The ASCII table was invented in the '70s, when the cost of disk storage was much higher than it is today. But it's a shared dictionary, a standard that we can all agree upon, something that's already on every computer. The thing I've wondered about is whether there could be any advantage to creating new generations of shared dictionaries that are domain-specific, and much larger. For example, in the specific (and over-simplified) case of transmitting large quantities of English text from a server to a client, you could reduce the amount of data sent over the wire if both parties shared a lookup table that contained the entire English dictionary. In that case, you wouldn't transmit a book as a collection of characters, but rather as a collection of words. Furthermore, it would seem like you could apply the same traditional compression methods like what's described in the article to furthermore reduce the amount of data being sent. Rather than identifying repeating patterns of letters, you would identify repeating patterns of words. Of course, the obvious drawback is that an English lookup table is useless for transmitting anything other than English text. But again, disk storage being as cheap as it is, I wonder if it wouldn't be such a monumental problem to store many domain-specific dictionaries. Of course, you'd always want to keep the ASCII table as a fallback. Much in the same way that a conversation in sign language (ASL, specifically) is largely composed of hand gestures referring to words or concepts, but the language still includes the complete alphabet as a fallback. The thing I don't understand well enough is whether modern compression already incorporates concepts that are similar enough such that a shared-word dictionary would be useless. It seems like the "LZXX" style of compression essentially includes a similar but dynamically-generated sort of dictionary at the beginning of the transmission, and subsequently refers to that in order to express the message itself. Would the gains of having enormous shared dictionaries cancel out the advantage of that approach, only in a much more "wasteful" way?

carey 10y ago
It sounds like what you're thinking of has been included in the Brotli compression algorithm, which uses a relatively large initial dictionary. There are similar ideas with a more limited scale in HTTP/2's HPACK algorithm for header compression.
Const-me 10y ago
Microsoft implemented large pre-shared dictionary for their binary XML format. When used in WCF, the XML is a SOAP envelope with some data-contract serialized messages. A lot of XML elements/attributes/values are known in advance. Works very well in practice, here's my blog post about that: http://const.me/articles/net-tcp/ http://const.me/articles/net-tcp/
Erwin 10y ago
Google's SDCH is kind of that, but each website can in advance decide what the contents of the shared dictionary are. So when you download a SDCH compressed page you may also download a dictionary. Information and experiences with usage are sparse, here's one article from LinkedIn: https://engineering.linkedin.com/shared-dictionary-compression-http-linkedin https://engineering.linkedin.com/shared-dictionary-compressi... -- "Average additional compression across our static content was about 24%"
xenadu02 10y ago
The cost-benefit is just too low for this to be practical in most cases: * The large data being transferred is almost never text; it's video, images, or audio which is already using advanced (sometimes lossy) compression * Even if it is text, it's probably in some document format or HTML which greatly complicates the shared dictionary scenario (and would require a separate dictionary for each format) In reality even deflate is already doing what you propose, but it builds the dictionary dynamically and includes it with each message. The up side is its dictionary can find common phrases and patterns that wouldn't be in your fixed dictionary. As the size of the text becomes larger the dictionary becomes a smaller and smaller percentage of the total.
- creshal 10y ago
  Even text is usually precompressed. Both OOXML and ODF use deflate internally, epub as well, and PDF has such a high bloat-to-text ratio that compressing only the text is moot (assuming you don't have one of the increasingly common PDFs where even the text is rendered as image, aaaaargh…).
  - Grishnakh 10y ago
    I've looked into PDFs a little for a personal project of mine that worked with auto-generated PDFs, and I've found they can really vary wildly in the amount of bloat, and I've also found that much of the bloat seems to be from including fonts. If you actually look at the PDF file's binary, it's not that hard to understand, and the actual text is stored mainly as ASCII/utf8 I think. So, if I wanted to really efficiently store a bunch of PDFs that come from the same source, it seems like it should be possible to copy the "bloat" sections (likely embedded fonts) which are all completely identical, and use those in a dictionary in a custom compressor, and then just use zlib for the rest. I've also noticed that some PDF generators include far, far more bloat than others, though I'm not sure why.
sn41 10y ago
I think this is a good idea and could reduce file sizes for compressing text. Moreover, people's active vocabulary is quite small, so even more might be possible. Just as an aside, a cliche was originally a single metal slug used to cast a repeatedly used phrase. So phrase-wise compression of English text might be useful. However, I don't know the practical improvement obtained over the currently existing methods. This is a good project to investigate, I think. Even if text compression might not be important in the larger picture of data transmission on the web, this sounds interesting on its own merit.
TD-Linux 10y ago
You exactly describe Brotli. It has a 100KB pre shared table trained on a large corpus of web content.
dalke 10y ago
The ASCII standard was from the 1960s, not 1970s. LBJ in 1968 mandated that all federal computers purchased by the government must support ASCII. This historical correction does not alter the rest of your comment.
Lerc 10y ago
I considered a project loosely along those lines. My idea was a One-Meg-of-Data project. Define a megabyte of data that everyone would have have in a bit-identical form. The appeal of this to me would be in the code golf style of approach of specifying the actual data. Apart from plain useful raw data, It would include a bare minimum VM that can be used to generate larger outputs from the data. More complex VMs would be permitted provided a reference implementation can be run on the Minimal VM. The code for the reference Implementation would, of course, be included in the one megabyte. A program using the data could request * raw bytes * output from the VM given code and parameters (with perhaps a cycle limit to stop endless loop hangs) * output from the VM given code and parameters specified at an index in the data. * output from the VM given code and parameters specified at an index in the data plus user parameters. The system would be stateless, the VM would only exist for the duration of the data generation call. The same parameters would always produce the same output. I have doubts as to it's fundamental usefulness but it would certainly make a fun collaborative project at the very least.
- woliveirajr 10y ago
  Not exactly your idea, I think, but perhaps similar: - A patent from ibm for some previous dynamic dictionary [1] - Brotli: 120kb predefined dictionary [2] [1] http://www.google.com.br/patents/US8610606 http://www.google.com.br/patents/US8610606 [2] https://en.m.wikipedia.org/wiki/Brotli https://en.m.wikipedia.org/wiki/Brotli
- nitrogen 10y ago
  Doesn't RAR have something kind of like a VM? https://github.com/taviso/rarvmtools https://github.com/taviso/rarvmtools
rakoo 10y ago
> Would the gains of having enormous shared dictionaries cancel out the advantage of that approach, only in a much more "wasteful" way? It does. The extreme of it is storing all information inside pi, as is done here: https://news.ycombinator.com/item?id=6698852 https://news.ycombinator.com/item?id=6698852. In the end the dictionary is so big that the indexes themselves start to be too big. If you really had infinite space and immediate access to all digits, there actually could be some way to make it work, though.
jasonwatkinspdx 10y ago
> The thing I've wondered about is whether there could be any advantage to creating new generations of shared dictionaries that are domain-specific, and much larger. The HPACK header compression used by HTTP2 has a static dictionary. > The thing I don't understand well enough is whether modern compression already incorporates concepts that are similar enough such that a shared-word dictionary would be useless. I believe this is generally the case.

by sebular 10y ago

carey 10y ago

It sounds like what you're thinking of has been included in the Brotli compression algorithm, which uses a relatively large initial dictionary. There are similar ideas with a more limited scale in HTTP/2's HPACK algorithm for header compression.

Const-me 10y ago

Microsoft implemented large pre-shared dictionary for their binary XML format. When used in WCF, the XML is a SOAP envelope with some data-contract serialized messages. A lot of XML elements/attributes/values are known in advance. Works very well in practice, here's my blog post about that: http://const.me/articles/net-tcp/ http://const.me/articles/net-tcp/

Erwin 10y ago

Google's SDCH is kind of that, but each website can in advance decide what the contents of the shared dictionary are. So when you download a SDCH compressed page you may also download a dictionary. Information and experiences with usage are sparse, here's one article from LinkedIn: https://engineering.linkedin.com/shared-dictionary-compression-http-linkedin https://engineering.linkedin.com/shared-dictionary-compressi... -- "Average additional compression across our static content was about 24%"

xenadu02 10y ago

The cost-benefit is just too low for this to be practical in most cases: * The large data being transferred is almost never text; it's video, images, or audio which is already using advanced (sometimes lossy) compression * Even if it is text, it's probably in some document format or HTML which greatly complicates the shared dictionary scenario (and would require a separate dictionary for each format) In reality even deflate is already doing what you propose, but it builds the dictionary dynamically and includes it with each message. The up side is its dictionary can find common phrases and patterns that wouldn't be in your fixed dictionary. As the size of the text becomes larger the dictionary becomes a smaller and smaller percentage of the total.

creshal 10y ago
Even text is usually precompressed. Both OOXML and ODF use deflate internally, epub as well, and PDF has such a high bloat-to-text ratio that compressing only the text is moot (assuming you don't have one of the increasingly common PDFs where even the text is rendered as image, aaaaargh…).
- Grishnakh 10y ago
  I've looked into PDFs a little for a personal project of mine that worked with auto-generated PDFs, and I've found they can really vary wildly in the amount of bloat, and I've also found that much of the bloat seems to be from including fonts. If you actually look at the PDF file's binary, it's not that hard to understand, and the actual text is stored mainly as ASCII/utf8 I think. So, if I wanted to really efficiently store a bunch of PDFs that come from the same source, it seems like it should be possible to copy the "bloat" sections (likely embedded fonts) which are all completely identical, and use those in a dictionary in a custom compressor, and then just use zlib for the rest. I've also noticed that some PDF generators include far, far more bloat than others, though I'm not sure why.

sn41 10y ago

I think this is a good idea and could reduce file sizes for compressing text. Moreover, people's active vocabulary is quite small, so even more might be possible. Just as an aside, a cliche was originally a single metal slug used to cast a repeatedly used phrase. So phrase-wise compression of English text might be useful. However, I don't know the practical improvement obtained over the currently existing methods. This is a good project to investigate, I think. Even if text compression might not be important in the larger picture of data transmission on the web, this sounds interesting on its own merit.

TD-Linux 10y ago

You exactly describe Brotli. It has a 100KB pre shared table trained on a large corpus of web content.

dalke 10y ago

The ASCII standard was from the 1960s, not 1970s. LBJ in 1968 mandated that all federal computers purchased by the government must support ASCII. This historical correction does not alter the rest of your comment.

Lerc 10y ago

I considered a project loosely along those lines. My idea was a One-Meg-of-Data project. Define a megabyte of data that everyone would have have in a bit-identical form. The appeal of this to me would be in the code golf style of approach of specifying the actual data. Apart from plain useful raw data, It would include a bare minimum VM that can be used to generate larger outputs from the data. More complex VMs would be permitted provided a reference implementation can be run on the Minimal VM. The code for the reference Implementation would, of course, be included in the one megabyte. A program using the data could request * raw bytes * output from the VM given code and parameters (with perhaps a cycle limit to stop endless loop hangs) * output from the VM given code and parameters specified at an index in the data. * output from the VM given code and parameters specified at an index in the data plus user parameters. The system would be stateless, the VM would only exist for the duration of the data generation call. The same parameters would always produce the same output. I have doubts as to it's fundamental usefulness but it would certainly make a fun collaborative project at the very least.

woliveirajr 10y ago
Not exactly your idea, I think, but perhaps similar: - A patent from ibm for some previous dynamic dictionary [1] - Brotli: 120kb predefined dictionary [2] [1] http://www.google.com.br/patents/US8610606 http://www.google.com.br/patents/US8610606 [2] https://en.m.wikipedia.org/wiki/Brotli https://en.m.wikipedia.org/wiki/Brotli
nitrogen 10y ago
Doesn't RAR have something kind of like a VM? https://github.com/taviso/rarvmtools https://github.com/taviso/rarvmtools

rakoo 10y ago

> Would the gains of having enormous shared dictionaries cancel out the advantage of that approach, only in a much more "wasteful" way? It does. The extreme of it is storing all information inside pi, as is done here: https://news.ycombinator.com/item?id=6698852 https://news.ycombinator.com/item?id=6698852. In the end the dictionary is so big that the indexes themselves start to be too big. If you really had infinite space and immediate access to all digits, there actually could be some way to make it work, though.

jasonwatkinspdx 10y ago

> The thing I've wondered about is whether there could be any advantage to creating new generations of shared dictionaries that are domain-specific, and much larger. The HPACK header compression used by HTTP2 has a static dictionary. > The thing I don't understand well enough is whether modern compression already incorporates concepts that are similar enough such that a shared-word dictionary would be useless. I believe this is generally the case.