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, nebo ke kompresi dat, ve kterých jsou malé hodnoty mnohem častější než velké.

Zakódování

editovat

Pro zakódování libovolného přirozeného (tj. celého kladného) čísla:

  1. Zapište číslo ve dvojkové soustavě. Nechť N je počet cifer zápisu (tj. první jednička má váhu 2N–1).
  2. 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í

editovat
  1. Čtěte a počítejte nuly, dokud nedosáhnete první jedničky. Nechť je tento počet nul N–1.
  2. 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í

editovat

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

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

editovat

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