Compressione dati: codifica aritmetica non chiara

Question

Qualcuno può spiegare la codifica aritmetica per la compressione dei dati con i dettagli di implementazione? Ho navigato su internet e ho trovato il post di nelson, ma la tecnica di implementazione non è chiara per me dopo aver provato per molte ore. La spiegazione di

Mark Nelson sulla codifica aritmetica può essere situato a

http://marknelson.us/1991/02/01/arithmetic-coding-statistical-modeling-data-compression/

Answer 1

L'idea principale con compressione aritmetica è la capacità di codificare una probabilità utilizzando la quantità esatta di lunghezza dei dati richiesta.

Questa quantità di dati è noto, provato da Shannon, e può essere calcolato semplicemente utilizzando la seguente formula: -log2 (p)

Ad esempio, se p = 50%, quindi è necessario 1 bit. E se p = 25%, hai bisogno di 2 bit.

Questo è abbastanza semplice per le probabilità che sono potenza di 2 (e in questo caso speciale, la codifica di huffman potrebbe essere sufficiente). Ma cosa succede se la probabilità è del 63%? Quindi è necessario -log2 (0.63) = 0.67 bit. Sembra difficile ...

Questa proprietà è particolarmente importante se la tua probabilità è alta. Se puoi prevedere qualcosa con un'accuratezza del 95%, allora hai solo bisogno di 0,074 bit per rappresentare una buona ipotesi. Il che significa che stai per comprimere molto.

Ora, come fare?

Bene, è più semplice di quanto sembri. Dividerai la tua gamma in base alle probabilità. Ad esempio, se hai un intervallo di 100, 2 possibili eventi e una probabilità del 95% per il primo, allora i primi 95 valori diranno "Evento 1" e gli ultimi 5 valori restanti diranno "Evento 2" .

OK, ma sui computer, siamo abituati a utilizzare le potenze di 2. Ad esempio, con 16 bit, avete un intervallo di 65536 valori possibili. Fai lo stesso: prendi il 1 ° 95% del range (che è 62259) per dire "Event 1", e il resto per dire "Event 2". Ovviamente hai un problema di "arrotondamento" (precisione), ma finché hai abbastanza valori da distribuire, non importa troppo. Inoltre, non sei vincolato a 2 eventi, potresti avere una miriade di eventi. Tutto ciò che conta è che i valori siano assegnati in base alle probabilità di ciascun evento.

OK, ma ora ho 62259 valori possibili per dire "Evento 1" e 3277 per dire "Evento 2". Quale dovrei scegliere? Beh, qualcuno di loro lo farà. Sia che sia 1, 30, 5500 o 62256, significa ancora "Evento 1".

In effetti, decidere quale valore selezionare non dipende dall'ipotesi corrente, ma da quelli successivi.

Supponiamo di avere "Evento 1". Così ora devo scegliere qualsiasi valore tra 0 e 62256. Il prossimo indovinare, ho la stessa distribuzione (95% Evento 1, 5% Evento 2). Alletterò semplicemente la mappa di distribuzione con queste probabilità. Tranne che questa volta, è distribuito su 62256 valori. E continuiamo così, riducendo l'intervallo di valori a ogni ipotesi.

Quindi, in effetti, stiamo definendo "intervalli", che restringono ad ogni ipotesi. Ad un certo punto, tuttavia, c'è un problema di accuratezza, perché rimangono pochissimi valori.

L'idea è semplicemente "gonfiare" di nuovo l'intervallo. Ad esempio, ogni volta che l'intervallo scende sotto 32768 (2^15), si emette il bit più alto e si moltiplica il resto per 2 (spostando in modo efficace i valori di un bit a sinistra). Continuando continuamente a fare questo, si emettono i bit uno per uno, poiché vengono risolti dalla serie di ipotesi.

Ora la relazione con la compressione diventa ovvia: quando l'intervallo viene ristretto rapidamente (es: 5%), si generano molti bit per riportare l'intervallo al di sopra del limite. D'altra parte, quando la probabilità è molto alta, la gamma si restringe molto lentamente. Puoi anche avere un sacco di ipotesi prima di emettere i tuoi primi bit. È così che è possibile comprimere un evento in "una frazione di un bit".

Ho usato volutamente il termine "probabilità", "indovinare", "eventi" per mantenere questo articolo generico. Ma per la compressione dei dati, è sufficiente sostituirli con il modo in cui si desidera modellare i dati. Ad esempio, il prossimo evento può essere il prossimo byte; in questo caso, ne hai 256.

Answer 2

Prima di tutto grazie per avermi fatto conoscere il concetto di compressione aritmetica!

mi rendo conto che questo metodo ha i seguenti passi:

1. Creazione di mapping: Calcolare la frazione di occorrenza per ogni lettera che dà una dimensione gamma per ogni alfabeto. Poi ordinare e assegnare intervalli effettivi da 0 a 1
2. Dato un messaggio calcolare l'intervallo (IMHO abbastanza semplice)
3. trovare il codice ottimale

La terza parte è un po 'complicato. Usa il seguente algoritmo.

Sia b la rappresentazione ottimale. Inizializza a stringa vuota (''). Sia x il valore minimo e y il valore massimo.

1. doppie xey: x = 2 * x, y = 2 * y
2. Se entrambi sono maggiori di 1 accodamento 1 a b. Passare al punto 1.
3. Se entrambi sono minori di 1, aggiungere 0 a b. Passare al punto 1.
4. Se x < 1, ma y> 1, quindi aggiungere 1 b ed arrestare

b contiene essenzialmente la parte frazionaria del numero che si sta trasmettendo. Per esempio. Se b = 011, la frazione corrisponde a 0,011 in binario.

Quale parte di implementazione non capisci?

Answer 3

Forse questo script potrebbe essere utile per costruire una migliore modello mentale di aritmetica coder: gen_map.py. Originariamente è stato creato per facilitare il debug della libreria di codificatori aritmetici e semplificare la generazione di test di unità per esso. Tuttavia crea piacevoli visualizzazioni ASCII che potrebbero essere utili anche nella comprensione della codifica aritmetica.

Un piccolo esempio. Immaginiamo di avere un alfabeto di 3 simboli: 0, 1 e 2 con probabilità 1/10, 2/10 e 7/10 corrispondentemente. E vogliamo codificare la sequenza [1, 2].Script darà il seguente output (ignorare -b N opzione per ora):

$ ./gen_map.py -b 6 -m "1,2,7" -e "1,2" 
000000111111|1111|111222222222222222222222222222222222222222222222 
------011222|2222|222000011111111122222222222222222222222222222222 
---------011|2222|222-------------00011111122222222222222222222222 
------------|----|-------------------------00111122222222222222222 
------------|----|-------------------------------01111222222222222 
------------|----|------------------------------------011222222222 
================================================================== 
000000000000|0000|000000000000000011111111111111111111111111111111 
000000000000|0000|111111111111111100000000000000001111111111111111 
000000001111|1111|000000001111111100000000111111110000000011111111 
000011110000|1111|000011110000111100001111000011110000111100001111 
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
001100110011|0011|001100110011001100110011001100110011001100110011 
010101010101|0101|010101010101010101010101010101010101010101010101 

Primi 6 linee (prima riga) ==== rappresentano un intervallo da 0,0 a 1,0, che è ripetutamente suddivisa in intervalli proporzionali alle probabilità di simboli. Annotated prima riga:

[1/10][  2/10 ][     7/10      ] 
000000111111|1111|111222222222222222222222222222222222222222222222 

Poi suddividere ogni intervallo ancora:

[ 0.1][  0.2  ][     0.7      ] 
000000111111|1111|111222222222222222222222222222222222222222222222 
     [ 0.7 ][.1][ 0.2 ][   0.7     ] 
------011222|2222|222000011111111122222222222222222222222222222222 
            [.1][ .2][ 0.7    ] 
---------011|2222|222-------------00011111122222222222222222222222 

nota, che alcuni intervalli non sono suddivise. Ciò accade quando non c'è spazio sufficiente per rappresentare ogni sottointervallo entro una data precisione (che è specificata dall'opzione -b).

Ogni riga corrisponde a un simbolo dall'input (nel nostro caso - sequenza [1, 2]). Seguendo i sottointervalli per ciascun simbolo di input otterremo un intervallo finale che vogliamo codificare con una quantità minima di bit. Nel nostro caso si tratta di un primo sottointervallo 2 su una seconda linea:

  [ This one ] 
------011222|2222|222000011111111122222222222222222222222222222222 

Following 7 linee (dopo ====) rappresentano lo stesso intervallo di 0,0 a 1,0, ma suddivisi secondo notazione binaria. Ogni linea è un po 'di output e scegliendo tra 0 e 1 si sceglie il semintervalore sinistro o destro. Ad esempio i bit 01 corrisponde sottointervallo [0.25, 05) su una seconda linea:

    [ This one ] 
000000000000|0000|111111111111111100000000000000001111111111111111 

L'idea di codificatore aritmetica è a bit di uscita (0 o 1) fino dell'intervallo corrispondente sarà completamente all'interno (o uguale a) l'intervallo determinato dalla sequenza di input. Nel nostro caso è 0011. La riga ~~~~ mostra dove abbiamo abbastanza bit per identificare senza ambiguità l'intervallo che vogliamo.

Le linee verticali formate dal simbolo | mostrano l'intervallo di sequenze di bit (righe) che potrebbero essere utilizzate per codificare la sequenza di input.