4 ms·

gzip (and all universal source coding) I don't think LZW uses anything statistical. Neither Huffman encoding.

• mturmon 12y ago
  The aim of universal source coding is to get the code rate as close to the source entropy as possible. The proof that this entropy is indeed an absolute limit is statistical (this will be in any introductory text, like Cover and Thomas, that discusses entropy of a stochastic process, i.e. a stream of symbols). And the method of analysis that shows the LZ algorithm itself approaches this limit is also statistical (http://www.cs.duke.edu/courses/spring03/cps296.5/papers/ziv_lempel_1978_variable-rate.pdf http://www.cs.duke.edu/courses/spring03/cps296.5/papers/ziv_...). One of the neat things about LZ is that the algorithm itself really doesn't have a statistical flavor, it's about building dictionaries/codebooks (as you say). But the analysis that shows it actually works is all statistical, or probabilistic, depending on how you define terms.
  • dragontamer 12y ago
    Precisely. Statistics were used in showing that LZ and Huffman Encoding were good from an entropy point of view. There were dozens of compression schemes proposed. How are you to tell which ones are better than other ones? Well... you experiment, and then measure with statistics.