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

## Main features

- statistic compression method
- one-pass compression method
- adaptive compression method
- symetric compression method
- used in CABAC (video compression)

### Time and space complexities

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

**Space complexity of algorithm**: O(`|Σ|`)

## History

As written in reference 1, arithmetic codes were invented by Elias, Rissanen and Pasco, and subsequently made practical by Witten in 1987.

## Description

Arithmetic coding, unlike many others methods, does not code source units one by one, but codes whole input into one decimal number from interval <0,1).

An interval is divided into disjoint subintervals, each belonging to one source unit. Each loaded unit is represented within a new interval using the same range as subinterval belonging to the unit in previous interval. New interval is then divided according to frequencies of units. As a result could be taken any number lying in the interval belonging to last loaded unit.

This version sets initial frequencies of all source units to 1. It is adaptive because of increasing frequency of each loaded unit during coding.

This implementation uses special character `#`

for detection of end-of-input.

## Pseudo-code

```
1:
```**begin**
2: set initial frequencies of all source units to 1
3: interval *I* := new interval [0;1)
4: divide *I* according to frequencies of source units
5: **readSymbol**(*X*)
6: **while** (*X* != EOF) **do**
7: **begin**
8: new *I* := subinterval *I* matching *X*
9: divide *I* according to frequencies of source units
10: increase frequency of *X*
11: **readSymbol**(*X*)
12: **end**
13: **end**

## References

- David J. C. MacKay: Information Theory, Inference, and Learning Algorithms.
- Arithmetic coding. Wikipedia, the free encyclopedia.
- E. Bodden, M. Clasen, J. Kneis: Arithmetic Coding revealed - description of the method.
- Context-Based Adaptive Binary Arithmetic Coding (CABAC) - application of the method.