Comment by lostgame
10 years ago
Absolutely love this:
'Suppose you have some strange coin - you've tossed it 10 times, and every time it lands on heads. How would you describe this information to someone? You wouldn't say HHHHHHHHH. You would just say "10 tosses, all heads" - bam! You've just compressed some data! Easy. I saved you hours of mindfuck lectures.'
This is a really great, simple way to explain what is otherwise a fairly complex concept to the average bear. Great work.
That's only one half of the problem - you now have an alphabet five times the size so you have actually increased the size of the message! You also need to explain how to encode this efficiently to explain compression.
Not really - the knowledge of what an alphabet can be universally agreed upon and doesn't need to be transmitted with the data. The metaphor here is that software and hardware-based decoding can now be much more powerful because the hardware is more powerful than it used to be.
And of course the truth is you would just transmit "H_10" with the universally agreed upon knowledge that "H" is "Heads" and "_" is number of times.
> you would just transmit "H_10" with the universally agreed upon knowledge that "H" is "Heads" and "_" is number of times.
Yes I get that the alphabet is already agreed upon.
But if I only transmit H or T (uncompressed) that's just one bit needed per symbol. So I can transmit HHHHHHHHH in ten bits. If I introduce this simplified compression to the system and add 0-9 to the alphabet, that now needs four bits per symbol, so the message H10 is 12 bits long (which is longer than uncompressed). And HTHTHTHTHT would be forty bits so if the message doesn't repeat simply it's now four times larger!
See what I mean? It's not successfully compressed anything.
The solution to this is easy and is Huffman coding, but it doesn't make sense to show it for a ten bit message as it won't work well, and in the trite explanation of compression of 'just the symbol and then the number of times it's repeated' this isn't mentioned, so it's only half the story and people will still be puzzled because they will see that your message contains MORE entropy after 'compression', not LESS!
9 replies →
wouldn't you just convert the alphabet to 0-1? Shouldn't the 0-1 compression be the most optimal? That is, you can't find a better deal with any alphabets or numerical?
That's how compression was first explained to me, and it really stuck with me ever since. It was in the context of an image though, and instead of heads, it was red pixels.
What's really cool is that the simple explanation can be extended to explain things like why ciphertext doesn't compress well: because ciphertext has no patterns
Not compression per se, but I remember when I was reverse engineering maps for Chip's Challenge. I would often see a tile (represented as a byte) that was encoded as 0xFF0502. I ended up realizing it meant "Repeat 'tile 2' 5 times." It was fun to figure that out as a kid.
RLE a given. It's true that the average person rarely understand that this is what computers call compression, but everything after that involves a bit of thinking. Optimal huffman.
I think the LZ family are all pretty intuitive --- just replace repeated sequences with a reference to where they occurred before. Even human languages have things like contractions, abbreviations, and acronyms. Thus it is, at least to me, somewhat surprising that LZ was only documented academically several decades after Huffman; perhaps it was thought to be too trivial? LZ can also be thought of as an extension of RLE.
In any case, an LZ decompressor fits in less than 100 bytes of machine instructions and a simple compressor can be implemented in not more than several hundred, all the while providing extremely high compression for its simplicity. It will easily outperform order-0 static or dynamic Huffman on practical files like English text, and would probably make a good assignment in an undergraduate-level beginning data structures/algorithms/programming course; yet it seems more popular to give an assignment on Huffman using trees, which is somewhat ironic since in the real world Huffman is implemented using bit operations and lookup tables, not actual tree data structures.
To give a trivial example, LZ will easily compress ABCDABCDABCDABCD while order-0 Huffman can't do much since each individual symbol has the same frequency.
Another LZ fan here.
My guess is that the "late" development of LZ is due to mainly two reasons:
i) At that moment the pattern matching algorithms were not so advanced. E.g. suffix tree was very recent, and in the next years lots of advances occurred in that area...
ii) Although LZ can appear easier or more intuitive than Huffman, I think it is much less intuitive to prove a good bound in the compression achieved by LZ. OTOH, Huffman is build in a way that shows that it achieves zeroth-order compression.
The DEFLATE[1] algorithm is actually fairly accessible, and will give a good idea of how compression works.
1: https://en.wikipedia.org/wiki/DEFLATE
I liked this explanation of DEFLATE here on HN a few months ago:
https://news.ycombinator.com/item?id=12334270
IMO Huffman is conceptually more complicated (not the implementation, but the logic) than arithmetic coding.
And Huffman isn't optimal unless you are lucky, unlike arithmetic coding.
I never learned AC. It's on my overflowing stack of thing to read about.
4 replies →
Huffman seems simpler to me, but I've implemented both at various times so that might colour my perspective.
1 reply →
I definitely wouldn't say "HHHHHHHHH," since I tossed it 10 times, not 9.
Saying "10 tosses, all heads" reduces the chance of omitting a toss in data entry, which is all to the better.
You're making the assumption the other party knows English, rather than say the abstraction of 'coinflip' which in itself can be abstracted. Do they understand the concept of fairness - is it even odds or not? There's a reason that numbers are considered a more universal 'language' than other forms of communication.
You likely enjoy this read too:
http://antirez.com/news/75
On the HyperLogLog algorithm to count things.
I would probably say I found a two headed coin. I also like how "HHHHHHHHHH" is shorter than "I tossed it 10 times, all heads"
The all-heads sequence is exactly as likely as any other sequence.
right, but you can also say there are many sequences that aren't all heads.
Which is shortest, you can recover the original dataset from any of the following:
- heads, heads, heads, tails, tails, heads
- hhhtth
- h3t2h
- 3b1
FAIL. "10 tosses, all heads" is 20 characters while "HHHHHHHHHH" is 10 characters. You've conducted expansion rather than compression.
That example is about conveying the information verbally to another human, so syllables is interesting, not characters. "h h h h h h h h h h" is 10 syllables, "10 tosses, all heads" is 4 (and could be compressed further to "10 heads").
"10H" is the string you should be comparing it to (or something equivalent.)
If we're going there, H10 may be more efficient.... h10t5h1... Thinking the heads vs tails expression would be before the iteration as a better use case.
1 reply →