> golomb | optymalna | kompresja <
// Kodowanie Golomba - Optymalna kompresja liczb całkowitych z elastycznym dzielnikiem
>> funkcje
Elastyczny dzielnik
Wybierz dowolną wartość M, aby uzyskać maksymalną efektywność kompresji.
Ucięte kodowanie binarne
Używa minimalnej liczby bitów do zakodowania reszty.
Zastosowanie ogólne
Działa dla dowolnego rozkładu nieujemnych liczb całkowitych.
>> informacje techniczne
Jak działa kodowanie Golomba
Kodowanie Golomba dzieli każdą liczbę całkowitą n przez dzielnik M, aby otrzymać iloraz q i resztę r. Iloraz jest kodowany unarnie, a reszta za pomocą uciętego kodu binarnego, który wykorzystuje minimalną liczbę bitów do reprezentacji M możliwych wartości. Tworzy to kod optymalny dla rozkładów geometrycznych o parametrze p = 1/M.
Przykład kodowania Golomba (M=5)
M=5, b=⌈log₂(5)⌉=3, c=2³-5=3 0 → q=0, r=0 → 0|00 → 000 (2 bity dla r<3) 1 → q=0, r=1 → 0|01 → 001 (2 bity dla r<3) 2 → q=0, r=2 → 0|10 → 010 (2 bity dla r<3) 3 → q=0, r=3 → 0|110 → 0110 (3 bity dla r≥3) 4 → q=0, r=4 → 0|111 → 0111 (3 bity dla r≥3) 5 → q=1, r=0 → 10|00 → 1000 6 → q=1, r=1 → 10|01 → 1001 7 → q=1, r=2 → 10|10 → 1010 Ucięte binarne: r<3 używa 2 bitów, r≥3 używa 3 bitów
Dlaczego warto używać kodowania Golomba
- Optymalne dla rozkładów geometrycznych
- Elastyczny parametr M
- Minimalne zużycie bitów
- Prosta implementacja
- Udowodniona optymalność
>> często zadawane pytania
Czym jest kodowanie Golomba?
Kodowanie Golomba to optymalny, bezprefiksowy kod o zmiennej długości przeznaczony dla rozkładów geometrycznych. Dzieli liczby całkowite przez regulowany parametr M, kodując iloraz unarnie, a resztę uciętym kodem binarnym, co zapewnia optymalną kompresję danych spełniających P(n) = (1-p)^n × p.
Jak dobrać parametr M?
Optymalna wartość M zależy od parametru geometrycznego p twoich danych. Dla danych o średniej μ przybliżenie wynosi M ≈ μ + 1. Dla prawdopodobieństw malejących wykładniczo z parametrem p optymalne M to ⌈-1/log₂(1-p)⌉. Użyj funkcji analizy, aby znaleźć najlepsze M dla swoich danych.
Czym jest ucięte kodowanie binarne?
Ucięte kodowanie binarne minimalizuje liczbę bitów przy kodowaniu jednej z M możliwych wartości. Jeśli M jest potęgą 2, używany jest standardowy kod binarny. W przeciwnym razie niektóre wartości używają ⌊log₂M⌋ bitów, a inne ⌈log₂M⌉ bitów, co zapewnia jednoznaczne dekodowanie przy minimalnej średniej długości.
Gdzie stosuje się kodowanie Golomba?
Kodowanie Golomba jest używane w kompresji obrazów JPEG-LS, kodowaniu wideo H.264 (jako Exp-Golomb) oraz w bezstratnych formatach audio. Idealnie nadaje się do kodowania długości serii, reszt po predykcji i wszelkich danych o rozkładach geometrycznych lub wykładniczych.