  Compression also known as entropy coding has a rich and long history.
However, a recent explosion of multimedia Internet applications (such as
teleconferencing and video streaming for instance) renews an interest in fast
compression that also squeezes out as much redundancy as possible. In 2009
Jarek Duda invented his asymmetric numeral system (ANS). Apart from a beautiful
mathematical structure, it is very efficient and offers compression with a very
low residual redundancy. ANS works well for any symbol source statistics.
Besides, ANS has become a preferred compression algorithm in the IT industry.
However, designing ANS instance requires a random selection of its symbol
spread function. Consequently, each ANS instance offers compression with a
slightly different compression rate.
  The paper investigates compression optimality of ANS. It shows that ANS is
optimal (i.e. the entropies of encoding and source are equal) for any symbol
sources whose probability distribution is described by natural powers of 1/2.
We use Markov chains to calculate ANS state probabilities. This allows us to
determine ANS compression rate precisely. We present two algorithms for finding
ANS instances with high compression rates. The first explores state probability
approximations in order to choose ANS instances with better compression rates.
The second algorithm is a probabilistic one. It finds ANS instances, whose
compression rate can be made as close to the best rate as required. This is
done at the expense of the number $\theta$ of internal random ``coin'' tosses.
The algorithm complexity is ${\cal O}(\theta L^3)$, where $L$ is the number of
ANS states. The complexity can be reduced to ${\cal O}(\theta L\log{L})$ if we
use a fast matrix inversion. If the algorithm is implemented on quantum
computer, its complexity becomes ${\cal O}(\theta (\log{L})^3)$.
