Aritmetické kódování
Teorie:
Aritmetické kódování je algoritmus bezeztrátové komprese dat, který provádí kódování celého vstupního řetězce do jednoho čísla.
Algoritmus kódování:
-
nastaví počáteční interval na [0,1),
-
projde vstupním řetězcem a spočítá četnosti výskytu jednotlivých znaků,
-
provede rozdělení pravděpodobnosti výskytu znaků do intervalu [0,1),
-
provede výpočet nových hranic intervalu pro každý znak vstupního řetězce,
-
provede výpočet výstupního čísla, které je střední hodnota z posledního intervalu,
-
provede převod výstupního čísla do binárního tvaru.
Algoritmus dekódování:
-
provádí převod výstupního čísla z binárního tvaru do desítkového tvaru,
-
nastaví počáteční interval na [0,1),
-
rozdělí interval [0,1) podle pravděpodobností výskytu jednotlivých znaků,
-
zkontroluje do jakého intervalu spadá výstupní číslo a tím určí výsledný znak,
-
provede výpočet nové hodnoty výstupního čísla,
-
zkontroluje do jakého intervalu spadá nové výstupní číslo a tím určí výsledný znak,
-
poslední dva kroky se opakují tak dlouho, dokud nebude dekódován celý řetězec.
(c) 2016 Ivan Tvorogov, Pavel Rajmic, Ústav telekomunikací, FEKT, VUT v Brně