> codifica aritmetica | bit frazionari | ottimale <
// Codifica aritmetica - codifica a bit frazionari vicina al limite di entropia
Quasi ottimale
Si avvicina al limite teorico di entropia per un'elevata efficienza di compressione.
Bit frazionari
Codifica i simboli usando bit frazionari in base alla loro probabilità.
Streaming
Può codificare e decodificare i dati in modo incrementale man mano che arrivano.
>> informazioni tecniche
Come funziona la codifica aritmetica:
La codifica aritmetica rappresenta l'intero messaggio come un unico numero nell'intervallo [0,1). Ogni simbolo restringe questo intervallo in base alla propria probabilità. L'intervallo finale viene codificato come frazione binaria, ottenendo una compressione molto vicina al limite di entropia.
Processo di codifica:
Testo: "AAB" Probabilità: A=0.67, B=0.33 1. Inizio: [0, 1) 2. 'A': [0, 0.67) 3. 'A': [0, 0.45) 4. 'B': [0.30, 0.45) Output: Qualsiasi numero in [0.30, 0.45) Binario: 0.010011...
Perché usare la codifica aritmetica:
- >Migliori rapporti di compressione
- >Si avvicina al limite di entropia
- >Gestisce qualsiasi distribuzione di probabilità
- >Usata in JPEG2000 e H.264
- >Brevetti scaduti (2024)
>> domande frequenti
Che cos'è la codifica aritmetica?
La codifica aritmetica è una forma di codifica entropica che converte una sequenza di simboli in un unico numero frazionario. A differenza della codifica di Huffman, che utilizza bit interi, la codifica aritmetica può usare bit frazionari per simbolo.
Perché è migliore di Huffman?
La codifica aritmetica può ottenere una compressione arbitrariamente vicina al limite di entropia, mentre Huffman è limitata a bit interi per simbolo. Per probabilità fortemente sbilanciate la codifica aritmetica può essere significativamente migliore.
Che cos'è il parametro di precisione?
La precisione controlla il numero di bit utilizzati per i calcoli interni. Una precisione maggiore permette di codificare messaggi più lunghi ma richiede più memoria. 16 bit sono di solito sufficienti per testi brevi.
Dove viene usata la codifica aritmetica?
La codifica aritmetica è utilizzata in standard di compressione moderni come il video H.264/H.265, le immagini JPEG2000 e la modalità DEFLATE64 di ZIP. In passato era soggetta a brevetti, ma i principali sono scaduti.
// Esempio svolto
| Step | Symbol | low | high |
|---|---|---|---|
| 0 | — | 0 | 1 |
| 1 | A | 0 | 0.5 |
| 2 | B | 0.25 | 0.375 |
| 3 | C | 0.34375 | 0.375 |
// Esempi di codice
Model P(A)=0.5 P(B)=0.25 P(C)=0.25 -> A:[0,0.5) B:[0.5,0.75) C:[0.75,1)
Update width = high - low
high = low + width * cum_high(symbol)
low = low + width * cum_low(symbol)
Output any value in [0.34375, 0.375) e.g. 0.34375 = 0.01011b (5 bits = 1 + 2 + 2)
Entropy -log2 P(A) - log2 P(B) - log2 P(C) = 1 + 2 + 2 = 5 bits
>> Altre domande
D: Perché la codifica aritmetica è spesso migliore di Huffman?
R: Huffman assegna a ogni simbolo un numero intero di bit (almeno 1). La codifica aritmetica codifica l’intero messaggio come un’unica frazione in [0, 1) e si avvicina all’entropia, anche per simboli con probabilità oltre il 50 % che in Huffman costano comunque 1 bit.
D: Come funziona l’esempio degli intervalli ABC?
R: Con A=0,5, B=0,25, C=0,25 l’intervallo si restringe a ogni simbolo: [0,1) → [0,0,5) → [0,25, 0,375) → [0,34375, 0,375). Qualsiasi numero al suo interno, ad esempio 0,34375 = 0,01011 in binario, codifica «ABC» con 5 bit, esattamente l’entropia.
D: Dove si usa la codifica aritmetica?
R: In CABAC di H.264/HEVC, nel codificatore MQ di JPEG 2000 e JBIG2, e in varianti come range coding (AV1) e ANS (zstd, JPEG XL). I primi brevetti ne frenarono la diffusione; oggi sono per lo più scaduti.