Loading AI tools
La codifica aritmetica è una tecnica di compressione senza perdita di informazione. Normalmente in informatica i dati sono rappresentati come un insieme fisso di bit, per esempio i caratteri sono spesso rappresentati con otto bit. La codifica aritmetica partendo dal presupposto che alcuni simboli tendono ad apparire più frequentemente di altri assegna dei codici di lunghezza variabile ai simboli al fine di minimizzare il numero totale di bit da trasmettere. Questa strategia viene utilizzata anche da altri sistemi di codifica, come la codifica di Huffman, ma mentre la codifica di Huffman associa una specifica codifica a ogni singolo simbolo la codifica aritmetica associa una singola codifica all'intero messaggio o a blocchi di questo.
Definizione del modello
La codifica aritmetica produce una compressione sub-ottima (secondo la teoria della compressione dei dati il valore ottimale è −log2P bit per ogni simbolo con probabilità P). L'algoritmo di compressione parte definendo un modello dei dati, una loro distribuzione probabilistica, questa influenza in misura preponderante la bontà della compressione.
Per esempio, un semplice modello statico potrebbe definire:
- 60% di possibilità di avere un simbolo NEUTRO;
- 20% di possibilità di avere un simbolo POSITIVO;
- 10% di possibilità di avere un simbolo NEGATIVO;
- 10% di possibilità di avere un simbolo di FINE-DEL-FILE (questo simbolo serve al decodificatore per dire che il flusso da decodificare è terminato).
Il modello di esempio utilizza solo quattro simboli ed è un modello didattico, ma conoscendo il contesto si possono sviluppare modelli più sofisticati, per esempio se si sa di dover codificare un testo in inglese si sa che la lettera "u" è molto più comune della lettera "Q" o "q" e quindi si potranno assegnare le probabilità di conseguenza. I modelli possono anche essere adattivi, in questo caso adattano le probabilità dei simboli all'andamento dei dati. Ovviamente il decodificatore deve conoscere il modello usato dal codificatore.
Un semplice esempio
Per chiarificare discuteremo un semplice esempio. Supponiamo di avere una sequenza di simboli, che provengono da un alfabeto con tre elementi: A, B, C. Un semplice codificatore a blocchi potrebbe trasformare ogni simbolo in una sequenza di due bit, ma sarebbe uno spreco, due bit possono esprimere quattro combinazioni e quindi una combinazione non verrebbe mai usata.
Possiamo pensare di rappresentare i simboli come un numero razionale compreso tra 0 e 1 in base 3 e di rappresentare ogni simbolo come una cifra del numero. Per esempio la sequenza "ABBCAB" verrebbe convertita in 0,0112013. Questa poi potrebbe essere convertita in base due e potrebbe diventare per esempio 0,0010110012 — questa sequenza usa 9 bit e al posto dei 12 bit richiesti da un codificatore ingenuo e quindi occupa il 25% in meno. Il decodificatore ovviamente dovrebbe fare i passi opposti per ottenere la sequenza di partenza.
Codifica e decodifica
In questa sezione si generalizzerà l'idea appena esposta, comunque i passi fondamentali sono gli stessi tranne che l'ultimo. Fondamentalmente si hanno tre passi:
- Il nuovo simbolo viene prelevato;
- Il corrente intervallo di codifica viene definito (all'inizio l'intervallo di codifica è quello massimo quindi [0,1) ma durante la codifica si riduce);
- Si calcola la probabilità dei simboli, questo passo è necessario se l'algoritmo stima le probabilità durante la codifica, se sono definite in modo fisso questo passo non viene eseguito.
Il codificatore suddivide il corrente intervallo in un sottointervallo che viene calcolato tenendo conto della probabilità di un certo simbolo di comparire.
Seguendo l'esempio precedente suddividiamo gli intervalli tramite una probabilità fissa.
- Il simbolo NEUTRO ha intervallo [0, 0,6)
- Il simbolo POSITIVO ha intervallo [0,6, 0,8)
- Il simbolo NEGATIVO ha intervallo [0,8, 0,9)
- Il simbolo FINE-DEL-FILE ha intervallo [0,9, 1)
Quando tutti i simboli vengono codificati il risultato è un intervallo che identifica in modo non ambiguo la sequenza di simboli che l'ha generato. Quindi ogni sistema che conosce il modello e l'intervallo è in grado di ricostruire la sequenza di simboli.
Comunque non è necessario trasmettere l'intervallo, basta trasmettere una frazione che si trova all'interno dell'intervallo. In particolare basta trasmettere abbastanza cifre della frazione in modo da eliminare gli altri intervalli.
Esempio
Supponiamo di dover decodificare la serie di simboli associati al valore 0,538, si inizia la decodifica partendo con un intervallo [0, 1) e utilizzando il modello indicato sopra si divide l'intervallo in quattro sottointervalli. Il primo simbolo secondo il nostro modello è NEUTRO dato che il numero vale meno di 0,6 e quindi ricade nell'intervallo NEUTRO.
Adesso dividiamo l'intervallo [0, 0,6) in sottointervalli secondo le probabilità indicate all'inizio e otteniamo:
- Il simbolo NEUTRO ha intervallo [0, 0,36) "60% dell'intervallo [0, 0,6)"
- Il simbolo POSITIVO ha intervallo [0,36, 0,48) "20% dell'intervallo [0, 0,6)"
- Il simbolo NEGATIVO ha intervallo [0,48, 0,54) "10% dell'intervallo [0, 0,6)"
- Il simbolo FINE-DEL-FILE ha intervallo [0,54, 0,6) "10% dell'intervallo [0, 0,6)"
Il numero 0,538 ricade nell'intervallo [0,48, 0,54) e quindi il secondo simbolo è NEGATIVO.
Ripetiamo nuovamente la suddivisione del nuovo intervallo e otteniamo:
- Il simbolo NEUTRO ha intervallo [0,48, 0,516) "60% dell'intervallo [0,48, 0,54)"
- Il simbolo POSITIVO ha intervallo [0,516, 0,528) "20% dell'intervallo [0,48, 0,54)"
- Il simbolo NEGATIVO ha intervallo [0,528, 0,534) "10% dell'intervallo [0,48, 0,54)"
- Il simbolo FINE-DEL-FILE ha intervallo [0,534, 0,540) "10% dell'intervallo [0,48, 0,54)"
Il numero 0,538 ricade entro l'intervallo [0,535, 0,54) che appartiene al simbolo FINE-DEL-FILE quindi abbiamo raggiunto la fine del flusso di simboli da decodificare. È da notare che anche i numeri 0,534, 0,535, 0,536, 0,537 o 0,539 sarebbero andati comunque bene. Questo potrebbe far pensare che il sistema soffra di alcune inefficienze, in realtà questo si ottiene perché nell'esempio abbiamo lavorato in base decimale, convertendo il tutto in base binaria avremmo usato come numero di decodifica 0,10001010 (che in decimale vale 0,5390625) che costa 8 bit.
La nostra codifica occupa 8 bit che è meglio dei 12 bit utilizzati da un codificatore banale ma comunque sono molti più bit di quelli definiti a livello teorico. Secondo la teoria dell'entropia ogni simbolo dovrebbe occupare 1,57 bit che moltiplicato per i tre simboli trasmessi fa 4,71 bit. Questa differenza tra il miglior risultato a livello teorico e il risultato del codificatore è dovuto al numero ridotto di simboli codificati, all'aumento del numero di simboli da codificare la differenza con il risultato teorico si assottiglia notevolmente. Inoltre le probabilità indicate nell'esempio sono molto diverse da quelle presenti nel messaggio codificato. Le reali probabilità del messaggio sono [0,33, 0, 0,33, 0,33], usando queste probabilità gli intervalli sarebbero [0, 1/3); [1/9, 2/9); [5/27, 6/27); in binario diverrebbero [1011110, 1110001] e quindi si potrebbe inviare che solamente il valore 111 per indicare la sequenza di simboli. Questo mostra anche che una statistica sbagliata può peggiorare significativamente le prestazioni della codifica.
Gli esempi precedenti contengono delle semplificazioni, una di queste è che il decodificatore prima lavori con cifre a infinite precisione e che in seguito cerchi la frazione binaria. In realtà la maggior parte dei decodificatori lavorano con un numero di cifre finite pari al numero massimo di simboli da decodificare in modo da non dover far conversioni. Nell'esempio precedente quindi il decodificatore avrebbe utilizzato subito 8 bit di precisione.
| Simbolo | Probabilità (espressa come frazione) | Intervallo indicato con otto bit di precisione (come frazione) | Intervallo indicato con otto bit di precisione (in binario) | Estremi in binario |
|---|---|---|---|---|
| A | 1/3 | [0, 85/256) | [0,00000000, 0,01010101) | 00000000 - 01010100 |
| B | 1/3 | [85/256, 171/256) | [0,01010101, 0,10101011) | 01010101 - 10101010 |
| C | 1/3 | [171/256, 1) | [0,10101011, 1,00000000) | 10101011 - 11111111 |
Il processo chiamato "rinormalizzazione" serve a mantenere la precisione finita durante la codifica dei simboli. Ogni volta che la gamma dei valori che specificano gli intervalli sono ridotti fino al punto di avere i bit iniziali degli intervalli iniziali questi sono inviati in fondo ai numeri binari. Questo nell'esempio trattato prima accede in due casi su tre.
| Simbolo | Probabilità | Range | Numero | Range dopo la rinormalizzazione |
|---|---|---|---|---|
| A | 1/3 | 00000000 - 01010100 | 0 | 00000000 - 10101001 |
| B | 1/3 | 01010101 - 10101010 | None | 01010101 - 10101010 |
| C | 1/3 | 10101011 - 11111111 | 1 | 01010110 - 11111111 |
Codifica Huffman
Questa codifica si basa su principi simili a quelli della codifica aritmetica e in effetti può essere vista come un caso particolare della codifica aritmetica dato che la codifica aritmetica trasforma l'intero messaggio in un numero in base N mentre la codifica di Huffman rappresenta ogni simbolo come un elemento base N.
Si può considerare la codifica Huffman una codifica aritmetica che arrotonda la frequenza di ogni simbolo alla più vicina potenza di un mezzo (0,5). Per questo motivo la codifica di Huffman mostra dei risultati modesti se applicata ad alfabeti con distribuzioni del tipo 0,75 o 0,375. Le distribuzioni di questo tipo sono molto diffuse soprattutto in alfabeti con pochi simboli.
Per esempio si consideri l'alfabeto {a, b, c} con distribuzione equiprobabile di 1/3. La codifica Huffman produce i seguenti codici:
- a → 0: 50%
- b → 10: 25%
- c → 11: 25%
Questi codici occupano (2+2+1)/3 ≈ 1,667 bit per simbolo con la codifica Huffman. La codifica aritmetica produce 1,585 bit per simbolo e quindi l'inefficienza è del 5%.
Ma se si considera un alfabeto binario del tipo {0, 1} con distribuzione 0,625 e 0,375, la codifica Huffman assegna a ogni simbolo la probabilità del 50% e quindi genera un alfabeto con due simboli, in sostanza non comprime i dati. La codifica aritmetica invece ottiene un incremento del:
- 1 - (0,625(−log2 0,625) + 0,375(−log2 0,375)) ≈ 4,6%.
Nel caso un simbolo sia molto più probabile per esempio supponendo che abbia una probabilità del 95% otteniamo un incremento del:
- 1 - (0,95(−log2 0,95) + 0,05(−log2 0,05)) ≈ 71,4%.
Un modo semplice per aggirare il problema è creare un nuovo alfabeto concatenando i simboli al fine di ottenere dei nuovi simboli con una distribuzione migliore per l'algoritmo. Per esempio si potrebbero concatenare i simboli al fine di ottenere:
- 000: 85,7%
- 001, 010, 100: 4,5%
- 011, 101, 110: 0,24%
- 111: 0,0125%
Questi verrebbero codificati con 1,3 bit per ogni gruppo di tre simboli quindi con 0,433 bit per simbolo, un notevole miglioramento rispetto al bit per simbolo della codifica iniziale.
Codifica a intervalli
La codifica a intervalli è un altro modo di vedere la codifica aritmetica. La codifica aritmetica è la codifica a intervalli sono sostanzialmente lo stesso concetto implementato in modo leggermente diverso. Spesso se si lavora su singoli bit si parla di codifica aritmetica mentre se si lavora su byte si parla di codifica a intervalli ma questa distinzione non è accettata universalmente. Spesso si afferma che questa codifica è libera da brevetti ma dato che il concetto che sta alla base è lo stesso l'affermazione è quantomeno dubbia.
L'idea che sta alla base della codifica è quello di prendere un intervallo e di suddividerlo in sottointervalli in modo proporzionale alla probabilità di ogni simbolo. Però a differenza della codifica aritmetica non si utilizza l'intervallo [0, 1) Ma un intervallo molto più grande, non negativo e intero, per esempio l'intervallo da 000 000 000 000 a 999 999 999 999. Quando i sottointervalli sono abbastanza differenziati da rendere nota la prima cifra questa viene spostata in fondo all'intervallo, questa operazione è come se portasse a una moltiplicazione dell'intervallo mantenendo sempre sufficienti numeri interi nell'intervallo.
Quindi se si trascura il fatto che l'intervallo è molto più grande e si usano numeri interi invece di frazioni le due tecniche sono uguali. Il fatto di applicare la moltiplicazione dell'intervallo sul byte (la codifica aritmetica effettua la rinormalizzazione sul bit) riduce leggermente la compressione ma questa compressione lavorando solo su numeri interi e mediamente più veloce della codifica aritmetica.
Molte implementazioni della codifica aritmetica sono protette da brevetti statunitensi. Diverse implementazioni inoltre sono utilizzate in standard internazionali, ma normalmente queste implementazioni sono distribuite con licenze RAND. Queste licenze a volte non prevedono il pagamento del brevetto per la maggior parte degli usi oppure prevedono compensi di modesta entità. Questo può essere accettabile per un software commerciale ma normalmente non è considerato ammissibile dai programmi open source e dal software libero in genere.
Tra le società note per il possesso di brevetti sulla codifica aritmetica si segnala IBM. È opinione diffusa che non si possano sviluppare algoritmi con codifica aritmetica senza infrangere un brevetto statunitense. Comunque alcuni brevetti sono scaduti e quindi in teoria si potrebbero utilizzare quelle implementazioni ma dato che non c'è la certezza che quelle implementazioni siano coperte parzialmente anche da brevetti successivi la maggior parte dei programmatori preferisce non utilizzare la codifica aritmetica.
Per esempio il programma bzip2 inizialmente gestiva la codifica aritmetica ma in seguito per paura dI cause legali i programmatori decisero di dismettere la codifica. Anche la codifica JPEG gestisce questa codifica insieme alla codifica Huffman, ma per evitare di dover pagare eventuali brevetti la maggior parte dei programmi gestisce solo la codifica di Huffman.
Tra i brevetti sulla codifica aritmetica si segnalano:
- (EN) US4122440, United States Patent and Trademark Office, Stati Uniti d'America. — (IBM) inviato il 4 marzo 1977, accettato il 24 ottobre 1978 (scaduto)
- (EN) US4286256, United States Patent and Trademark Office, Stati Uniti d'America. — (IBM) accettato il 25 agosto 1981 (presumibilmente scaduto)
- (EN) US4467317, United States Patent and Trademark Office, Stati Uniti d'America. — (IBM) accettato il 21 agosto 1984 (presumibilmente scaduto)
- (EN) US4652856, United States Patent and Trademark Office, Stati Uniti d'America. — (IBM) accettato il 4 febbraio 1986 (presumibilmente scaduto)
- (EN) US4891643, United States Patent and Trademark Office, Stati Uniti d'America. — (IBM) inviato il 15 settembre 1986, accettato il 2 gennaio 1990
- (EN) US4905297, United States Patent and Trademark Office, Stati Uniti d'America. — (IBM) accettato il 27 febbraio 1990
- (EN) US4933883, United States Patent and Trademark Office, Stati Uniti d'America. — (IBM) accettato il 12 giugno 1990
- (EN) US4935882, United States Patent and Trademark Office, Stati Uniti d'America. — (IBM) accettato il 19 giugno 1990
- (EN) US4989000, United States Patent and Trademark Office, Stati Uniti d'America. — inviato il 19 giugno 1989, accettato il 29 gennaio 1991
- (EN) US5099440, United States Patent and Trademark Office, Stati Uniti d'America. — (IBM) inviato il 5 gennaio 1990, accettato il 24 marzo 1992
- (EN) US5272478, United States Patent and Trademark Office, Stati Uniti d'America. — (Ricoh) inviato il 17 agosto 1992, accettato il 21 dicembre 1993
Nota: l'elenco non è esaustivo.
Ogni differente tecnica di codifica mostra un rapporto di compressione e un tempo di compressione diverso. Il fattore di compressione normalmente varia in modo insignificante (meno dell'1% normalmente) mentre i tempi di compressione e decompressione variano significativamente, alcuni metodi sono fino a dieci volte più rapidi di altri. La scelta del compressore migliore non risulta semplice dato che le prestazioni dipendono molto dai dati in ingresso. Alcuni compressori lavorano bene con pochi dati in ingresso, altri con alfabeti complessi, diversi lavorano solo con alfabeti binari.
- Jorma Rissanen, Generalized Kraft Inequality and Arithmetic Coding (PDF), in IBM Journal of Research and Development, vol. 20, n. 3, maggio 1976, pp. 198–203. URL consultato il 21 settembre 2007.
- J.J. Rissanen and G.G. Langdon, Jr., Arithmetic coding (PDF), in IBM Journal of Research and Development, vol. 23, n. 2, marzo 1979, pp. 149–162. URL consultato il 22 settembre 2007 (archiviato dall'url originale il 28 settembre 2007).
- Ian H. Witten, Radford M. Neal, and John G. Cleary, Arithmetic Coding for Data Compression (PDF), in CACM, vol. 30, n. 6, giugno 1987, pp. 520–540. URL consultato il 21 settembre 2007.
- David J.C. MacKay (2003) Information theory, inference and learning algorithms, CUP, ISBN 0-521-64298-1, (also available online)
Wikimedia Commons contiene immagini o altri file su Codifica aritmetica
- Codifica aritmetica (PDF), su vlsilab.polito.it. URL consultato il 21 novembre 2007 (archiviato dall'url originale il 20 marzo 2005).
- (EN) The on-line textbook: Information Theory, Inference, and Learning Algorithms, by David J.C. MacKay, explains arithmetic coding in Chapter 6.
- (EN) Newsgroup posting with a short worked example of arithmetic encoding (integer-only).
- (EN) Arithmetic encoding Archiviato il 28 febbraio 2003 in Internet Archive. da PlanetMath
- (EN) Anatomy of Range Encoder The article explains both range and arithmetic coding. It has also code samples for 3 different arithmetic encoders along with performance comparison.
- (EN) Introduction to Arithmetic Coding Archiviato il 9 novembre 2020 in Internet Archive.. 60 pages.
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
