Zobrazení zdroje stránky Golombovo kódování

'''Golombovo kódování''' je [[bezeztrátová komprese|bezeztrátová kompresní]] metoda patřící do skupiny kódu vynalezených [[Solomon W. Golomb|Solomonem W. Golombem]] v 60. letech. Pro takové abecedy, které mají geometrické rozdělení pravděpodobnosti, bude Golombovo kódování optimální a bude tvořit [[prefixový kód]]. Z této vlastnosti plyne, že toto kódování bude velmi vhodné pro takové případy, kdy pravděpodobnost malých hodnot na vstupu bude mnohonásobně vyšší než pravděpodobnost velkých.

'''Ricovo kódování''' (podle [[Robert F. Rice|Roberta F. Ricea]]) označuje podmnožinu Golombových kódů, které vytvářejí jednodušší (ale teoreticky suboptimální) prefixový kód. Rice použil tuto množinu kódů v rámci [[adaptivní kódování|adaptivního kódování]]; "Riceovo kódování" tak může odkazovat buď na toto adaptivní kódování, nebo na speciální podmnožinu Golombových kódů. Zatímco v obecném Golombově kódování může být volitelný parametr <math>M</math> libovolné kladné celé číslo, Riceovo kódování volí parametr tak, aby byl mocninou dvou. Tato vlastnost činí Riceovo kódování vhodnějším pro počítačové využití, protože násobení a dělení dvěma je v [[binární aritmetika|binární aritmetice]] mnohem efektivnější.

Riceovo kódování se používá v mnoha bezeztrátových kompresních algoritmech pro obrázky a zvuk.

== Přehled ==

=== Tvorba kódu ===
Golombovo kódování používá nastavitelný parametr ''M'' k tomu, aby vstupní hodnoty rozdělilo na dvě části: <math>q</math>, výsledek celočíselného dělení ''M'' a <math>r</math> zbytek po dělení. Hodnota <math>q</math> se zakóduje pomocí [[unární kódování|unárního kódování]] a je následována zbytkem zakódovaným pomocí [[zkrácené binární kódování|zkráceného binárního kódování]]. Pokud <math>M=1</math>, pak je Golombovo kódování shodné s unárním.

[[Soubor:golomb rice code.svg]]

Golomb-Riceovo kódování si můžeme představit jako zakódování čísla pomocí pozice ''q'' a posunu ''r''. Obrázek výše ukazuje pozici ''q'' a posun ''r'' pro kódování čísla ''N'' za použití Golomb-Riceova kódování s parametrem ''M''.

Formálně jsou dvě části definovány následujícím výrazem, kde <math>x</math> je číslo, které chceme zakódovat:
<math>q = \left \lfloor \frac{\left (x-1 \right )}{M} \right \rfloor</math> a <math>r = x-qM-1</math>
Konečný výsledek pak je: <math>\left( q+1 \right) r</math>.

<math>r</math> se může sestávat z proměnlivého počtu bitů, speciálně z ''b'' bitů pro Riceovo kódování,
v případě Golombova kódování se mění mezi ''b''-1 a ''b'' bity. Nechť <math>b = \lceil\log_2(M)\rceil</math>. Když <math>0 \leq r < 2^b-M</math>, pak se použije ''b''-1 bitů pro zakódování ''r'', pokud <math>2^b-M \leq r < M </math> pak se použije ''b'' bitů.
Je zřejmé, že <math>b=\log_2(M)</math> pokud ''M'' je mocnina dvou tak můžeme zakovat všechny hodnoty ''r'' pomocí ''b'' bitů.

Parametr ''M'' je funkcí odpovídajícího [[Bernouliho proces]]u, který je parametrizován pomocí <math>p=P(X=0)</math> pravděpodobností úspěchu daného [[Binomické rozdělení|binomického rozdělení]]. <math>M</math> je buď mediánem daného rozdělení, nebo medián +/- 1. Můžeme ho odvodit z následujících nerovností:

: <math>(1-p)^M + (1-p)^{M+1} \leq 1 < (1-p)^{M-1} + (1-p)^M.</math>

Golomb ve své práci tvrdí, že pro velká M je velmi malý postih, když vybereme <math>M = \left\lfloor \frac{-1}{\log_2(1-p)}\right\rfloor</math>.

Golombovo kování je ekvivalentní [[Huffmanovo kódování|Huffmanovu kódování]] pro zadané pravděpodobnosti, kdyby bylo možné vytvořit Huffmanův kód (což pro geometrické rozdělení nejde, neboť se nejedná o diskrétní rozdělení).

=== Případ s celými čísly ===
Golombovo bylo navrženo k zakódování sekvencí nezáporných čísel. Může být ale snadno rozšířeno tak, aby bylo schopné zakódovat i obecné posloupnosti celých čísel. Všem vstupním hodnotám přiřadíme nové hodnoty z množiny celých kladných čísel, tak aby byly unikátní a mohli jsme je později přiřadit zpět. Posloupnost začínající: 0,-1,1,-2,2,-3,3,-4,5 … n-tá negativní hodnota (tj. -n) je namapována jako n-té liché číslo (2n-1), a m-té kladné číslo je vyjádřeno jako m-té sudé číslo (2m). Optimální prefixový kód vznikne jen v případě, že kladná čísla a hodnoty záporných čísel odpovídají tomu samému geometrickému rozdělení.

== Jednoduchý algoritmus ==
Následující algoritmus popisuje, jak zakódovat hodnotu na vstupu pomocí Rice-Golombova kódování.

# Zaokrouhlit ''M'' na celočíselnou hodnotu.
# Pro číslo ''N'', které chceme zakódovat, najděme
## podíl = ''q'' = int[''N''/''M'']
## zbytek = ''r'' = ''N'' mod ''M''
# Vygenerujeme kódové slovo
## Formát kódu : <zakódovaný podíl><zakódovaný zbytek>, kde
## zakódovaný podíl je ([[unární kódování|zakódován unárně]])
### Zakódujeme ''q'' jako sekvenci ''q'' 1 a na konec přidáme 0
## kód zbytku je ([[zkrácené binární kódování|zakódován zkráceně binárně]])
### Když ''M'' je mocnina dvou, bude potřeba <math>\log_2(M)</math> bitů. (Riceovo kódování)
### Když ''M'' není mocnina 2, tak <math>b = \lceil\log_2(M)\rceil</math>
#### Když <math>r < 2^b-M</math> zakódujeme ''r'' pomocí standardního binárního kódování délky ''b''-1 bitů.
#### Když <math>r \ge 2^b-M</math> zakódujeme číslo <math>r+2^b-M</math> pomocí standardního binárního kódování o délce ''b'' bitů.

== Příklad ==
Nastavme ''M'' = 10. Tedy <math>b = \lceil\log_2(10)\rceil = 4</math>. Ořez pak bude <math>2^b-M = 16-10 = 6</math>

{|border="0" cellspacing="8" cellpadding="0"
|-valign="top"
|
{|border="1" class="wikitable"
|-
!colspan="2"|Zakódování podílu
|-
!''q''||výstupní bity
|-
|0||0
|-
|1||10
|-
|2||110
|-
|3||1110
|-
|4||11110
|-
|5||111110
|-
|6||1111110
|-
|:||:
|-
|N||<N opakování 1>0
|}
|
{|border="1" class="wikitable"
|-
!colspan="4"|Zakódování zbytku
|-
!''r''||posun||binárně||bity na výstupu
|-
|0||0||0000||000
|-
|1||1||0001||001
|-
|2||2||0010||010
|-
|3||3||0011||011
|-
|4||4||0100||100
|-
|5||5||0101||101
|-
|6||12||1100||1100
|-
|7||13||1101||1101
|-
|8||14||1110||1110
|-
|9||15||1111||1111
|}
|}

Například pro Golomb-Rice kódování s parametrem ''M''=10 a číslem pro zakódování 42 se nejprve spočítá ''q''=4 a ''r''=2. Pak se obě částí zakódují ''q''=11110 a ''r''=010 a výsledné kódové slovo vznikne složením těchto dvou částí. Části už není potřeba od sebe oddělovat, protože první část poznáme snadno – končí tam, kde se poprvé objeví nula.

== Ukázkový kód algoritmu ==
Tento základní kód předpokládá Riceovo kódování, tedy že ''M''=2<sup>k</sup>.

=== Zakódování ===
<syntaxhighlight lang="cpp">
 void golombEncode(char* vstup, char* vystup, int M)
 {
     IntReader intreader(vstup);
     BitWriter bitwriter(vystup);
     while(intreader.hasLeft())
     {
         int num = intreader.getInt();
         int q = num / M;
         for (int i = 0 ; i < q; i++)
             bitwriter.putBit(true);   // zapíše q jedniček
         bitwriter.putBit(false);      // zapíše jednu nulu
         int v = 1;
         for (int i = 0 ; i < log2(M); i++)
         {            
             bitwriter.putBit( v & num );  
             v = v << 1;         
         }
     }
     bitwriter.close();
     intreader.close();
 }
</syntaxhighlight>

=== Dekódování ===
<syntaxhighlight lang="cpp">
 void golombDecode(char* vstup, char* vystup, int M)
 {
     BitReader bitreader(vstup);
     IntWriter intwriter(vystup);
     int q = 0;
     int nr = 0;
     while (bitreader.hasLeft())
     {
         nr = 0;
         q = 0;
         while (bitreader.getBit()) q++;     
         for (int a = 0; a < log2(M); a++)   
             if (bitreader.getBit())
                 nr += 1 << a;
         nr += q*M;                          
         intwriter.putInt(nr);               
     }
     bitreader.close();
     intwriter.close();
 }
</syntaxhighlight>

== Použití pro [[Run-length encoding|run-length kódování]] ==
[[Soubor:GolombCodeRedundancy.svg|300px|Obrázek ukazuje Golombovo kódování, když vybíráme M optimálně pro dané ''p''&nbsp;≥&nbsp;1/2.|náhled|vpravo]]

Máme-li abecedu o dvou symbolech, nebo množinu dvou událostí ''P'' a ''Q'' s pravděpodobnostmi ''p'' a (1 – ''p''), kde <math>p\geq \frac{1}{2}</math>. Golombovo kódování může být použito k zakódování nula nebo více ''P'' oddělených jedním ''Q''. V takovém případě je nejlepší nastavit parametr ''M'' jako nejbližší celé číslo k <math> \frac{-1}{\log_{2}p}</math>. Když <math>p=\frac{1}{2}</math>, ''M'' = 1 a Golombovo kódování je shodné s unárním.

== Aplikace ==
Riceovo kódování je použito v několika kódech pro zpracování signálu pro predikci zbytků.
V prediktivních algoritmech, kde zbytky mají tendenci se rozdělit tak, že odpovídají dvoustrannému geometrickému rozdělení s malými zbytky častějšími než velkými, Riceův kód téměř odpovídá Huffmanovu kódu pro dané rozdělení s tou výhodou, že nemusí přenášet Huffmanovu tabulku.
Jediný signál, který neodpovídá geometrickému rozdělení je sinová vlna, kde jsou velké a malé zbytky podobně pravděpodobné.

Několik bezeztrátových zvukových kompresních algoritmů jako jsou [[Shorten]],<ref>{{Citace elektronického periodika |titul=man shorten |url=http://www.etree.org/shnutils/shorten/support/doc/shorten.txt |datum přístupu=2013-05-18 |url archivu=https://web.archive.org/web/20140130053525/http://www.etree.org/shnutils/shorten/support/doc/shorten.txt |datum archivace=2014-01-30 |nedostupné=ano }}</ref> [[FLAC]],<ref>[http://flac.sourceforge.net/documentation_format_overview.html FLAC documentation: format overview]</ref> [[Apple Lossless]], a [[MPEG-4 ALS]] používá Riceovo kódování v rámci svého kódovacího procesu. Riceovo kódování je také použito pro bezeztrátovou kompresi obrázků [[FELIICS]].

Rice-Golombovo kódování je použito jako součást [[Riceův algoritmus|Riceova algoritmu]] pro bezeztrátovou kompresi obrázků. Na grafu je vidět porovnání kompresních poměrů Riceova kódování a algoritmu [[Gzip]].

[[Soubor:Golomb coded Rice Algorithm experiment Compression Ratios.png|rám|střed|Experiment - zkoumání kompresních poměrů]]

Riceovo kódování může produkovat dlouhé posloupnosti jedniček pro podíl zakódovaný unárně, často je tedy nutné nastavit nějaký limit. Modifikovaná verze Rice-Golombova kódování umožňuje nahradit dlouhé sekvence jedniček pomocí rekurzivního Rice-Golombova kódování.

== Reference ==
{{Překlad|en|Golob coding|552840926}}
<references />

== Literatura ==
* Golomb, S.W. (1966). [http://urchin.earth.li/~twic/Golombs_Original_Paper/ , Run-length encodings. IEEE Transactions on Information Theory, IT--12(3):399--401 ]
* R. F. Rice (1971) and R. Plaunt, [http://dx.doi.org/10.1109/TCOM.1971.1090789 , "Adaptive Variable-Length Coding for Efficient Compression of Spacecraft Television Data, " IEEE Transactions on Communications, vol. 16(9), pp.&nbsp;889–897, Dec. 1971.]
* R. F. Rice (1979), "Some Practical Universal Noiseless Coding Techniques, " Jet Propulsion Laboratory, Pasadena, California, JPL Publication 79—22, Mar. 1979.
* Witten, Ian Moffat, Alistair Bell, Timothy. "Managing Gigabytes: Compressing and Indexing Documents and Images." Second Edition. Morgan Kaufmann Publishers, San Francisco CA. 1999 {{ISBN|1-55860-570-3}}
* David Salomon. "Data Compression",{{ISBN|0-387-95045-1}}.
* S. Büttcher, C. L. A. Clarke, and G. V. Cormack. [http://www.ir.uwaterloo.ca/book/ Information Retrieval: Implementing and Evaluating Search Engines] {{Wayback|url=http://www.ir.uwaterloo.ca/book/ |date=20201005195805 }}. MIT Press, Cambridge MA, 2010.

== Externí odkazy ==
* {{Commonscat}}

{{Autoritní data}}

[[Kategorie:Algoritmy]]
[[Kategorie:Komprese dat]]
[[Kategorie:Teorie kódování]]