ANS Visualizer#

Asymmetric Numeral Systems (ANS) is a family of entropy coding methods used in data compression. It was invented by Jarek Duda.

For arrays of independently sampled symbols, ANS can achieve compression ratios that approach the theoretical limit defined by Shannon entropy. ANS has been adopted in various compression algorithms and formats, including Facebook's Zstandard and Apple's LZFSE.

The simple_ans package is a simple and efficient Python implementation of ANS. The purpose of this app is to visualize the version of ANS encoding and decoding that is implemented in this library.

Explanation of ANS#

The core idea of ANS is to encode a sequence of symbols into a single integer state, with each symbol affecting the state in a way that reflects its probability of occurrence. This encoding is reversible, allowing us to recover the original sequence from the coded integer.

Suppose that $\{0, 1, ..., S-1\}$ are the symbols we want to encode (in the interactive view, these are denoted as $A, B, C, ...$ ), and assume that they occur with relative frequencies $f_0, ..., f_{S-1}$ (positive integers). The goal is to encode a sequence of symbols $(s_1, s_2, ..., s_k)$ into a single integer state $x$ .

We assume that the symbols are sampled randomly and independently of one another. Let

L = \sum_{i=0}^{S-1} f_i

be the sum of the symbol frequencies.

The Symbol Table#

To encode our symbols efficiently, we need a way to map between states and symbols that reflects their frequencies. We accomplish this using an infinite table $T$ that maps natural numbers to symbols: $T: \mathbb{N} \to \{0,...,S-1\}$

We construct this table with a periodic pattern where:

Each period of length $L$ $L$ consists of consecutive blocks:
- $f_0$ occurrences of symbol 0 (or A)
- $f_1$ occurrences of symbol 1 (or B)
- ...
- $f_{S-1}$ occurrences of symbol $S-1$
This pattern repeats every $L$ positions
For any position $n$ , $T(n) = T(n \text{ mod } L)$
Define $C_s = \sum_{i=0}^{s-1} f_i$ as the cumulative frequency (start position of symbol $s$ in each period)

Encoding#

The encoding process works by maintaining a state value $x$ that evolves as we process each symbol. Starting from state $x_0$ :

To encode symbol $s_1$ $s_{1}$ :
- Find the $x_0$ -th occurrence of symbol $s_1$ (counting from 0)
- This position index becomes our new state $x_1$
Repeat this process for each new symbol, using the previous state to find the next one

This process effectively "pushes" each symbol onto our state value in a way that can be reversed.

With the periodic structured table, the formula for this is

x_{i+1} = (x_i // f_{s_i}) \cdot L + C(s_i) + (x_i \text{ mod } f_{s_i})

where $//$ denotes integer division and $\text{ mod }$ is the modulo operation.

Notice that for large $x_i$ ,

x_{i+1} \approx x_i \cdot p_s^{-1}

where $p_s = f_s / L$ is the probability of symbol $s$ . This means that the expected value of $\log(x_i)$ grows by $-\log(p_s)$ at each step, leading to:

\lim_{k \to \infty} E(\frac{1}{k}\log(x_k)) = -\sum_{s=0}^{S-1} p_s \log(p_s).

Or in other words, if $H$ is the average number of bits required to encode a single symbol in the sequence, then

H = -\sum_{s=0}^{S-1} p_s \log(p_s)

which matches the Shannon entropy of the symbol distribution. In other words, the integer $x_k$ encodes the state using the theoretically optimal number of bits.

Decoding#

Given a final state $x_k$ , we can recover the original sequence as follows:

The last symbol $s_k$ is simply $T[x_k]$ (the symbol at position $x_k$ )
To get the previous state $x_{k-1}$ $x_{k - 1}$ :
- Count how many times $s_k$ appeared before position $x_k$
- This count is our previous state $x_{k-1}$
Continue this process to recover all symbols in reverse order

The formula for this decoding is

x_i = (x_{i+1} // L) \cdot f_{s_i} + (x_{i+1} \text{ mod } L) - C(s_i)

Interactive Visualization#

This app illustrates the encoding and decoding processes described above. You specify the symbol frequencies and the table of states is shown with each integer state represented as a box. As you hover over a box, you can see the path of black arrows representing the decoding process as well as blue arrows representing the encoding process for all possibilities of the next symbol to encode. For technical reasons, you also need to specify the number of leading A's for the decoded sequence, but this information cannot be captured by just the integer state alone.

Practical ANS Implementation#

The Need for Bounded State#

In practice, we can't work with arbitrarily large integers. Our state $x$ would grow indefinitely as we encode more symbols, and operating on integers with arbitrarily large precision is very inefficient. We therefore need a way to keep the state within a manageable range while preserving the reversibility of the encoding.

Word-Based Streaming with Conditional Normalization#

Instead of normalizing at every step, we use a more efficient approach that only normalizes when necessary. We maintain our state as a 64-bit integer and stream out 32-bit words when the state would overflow.

Let $W$ be an array of 32-bit words, initialized to empty. We define:

STATE_BITS = 64 (total bits for state)
WORD_BITS = 32 (bits per output word)
THRESHOLD = 2^32 (minimum state value after normalization)

For efficiency of calculations we assume that $L$ is a power of 2:

L = 2^{l}

Encoding Process#

When encoding symbol $s$ with current state $x$ :

Check for normalization: If $(x >> (64 - l)) \geq f_s$ , then:
- Extract the lower 32 bits: $w = x \text{ mod } 2^{32}$
- Append $w$ to word array $W$
- Update state: $x = x >> 32$
Encode the symbol:
- Compute: $remainder = x \text{ mod } f_s$
- Compute: $prefix = x // f_s$
- Update state: $x = (prefix << l) | (C_s + remainder)$

The key insight is that normalization only occurs when the next encoding step would cause overflow, making the algorithm more efficient.

Decoding Process#

To decode from final state $x$ and word array $W$ :

Extract symbol:
- $quantile = x \text{ mod } L$
- Find symbol $s$ such that $C_s \leq quantile < C_s + f_s$
Compute previous state:
- $prefix = x >> l$
- $previous\_state = prefix \cdot f_s + (quantile - C_s)$
Check for denormalization: If $previous\_state < THRESHOLD$ and words remain:
- Pop word $w$ from end of $W$
- Update: $previous\_state = (previous\_state << 32) | w$
Continue: Set $x = previous\_state$ and repeat

This approach maintains the state above the threshold while efficiently managing memory by streaming out words only when necessary.

Optimality of the Compression#

In the above, there are two sources of loss in the compression efficiency:

The assumption that the frequencies sum to a power of two
The need to normalize the state

The first of these can be addressed by choosing $L=2^l$ large enough so that the proportions $p_i = f_i / L$ are accurate enough so that the loss is negligible.

The second source of loss is more difficult to predict but can be examined empirically. (not yet explored)