Eliasovo gama kódování

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledá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 (2N) 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 2N. 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í[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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