Golomb-koding: Den smarte algoritmen som klemmer data smartere
Golomb-koding: Når matematikk møter datakompresjon
Vanlige komprimeringsalgoritmer som gzip og LZ4 fungerer godt i de fleste tilfeller. Men når dataene følger et forutsigbart mønster, finnes det ofte bedre alternativer. Golomb-koding er én av dem.
Teknikken ble utviklet på 1960-tallet av Solomon W. Golomb. Den er tapsfri og spesielt god på data der små verdier forekommer mye oftere enn store. Dette kalles geometrisk fordeling.
Hvorfor fordelingen betyr noe
Flere typer data har denne egenskapen. Antall forsøk i nettverksprotokoller følger ofte et slikt mønster – de fleste koblinger lykkes på første forsøk. Forskjeller mellom videobilder er gjerne små. I loggfiler er alvorlige feil sjeldnere enn mindre alvorlige.
Golomb-koding utnytter dette ved å gi korte koder til vanlige verdier og lengre koder til sjeldne. Resultatet er bedre kompresjon enn mange generelle metoder klarer.
Slik fungerer det
Algoritmen bruker en parameter kalt M. Hver verdi deles i en kvotient og en rest. Kvotienten kodes med unary (en rekke med nuller etterfulgt av en ener), mens resten kodes binært. Én parameter styrer hele prosessen.
For utviklere er poenget enkelt: har du data der små verdier dominerer, kan Golomb-koding gi god kompresjon med lavt CPU-forbruk.
Rice-koding: En raskere variant
Robert F. Rice laget en forenklet utgave kalt Rice-koding. Her er M alltid en potens av to. Det betyr at divisjon og modulo erstattes med bit-skift og masker – operasjoner som er svært raske på moderne prosessorer.
Dette gjør Rice-koding spesielt egnet der hastighet er viktig.
Bruksområder i dag
Teknikkene brukes fortsatt i flere systemer:
- Video: H.264 og H.265 benytter Exp-Golomb for syntakselementer
- Lyd: Rice-koding brukes i enkelte talekomprimeringsalgoritmer
- Genomikk: Verktøy for DNA-analyse bruker Golomb-varianter
- IoT: Sensorer med begrenset strøm sparer data ved å bruke Rice-koding
- Embedded: Der CPU-kapasitet er knapp, er bitwise-operasjoner en fordel
Fordeler for utviklere
Golomb- og Rice-koding krever bare én parameter. Det gir forutsigbar kompresjon uten behov for frekvenstabeller. Både koding og dekoding er O(1), og det trengs ingen store oppslagstabeller. Resultatet er alltid det samme, noe som er nyttig ved testing og reproduserbare systemer.
Når det ikke lønner seg
Hvis dataene er jevnt fordelt eller følger en normalfordeling, kan Golomb-koding faktisk øke størrelsen. Generelle algoritmer med adaptive modeller vil ofte gi bedre resultater på vilkårlige data. Trenger du maksimal kompresjon uansett hastighet, er LZMA eller Zstandard som regel bedre valg.
Kort oppsummert
Golomb-koding viser at god forståelse av dataenes egenskaper kan gi enklere og raskere løsninger. Selv om algoritmen er over 60 år gammel, er den fortsatt relevant – spesielt når dataene har den geometriske fordelingen den ble laget for.
Neste gang du ser at små verdier dominerer, kan det være verdt å vurdere Golomb- eller Rice-koding.