3 ms·

The article does not say what dictionary compression is and how it works or I have missed it? It would be interesting, and also dictionary compression seems to

The article does not say what dictionary compression is and how it works or I have missed it? It would be interesting, and also dictionary compression seems to be topic of article.

smueller1234 9y ago
https://en.m.wikipedia.org/wiki/Dictionary_coder https://en.m.wikipedia.org/wiki/Dictionary_coder (and an arbitrary large number of other explanations that you can find with a search) In a nutshell, both encoding and deciding side hold a dictionary that maps long sequences of data to still-unique short ones and vice versa (ie. a bijective mapping). Encoder uses it to compress, decoder reverses it. There are obviously many interesting practical questions such as how the dictionary is synchronized, how the mappings are determined, how to keep it a bijective function, etc.
pronoiac 9y ago
Usually, when you compress, it's with, say, gzip, rather than something custom for the data. The compression dictionary is kinda implicitly built and encoded along with the data. If you have, like, some standard data (handwave), you can build a dictionary of frequently-used terms and refer to it when you compress and decompress, and you can get better compression for being able to point at that pre-built dictionary. I might be totally offbase here, as I think database normalization would remove much of the redundancy that a dictionary would target.
- smueller1234 9y ago
  Database normalization has little to do with this. It's about structurally removing redundancy from your schema. Like not having the same column and data twice in two tables. It's not going to do anything if you have two rows with common data such as two people with the same first name. In the context of compression, dictionaries also don't generally correspond to a set of words or records per se but rather arbitrary (sub)strings or blobs.
  - mbreese 9y ago
    I think they were trying to say if you had a normalized database where instead of repeated varchar fields, you had a foreign key — that would act like a dictionary. CREATE TABLE customer( id SERIAL, name VARCHAR(1024), status VARCHAR(1024) ) Vs CREATE TABLE customer( id SERIAL, name VARCHAR(1024), status INT REFERENCES status(id) ) CREATE TABLE status( id SERIAL, name VARCHAR(1024), ) It wasn’t very clear from the parent above, but I think this is where they were trying to go. The normalized version is smaller because you’ve swapped a repeated varchar ‘status’ for an int — so that’s effectively a dictionary. It’s not entirely correct, but it’s not that far off.
    - smueller1234 9y ago
      That makes sense, thanks for pointing out my misreading of the parent comment.
kazinator 9y ago
"Dictionary compression" can be any scheme in which coded symbols in the compressed data are references to some body of accompanying data where their replacements are found.

The article does not say what dictionary compression is and how it works or I have missed it? It would be interesting, and also dictionary compression seems to be topic of article.

smueller1234 9y ago

https://en.m.wikipedia.org/wiki/Dictionary_coder https://en.m.wikipedia.org/wiki/Dictionary_coder (and an arbitrary large number of other explanations that you can find with a search) In a nutshell, both encoding and deciding side hold a dictionary that maps long sequences of data to still-unique short ones and vice versa (ie. a bijective mapping). Encoder uses it to compress, decoder reverses it. There are obviously many interesting practical questions such as how the dictionary is synchronized, how the mappings are determined, how to keep it a bijective function, etc.

pronoiac 9y ago

Usually, when you compress, it's with, say, gzip, rather than something custom for the data. The compression dictionary is kinda implicitly built and encoded along with the data. If you have, like, some standard data (handwave), you can build a dictionary of frequently-used terms and refer to it when you compress and decompress, and you can get better compression for being able to point at that pre-built dictionary. I might be totally offbase here, as I think database normalization would remove much of the redundancy that a dictionary would target.

smueller1234 9y ago
Database normalization has little to do with this. It's about structurally removing redundancy from your schema. Like not having the same column and data twice in two tables. It's not going to do anything if you have two rows with common data such as two people with the same first name. In the context of compression, dictionaries also don't generally correspond to a set of words or records per se but rather arbitrary (sub)strings or blobs.
- mbreese 9y ago
  I think they were trying to say if you had a normalized database where instead of repeated varchar fields, you had a foreign key — that would act like a dictionary. CREATE TABLE customer( id SERIAL, name VARCHAR(1024), status VARCHAR(1024) ) Vs CREATE TABLE customer( id SERIAL, name VARCHAR(1024), status INT REFERENCES status(id) ) CREATE TABLE status( id SERIAL, name VARCHAR(1024), ) It wasn’t very clear from the parent above, but I think this is where they were trying to go. The normalized version is smaller because you’ve swapped a repeated varchar ‘status’ for an int — so that’s effectively a dictionary. It’s not entirely correct, but it’s not that far off.
  - smueller1234 9y ago
    That makes sense, thanks for pointing out my misreading of the parent comment.

kazinator 9y ago

"Dictionary compression" can be any scheme in which coded symbols in the compressed data are references to some body of accompanying data where their replacements are found.