Eliasův gama kód je univerzální kód pro kladná celá čísla, jehož autorem je Peter Elias. Nejčastější využití je kódování celých čísel, u kterých není předem zjistitelná jejich horní hranice, nebo ke kompresi dat, ve kterých jsou malé hodnoty mnohem častější než velké.
Zakódování Pro zakódování libovolného přirozeného (tj. celého kladného) čísla: Zapište číslo ve dvojkové soustavě. Nechť N je počet cifer zápisu (tj. první jednička má váhu 2N–1). Před dvojkový zápis předřaďte N–1 nul.
Začátek kódu včetně pravděpodobnostního rozdělení, jenž je zmíněno pro přehlednost:
Číslo Binární reprezentace čísla Zakódované číslo Pravděpodobnost 1 = 20 + 0 1 1 1/2 2 = 21 + 0 1 0 0 1 0 1/8 3 = 21 + 1 1 1 0 1 1 1/8 4 = 22 + 0 1 00 00 1 00 1/32 5 = 22 + 1 1 01 00 1 01 1/32 6 = 22 + 2 1 10 00 1 10 1/32 7 = 22 + 3 1 11 00 1 11 1/32 8 = 23 + 0 1 000 000 1 000 1/128 9 = 23 + 1 1 001 000 1 001 1/128 10 = 23 + 2 1 010 000 1 010 1/128 11 = 23 + 3 1 011 000 1 011 1/128 12 = 23 + 4 1 100 000 1 100 1/128 13 = 23 + 5 1 101 000 1 101 1/128 14 = 23 + 6 1 110 000 1 110 1/128 15 = 23 + 7 1 111 000 1 111 1/128 16 = 24 + 0 1 0000 0000 1 0000 1/512 17 = 24 + 1 1 0001 0000 1 0001 1/512
Dekódování Čtěte a počítejte nuly, dokud nedosáhnete první jedničky. Nechť je tento počet nul N–1. První dosažená jednička představuje dvojkovou číslici N ciferného čísla, tj. číslici s vahou 2N–1. Čtěte zbývajících N–1 dvojkových cifer.
Zobecnění Gama kódování nekóduje nulu nebo záporná celá čísla. Způsob, jak zachytit nulu, je přičíst 1 před zakódováním a odečíst 1 po dekódování. Jiný způsob je dát 1 před každou nenulovou hodnotu a zakódovat nulu jako 0. Způsob jak zakódovat všechna celá čísla je udělat bijekci, která zobrazí čísla (0, 1, -1, 2, -2, 3, -3, …) na (1, 2, 3, 4, 5, 6, 7, …) před zakódováním.
Příklad zdrojového kódu Zakódování v jazyce C: void eliasGammaEncode(char* source, char* dest) { IntReader intreader(source); BitWriter bitwriter(dest); while(intreader.hasLeft())
int num = intreader.getInt(); int l = log2(num); for (int a=0; a < l; a++)
bitwriter.putBit(false); //put 0s to indicate how much bits that will follow
bitwriter.putBit(true); //mark the end of the 0s for (int a=0; a < l; a++) //Write the bits as plain binary
if (num & 1 << a) bitwriter.putBit(true); else bitwriter.putBit(false);
intreader.close(); bitwriter.close(); }
Dekódování: void eliasGammaDecode(char* source, char* dest) { BitReader bitreader(source); BitWriter bitwriter(dest); int numberBits = 0; while(bitreader.hasLeft())
while(!bitreader.getBit() || bitreader.hasLeft())numberBits++; //keep on reading until we fetch a one... int current = 0; for (int a=0; a < numberBits; a++) //Read numberBits bits
if (bitreader.getBit()) current += 1 << a;
//write it as a 32 bit number
current= current | ( 1 << numberBits ) ; //last bit isn't encoded! for (int a=0; a < 32; a++) //Read numberBits bits
if (current & (1 << a)) bitwriter.putBit(true); else bitwriter.putBit(false);
Reference
Kategorie:Kódování Kategorie:Matematické zápisy Kategorie:Kompresní algoritmy