1
$\begingroup$

I was reading about limits of data compression and I had this question that kept me thinking.

Alphabet set: Set of all the unique symbols in the input data

Q. If the distribution over the alphabet set is uniform then is it possible to compress data theoretically ? Standard compression methods (like Huffman codes) exploit the bias in the frequency distribution to obtain codes that have a lower average length of the input text. Is it possible to work without frequency?

Idea 1: One idea is that since the distribution is uniform over the symbols, then any assignment of codes would result in the same number of symbols in the range of the mapping, thus we would require the same number of bits to store that information. Hence the average length of compressed data should be greater than or equal to the original average length.

Idea 2: Another idea that pops up in my head is that if the distribution of symbols is uniform, why not create a new symbol set S' that is essentially a set of all the bi-grams of symbols. But, this distribution also needs to be uniform as the probability of a pair of symbols is same for all the possible cases.

These ideas force me to conclude that it is not possible to compress data if the distribution is uniform.

Please correct me if I am wrong at any point, also I would like to know your views on the problem.

Edit: If you can also provide a formal proof or a book for reference then it would be great.

$\endgroup$
3
  • $\begingroup$ This question is too broad to admit any answer... and is more like a discussion. $\endgroup$ – Brethlosze Sep 24 '17 at 17:49
  • $\begingroup$ agreed. Though it can be answered with a Yes/No if this is what you mean. ;) $\endgroup$ – Pinkesh Badjatiya Sep 24 '17 at 17:55
  • $\begingroup$ Maybe yes, maybe no. You seek for actually compression? You seek for specific distributions? You seek for brown noise in the spectrum? You seek for real random data or filtered data? You seek for pseudo random patterns? $\endgroup$ – Brethlosze Sep 24 '17 at 18:01
0
$\begingroup$

Your intuitive arguments are correct, however, under the additional assumption (which, I guess you also consider but don't explicitly state):

The source generates symbols that are not only uniformly distributed over the alphabet but also independent.

In that case, there is no (statistical) redundancy of the generated symbol sequence, hence, no room for compression.

Note that if the source symbols are correlated, then one could consider "super-symbols" (such as what you propose in idea 2) that would not be uniformly distributed, and, therefore, compressible.

$\endgroup$
2
  • $\begingroup$ just out of curiosity, are there any compression techniques that do not rely on the distribution of symbols and still compress data? $\endgroup$ – Pinkesh Badjatiya Sep 24 '17 at 18:01
  • $\begingroup$ @PinkeshBadjatiya I cannot say for sure, but I believe that for lossless compression the frequency of symbols comes into play in every (practical) compression algorithm. Even if the frequency is not known, the algorithm will attempt to estimate it and compress based on that estimate. $\endgroup$ – Stelios Sep 24 '17 at 18:07
0
$\begingroup$

Without loss of information, there is no way to compress any data source further than its Shannon Entropy, which is a measure of uncertainty, or information that you get with every new symbol.

The entropy is defined in bits as $H(X) = -\sum_i P[X=i] \log_2 P[X=i]$ for every symbol $i$.

For a symbol source that produces independent and uniformly distributed symbols, the entropy is just the same as the number of bits needed to encode the symbols, and no compression scheme can compress it any further. Your intuition is correct as why it is so.

Sometimes doing n-grams (grouping symbols into a "supersymbol") may help you to compress your data more efficiently. This can work on an uniformly distributed source, but only if your source produces symbols that are dependent on each other. If instead they are independent, no luck. Also, this coding scheme introduces algorithmic delay, since you need two symbols to produce the output.

In some types of coding, you can however get away with using less bits, but the information transmitted will not be the same as before, but likely similar enough for your purpose. This is lossy compression, wildly used in movies, TV and audio to exploit the fact that not every detail in the original audio is perceptible to humans. In that case, since you can't ever perceive the extra information, it's like if it was redundant from the beginning.

$\endgroup$
0
$\begingroup$

On a separate note, here are a few ideas that popped up in my head after reading the initial answers. Posting them here to keep the discussion along these lines separate from the original question.

Theoretically: A random symbol generator that generates a symbol from the alphabet set should be able to generate the data which has a uniform distribution and who's characters are independent by repeatedly running it. But since it is perfectly random, it has to have maximum entropy and thus maximum information.

Practically: We are working with data as a way to send some message/information. If we consider the above type of data, then it does not help us convey information in any way as it is random noise in the universe. We cannot even send 2 similar messages using the above data generator. So, practically speaking this data type is of least importance to us. Even with maximum entropy, it does not help us convey any information. (yes, it seems a bit strange at first look). So we are not dealing with such data and hence there is not really any need to compress such data types.

Practically we use pseudo-random generators, so given a seed, we should be able to generate the whole sequence. Interestingly, a tuple of (seed, message_length) should be enough to generate a message of given length using a pseudo-random generator. So it can be thought of as a way to compress data. But is it possible to generate all possible sequences from the generator?

Now, this boils down to the question: Can pseudo-random generators generate all possible sequences?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.