Cesko.wiki Eliasovo gama kódování
Author
Albert FloresEliasů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ě. +more 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:
| wikitable | Čí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. +more # 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í. +more 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
Dekódování:
void eliasGammaDecode(char* source, char* dest) { BitReader bitreader(source); BitWriter bitwriter(dest); int numberBits = 0; while(bitreader. hasLeft) { while(. +morebitreader. getBit || bitreader. hasLeft)numberBits++; //keep on reading until we fetch a one. int current = 0; for (int a=0; a.