96 votes
Accepted

Is Morse code without spaces uniquely decipherable?

The following are both plausible messages, but have a completely different meaning: ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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. ...
user avatar
  • 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 ...
user avatar
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, ...
user avatar
  • 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,...
user avatar
  • 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 ...
user avatar
  • 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. ...
user avatar
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'...
user avatar
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 ...
user avatar
  • 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). ...
user avatar
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: ...
user avatar
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 ...
user avatar
  • 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: ...
user avatar
  • 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 ...
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 ...
user avatar
  • 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 ...
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,...
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 ...
user avatar
  • 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. (...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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. ...
user avatar
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 ...
user avatar

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