96
votes
Accepted
Is Morse code without spaces uniquely decipherable?
The following are both plausible messages, but have a completely different meaning:
...
- 1,054
45
votes
Accepted
Can PRNGs be used to magically compress stuff?
You've got a brilliant new compression scheme, eh? Alrighty, then...
♫ Let's all play, the entropy game ♫
Just to be simple, I will assume you want to compress messages of exactly $n$ bits, for some ...
44
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.♦
- 140k
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
Is Morse code without spaces uniquely decipherable?
Quoting David Richerby from the comments:
Since ⋅ represents E and − represents T, any Morse message without spaces can be interpreted as a string in $\{E,T\}^*$
Further, since A, I, M, and N are ...
- 480
36
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.3k
35
votes
Accepted
Data compression using prime numbers
always compress random data sets by more than 50%
That's impossible. You can't compress random data, you need some structure to take advantage of. Compression must be reversible, so you can't ...
30
votes
Is Morse Code binary, ternary or quinary?
This answer isn't as long as it looks; this site just puts a lot of spacing between list items! Update: Actually it's getting pretty long...
Morse Code isn't "officially" binary, ternary, quaternary, ...
- 402
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.♦
- 140k
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.♦
- 140k
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,641
22
votes
Can PRNGs be used to magically compress stuff?
There are $2^N-1$ binary strings of length less than $N$, and $2^N$ binary strings of length exactly $N$. This means that whatever your compression algorithm is, there must be some string which it can'...
- 269k
21
votes
Accepted
Is Morse Code binary, ternary or quinary?
Morse code is a prefix ternary code (for encoding 58 characters) on top of a prefix binary code encoding the three symbols.
This was a much shorter answer when accepted. However, considering the
...
- 19.1k
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
17
votes
Is Morse code without spaces uniquely decipherable?
It is enough to observe that certain short combinations of letters give ambiguous decodings. A single ambiguous sequence suffices, but I can see the following:
...
- 4,091
17
votes
Data compression using prime numbers
I'm going to defer to Tom van der Zanden who seems to have read the paper and discovered a weakness in the method. While I didn't read the paper in detail, going from the abstract and the results ...
- 18.8k
17
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,272
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 ...
- 80.1k
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 ...
- 18.8k
13
votes
Data compression using prime numbers
You ask:
Is this really feasible as the authors suggest it? According to the paper, their results are very efficient and always compress data to a smaller size. Won't the dictionary size be ...
- 279
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,...
- 269k
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 ...
- 18.8k
12
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. (...
- 283
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
Is Morse code without spaces uniquely decipherable?
Morse Code is actually a ternary code, not a binary code, so the spaces are necessary. If spaces were not there, a lot of ambiguity would result, not so much with the entire message, but with ...
- 658
11
votes
Accepted
Compression functions are only practical because "The bit strings which occur in practice are far from random"?
First of all, you're right: Multimedia files are represented (more or less) as random files. The reason for that is that those files are already compressed (lossy). Note that mp3, for example, is ...
- 1,841
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,787
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.1k
10
votes
Accepted
Compression of Random Data is Impossible?
Here's the Kolmogorov complexity argument that @YuvalFilmus mentions in his answer.
Your input here is a sed script of some size plus an input file of some size. ...
- 17.3k
10
votes
Compression functions are only practical because "The bit strings which occur in practice are far from random"?
Multimedia data is very far from random, which is why it compresses so well. For example, a single second of video at 1920x1080 pixel resolution, with 24-bit colour and 24 frames per second is about ...
- 80.1k
Only top scored, non community-wiki answers of a minimum length are eligible