Unární kódování

Unární kódování je kódování, které zakóduje přirozené číslo n pomocí n po sobě následujících jedniček a jednou nulou (pokud je přirozené číslo chápáno jako nezáporné celé číslo) nebo jako n − 1 po sobě následujících jedniček následovaných jednou nulou (když přirozené číslo je chápáno jako kladné celé číslo). Například 5 je reprezentována 111110 nebo 11110. Některé varianty tohoto kódování prohazují 0 a 1. Nuly a jedničky můžeme považovat za zaměnitelné bez ztráty obecnosti. Unární kódování tvoří prefixový kód.

Unární kódování je optimálním kódováním pro následující diskrétní pravděpodobnostní rozdělení

${\displaystyle \operatorname {P} (n)=2^{-n}\,}$

pro ${\displaystyle n=1,2,3,...}$.

Kódujeme-li po symbolech, pak je unární kódování optimální pro každé geometrické rozdělení

${\displaystyle \operatorname {P} (n)=(k-1)k^{-n}\,}$

pro každé k ≥ φ = 1.61803398879…, zlatý řez, nebo více obecně, pro každé diskrétní rozdělení pro které platí

${\displaystyle \operatorname {P} (n)\geq \operatorname {P} (n+1)+\operatorname {P} (n+2)\,}$

pro ${\displaystyle n=1,2,3,...}$.

Přestože je kódování optimální pro výše zmíněné pravděpodobnosti, Golombovo kódování dosahuje lepšího kompresního poměru pro geometrická rozdělení, protože nepovažuje vstupní symboly za nezávislé. Ze stejného důvodu funguje aritmetické kódování lépe pro obecná rozdělení pravděpodobnosti.

Modifikované unární kódování je použito v UTF-8. Unární kódování je také použito v kódováních, která používají schémata pro dělení kódových slov jako např. Golombovo kódování.

Reference

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