1## Explanation of Asymmetric Numeral Systems (ANS)
3The 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.
5Suppose that $\{0, 1, ..., S-1\}$ are the symbols we want to encode (in this UI 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$.
7We assume that the symbols are sampled randomly and independently of one another. Let
9$$
10L = \sum_{i=0}^{S-1} f_i
11$$
13be the sum of the symbol frequencies.
15## ANS Encoding/Decoding
17### The Symbol Table
18To 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\}$
20We construct this table with a periodic pattern where:
21- Each period of length $L$ consists of consecutive blocks:
22 * $f_0$ occurrences of symbol 0 (or A)
23 * $f_1$ occurrences of symbol 1 (or B)
24 * ...
25 * $f_{S-1}$ occurrences of symbol $S-1$
26- This pattern repeats every $L$ positions
27- For any position $n$, $T(n) = T(n \text{ mod } L)$
28- Define $C_s = \sum_{i=0}^{s-1} f_i$ as the cumulative frequency (start position of symbol $s$ in each period)
30### The Encoding/Decoding Process
32The encoding process works by maintaining a state value $x$ that evolves as we process each symbol. Starting from state $x_0$:
341. To encode symbol $s_1$:
35 - Find the $x_0$-th occurrence of symbol $s_1$ (counting from 0)
36 - This position index becomes our new state $x_1$
372. Repeat this process for each new symbol, using the previous state to find the next one
39This process effectively "pushes" each symbol onto our state value in a way that can be reversed.
41With the periodic structured table, the formula for this is
43$$x_{i+1} = (x_i // f_{s_i}) \cdot L + C(s_i) + (x_i \text{ mod } f_{s_i})$$
45where $//$ denotes integer division and $\text{ mod }$ is the modulo operation.
47Notice that for large $x_i$,
49$$x_{i+1} \approx x_i \cdot p_s^{-1}$$
51where $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:
53$$\lim_{k \to \infty} E(\frac{1}{k}\log(x_k)) = -\sum_{s=0}^{S-1} p_s \log(p_s).$$
55Or in other words, if $H$ is the average number of bits required to encode a single symbol in the sequence, then
57$$H = -\sum_{s=0}^{S-1} p_s \log(p_s)$$
59which 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.
61**Now for decoding.** Given a final state $x_k$, we can recover the original sequence as follows:
631. The last symbol $s_k$ is simply $T[x_k]$ (the symbol at position $x_k$)
642. To get the previous state $x_{k-1}$:
65 - Count how many times $s_k$ appeared before position $x_k$
66 - This count is our previous state $x_{k-1}$
673. Continue this process to recover all symbols in reverse order
69The formula for this decoding is
71$$x_i = (x_{i+1} // L) \cdot f_{s_i} + (x_{i+1} \text{ mod } L) - C(s_i)$$
73## Practical ANS Implementation
75### The Need for Bounded State
76In 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.
78### Word-Based Streaming with Conditional Normalization
79Instead 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.
81Let $W$ be an array of 32-bit words, initialized to empty. We define:
82- `STATE_BITS = 64` (total bits for state)
83- `WORD_BITS = 32` (bits per output word)
84- `THRESHOLD = 2^32` (minimum state value after normalization)
86For efficiency of calculations we assume that $L$ is a power of 2:
88$$
89L = 2^{l}
90$$
92### Encoding Process
93When encoding symbol $s$ with current state $x$:
951. **Check for normalization**: If $(x >> (64 - l)) \geq f_s$, then:
96 - Extract the lower 32 bits: $w = x \text{ mod } 2^{32}$
97 - Append $w$ to word array $W$
98 - Update state: $x = x >> 32$
1002. **Encode the symbol**:
101 - Compute: $remainder = x \text{ mod } f_s$
102 - Compute: $prefix = x // f_s$
103 - Update state: $x = (prefix << l) | (C_s + remainder)$
105The key insight is that normalization only occurs when the next encoding step would cause overflow, making the algorithm more efficient.
107### Decoding Process
108To decode from final state $x$ and word array $W$:
1101. **Extract symbol**:
111 - $quantile = x \text{ mod } L$
112 - Find symbol $s$ such that $C_s \leq quantile < C_s + f_s$
1142. **Compute previous state**:
115 - $prefix = x >> l$
116 - $previous\_state = prefix \cdot f_s + (quantile - C_s)$
1183. **Check for denormalization**: If $previous\_state < THRESHOLD$ and words remain:
119 - Pop word $w$ from end of $W$
120 - Update: $previous\_state = (previous\_state << 32) | w$
1224. **Continue**: Set $x = previous\_state$ and repeat
124This approach maintains the state above the threshold while efficiently managing memory by streaming out words only when necessary.
126## Optimality of the Compression
128In the above, there are two sources of loss in the compression efficiency:
1291. The assumption that the frequencies sum to a power of two
1302. The need to normalize the state
132The 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.
134The second source of loss is more difficult to predict but can be examined empirically. (not yet explored)
136[Source code for the ANS Visualizer](https://github.com/magland/ans-visualizer)
138[simple_ans: A simple and efficient Python implementation of ANS](https://github.com/flatironinstitute/simple_ans)