Compression Models

Question 1

Entropy compression model ( Huffman coding )

Answer 1

Generates codewords based on the distribution of inputs.

Optimal in terms of compression rate.
Primary tests are required for learning the statistics of the data.

Question 2

Static compression model ( MORSE ASCII)

Answer 2

Same compression model for all input symbols and the compressed codewords have all the same length for different input symbols.

Fast but not optimal because symbols have statistical probability.

Question 3

Adaptive compression model (LWZ)

Answer 3

Progressively learns and updates the model of incoming text.

Highly efficient despite the lack of statistics of incoming data.

Question 4

Huffman coding

Answer 4

• Sort symbols by probability
• Start from 2 symbols with smallest probability and join them into a new symbol.
• assign 0 to one of the symbols and 1 to the other

Terminate when the sum of the two probabilities reaches 100

Question 5

Huffman encoding (dynamic)

Answer 5

Advantages:
The code is uniquely decodable and prefix free

Used in many applications ( compression jpeg)

Limitations:
Need to know probabilities of the symbols
Error propagation

Question 6

Lzw (adaptive)

Answer 6

Encoding and decoding complexity
Nlog(n)

Question 7

Why not use entropy for compression of symbols with similar probability?

Answer 7

Because the associated code words would have the same length so the compression rate would be low.

Question 8

Entropy

Answer 8

Is the average amount of bits of any uniquely decodable source needs to be grater or equal than the entropy.

Question 9

Compression rate

Answer 9

Len uncompressed/ Len compressed compare with entropy