Asymmetric numeral systems, review of advances in entropy coding

Abstract

This thesis explores the advances in entropy coding, primarily focusing on asymmetric numeral systems introduced by Jarek Duda. The goal of entropy coding is to compress messages by exploiting redundancy in unequal symbol distributions. For example, the letter “e” occurs 60 times more often in English text than “z”, meaning that encoding either in the same space is immensely wasteful. There exists an intrinsic informational content in a message which determines the shortest message required to transmit that information, which entropy coding aims to reach.

Before asymmetric numeral systems, there have been two widely used entropy coding methods: Huffman coding and arithmetic coding. Huffman coding can be decoded very efficiently but it cannot reach the lower bound. Arithmetic coding is nearly optimal, but slower to decode. Asymmetric numeral systems aim to provide the accuracy of arithmetic coding, while retaining the performant decoding of Huffman coding.

The thesis is primarily a review of existing literature, but it also contains some experimental work to analyze the properties of various entropy coding systems. The work also contains some survey of literature apart from publications, as many significant advances in entropy coding have occurred outside academia.

The research indicated that asymmetric numeral systems are currently the best choice for many, if not most, entropy coding use cases. Many implementation concerns and advances in implementation are considered in the thesis. As such, this work should serve as a solid starting point for understanding and implementing modern and efficient entropy coders.

Entropiakoodaus on oleellinen osa tiedon pakkausta: lähes kaikki käytännön pakkausmuodot (esim. zip, mp3 tai jpg) sisältävät entropiakoodausvaiheen toteutuksissaan. Entropiakoodaus perustuu informaatioteoreettiseen tulokseen, jonka mukaan viestejä voi pakata vain tiettyyn alarajaan asti menettämättä tietoa. Kaksi yleisintä entropiakoodausmenetelmää ovat Huffmanin koodaus sekä aritmeettinen koodaus. Huffmanin koodaus on mahdollista purkaa hyvin tehokkaasti, mutta sitä käyttämällä ei voi saavuttaa optimaalista koodauspituutta useissa tapauksissa. Aritmeettinen koodaus puolestaan pääsee hyvin lähelle pakatun koon raja-arvoa, mutta siten koodattuja viestejä on hitaampi purkaa. Tämä kandidaatintyö tutkii uutta vaihtoehtoista menetelmää: epäsymmetrisiä lukujärjestelmiä (engl. asymmetric numeral system, ANS). Jarek Dudan kehittämien epäsymmetristen lukujärjestelmien väitetään kykenevän saavuttamaan aritmeettisen koodauksen tarkkuuden Huffmanin koodauksen tehokkuudella. Tutkielmassa tarkastellaan etenkin epäsymmetristen lukujärjestelmien rANS- sekä tANS-variantteja, jotka ovat lupaavimmat käytännön tarkoituksiin.

Työ on suoritettu suurimmalta osin kirjallisuustutkimuksena. Materiaalina on käytetty artikkeleita, joissa entropiakoodaus ja tekniikat ovat alun perin esitelty. Lisäksi materiaaliin sisältyy laajasti tutkimuksia tekniikoiden jatkokehityksestä sekä niiden ominaisuuksien analysoinnista. Työssä on otettu myös huomioon keskeisiä akateemisen maailman ulkopuolisia lähteitä, sillä suuri osa innovaatiosta entropiakoodauksessa tapahtuu sen ulkopuolella. Monet työssä esitellyt algoritmit ovat myös toteutettu ohjelmallisesti itsenäistä analysointia varten. Tutkimus myös sisältää katsauksen tANS-koodausta käyttävään FiniteStateEntropy-kodeekkiin ja sen suorituskykyyn Huffman-koodaukseen verrattuna.

Tutkimus varmistaa väitteen epäsymmetristen lukujärjestelmien lupaavasta tarkkuudesta. Algoritmien toteutuksista paljastui rakenteita vaihtoehtoisen tANS-alustusalgoritmien suhteellisessa tarkkuudessa, joista voi olla hyötyä uusien alustusalgoritmien kehityksessä. Kirjallisuuskatsauksesta selvisi, että epäsymmetristen lukujärjestelmien rANS-variantin on todistettu saavuttavan asymptoottisesti optimaalisen koodauksen, mutta käytännön epätarkkuuden ylärajan tarkasti määrittäminen on yhä avoin ongelma.

Tutkimus osoittaa, että epäsymmetriset lukujärjestelmät ovat tällä hetkellä paras valinta suureen osaan entropiakoodaustarpeista. Huffmanin koodaus on yhä laskennallisesti tehokkain vaihtoehto ja aritmeettinen koodaus on luontevampi adaptiivisiin tarkoituksiin. Kandidaatintutkielma toimii myös lähestyttävänä lähteenä epäsymmetrisiin lukujärjestelmiin ja voi siten helpottaa niiden käyttöönottoa.