3 ms·

In the example in the article, if you want to communicate a series of 5 dice rolls, you can send a binary symbol of the number of each roll (1-6), 5 times. Usin

by nico 3y ago

In the example in the article, if you want to communicate a series of 5 dice rolls, you can send a binary symbol of the number of each roll (1-6), 5 times. Using 3-bit coding for each number, it would take 15bits (5 numbers in the sequence, 3 bits each) to communicate a message But there’s an alternative way, instead of each number individually, you can code the sequences of 5 numbers, which there are 65432 of in this case, 6!/1! = 720, which can be encoded in binary with 8 bits So instead of 15 bits, you can use 8

rododendro 3y ago
All sequences of 5 numbers in the range [6] should be 6 * 6 * ... * 6 = 6^5, which would give 12.92 bits, so 13. The only way to actually do better than sending every symbol would be run length encoding or other non fixed alphabet encodings, which fortunately do not need to be longer than the entropy of the distribution.
- nico 3y ago
  You are right, it’s 6^5 to include sequences with repeating symbols In any case, you don’t need to index the whole numbers space to transmit all the information Like you say, you can use 13 bits instead of 15 And using variable length encoding you can reduce it even more But what is the distribution in this case?
  - rododendro 3y ago
    Well in this case the distribution would simply be a uniform distribution over [1:6], which has entropy 2.58 for each symbol. Which is also the most entropic distribution on the sets of size 6. Like other have said, you can't actually know in a real world scenario your underlying distribution in whatever file you are trying to compress, but since you want to compress it you are telling the program that the file has interesting information (otherwise it would be just noise) and so grammar based encoding would probably not be best, instead lz77 or lz78 would perform better (for example, if you know more about the file you could even do better by transforming first into some frequency domain and then compressing).
    - nico 3y ago
      Fascinating. Thank you. Why do you need to know more about the file to transform to frequency domain?
      - rododendro 3y ago
        Because no information is lost if you simply change domain, but you may spot more patterns faster or easier. For example (even if a bit dated) https://ieeexplore.ieee.org/abstract/document/1614066 https://ieeexplore.ieee.org/abstract/document/1614066 There is a lot of research in this field because of the IoT fad/trend. If you want to know more i would suggest to simply pic a paper from IEEE and deep dive into the terms and terminology and simply skip the proofs of most algorithms/theorems.
- contravariant 3y ago
  You don't need variable length you just need to send the data in bigger blocks. Count all 6^5n ways to throw 5 dice n times, order them lexicographically and send the index in 5nlog(6) bits, rounding up. Your inefficiency is just the rounding error, which quickly becomes trivial. In theory some block sizes should even coincidentally be close to a whole number of bits.
AnimalMuppet 3y ago
> 720, which can be encoded in binary with 8 bits Even if 720 were the right number, that takes 10 bits, not 8.
- nico 3y ago
  Yes, embarrassing mistake Still 10 is less than 15 Additionally, as someone else pointed out, it would be 6^5 sequences, which would need 13 bits Still 13 is less than 15 But the interesting thing is, you can then index the most commonly used sequences of sequences and compress by a few more bits You can keep the process going until you have a 2 bit index for the most commonly used sequences (of sequences (of sequences… ))
  - AnimalMuppet 3y ago
    Sorry to keep nitpicking, but: In this case, you can't compress further. These are dice rolls; there aren't "most commonly used sequences" (if the dice are any good).
    - nico 3y ago
      Yes, however, the moment you choose a message size, there is always only a finite set of ways to arrange the symbols in those positions
IIAOPSW 3y ago
6 possible dice values log2 gives around 2.6 bits per roll. Naively you can spend 3 bits per roll, wasting .4 bits each time, or you can pack n bits into a single message to asymptotically approach 2.6 bits per roll on average. But you can't get under 12.9 bits for 5 dice rolls.

by nico 3y ago

rododendro 3y ago

All sequences of 5 numbers in the range [6] should be 6 * 6 * ... * 6 = 6^5, which would give 12.92 bits, so 13. The only way to actually do better than sending every symbol would be run length encoding or other non fixed alphabet encodings, which fortunately do not need to be longer than the entropy of the distribution.

nico 3y ago
You are right, it’s 6^5 to include sequences with repeating symbols In any case, you don’t need to index the whole numbers space to transmit all the information Like you say, you can use 13 bits instead of 15 And using variable length encoding you can reduce it even more But what is the distribution in this case?
- rododendro 3y ago
  Well in this case the distribution would simply be a uniform distribution over [1:6], which has entropy 2.58 for each symbol. Which is also the most entropic distribution on the sets of size 6. Like other have said, you can't actually know in a real world scenario your underlying distribution in whatever file you are trying to compress, but since you want to compress it you are telling the program that the file has interesting information (otherwise it would be just noise) and so grammar based encoding would probably not be best, instead lz77 or lz78 would perform better (for example, if you know more about the file you could even do better by transforming first into some frequency domain and then compressing).
  - nico 3y ago
    Fascinating. Thank you. Why do you need to know more about the file to transform to frequency domain?
    - rododendro 3y ago
      Because no information is lost if you simply change domain, but you may spot more patterns faster or easier. For example (even if a bit dated) https://ieeexplore.ieee.org/abstract/document/1614066 https://ieeexplore.ieee.org/abstract/document/1614066 There is a lot of research in this field because of the IoT fad/trend. If you want to know more i would suggest to simply pic a paper from IEEE and deep dive into the terms and terminology and simply skip the proofs of most algorithms/theorems.
contravariant 3y ago
You don't need variable length you just need to send the data in bigger blocks. Count all 6^5n ways to throw 5 dice n times, order them lexicographically and send the index in 5nlog(6) bits, rounding up. Your inefficiency is just the rounding error, which quickly becomes trivial. In theory some block sizes should even coincidentally be close to a whole number of bits.

AnimalMuppet 3y ago

> 720, which can be encoded in binary with 8 bits Even if 720 were the right number, that takes 10 bits, not 8.

nico 3y ago
Yes, embarrassing mistake Still 10 is less than 15 Additionally, as someone else pointed out, it would be 6^5 sequences, which would need 13 bits Still 13 is less than 15 But the interesting thing is, you can then index the most commonly used sequences of sequences and compress by a few more bits You can keep the process going until you have a 2 bit index for the most commonly used sequences (of sequences (of sequences… ))
- AnimalMuppet 3y ago
  Sorry to keep nitpicking, but: In this case, you can't compress further. These are dice rolls; there aren't "most commonly used sequences" (if the dice are any good).
  - nico 3y ago
    Yes, however, the moment you choose a message size, there is always only a finite set of ways to arrange the symbols in those positions

IIAOPSW 3y ago

6 possible dice values log2 gives around 2.6 bits per roll. Naively you can spend 3 bits per roll, wasting .4 bits each time, or you can pack n bits into a single message to asymptotically approach 2.6 bits per roll on average. But you can't get under 12.9 bits for 5 dice rolls.