Snění o aritmetickém kódování

🌐/ SW

Jde mi o ukládání řady celých kladných čísel s limitem každého čísla.

Obecně chci uložit třeba čísla 3 v rozsahu 0-12, 8 v rozsahu 0-17, 0 v rozsahu 0-22.

Uložená informace odpovídá

log2(13)+log2(18)+log2(23) = 12,393926676 bitů.

Pokud bychom chtěli ukládat informaci po celých bitech, tak uložíme v rozsahu 0-15(4 bity), 0-31(5 bitů), 0-31(5 bitů) - tj. celkem 14 bitů.

S každým číslem ztratíme část bitu, který nebyl využit. Výhodou ukládání po bitech jsou rychlé bitové operace. Bitový posun je skoro to nejrychlejší a nejjednodušší, co může počítač dělat.

Naproti tomu ukládání informace po částech bitu vyžaduje násobení pro ukládání (celkem rychlé) a dělení pro čtení (hodně pomalé).

Základní princip je podobný uložení čísla v číselné soustavě.

Např. v desítkové soustavě je

1548741 = 1*10^6 + 5*10^5 + 4*10^4 + 8*10^3 + 7*10^2 + 4*10^1 + 1*10^0.

V binární soustavě je

11011 = 1*2^4 + 1*2^3 +0*2^2 +1*2^1 + 1*2^0

Tady se ale ukládá každá cifra v jiné číselné soustavě - o to je to zajímavější.

3 * 1 + 8 * 13 + 0 * 13*18

---

Teoreticky je tedy možné uložit do jednoho (velkého) čísla libovolný počet čísel v definovaném rozsahu, prakticky bych se ale měl vejít do uint64_t.

Je tedy potřeba naakumulovanou hodnotu rovnou i odsypávat ven.

To je možné, pokud se provede zaokrouhlení nahoru.

Navíc musí být jednoznačně definováno, kdy dojde k odsypání, aby se dal proces replikovat při dekódování.

Teď mi jako nejvhodnější okamžik připadá, že bych měl odsypávat, pokud by vynásobením base došlo k přetečení.

Je to celkem ideální, protože pokud budu odsypávat z velkého čísla po malých kouscích, tak zaokrouhlovací ztráty (musím zaokrouhlovat nahoru) budou zanedbatelné.

---

#include <stdbool.h>
#include <stdint.h>

bool safe_mul_int(int a, int b, int *res) {
    return __builtin_mul_overflow(a, b, res);  // vrací true při přetečení
}

---

Moje teorie

Base udává, kolik bitů je zafixováno. Zafixované bity už se nezmění.

Mělo by být absolutně bezpečné ponížit kdykoliv base o všechny bity, které jsou kompletní.

Tj. pokud beru výstupní základ jako 95 (ASCII nad ' '), tak to dává 6,569855608 bitů.

Mohu odebrat bity kdykoliv, kdy je base >= 95.

Je tam problém? představme si, že je base 115 a hodnota 104.

odeberu hodnotu 104 % 95 = 9/95

a zůstane mi 104 / 95 = 1 z 115+94/95 = 2.

Došlo k celkem brutálnímu zaokrouhlení na 1 bit, což není úplně zdravé.

Pokud ale odeberu bity, když je base >= 95*95, tak zaokrouhlení už není tak hrozné.

Nejefektivněji odeberu bity jen, když se mi base už nevejde do 32 bitového čísla.

*13*18*23*457*14/95*564/95/95*4564*12|/95/95/95/95/95
encoded[8]={50,30,32,27,0,30,20,15,};

Takto vypadá testovací příklad.

Pokud budu postupovat opačně, musím jet od konce?

*95*95*95*95*95

ANO a budu muset také úplně obrátit pořadí operací.

Příklad

*13	        13 **
*18	       234 **
*23	      5382 ** 
*457	   2459574 ** 
*14	  34434036 ** 
/95	    362464
*564	 204429696 ** 
/95	   2151892
/95	     22652
*4564	 103383728 **
*12	1240604736 **
----------------
/95	  13058998
/95	    137464
/95	      1447
/95	        16
/95	         1

Modified 2025-12-08 20:02:46.719 by petr.