0
$\begingroup$

I am working on a personal project and I am having some conceptual level questions on arithmetic encoding.

  1. Let's take a scenario where I have an array of sensors and the data collected is transmitted over the internet to Alice. Naturally to decrease transmission cost I would want to transmit data in compressed form. But the data source is non stationary in nature and I have read that we use Adaptive Arithmetic Encoding in such scenario. But I can do this trick that, collect sensor data in a fixed size buffer and when buffer is full then use Normal Arithmetic Encoding and send the encoded sequence over the internet. So my question is why would I want to use Adaptive Arithmetic Encoding in this scenario and what advantage will it serve me? If the above stated scenario is not applicable please explain using other example.
  2. Have I understood both the concepts correctly? (By checking algorithms of both and please point out mistakes if any)
    Arithmetic Encoding

    
    start
        statistical_model = collect_stats(data) //we need to perform single pass over data to collect stats
        for each symbol in data:
            probability_distribution = statistical_model(symbol) //calculate conditional probability distribution for the current symbol given previous n symbols
            current_state = artimetic_encoding(probability_distribution, previous_state)
        return current_state 
    end
    

    Adaptive Arithmetic Encoding

    
    start
        statistical_model = init() // initialize the model in such a way which is known to both encoder and decoder (for example: zero initialization)
        for each symbol in data:
            probability_distribution = statistical_model(symbol) //calculate conditional probability distribution for the current symbol given previous n symbols
            current_state = adaptive_artimetic_encoding(probability_distribution, previous_state)
            update_model(statistical_model, symbol)
        return current_state 
    end
$\endgroup$

1 Answer 1

1
$\begingroup$

The pseudocode looks good to me, except of course that in static arithmetic coding, you need to transmit the model before the decoder can use it.

Exactly how to do that in a space-efficient way is not obvious. One of the advantages of adaptive coding is that it gives you that for free: the loss of compression while the model is "learning" should be (if you did it correctly) exactly the minimal cost of transmitting the model.

But, of course, it's not free because updating an adaptive model isn't free. You pay for it in the CPU and memory efficiency of the encoder and decoder.

$\endgroup$
2
  • $\begingroup$ thank you for your explanation! In case of adaptive, can we make an optimization wherein instead of updating model after each symbol, we do it after n symbols (where n is constant. for example n=256)? This will cause model to learn lot more slowly in start but can helpwith computation. $\endgroup$ Nov 3, 2020 at 14:12
  • $\begingroup$ As long as the encoder and decoder agree, they can do whatever they want. $\endgroup$
    – Pseudonym
    Nov 3, 2020 at 22:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.