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.♦
- 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 ...
- 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.
...
- 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.♦
- 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.♦
- 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. ...
- 1,671
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). ...
- 281
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:
...
- 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 ...
- 81.4k
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 ...
- 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. (...
- 293
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,...
- 275k
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 ...
- 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 ...
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 ...
- 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 ...
- 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 > \...
- 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.
- 275k
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 "...
- 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\...
- 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|=...
- 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 ...
- 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 $...
- 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 ...
- 275k
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 ...
- 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 ...
- 275k
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 ...
- 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 ...
- 81.4k
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.♦
- 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 ...
- 4,301
Only top scored, non community-wiki answers of a minimum length are eligible