// Elias Omega – asymptotycznie optymalny kod dla liczb całkowitych o dowolnym rozmiarze
Zbliża się do teoretycznego minimum dla dużych liczb.
Rekursywnie koduje długości w elegancki sposób.
Działa dla każdej dodatniej liczby całkowitej bez dodatkowych parametrów.
Elias Omega rekursywnie koduje długość liczby, aż do osiągnięcia 1. Zaczynamy od n, kodujemy log₂(n), potem log₂(log₂(n)) i kontynuujemy do 1. Kod składa się z tych wartości w odwróconej kolejności i kończy się 0. Daje to log(n) + log(log(n)) + log(log(log(n))) + ... bitów.
n=16: 16 → binarnie: 10000 (długość 5) 5 → binarnie: 101 (długość 3) 3 → binarnie: 11 (długość 2) 2 → binarnie: 10 (długość 2) 1 → stop Budowanie kodu od końca: Zacznij od 0 (znacznik końca) Dodaj z przodu 10 (koduje 2) Dodaj z przodu 11 (koduje 3) Dodaj z przodu 101 (koduje 5) Dodaj z przodu 10000 (koduje 16) Wynik: 10 11 101 10000 0 Porównanie wydajności: n=100: Gamma=13, Delta=12, Omega=10 bitów n=1000: Gamma=19, Delta=16, Omega=14 bitów
Elias Omega to najbardziej zaawansowany kod z rodziny Eliasa. Wykorzystuje rekursywne kodowanie długości, aby osiągnąć asymptotyczną optymalność. Koduje długość reprezentacji, następnie długość tej długości itd. aż do 1, dzięki czemu jest bardzo wydajny dla bardzo dużych liczb całkowitych.
Dla małych liczb (< 10) zazwyczaj najlepszy jest Gamma. Dla wartości średnich (10–1000) lepiej sprawdza się Delta. Dla dużych liczb (> 1000) Omega staje się coraz bardziej korzystny. Omega wykorzystuje iteracje log*(n) i osiąga optymalne zachowanie w granicy.
Kod jest asymptotycznie optymalny, jeśli stosunek jego długości do teoretycznego minimum dąży do 1, gdy n rośnie. W przypadku Omega zachodzi: length(n)/log₂(n) → 1 dla n → ∞.
Mimo przewagi teoretycznej Omega jest bardziej złożony we wdrożeniu i dekodowaniu. Dla praktycznych danych z ograniczonym zakresem wartości prostsze kody, takie jak Exp-Golomb czy Rice, są często wygodniejsze. Omega jest szczególnie przydatny w analizie teoretycznej i scenariuszach z nieograniczonymi liczbami całkowitymi.