> elias | gamma | uniwersalny <
// Elias Gamma – uniwersalny kod dla dodatnich liczb całkowitych bez parametrów
Kod uniwersalny
Działa dla każdej dodatniej liczby całkowitej bez parametrów.
Bez prefiksów
Żaden kod nie jest prefiksem innego, co zapewnia jednoznaczne dekodowanie.
Asymptotycznie optymalny
Zbliża się do optymalnej kompresji dla pewnych rozkładów.
>> informacje techniczne
Jak działa Elias Gamma:
Elias Gamma koduje dodatnią liczbę całkowitą n w następujący sposób: 1) Oblicza N = ⌊log₂(n)⌋, 2) Zapisuje N zer jako kod unarny, 3) Dołącza binarną reprezentację n (mającą N+1 bitów). Wynikiem jest kod o długości (2N+1) bitów.
Przykłady kodowania:
n=1: log₂(1)=0 Kod: 1 (bez zer + "1") n=2: log₂(2)=1 Kod: 010 (jedno zero + "10") n=5: log₂(5)=2 Kod: 00101 (dwa zera + "101") n=10: log₂(10)=3 Kod: 0001010 (trzy zera + "1010") Wzór na długość: 2⌊log₂(n)⌋ + 1
Dlaczego warto używać Elias Gamma:
- >Brak wymaganych parametrów
- >Prosta implementacja
- >Dobre dla małych liczb całkowitych
- >Uniwersalny schemat kodowania
- >Istotny w teorii informacji i kompresji danych
>> często zadawane pytania
Czym jest kodowanie Elias Gamma?
Elias Gamma to uniwersalny kod dla dodatnich liczb całkowitych zaproponowany przez Petera Eliasa. Każda liczba jest kodowana przy użyciu długości jej zapisu binarnego w formie unarnej, a następnie dołączany jest sam zapis binarny. Kod jest „uniwersalny”, ponieważ działa bez znajomości rozkładu danych.
Kiedy Elias Gamma jest efektywny?
Elias Gamma jest najbardziej efektywny dla liczb, które podlegają rozkładowi potęgowemu (P(n) ∝ n^-2). Zużywa około 2log₂(n)+1 bitów, co sprawia, że jest dobry dla małych wartości, ale mniej wydajny dla dużych n.
Gamma vs Delta vs Omega?
Elias Gamma używa 2log₂(n)+1 bitów. Delta poprawia to do log₂(n)+2log₂(log₂(n)+1)+1 bitów, a Omega zapewnia jeszcze lepszą kompresję dla bardzo dużych liczb. Gamma jest najprostszy, Delta lepsza dla wartości średnich, a Omega dla dużych n.
Gdzie używa się kodów Eliasa?
Kody Eliasa są stosowane w teorii informacji, badaniach nad kompresją danych oraz w niektórych wyspecjalizowanych algorytmach kompresji. Są ważne teoretycznie jako kody uniwersalne, ale w praktyce rzadziej używane niż kodowanie Huffmana czy arytmetyczne.