Eliasovo gama kódování

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.

Zakódování čísla:

1. Zapište jej dvojkově.
2. Odečtěte 1 od počtu bitů zapsaných v kroku 1 a na začátek připojte takový počet nul.

Rovnocenný způsob:

1. Rozdělte celé číslo na nejvyšší mocninu dvou (2^N) a zbývající N dvojková čísla.
2. Zakódujte N jedničkově; což znamená N nul a za nimi jednička.
3. Připojte oněch zbývajících N dvojkových čísel k jedničkové reprezentaci čísla N.

Začátek kódu:

                            pravděpodobnost
 1 = 20 + 0 = 1                  1/2
 2 = 21 + 0 = 010                1/8
 3 = 21 + 1 = 011                 "
 4 = 22 + 0 = 00100              1/32
 5 = 22 + 1 = 00101               "
 6 = 22 + 2 = 00110               "
 7 = 22 + 3 = 00111               "
 8 = 23 + 0 = 0001000            1/128
 9 = 23 + 1 = 0001001             "
10 = 23 + 2 = 0001010             "
11 = 23 + 3 = 0001011             "
12 = 23 + 4 = 0001100             "
13 = 23 + 5 = 0001101             "
14 = 23 + 6 = 0001110             "
15 = 23 + 7 = 0001111             "
16 = 24 + 0 = 000010000          1/512
17 = 24 + 1 = 000010001           "
...

Pravděpodobnostní rozdělení je zmíněno pro přehlednost.

Dekódování čísla:

1. Čtěte a počítejte nuly, dokud nedosáhnete první jedničky. Nechť je tento počet nul N.
2. Ona první dosažená jednička představuje hodnotu 2^N. Nyní už jen čtěte zbývajících N bitů.

Gama kódování se používá v aplikacích, kde největší zakódovaná hodnota není předem známá, nebo ke kompresi dat, ve kterých jsou malé hodnoty mnohem častější než velké.

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í

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

V tomto článku byl použit překlad textu z článku Elias gamma coding na anglické Wikipedii.