Asymmetric Numeral Systems (ANS) sind eine Familie von Entropiekodierungs-Verfahren, die Jarosław (Jarek) Duda von der Jagiellonen-Universität Krakau entwickelte und 2014 auf der Data Compression Conference vorstellte. ANS verbindet die Kompressionsrate der arithmetischen Kodierung — also die Nähe zur Entropiegrenze — mit der Geschwindigkeit der Huffman-Codierung, die mit einfachen Tabellenoperationen arbeitet. Die Abkürzung ANS steht für den Familiennamen; die Verfahren sind patentfrei publiziert.
Idee
Statt Symbole über ein Intervall zu kodieren, hält ANS einen Zustand in Form einer natürlichen Zahl x. Jedes Symbol s wird durch eine Umformung x' = C(x, s) in diesen Zustand hineingemischt. Beim Dekodieren wird das Symbol aus x extrahiert und der Zustand rückgängig gemacht. Die Asymmetrie entsteht dadurch, dass jedes Symbol einen eigenen Zahlenbereich beansprucht, dessen Größe seiner Wahrscheinlichkeit entspricht — ähnlich den Ziffern eines Zahlensystems mit symbolabhängigen Basen. Dadurch entstehen im Mittel Bruchteilsbits pro Symbol, ohne dass ein Intervall mit wachsender Präzision verwaltet werden muss.
Varianten
- rANS: range-basierte Variante, gut für Streaming und parallele Verarbeitung
- tANS: tabellenbasierte Variante mit endlichen Zuständen; Grundlage von FSE (Finite State Entropy), das Yann Collet für Zstandard entwickelte
Einsatzgebiete
- Zstandard (zstd): Kompressionsformat von Facebook/Meta, nutzt FSE als Entropiestufe
- JPEG XL: modernes Bildformat mit ANS-basierter Entropiekodierung
- LZFSE von Apple sowie Genomik-Formate wie CRAM
Der Range Coder als Ganzzahl-Form der arithmetischen Kodierung bleibt in LZMA und CABAC verbreitet; ANS hat sich vor allem dort durchgesetzt, wo hoher Durchsatz und gute Kompression gleichzeitig gefordert sind.
Verwandte Grundlagen: Datenkompression, verlustfreie Kompression, LZ77.