PaperlayerView exact revision on arXiv

Source-linked AI summary

Asymmetric numeral systems: entropy coding combining speed of Huffman coding with compression rate of arithmetic coding

Jarek Duda

arXiv:1311.2540v2cs.IT

TL;DR

ANS addresses the speed–compression trade-off between Huffman and arithmetic coding by using a single natural-number state and table-driven renormalization. The paper develops ANS variants and reports 50% faster decoding than fast Huffman coding for a 256-symbol alphabet, with nearly optimal compression. It also identifies keyed coding-table selection as a route to simultaneous encryption.

  • Problem

    Huffman coding is fast but approximates probabilities, whereas arithmetic coding approaches Shannon-rate compression at higher computational cost.

  • Method

    The paper develops ANS variants that use a single natural-number state and coding tables to represent symbol distributions and simplify renormalization.

  • Results

    50% faster decoding than fast Huffman coding was reported for a 256-symbol alphabet, with nearly optimal compression and a 1–16kB coding-table cost.

  • Takeaways & Limitations

    ANS provides a tabled large-alphabet entropy coder combining Huffman-like speed with arithmetic-coding-like compression, while keyed table choice can also encrypt encoded data.

  • Takeaways & Limitations

    The paper notes that the optimality of low-state entropy-coding automata and more convenient automaton families remain open questions.

Abstract

from arXiv · show

The modern data compression is mainly based on two approaches to entropy coding: Huffman (HC) and arithmetic/range coding (AC). The former is much faster, but approximates probabilities with powers of 2, usually leading to relatively low compression rates. The latter uses nearly exact probabilities - easily approaching theoretical compression rate limit (Shannon entropy), but at cost of much larger computational cost. Asymmetric numeral systems (ANS) is a new approach to accurate entropy coding, which allows to end this trade-off between speed and rate: the recent implementation [1] provides about $50\%$ faster decoding than HC for 256 size alphabet, with compression rate similar to provided by AC. This advantage is due to being simpler than AC: using single natural number as the state, instead of two to represent a range. Beside simplifying renormalization, it allows to put the entire behavior for given probability distribution into a relatively small table: defining entropy coding automaton. The memory cost of such table for 256 size alphabet is a few kilobytes. There is a large freedom while choosing a specific table - using pseudorandom number generator initialized with cryptographic key for this purpose allows to simultaneously encrypt the data. This article also introduces and discusses many other variants of this new entropy coding approach, which can provide direct alternatives for standard AC, for large alphabet range coding, or for approximated quasi arithmetic coding.

1 Introduction

ANS asymmetrizes numeral systems so symbol probabilities determine information content, combining accurate compression with simpler state handling and faster renormalization than arithmetic coding. Its tabled form achieves near-optimal compression while retaining Huffman-like speed and enables keyed coding-table choices for encryption.

  • Motivation: Standard numeral systems assign equal information to digits, whereas an event of probability p contains lg(1/p) bits; asymmetrization adapts coding to nonuniform distributions.Adding information in the most significant position yields AC-like range proportions, while adding it in the least significant position yields ANS-like density changes.
  • Motivation: Huffman coding approximates probabilities with powers of 1/2, and its convergence toward Shannon entropy is relatively slow without impractical symbol grouping.The supplied example reports ∆H ≈0.003 bits/symbol for 3^10 possibilities, while smaller ANS state counts can achieve lower losses in the cited cases.
  • ANS approach: ANS uses a single natural-number state, with coding rules of the form type (symbol, state) → (bit sequence, new state).Unlike AC’s range representation, ANS stores the evolving information in one state and redistributes even/odd-number densities according to symbol probabilities.
  • ANS approach: ANS renormalization transfers a determined block of least significant bits while returning the state to a fixed range, avoiding AC’s slower bit-extraction branches.For a 4-state example with Pr(a)=3/4 and Pr(b)=1/4, symbol b produces 2 bits while symbol a usually accumulates information before producing a bit.
  • Results: 50% faster decoding than fast Huffman coding was reported for a 256-symbol alphabet, with nearly optimal compression from a table requiring 1–16kB.The table’s entropy loss decreases approximately with the square of the number of states.
  • Applications: ANS coding tables can be selected with a cryptographically keyed pseudorandom process, providing simultaneous encryption of encoded data.The paper attributes this possibility to freedom in table choice and difficult state tracing without complete knowledge.

2 Basic concepts and versions

The paper formulates ANS as reversible transformations on natural-number states whose information grows by approximately lg(1/p) per symbol. It develops uniform and range-based variants, including large-alphabet rANS, trading some accuracy for simpler arithmetic and table-driven speed.

  • Basic concepts: ANS encoding maps a state x and symbol s to x′ ≈ x/p_s, so the state accumulates the symbol’s fractional information content.The corresponding inverse functions satisfy D(C(s,x))=(s,x) and C(D(x′))=x′.
  • Basic concepts: The general ANS construction partitions natural numbers into symbol-specific subsets with densities matching the target probabilities, then decodes by identifying each state’s subset.For a binary system, this generalizes even/odd splitting into unequal-density subsets.
  • uABS: The binary uABS construction chooses symbol counts near x·p_s, yielding |x_s−x p_s|<1 and average coding cost of Shannon entropy plus higher-order corrections.Because the approximation error decreases as 1/x while x grows exponentially, the total correction remains O(1) over the sequence.
  • Range variants: Range variants place symbol appearances in contiguous ranges, supporting large alphabets and requiring one multiplication per decoding step instead of two in Range Coding.With m chosen as a power of 2, multiplication and division can use shifts and the modulo operation can use a mask.
  • Range variants: rANS generalizes the range construction to probabilities represented as (l_0,…,l_n−1)/m and stores symbol parameters in tables.The tabled values l(x), b(x), and s(x) can reduce each step to one table-driven use.
  • Range variants: Range variants have an inaccuracy boundary m times larger than uABS, although sufficiently large states can make this error negligible.This accuracy–cost trade-off motivates their use as direct arithmetic-coding alternatives.

3 Stream version - encoding finite-state automaton

The stream version keeps the ANS state within a fixed interval by extracting least significant base-b digits as symbols are encoded. Decoding reverses this process, and b-unique intervals ensure the encoder and decoder remain inverse operations.

  • Stream algorithm: Stream ANS enforces x∈I={l,…,bl−1}, treating the state as a finite information buffer while complete digits are emitted to the stream.The encoder extracts digits until it can apply the symbol transformation; the decoder restores digits after applying the inverse transformation.
  • Stream algorithm: Digits may be extracted in any base b≥2, with b=2 yielding bits and b=2^k allowing k bits to be transferred at once.Removing a least significant digit maps x to floor(x/b), while mod(x,b) enters the bitstream.
  • Uniqueness: A b-unique interval guarantees that inserting or removing least significant digits reaches the operating interval in a unique way.This uniqueness is required for stream encoding and decoding to be exact inverses.
  • Direction: The decoder travels opposite the encoder through the stream, recovering symbols by applying D and then consuming digits until the state returns to the fixed interval.The schematic describes encoder motion to the right and decoder motion to the left.
  • Implementation: Coding tables can store the number of digits to transfer and perform the whole transfer as one unconditional operation rather than repeated branching.This table-driven operation is used in the fast implementation cited by the paper.

3.2 Example

The worked stream example shows how interval selection affects valid ANS operation and how stationary-state probabilities determine average coding cost. It also introduces construction conditions for unique stream decoding and table-based alternatives.

  • Example: For uABS with p=0.3 and l=8, the resulting symbol intervals are not b-unique, so encoding a symbol can leave the operating interval without reaching its designated range.For example, encoding s=1 from x=10 reduces the state from 10 to 5 and then 2.
  • Example: Choosing l=9 instead yields I={9,…,17}, I_0={6,…,11}, and I_1={3,4,5}, which are b-unique for the example.The encoder emits least significant bits until the state reaches the relevant symbol interval, then applies the ABS formula.
  • Performance: The stationary state distribution is used to calculate the expected number of bits per symbol for the automaton.The distribution is obtained from the transition process and compared with an approximately 1/x-shaped distribution.
  • Performance: 0.00529 bits/symbol is the example automaton’s excess over Shannon entropy, which is approximately 0.88129 bits/symbol.The reported comparison is for the p=0.3 binary example.
  • Validity conditions: For rABS and rANS, stream operation is supported when m divides l, while uABS requires its interval conditions to be checked separately.The paper states that m|l is a sufficient condition for the range variants in stream form.
  • Implementation trade-offs: Direct formulas can use large integer arithmetic with negligible inaccuracy at sufficiently large l, whereas table storage offers a faster but less accurate alternative.The direct approach can extract multiple digits at once but multiplication may make it somewhat slower.

3.4 Analysis of a single step

A single ANS stream step determines how many base-b digits to transfer from the current state and updates the state back into the fixed interval. When b does not divide l, decoding may require an extra digit and depends on digit order.

  • Encoding and decoding: The encoder transfers k = ⌊log_b(x/l_s)⌋ digits so the updated state returns to the symbol-specific range I_s = {l_s, …, b l_s−1}.The transferred value is mod(x, b^k), emitted in base b.
  • Encoding and decoding: For symbol s, the transfer count is either k_s−1 or k_s, with the threshold X_s = l b^k_s determining which states use each count.States below X_s use k_s−1 digits; states from X_s onward use k_s digits.
  • Encoding and decoding: During decoding, the current state identifies the produced symbol and often determines how many digits to consume.In the example, states 4, 5, 6, and 7 consume 1, 2, 0, and 0 digits respectively.
  • Decoding edge case: If b does not divide l, a state can require either k_s−1 or k_s digits because the first transfer may leave the state outside I.The state x = 13 example needs a second digit when the first digit is 0.
  • Decoding edge case: When b divides l, every state has a fixed transfer count; otherwise, digits must be consumed in reverse order from least to most significant.The supplied Figure 5 gives a concrete binary example with b = 2 and a final state of 79.

3.5 Stationary probability distribution of states

ANS state dynamics are analyzed through the informational coordinate y = log_b(x/l), where symbol shifts, digit transfers, and chaotic effects produce an approximately uniform stationary distribution. Transforming back gives state probabilities approximately proportional to 1/x.

  • Stationary distribution: The stationary state distribution is motivated by Pr(x) ∝ 1/x, matching the information content lg(x) assumed by ANS.This follows from analyzing the informational coordinate over the fixed state interval.
  • Informational coordinate: Encoding a symbol of probability p_s increases y by approximately log_b(1/p_s), while each transferred digit decreases y by approximately one.The stream step combines symbol-dependent information increases with renormalizing digit transfers.
  • Chaotic behavior: ANS states behave chaotically through asymmetry, ergodicity, and diffusion, unlike the neighboring, progressively compressed ranges of arithmetic coding.The three effects arise from unequal symbol shifts, typically irrational shifts, and position-dependent approximation error.
  • Stationary distribution: Numerical simulations support Pr(y ≤ a) ≈ a on [0, 1], which transforms into state usage approximately proportional to 1/x.This nearly uniform y distribution supplies the stationary-distribution interpretation for x.
  • Figures: Figure 6 presents the three chaotic effects in y, while Figure 7 relates ∆H to state-range size and rational approximations of symbol probabilities.Figure 7 also shows the fixed-l = 100 behavior across p = i/100, including ∆H = 0 at i = 50.

3.6 Bound for ∆H

The ∆H analysis bounds ANS capacity loss using an absolute error bound on state-symbol proportions. The resulting bound is approximate but captures the general behavior, with rANS incurring an additional factor m.

  • Error bound: The analysis bounds inaccuracy using |ϵ_s(x)| ≤ 1/x for uABS and m/x for rANS.This provides an independent absolute bound without requiring the exact stationary distribution.
  • Capacity loss: The coding penalty is expressed as a Kullback-Leibler distance when the coder uses q_s bits for symbols with true distribution p_s.In ANS, the relevant coding cost is lg(x/x_s) for symbol s.
  • Capacity loss: Because |ϵ_s(x)|^2 < 1/l^2 over I = {l, …, b l−1}, the expected uABS capacity loss can be bounded over that interval.The bound averages over encoder states conservatively through the general error bound.
  • Comparison with simulations: The bound is rough but reflects the general behavior observed in Figure 7; for rANS, it should be multiplied by m.The figure provides empirical context for the analytical estimate.

3.7 Initial state and direction of encoding/decoding

ANS encodes and decodes in reverse direction by default, requiring a final state for decoding, while same-direction operation is possible at substantially higher cost. Its precise initialization constructs coding tables by distributing symbol appearances according to target probabilities, though heuristic distributions are not always optimal.

  • Direction of encoding/decoding: Reversed-direction encoding and decoding suit stack-based symbol processing but can inconvenience applications and require storing the final encoding state.The final-state cost is usually negligible, at a few bits per data block.
  • Initial state: The initial state can absorb stored symbols, be generated by encoding from x = 1, or be supported by extending tables below the usual interval.These alternatives trade final-state storage against additional initialization or table memory.
  • Direction of encoding/decoding: Same-direction encoding or decoding is possible, but the paper characterizes it as much more costly than standard operation.Figure 8 illustrates searching possible states, symbols, digits, or paths to reverse the direction.
  • Precise initialization algorithm: Precise initialization distributes (b −1)l_s appearances of symbol s across I = {l, .., b^l −1}, then enumerates each symbol’s appearances.The construction uses symbol-specific ranges I_s = {l_s, .., b^l_s −1}.
  • Precise initialization algorithm: When tied symbol positions occur, experiments favor choosing the least probable symbol first, although the most probable-first rule can sometimes yield slightly smaller ∆H.The tie-breaking choice can therefore affect coding accuracy.

4.2 Inaccuracy bound

The paper derives an inaccuracy bound for heuristic symbol distributions and evaluates practical tANS behavior across alphabet sizes and random distributions. Simulations suggest that increasing the state count relative to alphabet size reduces ∆H approximately quadratically.

  • Analytic bound: The heuristic’s symbol sequence has period l, enabling analysis by imagining initialization at x = 0.The analysis defines approximation error as ϵ_s(x) = x_s/x − p_s.
  • Analytic bound: The derived bound is described as very rough when compared with numerical values and the formula in Figure 10.Figure 10 evaluates the bound for a three-symbol distribution and larger alphabets.
  • Practical behavior: ∆H ≈0.5/k^2 when the number of states is k times the alphabet size for practical random-distribution simulations.The simulations use tANS with state counts that are 2, 4, or 8 times alphabet size.
  • Practical behavior: For ∆H ≈0.01 bits/symbol, the paper suggests k = 2 or 4; for ∆H ≈0.001 bits/symbol, it suggests k = 8 or 16.These recommendations follow the observed relationship between state multiplicity and inaccuracy.
  • Scope of the analysis: The simulations do not include the additional approximation caused by l p_s usually being nonintegral.The paper notes that this approximation can shift results in either direction and motivates tuning the symbol distribution.

4.3 Quasi ABS (qABS) and tuning

qABS approximates quasi-arithmetic coding by switching among small ANS automata tuned to different probability ranges. The paper also studies how shifting symbol appearances changes the probabilities for which fixed coders are most accurate.

  • qABS: Five automata with five states can cover binary probability distributions at approximately ∆H ≈0.01 bits/symbol, while about 20 automata with 16 states target ∆H ≈0.001 bits/symbol.This switching strategy is presented as a qABS approximation.
  • Comparison with quasi-arithmetic coding: For static i.i.d. sources, the five-state ANS case matches the graph of a six-state Howard–Vitter quasi-arithmetic-coding example, although the comparison requires further investigation.The paper notes that ANS uses one fewer state for similar precision in this comparison.
  • Tuning: Shifting symbol appearances toward lower x generally shifts the optimal probability toward higher values.The paper relates lower x to increased x_s/x, the approximated symbol probability.
  • Tuning: For mismatched probabilities, initialization can be tuned by modifying initial N_s values, while exhaustive search can store optimized distributions for specific applications.The general behavior is described as complex and requiring further work.
  • Tuning: The distribution (000..01) yields a coder whose lowest optimal probability is near p = 0, using repeated state increments for the more probable symbol.This provides a simple coder for difficult low-probability cases.

4.4 Combining tANS with encryption

tANS can support simultaneous encryption by using pseudorandomly selected coding tables. Its variable-length blocks and chaotic state behavior are presented as obstacles to direct analysis, while table generation can be made more resistant to brute-force key testing.

  • Encryption mechanism: tANS encryption uses blocks whose lengths vary pseudorandomly, making direct division of the bitstream into single-step blocks difficult for cryptanalysis.This differs from standard cryptography’s constant-length bit blocks.
  • State behavior: ANS state behavior is chaotic because asymmetry makes neighboring states diverge, unlike arithmetic coding where nearby values remain nearby under further compression.Without the exact decoding tables, the current state is quickly difficult to determine.
  • Encryption mechanism: A cryptographic-key-initialized PRNG can choose or disturb the exact coding distribution, generating the table used for encoding and decoding.ANS permits many different codings because each symbol distribution defines a different encoding.
  • Keyed table generation: Making table generation more computationally demanding can increase resistance to brute-force attacks that test successive keys by attempting decryption.The encryption philosophy shifts computational effort into keyed table generation.

5 CONCLUSIONS

ANS provides a simpler alternative to arithmetic coding, enabling fast block-based renormalization, tabled large-alphabet coding, and optional encryption, while retaining practical compression advantages. The approach still requires coding tables and leaves open questions about table generation, theory, and cryptographic security.

  • ANS uses a single natural-number state instead of arithmetic coding’s two-number range representation.
  • Known-size bit blocks can replace complex arithmetic-coding renormalization and be transferred once per symbol.
  • tANS stores large-alphabet coding behavior in tables, combining Huffman-like speed with arithmetic-coding-like compression rates.For a 256-symbol alphabet, coding tables require about 1–16kB.
  • ANS’s flexible, chaotic coding behavior supports simultaneous encryption and inexpensive nonlinear cryptographic building blocks.PRNG-selected tables and variable-length blocks are described as cryptographic mechanisms.
  • Maintaining one state space allows switching among probability distributions, alphabets, variants, and multiple context-specific coding tables.Memory cost grows to a few kilobytes times the number of tables or contexts.
  • Open research questions include effective tANS table generation, correlated-source analysis, theoretical understanding, and achieving required cryptographic security.
Loading 1311.2540v2…