Fast and Exact: Asymptotically Linear KL-Optimal Frequency Normalization

1. Probleemstelling

Bij entropiecodering (Range Coding, ANS, rANS) moeten reëelwaardige kansverdelingen worden omgezet in geheeltallige frequenties die optellen tot een vaste doelwaarde $M$ (vaak een macht van twee, $2^k$) om efficiënte bit-shift-operaties tijdens codering en decodering mogelijk te maken.

Het kernoptimalisatieprobleem is het vinden van geheeltallige frequenties $m_a$ voor elk symbool $a$ zodat:

1. $\sum m_a = M$
2. $m_a \ge 1$ voor alle symbolen met niet-nul empirische tellingen.
3. De Kullback-Leibler (KL)-divergentie tussen de empirische verdeling $p$ en de gekwantiseerde verdeling $q$ ($q_a = m_a/M$) wordt geminimaliseerd.

Het minimaliseren van $D(p \parallel q)$ is equivalent aan het minimaliseren van de verwachte redundantie per symbool (in nat of bits) die wordt gemaakt door het geheeltallige model $q$ te gebruiken om een bron te coderen die gegenereerd wordt door $p$.

De Uitdaging:
Bestaande snelle normalisatiemethoden die in productie-codecs worden gebruikt (zoals Giesen's cumulatieve herschaling, Bloom's geometrisch-gemiddelde afronding, Collet's FSE-normalisatie) zijn heuristisch. Hoewel ze draaien in $O(r)$ of $O(r \log r)$ tijd, garanderen ze niet het globale KL-optimum. Ze vertrouwen vaak op:

• Volgorde-afhankelijke afrondingsfouten.
• Eendirectionele aanpassingen (alleen verhogen of alleen verlagen van frequenties).
• Initialisatie-heuristieken die "onder" het ware optimum kunnen landen, waardoor herstel onmogelijk wordt voor decrement-only algoritmen.

Het paper adresseert de behoefte aan een algoritme dat zowel wiskundig exact is (garandeert het globale KL-minimum te vinden) als snel genoeg om op het "hot path" van een entropiecoder te zitten.

---

2. Methodologie & Theoretische Grondslag

Het paper stelt vast dat het probleem een separabel concave integer allocation probleem is. Het globale optimum wordt gekenmerkt door een marginaal-uitwisselingsvoorwaarde (Lemma 1):
Een frequentievector $m$ is optimaal dan en slechts dan als de minimale kosten van het verwijderen van een eenheid van elk symbool (decrement ticket $\Delta^-$) groter dan of gelijk is aan de maximale winst van het toevoegen van een eenheid aan elk symbool (increment ticket $\Delta^+$).

$$\min_{a: m_a \ge 2} \Delta^-_a(m_a) \ge \max_{b} \Delta^+_b(m_b)$$

Waarbij:

• $\Delta^+_a(j) = c_a \log(\frac{j+1}{j})$ (Winst van het verhogen van telling $j \to j+1$)
• $\Delta^-_a(j) = c_a \log(\frac{j}{j-1})$ (Verlies van het verlagen van telling $j \to j-1$)

De auteur stelt drie exacte algoritmen voor die worden gedreven door dit principe van marginale tickets, met afwegingen tussen eenvoud, asymptotische complexiteit en implementatie-overhead.

Algoritme 1: Bottom-Up Archetype

• Benadering: Start met de minimaal haalbare toewijzing ($m_a=1$ voor alle actieve symbolen) en voegt gretig $M-r$ eenheden toe aan het symbool dat de hoogste marginale winst biedt ($\Delta^+$).
• Mechanisme: Gebruikt een max-heap om de volgende beschikbare winst voor elk symbool bij te houden.
• Complexiteit: $O(M \log r)$.
• Voordelen: Eenvoudigste bewijs van optimaliteit; geen aannames over omhulsels vereist.
• Nadelen: Te traag voor praktisch gebruik wanneer $M \gg r$ (typisch bij entropiecodering waar $M=2^{14}$ tot $2^{20}$).

Algoritme 2: Bidirectionele Bloom Reparatie

• Benadering: Een exacte correctie van Bloom's heuristiek. Het start met Bloom's geometrisch-gemiddelde initialisatie. Als de som niet $M$ is, voert het een bidirectionele uitwisseling uit.
• Mechanisme:
  1. Past de totale som aan tot $M$ met behulp van een eendirectionele heap (als som $>M$, decrement; als som $<M$, increment).
  2. Cruciaal Stap: Zodra de som $M$ is, gaat het een "Fase 2" uitwisselingslus in. Het wisselt herhaaldelijk een eenheid om van het symbool met de laagste decrementkosten naar het symbool met de hoogste incrementwinst, mits de winst de kosten overtreft.
• Complexiteit: $O(M \log r)$ in het slechtste geval, maar $O(r \log r)$ op "vriendelijke" invoer waarbij de initialisatie dicht bij het optimum ligt.
• Betekenis: Repareert de fout in Bloom's originele algoritme waarbij een eendirectionele correctie faalt als de initialisatie voor meerdere coördinaten tegelijkertijd aan de verkeerde kant van het optimum terechtkomt.

Algoritme 3: Lineaire Top-Down Venster (De Hoofdprestatie)

• Benadering: Een top-down selectiemethode die de $O(M)$-afhankelijkheid vermijdt.
• Mechanisme:
  1. Begrenzing: Bewijst dat de optimale frequentie $m^*_a$ voor elk symbool ligt binnen een strak venster $[L_a, U_a]$ rond de geschaalde ideale frequentie $s_a = M \cdot c_a / N$. De vensterbreedte is begrensd door $O(r)$.
  2. Selectie: In plaats van te starten bij $M$ en decrementen, start het bij een bovengrens $U_a$ en selecteert de $D$ goedkoopste decrementtickets binnen dit venster.
  3. Optimalisatie: Gebruikt een lineaire-tijd selectie-algoritme (zoals Quickselect) om de $D$ kleinste tickets te vinden zonder ze volledig te sorteren.
• Complexiteit: $O(r)$ (asymptotisch lineair in de alfabetgrootte).
• Betekenis: Dit is het eerste algoritme dat exacte KL-optimaliteit bereikt met lineaire tijdscomplexiteit ten opzichte van de alfabetgrootte, onafhankelijk van de doel-frequentie $M$.

---

3. Belangrijkste Bijdragen

1. Exactheidswijs: Biedt de eerste reeks algoritmen die wiskundig bewezen globaal KL-optimaal zijn, en corrigeert de sub-optimaliteit van veelgebruikte heuristieken (Giesen, Bloom, Collet).
2. Asymptotisch Lineair Algoritme: Introduceert de "Top-Down Window" methode (Algoritme 3), die draait in $O(r)$ tijd, waardoor het theoretisch superieur is aan heap-gebaseerde methoden ($O(M \log r)$) voor grote $M$.
3. Bidirectionele Correctie: Identificeert en repareert de specifieke faalmodus van Bloom's algoritme waarbij eendirectionele reparatie niet kan herstellen van meervoudige coördinatie-initialisatiefouten.
4. Implementatie & Validatie:
   • Biedt portable C-implementaties en AVX2-gevectoriseerde versies.
   • Valideert correctheid tegen specifieke "getuige" tegenvoorbeelden waar bestaande heuristieken falen.
   • Demonstreert dat de exacte algoritmen in de praktijk de snelheid van de snelste heuristieken evenaren.

---

4. Experimentele Resultaten

De auteurs hebben de algoritmen getest op een AMD Ryzen 9 5900X over diverse verdelingen (Uniform, Geometrisch, Zipf, Gaussisch, Spaarzaam) en alfabetgroottes ($r$ tot 65.536).

• Correctheid: Alle voorgestelde algoritmen slaagden voor strikte marginaal-uitwisselingscontroles en kwamen overeen met het theoretische KL-optimum. Bestaande heuristieken (Giesen, FSE snelle doorgang) vertoonden redundantiekloven variërend van $10^{-3}$ tot $0.5$ nat per symbool op adversariële invoer.
• Prestaties (Scalar):
  • Window-smart (Alg 3): Consistent snel ($\approx 36\text{--}49$ cycli/symbool) ongeacht de vorm van de invoerverdeling. Het is de "veilige standaard" voor onbekende of zwaarstaart-invoer.
  • Bloom-smart (Alg 2): Uiterst snel ($\approx 13$ cycli/symbool) op uniform-achtige invoer waarbij de geometrische initialisatie dicht bij het optimum ligt. Echter, prestaties verslechteren aanzienlijk (tot $119$ cycli/symbool) op scheve verdelingen (bijv. Geometrisch $p=0.95$) naarmate de initialisatie verder van het optimum afwijkt.
  • Bottom-up: Aanzienlijk trager (ordes van grootte) door $O(M)$ iteraties, dienend slechts als correctheidstest.
• Prestaties (AVX2):
  • Window-super: Bereikte een $1.4\times$ tot $2.2\times$ snelheidswinst op zwaarstaart-invoer door een Lagrangiaanse drempelpad (bisectie) te gebruiken om tickets niet te hoeven materialiseren, waardoor het selectieproces effectief wordt gevectoriseerd.
  • Bloom-super: Zie beperkte winsten omdat de heap-operaties (Fase 1 en 2) serieel en data-afhankelijk zijn, wat vectorisatie weerstaat.

---

5. Betekenis en Conclusie

Dit paper overbrugt de kloof tussen theoretische optimaliteit en praktische prestaties in entropiecodering.

• Theoretische Impact: Het lost de open vraag op of een polynomiale-tijd, exact KL-optimale normalisator bestaat die snel genoeg is voor real-time codering. Het antwoord is ja, via de $O(r)$ venstermethode.
• Praktische Impact:
  • Codec-ontwikkelaars kunnen nu heuristische normalisators vervangen door exacte versies zonder snelheid in te leveren.
  • Het paper biedt een "complementaire" strategie: Gebruik Bloom-smart voor uniforme/symmetrische data (snelste) en Window-smart voor scheve/onbekende data (meest robuust).
  • De reductie in redundantie (hoewel klein in bits per symbool) is wiskundig gegarandeerd, wat cruciaal is voor hoog-efficiënte compressiestandaarden (zoals zstd, CRAM, rANS) waar elke bit telt.
• Toekomstig Werk: De auteurs suggereren het onderzoeken van strakkere venstergrenzen ($o(r)$), implementaties met geheeltallige rekenkunde om drijvende-kommaproblemen te vermijden, en end-to-end codec-integratiestudies om bestandsgrootte-reducties in productie te meten.

Kortom, Szewczyk presenteert een rigoureus wiskundig raamwerk en sterk geoptimaliseerde implementaties die exacte KL-optimale frequentienormalisatie een haalbare, hoogpresterende realiteit maken voor moderne entropie-coders.