Eliasův gama kód
Eliasův gama kód je univerzální kód pro kódování kladných celých čísel, který vyvinul Peter Elias . Běžně se používá při kódování celých čísel, jejichž maximální hodnotu nelze předem určit.
Popis algoritmu
Chcete-li zakódovat číslo:
- Napište to v binárním tvaru.
- Přidejte nuly před binární reprezentaci čísla. Počet nul je o jednu menší než počet bitů v binární reprezentaci čísla.
Podobný způsob popisu tohoto procesu je:
- Vyberte nejvýznamnější bit z celého čísla (největší mocnina 2, kterou číslo zahrnuje - 2 N ) a nejméně významných N bitů.
- Napište N v unárním kódu; to znamená N nul následovaných jedničkou.
- Přidejte N nejméně významných binárních číslic čísla za tímto unárním kódem.
Začněte kódovat:
| Číslo |
Význam |
Kódování |
Odhadovaná
pravděpodobnost
|
| jeden |
20 + 0 |
jeden |
1/2
|
| 2 |
2 1 + 0 |
0 1 0 |
1/8
|
| 3 |
2 1 + 1 |
0 1 1 |
1/8
|
| čtyři |
2² + 0 |
00 1 00 |
1/32
|
| 5 |
2² + 1 |
00 1 01 |
1/32
|
| 6 |
2² + 2 |
00 1 10 |
1/32
|
| 7 |
2² + 3 |
00 1 11 |
1/32
|
| osm |
2³ + 0 |
000 1000 |
1/128
|
| 9 |
2³ + 1 |
000 1 001 |
1/128
|
| deset |
2³ + 2 |
000 1 010 |
1/128
|
| jedenáct |
2³ + 3 |
000 1 011 |
1/128
|
| 12 |
2³ + 4 |
000 1 100 |
1/128
|
| 13 |
2³ + 5 |
000 1 101 |
1/128
|
| čtrnáct |
2³ + 6 |
000 1 110 |
1/128
|
| patnáct |
2³ + 7 |
000 1 111 |
1/128
|
| 16 |
24 + 0 |
0000 10000 |
1/512
|
| 17 |
2 4 + 1 |
0000 1 0001 |
1/512
|
| … |
|
|
|
Pro přehlednost bylo přidáno rozdělení předpokládaných pravděpodobností pro kódy.
Chcete-li dekódovat číslo zakódované Eliasovým gama kódem, měli byste:
- Spočítejte všechny nuly až do první 1. Nechť N je počet těchto nul.
- S ohledem na ten, který bude prvním (nejvýznamnějším) bitem celého čísla, s hodnotou 2 N , spočítejte zbývajících N číslic celého čísla.
Gamma kódování se používá v aplikacích, kde nelze předem znát největší hodnotu, nebo ke kompresi dat, ve kterých se malé hodnoty vyskytují častěji než velké hodnoty.
Generalizace
Gamma kódování není vhodné pro kódování nulových hodnot nebo záporných čísel. Jediný způsob, jak zakódovat nulu, je přidat k ní 1 před kódováním a odečíst po dekódování. Dalším způsobem je přidat jakýkoli nenulový kód před 1 a pak zakódovat nulu jako jednoduchou 0. Jediný způsob, jak zakódovat všechna celá čísla, je nastavit bijekci (shodu) před zahájením kódování, mapování celých čísel od (0, 1, −1, 2, −2, 3, −3, …) na (1, 2, 3, 4, 5, 6, 7, …).
Příklad kódu
// Kódování
void eliasGammaEncode ( char * source , char * dest )
{
IntReader intreader ( zdroj );
BitWriter bitwriter ( cíl );
while ( intreader . hasLeft ())
{
int num = vetřelec . getint ();
intl = log2 ( num ) ;
for ( int a = 0 ; a < l ; a ++ )
{ bitwriter . putBit ( false ); //uveďte nuly, abyste ukázali, kolik bitů je třeba sledovat }
bitwriter . putBit ( true ); //označte koncové nuly pro ( int a = l -1 ; a >= 0 ; a -- ) //zapište bity jako jednoduchá binární čísla {
if ( num & ( 1 << a ))
bitwriter . putBit ( true );
jiný
bitwriter . putBit ( false );
}
}
vetřelec . zavřít ();
bitwriter . zavřít ();
}
// Decode
void eliasGammaDecode ( char * source , char * dest )
{
BitReader bitreader ( zdroj );
BitWriter bitwriter ( cíl );
int cisloBity = 0 ;
while ( bitreader.hasLeft ( ) )
{
while ( ! bitreader . getBit () || bitreader . hasLeft ()) numberBits ++ ; //pokračovat ve čtení, dokud nenarazíme... int current = 0 ;
for ( int a = 0 ; a < početBitů ; a ++ ) // přečtení počtuBitů bitů {
if ( bitreader.getBit ( ) )
proud += 1 << a ;
}
//zapište to jako 32bitové číslo
current = current | ( 1 << početBitů ) ; //poslední bit není dekódován! for ( int a = 0 ; a < 32 ; a ++ ) //přečtení počtuBitů bitů {
if ( aktuální & ( 1 << a ))
bitwriter . putBit ( true );
jiný
bitwriter . putBit ( false );
}
}
}
Viz také
Literatura