Lossless decompression and the generation of random samples (opens in new tab)

(blog.sigfpe.com)

44 pointsjoelg23612y ago6 comments

6 comments

6 comments · 3 top-level

Chris204812y ago· 3 in thread

I simply don't understand this, I don't think I have the right background. Any good starting places for finding more about this topic?

susi2212y ago

I'd suggest diving into discrete probability for a few hours. That should be enough to understand this post. Huffman coding is a little advanced but you can understand the algorithm (not the theory) with just the probability.

DanBC12y ago

I have an alpha version of a text about lossless compression here (http://danbcstupidideas.neocities.org/compression.html)

It's very rough and I'm not a good writer. It's probably horribly patronising. I welcome any corrections and suggestions and etc.

gtani12y ago

this is 100 pages into MacKay's text, which is well paced

http://www.inference.phy.cam.ac.uk/itprnn/book.html

DanBC12y ago

> Huffman coding tries to compress text one letter at a time on the assumption that each letter comes from some fixed and known probability distribution. If the algorithm is successful then we'd expect the compressed text to look like a uniformly distributed sequence of bits. If it didn't then there'd be patterns that could be used for further compression.

This can be gently confusing when you're using different compression systems, (bits vs bytes)

(https://groups.google.com/d/topic/lz4c/DcN5SgFywwk/discussio...)

Someone is compressing very large log files. They then compressed the output, and got further reductions in size.

> The fundamental reason is that these highly repetitive byte sequences, with very small and regular differences, produce repetitive compressed sequences, which can therefore be compressed further. - Yann Collet

hadronzoo12y ago

The same is true of arithmetic coding, which separates the probability model from the encoding process. Feed an arithmetic coder a stream of random bits and it will efficiently sample from your model. See section 6.3: http://www.inference.phy.cam.ac.uk/mackay/itprnn/ps/105.124....

j / k navigate · click thread line to collapse

6 comments

6 comments · 3 top-level

Chris204812y ago· 3 in thread

I simply don't understand this, I don't think I have the right background. Any good starting places for finding more about this topic?

susi2212y ago

DanBC12y ago

I have an alpha version of a text about lossless compression here (http://danbcstupidideas.neocities.org/compression.html)

It's very rough and I'm not a good writer. It's probably horribly patronising. I welcome any corrections and suggestions and etc.

gtani12y ago

this is 100 pages into MacKay's text, which is well paced

http://www.inference.phy.cam.ac.uk/itprnn/book.html

DanBC12y ago

This can be gently confusing when you're using different compression systems, (bits vs bytes)

(https://groups.google.com/d/topic/lz4c/DcN5SgFywwk/discussio...)

Someone is compressing very large log files. They then compressed the output, and got further reductions in size.

hadronzoo12y ago

j / k navigate · click thread line to collapse