45 votes

Efficient compression of simple binary data

Sure, of course there are algorithms. Here is my algorithm: First, check if the file contains ordered binary numbers from $0$ to $2^n-1$, for some $n$. If so, write out a 0 bit followed by $n$ one ...
D.W.'s user avatar
  • 156k
39 votes
Accepted

Do lossless compression algorithms reduce entropy?

A lot of casual descriptions of entropy are confusing in this way because entropy is not quite as neat and tidy a measure as sometimes presented. In particular, the standard definition of Shannon ...
senderle's user avatar
  • 596
38 votes
Accepted

Can data be compressed to size smaller than Shannon data compression limit?

Actually I don't fully understand this algorithm or the Shannon limit very well, I just know it's the sum of the probability of each character multiplied by log2 of the reciprocal of the probability. ...
orlp's user avatar
  • 12.7k
28 votes
Accepted

Simulating a probability of 1 of 2^N with less than N random bits

Wow, great question! Let me try to explain the resolution. It'll take three distinct steps. The first thing to note is that the entropy is focused more on the average number of bits needed per draw,...
D.W.'s user avatar
  • 156k
27 votes
Accepted

Compressing two integers disregarding order

Yes, one can. If $x<y$, map the set $\{x,y\}$ to the number $$f(x,y) = y(y-1)/2 + x.$$ It is easy to show that $f$ is bijective, and so this can be uniquely decoded. Also, when $0 \le x < y ...
D.W.'s user avatar
  • 156k
27 votes
Accepted

Efficient compression of simple binary data

This seems to be a clear use case for delta compression. If $n$ is known a priori this is trivial: store the first number verbatim, and for each next number store only the difference to the previous. ...
leftaroundabout's user avatar
18 votes

Shannon Entropy of 0.922, 3 Distinct Values

Here is a concrete encoding that can represent each symbol in less than 1 bit on average: First, split the input string into pairs of successive characters (e.g. AAAAAAAABC becomes AA|AA|AA|AA|BC). ...
nomadictype's user avatar
16 votes

Efficient compression of simple binary data

Anything using a BWT (Burrows–Wheeler transform) ought to be able to compress that fairly well. My quick Python test: ...
TLW's user avatar
  • 1,404
16 votes
Accepted

Shannon Entropy of 0.922, 3 Distinct Values

The entropy you've calculated isn't really for the specific string but, rather, for a random source of symbols that generates $A$ with probability $\tfrac{8}{10}$, and $B$ and $C$ with ...
David Richerby's user avatar
14 votes
Accepted

Is there a generalization of Huffman Coding to Arithmetic coding?

Let's look at a slightly different way of thinking about Huffman coding. Suppose you have an alphabet of three symbols, A, B, and C, with probabilities 0.5, 0.25, and 0.25. Because the probabilities ...
Pseudonym's user avatar
  • 21.6k
13 votes

Can data be compressed to size smaller than Shannon data compression limit?

It's trivially simple to show that you can compress below the Shannon limit--take a cheating compressor that has a bunch of common files assigned to tokens. Said files are stored as those tokens. (...
Loren Pechtel's user avatar
13 votes

Shannon Entropy of 0.922, 3 Distinct Values

Let $\mathcal{D}$ be the following distribution over $\{A,B,C\}$: if $X \sim \mathcal{D}$ then $\Pr[X=A] = 4/5$ and $\Pr[X=B]=\Pr[X=C]=1/10$. For each $n$ we can construct prefix codes $C_n\colon \{A,...
Yuval Filmus's user avatar
12 votes
Accepted

PRNG for generating numbers with n set bits exactly

What you need is a random number between 0 and ${ 64 \choose n } - 1$. The problem then is to turn this into the bit pattern. This is known as enumerative coding, and it's one of the oldest deployed ...
Pseudonym's user avatar
  • 21.6k
12 votes

Do lossless compression algorithms reduce entropy?

No, if the algorithm is lossless no steps in the compression sequence can reduce its entropy - otherwise it would not be able to be decompressed/decoded. However, the additional entropy may be stored ...
Luke Schwartzkopff's user avatar
11 votes

Can data be compressed to size smaller than Shannon data compression limit?

You first apply the model to the data, computing the sequence of probabilities, f.e. $1/2$, $1/3$, $1/6$. Then, to encode each symbol with probability $p$, you need $log_2(1/p)$ bits. And given some ...
Bulat's user avatar
  • 1,845
11 votes

I think you can always compress compressed data, is it true?

Here's the problem with that reasoning: If you could always compress data, you could compress the compressed data, then compress that, etc. until you have something that is 0 bytes long. You can ...
jmite's user avatar
  • 29.7k
10 votes

Compressing two integers disregarding order

As an addition to D.W.'s answer, note that this is a particular case of the Combinatorial Number System, which compactly maps a strictly decreasing sequence of $k$ non-negative integers $c_k > \...
filipos's user avatar
  • 261
10 votes
Accepted

The Entropy of the phrase "Eile Mit Weile"

The two answers agree, with the following change: it's 1.63263 nats, not bits. That is, the value 1.63263 is calculated using the natural logarithm.
Yuval Filmus's user avatar
9 votes

Efficient compression of simple binary data

PNG encoding does exactly what you want. It works on real life data also, not just extremely organized data. In PNG, each row is encoded with a filter, of which 4 are specified. One of these is "...
Cort Ammon's user avatar
  • 3,241
9 votes
Accepted

Prove that Hitting Set is NP-Complete

3SAT is reduced to the Hitting Set problem. Given a 3SAT $\phi$ having $m$ clauses and $n$ variables, define $$S = \{ x_1, \dots x_n, \overline{x_1}, \dots , \overline{x_n}\}$$ $$S_i=\{y_1, y_2, y_3\...
fade2black's user avatar
  • 9,757
9 votes
Accepted

Does a binary code with length 6, size 32 and distance 2 exist?

Yes, there is such a set. You are actually on the right track to find the following example. Let $C = \{c : |c|=6 \text{ and there are even number of 1's in c}\}$. You can check the following. $|C|=...
John L.'s user avatar
  • 38.6k
9 votes

Find the number using binary search against one possible lie

A generalization of this class of problems is widely studied. See, e.g., this paper for a survey. In your particular case, the problem can be easily solved without any asymptotic change in the ...
Steven's user avatar
  • 28.2k
8 votes

Under what conditions does the function C = f(A,B) satisfy H(C|A) = H(B)?

Note \begin{align} 0&=H(C|A,B)\\ &=H(A,B,C)-H(A,B)\\ &=H(B|A,C)+H(C|A)+H(A)-H(A,B)\quad\text{(chain rule)}\\ &=H(B|A,C)+H(C|A)-H(B|A), \end{align} so $H(C|A)=H(B)$ is equivalently $...
xskxzr's user avatar
  • 7,395
8 votes
Accepted

What is the name of the following binary encoding?

Your encoding is not self-terminating, which makes it somewhat less useful than encodings such as universal codes. Given an integer $n \geq 0$, write $n+2$ in binary without leading zeroes, and remove ...
Yuval Filmus's user avatar
7 votes

I think you can always compress compressed data, is it true?

The effect of a compression method is to replace a string (the uncompressed data) with another string (the compressed data). So it is a function from strings to strings. We want this function to have ...
reinierpost's user avatar
  • 5,359
7 votes

Does a binary code with length 6, size 32 and distance 2 exist?

All words of even parity from a linear code with $2^{n-1}$ codewords and minimum distance $2$. More generally, if $A_2(n,d)$ is the maximum size of a code of length $n$ and minimum distance $d$, then ...
Yuval Filmus's user avatar
7 votes

Find the number using binary search against one possible lie

If normal binary search would take k questions, then you can solve this with 2k+1 questions: Ask each question twice. If you get the same answer, it was the truth. If not, a third question reveals the ...
gnasher729's user avatar
  • 28.3k
6 votes

Algorithms that achieve better compression for more data

Compressing compressed data only benefits you if the original compression wasn't very good. Good compression essentially removes all the patterns, leaving very little for any future round of ...
David Richerby's user avatar
6 votes

Arithmetic coding and "the optimal compression ratio"

Beware: The phrase "optimal compression ratio" is perhaps a bit misleading. It is intended to make you think of "the best compression ratio that is achievable", but there are some assumptions that it ...
D.W.'s user avatar
  • 156k
6 votes

Do lossless compression algorithms reduce entropy?

They reduce the apparent entropy inherent in the structure of the original message. Or in other words they tune the message to make use of the strengths of the next stages of compression. One simple ...
ratchet freak's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible