Golomb-codering: de slimme compressietechniek die data efficiënter maakt

Golomb-codering: wiskunde die data slim inkrimpt

Niet elke dataset past in dezelfde compressie-mal. Algoritmes als gzip of LZ4 doen het prima voor algemeen gebruik, maar wanneer je data een duidelijke wiskundige verdeling volgt, kun je vaak beter scoren met een gerichtere aanpak. Golomb-codering is zo'n aanpak. Solomon Golomb bedacht het in de jaren zestig, en het werkt nog steeds verrassend goed.

Het idee is simpel: de techniek is gemaakt voor data waarin kleine waarden veel vaker voorkomen dan grote. Dat heet een geometrische verdeling. Denk aan retry-tellingen in netwerkverkeer, kleine verschillen tussen videoframes of zeldzame fouten in logbestanden. In al die gevallen wint een methode die korte codes geeft aan kleine getallen.

Hoe het werkt

Golomb-codering gebruikt één instelbare parameter, meestal aangeduid als M. Elk getal wordt opgesplitst in een quotient en een rest. De quotient wordt in unaire vorm weergegeven (een reeks nullen gevolgd door een één), de rest in binaire vorm. Door M goed te kiezen, pas je de code precies aan op hoe vaak kleine waarden voorkomen.

Rice-codering: de snelle variant

Robert Rice maakte er een praktische variant van: Rice-codering. Hierbij moet M altijd een macht van twee zijn. Dat lijkt een beperking, maar het voordeel is groot. De berekeningen veranderen in simpele bit-operaties: shifts en masks. Die zijn op moderne processors veel sneller dan delingen. Daardoor is Rice-codering zowel compact als licht op de CPU.

Waar je het tegenkomt

Je komt Golomb- en Rice-codering nog steeds tegen in actuele systemen:

• Video: H.264 en H.265 gebruiken Exp-Golomb voor syntax-elementen
• Audio: Sommige spraakcompressie-algoritmes vertrouwen op Rice-codering
• Genomics: Bio-informatica-tools passen varianten toe op DNA-sequenties
• IoT: Sensoren met beperkte batterij sturen data efficiënter met Rice-codes
• Embedded: Waar elke cyclus telt, maken bitwise operaties het verschil

Voordelen voor ontwikkelaars

Wat Golomb- en Rice-codering aantrekkelijk maakt:

• Je hoeft geen frequentietabellen op te bouwen; één parameter volstaat
• Zowel coderen als decoderen is O(1) met lage overhead
• Er zijn geen grote lookup tables nodig
• De uitkomst is altijd hetzelfde, wat handig is voor testen en reproduceerbaarheid

Wanneer je het beter kunt laten

De techniek werkt alleen als je data echt een geometrische verdeling volgt. Bij uniforme of normale verdelingen kan het bestand juist groter worden. Voor maximale compressie zonder snelheidseisen zijn LZMA of Zstandard vaak betere keuzes.

Conclusie

Golomb-codering toont dat een goed begrip van je data soms tot eenvoudigere en snellere oplossingen leidt dan generieke algoritmes. In een tijd van AI en geavanceerde compressie blijft een zestig jaar oud idee relevant, juist omdat het perfect past bij bepaalde patronen. Zie je dat kleine waarden in je data de boventoon voeren? Dan is het misschien tijd om Golomb of Rice een kans te geven.