3Asymmetric Numeral Systems (ANS) is a family of entropy coding methods used in data compression. It was invented by Jarek Duda.
5- [arXiv preprint, 2013](https://arxiv.org/abs/1311.2540)
6- [IEEE Paper, 2015](https://ieeexplore.ieee.org/abstract/document/7170048)
8For 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.
10The [simple_ans](https://github.com/flatironinstitute/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.
12## Explanation of ANS
14The 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.
cbff9a2update layout, etcJeremy Magland 16Suppose 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$.
18We assume that the symbols are sampled randomly and independently of one another. Let
20$$
21L = \sum_{i=0}^{S-1} f_i
22$$
24be the sum of the symbol frequencies.
26### The Symbol Table
27To 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\}$
29We construct this table with a periodic pattern where:
30- Each period of length $L$ consists of consecutive blocks:
31 * $f_0$ occurrences of symbol 0 (or A)
32 * $f_1$ occurrences of symbol 1 (or B)
33 * ...
34 * $f_{S-1}$ occurrences of symbol $S-1$
35- This pattern repeats every $L$ positions
36- For any position $n$, $T(n) = T(n \text{ mod } L)$
37- Define $C_s = \sum_{i=0}^{s-1} f_i$ as the cumulative frequency (start position of symbol $s$ in each period)
41The encoding process works by maintaining a state value $x$ that evolves as we process each symbol. Starting from state $x_0$:
431. To encode symbol $s_1$:
44 - Find the $x_0$-th occurrence of symbol $s_1$ (counting from 0)
45 - This position index becomes our new state $x_1$
462. Repeat this process for each new symbol, using the previous state to find the next one
48This process effectively "pushes" each symbol onto our state value in a way that can be reversed.
50With the periodic structured table, the formula for this is
52$$x_{i+1} = (x_i // f_{s_i}) \cdot L + C(s_i) + (x_i \text{ mod } f_{s_i})$$
54where $//$ denotes integer division and $\text{ mod }$ is the modulo operation.
56Notice that for large $x_i$,
58$$x_{i+1} \approx x_i \cdot p_s^{-1}$$
60where $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:
62$$\lim_{k \to \infty} E(\frac{1}{k}\log(x_k)) = -\sum_{s=0}^{S-1} p_s \log(p_s).$$
64Or in other words, if $H$ is the average number of bits required to encode a single symbol in the sequence, then
66$$H = -\sum_{s=0}^{S-1} p_s \log(p_s)$$
68which 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.
72Given a final state $x_k$, we can recover the original sequence as follows:
741. The last symbol $s_k$ is simply $T[x_k]$ (the symbol at position $x_k$)
752. To get the previous state $x_{k-1}$:
76 - Count how many times $s_k$ appeared before position $x_k$
77 - This count is our previous state $x_{k-1}$
783. Continue this process to recover all symbols in reverse order
80The formula for this decoding is
82$$x_i = (x_{i+1} // L) \cdot f_{s_i} + (x_{i+1} \text{ mod } L) - C(s_i)$$
86This 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.
90### The Need for Bounded State
91In 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.
93### Word-Based Streaming with Conditional Normalization
94Instead 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.
96Let $W$ be an array of 32-bit words, initialized to empty. We define:
97- `STATE_BITS = 64` (total bits for state)
98- `WORD_BITS = 32` (bits per output word)
99- `THRESHOLD = 2^32` (minimum state value after normalization)
101For efficiency of calculations we assume that $L$ is a power of 2:
103$$
104L = 2^{l}
105$$
107### Encoding Process
108When encoding symbol $s$ with current state $x$:
1101. **Check for normalization**: If $(x >> (64 - l)) \geq f_s$, then:
111 - Extract the lower 32 bits: $w = x \text{ mod } 2^{32}$
112 - Append $w$ to word array $W$
113 - Update state: $x = x >> 32$
1152. **Encode the symbol**:
116 - Compute: $remainder = x \text{ mod } f_s$
117 - Compute: $prefix = x // f_s$
118 - Update state: $x = (prefix << l) | (C_s + remainder)$
120The key insight is that normalization only occurs when the next encoding step would cause overflow, making the algorithm more efficient.
122### Decoding Process
123To decode from final state $x$ and word array $W$:
1251. **Extract symbol**:
126 - $quantile = x \text{ mod } L$
127 - Find symbol $s$ such that $C_s \leq quantile < C_s + f_s$
1292. **Compute previous state**:
130 - $prefix = x >> l$
131 - $previous\_state = prefix \cdot f_s + (quantile - C_s)$
1333. **Check for denormalization**: If $previous\_state < THRESHOLD$ and words remain:
134 - Pop word $w$ from end of $W$
135 - Update: $previous\_state = (previous\_state << 32) | w$
1374. **Continue**: Set $x = previous\_state$ and repeat
139This approach maintains the state above the threshold while efficiently managing memory by streaming out words only when necessary.
141## Optimality of the Compression
143In the above, there are two sources of loss in the compression efficiency:
1441. The assumption that the frequencies sum to a power of two
1452. The need to normalize the state
147The 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.
1f5f0efupdate .mdJeremy Magland 149The second source of loss is more difficult to predict but can be examined empirically. (not yet explored)