6 ms·

>In fact, any lossless compression algorithm has the property that the output is (on average) at least as long as the input I don't think this is true. If it w

by aengvs 8y ago

>In fact, any lossless compression algorithm has the property that the output is (on average) at least as long as the input I don't think this is true. If it was, lossless compression would be useless in a lot of applications. It's pretty easy to come up with a counter example. E.g. (simple huffman code off the top of my head, not optimal) symbol -> code "00" -> "0" "01" -> "10" "10" -> "110" "11" -> "111" If "00" will appear 99.999% of the time, and the other 3 symbols only appear 0.001% of the time, the output will "on average" be slightly more than half the length of the input.

OscarCunningham 8y ago
Sure, I'm assuming that (a) you are trying to encode all strings of length at most n and (b) you have the uniform distribution over those strings. This makes sense in the original context of encoding random data.
- aengvs 8y ago
  >you have the uniform distribution over those strings. This makes sense in the original context of encoding random data. Lossless compression is nothing more than taking advantage of prior knowledge of the distribution of the data you are compressing. Random data isn't always (or even often) uniformly distributed. Everything we compress is "random" (in the context of information theory), so I disagree that it makes sense to assume uniformly distributed data.
  - OscarCunningham 8y ago
    Then the original statement about not being able to use pi as a data compression method is false. It could be the case that 99% of the time you want to encode the string "141592653".
    - aengvs 8y ago
      The efficacy of a compression algorithm is dependent on the data it is compressing, so that statement is true for some data.
tylerhou 8y ago
https://en.wikipedia.org/wiki/No_free_lunch_theorem https://en.wikipedia.org/wiki/No_free_lunch_theorem
- aengvs 8y ago
  https://en.wikipedia.org/wiki/Entropy_(information_theory) https://en.wikipedia.org/wiki/Entropy_(information_theory)

by aengvs 8y ago

OscarCunningham 8y ago

Sure, I'm assuming that (a) you are trying to encode all strings of length at most n and (b) you have the uniform distribution over those strings. This makes sense in the original context of encoding random data.

aengvs 8y ago
>you have the uniform distribution over those strings. This makes sense in the original context of encoding random data. Lossless compression is nothing more than taking advantage of prior knowledge of the distribution of the data you are compressing. Random data isn't always (or even often) uniformly distributed. Everything we compress is "random" (in the context of information theory), so I disagree that it makes sense to assume uniformly distributed data.
- OscarCunningham 8y ago
  Then the original statement about not being able to use pi as a data compression method is false. It could be the case that 99% of the time you want to encode the string "141592653".
  - aengvs 8y ago
    The efficacy of a compression algorithm is dependent on the data it is compressing, so that statement is true for some data.

tylerhou 8y ago

https://en.wikipedia.org/wiki/No_free_lunch_theorem https://en.wikipedia.org/wiki/No_free_lunch_theorem

aengvs 8y ago
https://en.wikipedia.org/wiki/Entropy_(information_theory) https://en.wikipedia.org/wiki/Entropy_(information_theory)