Elias omega kódování - Elias omega coding

Elias ω kódování nebo Elias omega kódování je univerzální kód kódování kladných celých čísel vyvinutých Peter Elias. Jako Eliasovo gama kódování a Eliasovo delta kódování, funguje tak, že předčíslí celého čísla reprezentuje jeho řádově v univerzálním kódu. Na rozdíl od těchto dalších dvou kódů však Elias omega rekurzivně kóduje tuto předponu; tak, oni jsou někdy známí jako rekurzivní Eliasovy kódy.

Omega kódování se používá v aplikacích, kde největší kódovaná hodnota není známa předem nebo doposud komprimovat data, ve kterých jsou malé hodnoty mnohem častější než velké hodnoty.

Chcete-li kódovat a číslo N:

  1. Na konec kódu vložte „0“.
  2. Li N = 1, stop; kódování je dokončeno.
  3. Připravte binární zastoupení N na začátek kódu. Budou to nejméně dva bity, z nichž první bit bude 1.
  4. Nechat N stejný počet právě přidaných bitů, mínus jedna.
  5. Vraťte se ke kroku 2 a vložte kódování nového N.

Dekódování Eliasova omega kódovaného čísla:

  1. Začněte s proměnnou N, nastavena na hodnotu 1.
  2. Pokud je další bit „0“, zastavte. Dekódované číslo je N.
  3. Pokud je další bit „1“, přečtěte jej plus N více bitů a použijte toto binární číslo jako novou hodnotu N. Vraťte se ke kroku 2.

Příklady

Omega kódy lze považovat za řadu „skupin“. Skupina je buď jeden 0 bitů, které ukončují kód, nebo dva nebo více bitů začínajících 1, za kterou následuje další skupina.

Prvních pár kódů je zobrazeno níže. Zahrnuto je tzv implicitní distribuce, popisující distribuci hodnot, pro které toto kódování poskytuje kód minimální velikosti; vidět Vztah univerzálních kódů k praktické kompresi pro detaily.

HodnotaKódImplikovaná pravděpodobnost
101/2
210 01/8
311 01/8
410 100 01/64
510 101 01/64
610 110 01/64
710 111 01/64
811 1000 01/128
911 1001 01/128
1011 1010 01/128
1111 1011 01/128
1211 1100 01/128
1311 1101 01/128
1411 1110 01/128
1511 1111 01/128
1610 100 10000 01/2048
1710 100 10001 01/2048
...
10010 110 1100100 01/8192
100011 1001 1111101000 01/131,072
10,00011 1101 10011100010000 01/2,097,152
100,00010 100 10000 11000011010100000 01/268,435,456
1,000,00010 100 10011 11110100001001000000 01/2,147,483,648

Kódování pro 1 googol, 10100, je 11 1000 101001100 (15 bitů délky záhlaví) následované 333bitovou binární reprezentací 1 googolu, což je 10010 01001001 10101101 00100101 10010100 11000011 01111100 11101011 00001011 00100111 10000100 11000100 11001110 00001011 11110011 10001010 11001110 0100 01000011 00001000 10101000 00101110 10001111 00010000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 a koncová 0, celkem 349 bitů.

Googol na setou sílu (1010000) je binární číslo 33220 bitů. Jeho kódování omega je 33 243 bitů dlouhé: 11 1111 1000000111000100 (22 bitů), následuje 33 220 bitů hodnoty a koncová 0. Pod Eliasovo delta kódování, stejné číslo je dlouhé 33 250 bitů: 000000000000000 1000000111000100 (31 bitů) následované 33 219 bitů hodnoty. Jako log2(1010000) = 33219,28, takže v tomto případě je kódování omega a delta pouze o 0,07% a 0,09% delší než optimální.

Příklad kódu

Kódování

prázdnota eliasOmegaEncode(char* zdroj, char* dest){    IntReader intreader(zdroj);    BitWriter bitwriter(dest);    zatímco (intreader.opustil())    {        int počet = intreader.dostat();        BitStack bity;        zatímco (počet > 1) {            int len = 0;            pro (int tepl = počet; tepl > 0; tepl >>= 1)  // výpočet 1 + patro (log2 (num))                len++;            pro (int i = 0; i < len; i++)                bity.pushBit((počet >> i) & 1);            počet = len - 1;        }        zatímco (bity.délka() > 0)            bitwriter.putBit(bity.popBit());        bitwriter.putBit(Nepravdivé);                        // zapsat jednu nulu    }    bitwriter.zavřít();    intreader.zavřít();}

Dekódování

prázdnota eliasOmegaDecode(char* zdroj, char* dest) {    BitReader bitreader(zdroj);    IntWriter intwriter(dest);    zatímco (bitreader.opustil())    {        int počet = 1;        zatímco (bitreader.inputBit())     // potenciálně nebezpečné s poškozenými soubory.        {            int len = počet;            počet = 1;            pro (int i = 0; i < len; ++i)            {                počet <<= 1;                -li (bitreader.inputBit())                    počet |= 1;            }        }        intwriter.putInt(počet);           // vypíše hodnotu    }    bitreader.zavřít();    intwriter.zavřít();}

Zobecnění

Viz také: Množství s proměnnou délkou § Cik-cak kódování

Elias omega kódování nekóduje nula nebo záporná celá čísla. Jedním ze způsobů, jak kódovat všechna nezáporná celá čísla, je přidat 1 před kódováním a poté odečíst 1 po dekódování. Jedním ze způsobů, jak kódovat všechna celá čísla, je nastavit bijekce, mapování všech celých čísel (0, 1, -1, 2, -2, 3, -3, ...) na přísně pozitivní celá čísla (1, 2, 3, 4, 5, 6, 7, ...) před kódování.

Viz také

Reference

Další čtení

  • Elias, Peter (Březen 1975). "Univerzální sady kódových slov a reprezentace celých čísel". Transakce IEEE na teorii informací. 21 (2): 194–203. doi:10.1109 / tit.1975.1055349.
  • Fenwick, Peter (2003). "Univerzální kódy". V Sayood, Khalid (ed.). Příručka bezztrátové komprese. New York, NY, USA: Akademický tisk. str. 55–78. doi:10.1016 / B978-012620861-0 / 50004-8. ISBN  978-0123907547.

externí odkazy