Is there any value in thinking of the data to be compressed as a big integer, and trying to come up with an expression or program that, when evaluated or executed, produces the desired integer?
A Gentle Introduction to Data Compression
11–16 of 16 posts
Re: A Gentle Introduction to Data Compression
#12Is there any value in thinking of the data to be compressed as a big integer, and trying to come up with an expression or program that, when evaluated or executed, produces the desired integer?
In some sense, this is exactly what decompression does. The question, if I understand you correctly, becomes one of "how is this decompression program designed?" Does it require any particular inputs? etc.
Although somewhat different than what you're describing, you might be interested in arithmetic coding, which encodes data to a single numerical value that can later be recovered by an inverse process.
Re: A Gentle Introduction to Data Compression
#13Huffman encoding reminds me of UTF-8. What is the connection there? Is UTF-8 based on Huffman encoding?
It's not based on it, but the fact that English takes 1 character and the rest take 2 does resembles the same concept, since English is more common than other languages in general.
Re: A Gentle Introduction to Data Compression
#14I think that for beginners it's far better to talk about the LZ-style algorithms first, since they are much easier to understand without requiring any discussion of probabilities and the associated maths; the idea of replacing repeated strings with a reference to them is very intuitive, and so is the implementation of an LZ compressor/decompressor. In fact, an in-memory LZ decompressor core can be written in less tha…
I agree. Transforms (LZ77, BWT, RLE, ...) are generally more interesting and productive than entropy coding. http://mattmahoney.net/dc/dce.html
Re: A Gentle Introduction to Data Compression
#15Very nice introduction. Recently I've been following the progress of the Finite State Entropy algorithm[1]. From the readme on the github project [2]: >FSE is a new kind of Entropy encoder, based on ANS theory, from Jarek Duda. >It is designed to compete with Huffman encoder and Arithmetic ones. >While huffman is fast but can only represent probabilities in power of 2 (50%, 25%, etc.) arithmetic coding can represent…
The performance figures displayed on those pages look exceptional. Has anyone experimented with it already ?
Re: A Gentle Introduction to Data Compression
#16Very nice introduction. Recently I've been following the progress of the Finite State Entropy algorithm[1]. From the readme on the github project [2]: >FSE is a new kind of Entropy encoder, based on ANS theory, from Jarek Duda. >It is designed to compete with Huffman encoder and Arithmetic ones. >While huffman is fast but can only represent probabilities in power of 2 (50%, 25%, etc.) arithmetic coding can represent…
Well, if it's as good as claimed, then maybe it needs to be described as a new category, alongside Huffman, arithmetic & Rle