Wolfram Cloud Document

MAIN ARTICLE: Jarek Duda, https://en.wikipedia.org/wiki/Asymmetric_numeral_systems
DEMONSTRATION: Jarek Duda, Data Compression Using Asymmetric Numeral Systems, Wolfram Demonstrations Project. https://demonstrations.wolfram.com/DataCompressionUsingAsymmetricNumeralSystems/

Abstract: Numeral systems went a long way, from among others Babylonian, Chinese, Egyptian, Roman numbers, up to the modern dominance of decimal system for humans, and binary for computers. It is not over yet - in recent years data in our computers is more and more frequently written with asymmetric numeral systems (ANS) - optimized for nonuniform probability distributions of digits/symbols, what is exploited by entropy coders e.g. at heart of data compressors.
Since 2014 ANS replaces Huffman and arithmetic coding thanks to combining their advantages. Among others (long list), ANS is used by very popular Facebook Zstandard (zstd) compressor widely replacing ‘zip’ (3-5x faster, much better compression) e.g. in Linux kernel, in Apple LZFSE compressor - default in iPhones and Macs, Google Draco 3D compressor used e.g. by Pixar, CRAM - nearly default DNA compressor, Microsoft DirectStorage BCPack texture compressor for games. Also by JPEG XL: finally the long-term replacement of 1992 JPEG image format, already supported e.g. by Apple devices.

Standard numeral systems like binary (2) or decimal (10) are optimal for uniform probability distributions of digits. However, real data is usually from non-uniform distributions - asymmetric numeral systems (ANS) is generalization optimized for this purpose, used e.g. in data compression for savings in storage and transmission. It has developed into a popular family of methods (

[3]

) - started in my physics MSc 2006

[1]

(together with Maximal Entropy Random Walk - introduction) with variant now called uABS (uniform binary). Then in 2007 a later version of this article has started tANS variant (tabled numeral) - used e.g. by Facebook Zstandard (zstd) and Apple LZFSE compressors. Later in 2013

[3]

it lead to rANS variant (range numeral) - used e.g. by JPEG XL, CRAM DNA compressor, and neural network based compressors. This article briefly introduces to them including basic Mathematica code, using slides from here (recorded talk). Here is a long list of materials/implementations, compressors. Below slide shows a summary of the most popular ANS-based compressors, with companies/products using zstd from http://facebook.github.io/zstd/ :

Its popularity comes from combining advantages of Huffman coding (fast but suboptimal: works on full bits) and arithmetic coding (optimal but slow, can handle fractional bits) - ANS allows for extremely fast and still nearly optimal implementations handling fractional bits:

The difficulty of its task (called entropy coding) is that the less frequent an event/symbol, the more bits of information it carries. Turns out ideally, symbol of probability p carries lg(1/p) bits (

lg≡

log

). Averaging over symbols, it means on average

HE[lg(1/p)]

∑

lg(1/

)

bits/symbol - called Shannon entropy, being the theoretical bound we would like to approach with entropy coders. For example 50% probability symbol carries 1 bit, 2 bits for 25% and so on. For such power-of-2 probabilities we can directly transform symbols into bits e.g. A -> 0, B -> 10, C->11, what is done e.g. in prefix codes like popular Huffman coding - finding an optimal prefix code. Thanks to simplicity it was very popular in the old compressors like zip/gzip, JPEG, PNG, GIF, MP3. However, probabilities are not always powers-of-2, e.g. digit in decimal system carries

lg(10)≈3.32

bits of information. Event/symbol of probability 0.99 would carry only

lg(1/0.99)≈0.0014

bits, while e.g. Huffman would need to use 1 bit for it - what is extremely inoptimal. To repair it, we would literally have to handle fractional bits - cannot just directly transform symbols into bits. Instead, there is used some kind of buffer allowing to accumulate fractional bits, finally releasing encoded data in chunks of full bits. The standard method is arithmetic coding using a range as this buffer, represented by two numbers - e.g. start and width of this range. This range is split into subranges of lengths proportional to the assumed probability distribution, encoding a symbol transforms range into the corresponding subrange. In contrast to buffer as two numbers, the advantage of ANS is using a single natural number instead:

x∈N

imagined to contain

lg(x)

bits of information. Working on state as a single number allows for much faster implementations: there is a smaller number of operations, also it is much more convenient for vectorization - e.g. SIMD for CPU or GPU. However, while arithmetic coding is FIFO: first-in-first out allowing to decode in the same direction, ANS rather requires LIFO - decoding in the opposite direction, like stack. This inconvenience is usually resolved by encoding in backward direction, what allows to decode forward. Here is a brief history with examples of Huffman, arithmetic coding and ANS:

ANS basics, uABS uniform binary variant, renormalization

Let us now get into the basics of ANS. Imagining

x∈N

contains

lg(x)

bits of information, and knowing that symbol of probability p carries

lg(1/p)

bits, to encode both into a new state:

′

C(s,x)

, we should have:

lg(

′

)≈lg(x)+lg(1/p)lg(x/p)

, hence we should transform x into approximately x/p. While such

C(s,x)≈x/p

defines encoding step, we also need decoding function D to invert it:

D(C(s,x))(s,x)

. For standard binary numeral system we can use

C(s,x)2x+s

encoding for

s∈{0,1}

digit/symbols, for which decoding is

D(s,x)(xmod2,⌊x/2⌋)

. This encoding can be viewed as: C(s,x) = x-th appearance of symbol s, here: of even numbers for s=0 (

x2x

), odd for s=1 (

x2x+1

). We can generalize it by just redefining the above uniform split into even/odd numbers, to a nonuniform split - with densities in agreement with the assumed probability distribution. For this purpose define symbol spread as

:NA

function specifying such split, e.g.

(x) mod(x,2)

for binary system splitting into even/odd numbers,

(x) mod(x,b)

for base b numeral system - splitting into subsets of fixed last digit. To generalize it to nonuniform distributions, we would like still a nearly uniform split, but with densities as in the assumed probability distributions. Specifically, for a symbol s of probability p, we would like

:#{y<x:

s}≈x

. This way decoding step is

D(x)(

(x),

)

and encoding as above “x-th appearance of symbol s” can be formalized as:

C(x,s)

′

s,

#{y<

′

s}x

. In practice these encoding/decoding functions can be defined with a formula (e.g. binary uABS and general rANS variants), or generally it can be just put into generated tables (tANS) defining a finite state automaton optimized to transcribe sequence of a chosen probability distribution. Let us start with historically the first

[1]

uABS (uniform binary) variant for binary alphabet (

A{0,1}

) with p=Pr(1) assumed probability of ‘1’ (Pr(0)=1-p). To make that among {0, ..., x-1} positions there are

≈xp

appearances of

corresponding to symbol ‘1’ (marked gray in table below), we can define it is exactly e.g. ceiling of

, this way jumps of this ceiling describe symbol spread:

(x)⌈(x+1)p⌉-⌈xp⌉

. It defines decoding function, for which we can derive

[1]

encoding functions - leading to the formulas below.

Below these formulas can be tested - the code generates length len sequence with Pr(1)=q, encodes it using C(s,x) for succeeding symbols in backward direction (starting from x=1), then decodes allowing to visually confirm that it indeed returns to the original sequence. The parts directly corresponding to encoding/decoding are marked with color. It also tests the issue of not knowing the real probability distribution (Pr(1)=q) - that entropy coder is optimized for some usually different distribution (Pr(1)=p). This way instead of

H

∑

lg(1/

)

Shannon entropy bits/symbol, we use

′



∑

lg(1/

)

cross entropy - minimized for accurate



. Their difference

ΔH

′

-H

is the cost of approximating q with p in mean bits/symbol, referred as Kullback-Leibler divergence. For example prefix codes like Huffman are restricted to assuming probabilities

(

)

being natural powers of 1/2.

In[]:=

(*uABSbasicencodinganddecodingsteps:*)c[s_,x_]:=If[s==0,Ceiling[(x+1)/(1-p)]-1,Floor[x/p]];d[x_]:={s=Ceiling[(x+1)p]-Ceiling[x*p],If[s==1,Ceiling[x*p],x-Ceiling[x*p]]};xs={};q=0.1;len=100;(*generatedPr(1),itslength*)p=q;data=Floor[RandomReal[{0,1},len]+p];(*generate*)Print["Pr(1)=p=",p," data: ",Row[data]];Do[x=1;Do[x=c[s,x],{s,Reverse[data]}];(*encode*)Print["assuming p=",p+0.," encoded into x = ",Style[x,Bold]];AppendTo[xs,{p,Log[2,x]/len}];dec={};While[x>1,{s,x}=d[x];AppendTo[dec,s]];(*decode*)Print["decoded into: ",Row[dec]],{p,1/10,5/10,1/10}];Show[ListPlot[xs,PlotLabel->"points: lg(x)/length bits for above, curve: cross-entropy "],Plot[-q*Log[2,p]-(1-q)Log[2,1-p],{p,0,0.5}]]

Formula for large alphabet: rANS range variants

Below is analogously with added base b renormalization:

Tabled variants: tANS

References

[1] J. Duda, Optimal encoding on discrete lattice with translational invariant constrains using statistical algorithms, arXiv:0710.3861 (2007, translation of 2006 MSc thesis)

[2] J. Duda, Asymmetric numeral systems, arXiv:0902.0271, PhD thesis (2009)

[3] J. Duda, Asymmetric numeral systems: entropy coding combining speed of Huffman coding with compression rate of arithmetic coding, arXiv:1311.2540 (2013)

[4] J. Duda, N. Gadgil, K. Tahboud, E. J. Delp, The use of Asymmetric Numeral Systems as an accurate replacement for Huffman coding, PCS 2015 (2015)

[5] J. Duda, M. Niemiec, Lightweight compression with encryption based on Asymmetric Numeral Systems, arXiv:1612.04662 (2016), AMCS vol 33 (2023)

[6] J. Duda, Encoding of probability distributions for Asymmetric Numeral Systems, arXiv:2106.06438 (2021)

[7] S. Camtepe, J. Duda, A. Mahboubi, P. Morawiecki, S. Nepal, M. Pawłowski, J. Pieprzyk, Compcrypt – Lightweight ANS-based Compression and Encryption, https://eprint.iacr.org/2021/010, IEEE Transactions on Information Forensics & Security (2021)

[8] S. Camtepe, J. Duda, A. Mahboubi, P. Morawiecki, S. Nepal, M. Pawłowski, J. Pieprzyk, ANS-based Compression and Encryption with 128-bit Security, https://eprint.iacr.org/2021/900 (2021), International Journal of Information Security (2022)

[9] J. Pieprzyk, J. Duda, M. Pawlowski, S. Camtepe, A. Mahboubi, P. Morawiecki, Compression Optimality of Asymmetric Numeral Systems, arXiv:2209.02228, Entropy (2023),

CITE THIS NOTEBOOK

Data Compression Using Asymmetric Numeral Systems
by Jarek Duda
Wolfram Community, STAFF PICKS, September 28, 2023
https://community.wolfram.com/groups/-/m/t/3023601