česky
previous main page content next

Adaptive arithmetic coding - initial frequencies of source units set to 1/n

Main features

Time and space complexities

Time complexity of algorithm: O(|Σ|*n)
Space complexity of algorithm: O(|Σ|)

Description

The algorithm of this method is very similar to its non-adaptive version. The only difference is that we do not count the probability before coding but after coding of every symbol from the input message. This new probability is used to divide the new interval. Decoder counts the probabilities of symbols during decoding in the same way as the coder so the probalities of symbols does not have to be saved in the output file.

In the applet you can see visual representation of this method. The fractions next to the symbols in the boxes on the left side of the output window are actual probabilities of symbols. The numerator and donominator of all fractions are represented in BigInteger so no loss of precision occures.

Pseudo-code


 1:  begin
 2:     set probability of all symbols according to selected method
 3:     interval I := new interval (0,1)
 4:     divide I according to the probability of symbols
 5:     readSymbol(X)
 6:     while (X!=EOF) do
 7:      begin
 8:        new I := subinterval I corresponding symbol X
 9:        update probabilities of all symbols
10:        divide I according to the probability of symbols
11:        readSymbol(X)
12:      end
13:     output(arbitry number from interval I)
14:  end

References

  1. Arithmetic coding. Wikipedia, the free encyclopedia.
  2. US patents on arithmetic coding. Wikipedia, the free encyclopedia.
  3. David J. C. MacKay: Information theory, inference and learning algorithms. Cambridge University Press 2003.
  4. The Arithmetic Coding Page.
  5. Arithmetic Coding. Binary Essence.
  6. Mark Nelson: Arithmetic Coding + Statistical Modeling = Data Compression.

Example