Golomb Coding – sprytna kompresja, która naprawdę robi robotę

Golomb i Rice coding – kompresja, która lubi matematykę

Nie każdy zbiór danych lubi się z uniwersalnymi algorytmami. Czasem gzip czy LZ4 po prostu nie wykorzystują w pełni tego, co wiemy o strukturze danych. Wtedy warto sięgnąć po coś bardziej wyspecjalizowanego.

Golomb coding powstał w latach 60. i do dziś sprawdza się tam, gdzie wartości występują według rozkładu geometrycznego – małe liczby pojawiają się znacznie częściej niż duże.

Kiedy warto po nim sięgnąć

W praktyce taki rozkład pojawia się dość często. W logach błędy o niskim priorytecie dominują nad krytycznymi. W strumieniach wideo różnice między klatkami zwykle są małe. W protokołach sieciowych większość połączeń udaje się za pierwszym razem.

Właśnie w takich przypadkach Golomb coding błyszczy. Krótkie kody przypisuje częstym, małym wartościom, a dłuższe – rzadkim. Dzięki temu uzyskuje lepsze wyniki niż standardowe metody kodowania o zmiennej długości.

Jak to działa w praktyce

Algorytm dzieli każdą liczbę na iloraz i resztę. Iloraz zapisuje w kodzie unarnym, resztę – binarnie. Kluczowy jest parametr M, który decyduje, jak bardzo „agresywnie” algorytm skraca kody dla małych wartości.

Dla programisty najważniejsze jest to, że przy dobrze dobranym M można uzyskać bardzo dobrą kompresję przy niskim zużyciu procesora.

Rice coding – szybsza wersja Golomba

Rice coding to wariant Golomba, w którym parametr M musi być potęgą dwójki. Ta pozornie drobna zmiana ma duże konsekwencje – operacje dzielenia i modulo zastępują szybkie operacje bitowe.

Dzięki temu Rice coding jest szczególnie atrakcyjny w systemach embedded i urządzeniach IoT, gdzie każdy cykl procesora ma znaczenie.

Gdzie spotkasz te algorytmy

• kodeki wideo H.264 i H.265 (wariant Exp-Golomb)
• kompresja dźwięku
• narzędzia bioinformatyczne przetwarzające sekwencje DNA
• sensory IoT ograniczające zużycie energii
• systemy embedded wymagające deterministycznego zachowania

Zalety z perspektywy developera

Golomb i Rice coding nie wymagają budowania tabel częstotliwości. Wystarczy jeden parametr. Działają w czasie stałym, nie zużywają dużo pamięci i dają identyczne wyniki przy każdym uruchomieniu – to ważne przy testowaniu i systemach odtwarzalnych.

Kiedy lepiej wybrać coś innego

Przy danych o rozkładzie równomiernym lub normalnym Golomb coding może zwiększyć rozmiar pliku. W takich przypadkach lepiej sprawdzają się algorytmy adaptacyjne lub metody o wysokim stopniu kompresji, takie jak LZMA czy Zstandard.

Podsumowanie

Golomb i Rice coding pokazują, że czasem najprostsze rozwiązania – oparte na matematyce, a nie na uniwersalnych modelach – okazują się najskuteczniejsze. Jeśli wiesz, że Twoje dane mają konkretny rozkład, warto rozważyć te algorytmy zamiast sięgać po ciężkie narzędzia.