Confusione di codifica aritmetica adattiva

Question

Sono confuso sul punto di codifica aritmetica adattiva.

Comprendo che la codifica aritmetica statica comporta l'uso di probabilità preimpostata dei simboli che rimangono statici durante l'intero processo.Comprendo anche che la codifica aritmetica adattiva implica modificare tutte le probabilità dopo ogni simbolo riscontrato.

Tuttavia, qual è il punto di cambiare la probabilità dopo ogni simbolo?Perché non dovresti solo passare attraverso un intero file e determinare le probabilità e poi fai la codifica aritmetica come un secondo passaggio?

Inoltre, non capisco come cambiare la probabilità dei simboli influisce sulla compressione?Se conosciamo le veri probabilità dei simboli nel file che stiamo comprimendo, renderà il file più piccolo?

Answer 1

In primo luogo, considera "Aspettare un intero file". Ci sono alcune ipotesi che vale la pena pensare qui.

I file possono essere molto grandi e che li attraversano due volte possono essere costosi. Questo è uno dei motivi per cui la maggior parte degli standard di compressione del mondo reale si basano su blocchi o finestre.

Ci sono situazioni in cui non hai "l'intero file" per cominciare, come un canale di comunicazione. TLS (prima di 1.3, almeno) supporta la compressione, ad esempio.

I file non sono sempre omogenei. Archivi (ad esempio tar ) sono un caso in punto. Un modello statistico appropriato per una parte di un file potrebbe non essere appropriato per un'altra parte. La codifica adattativa si adatta anche a questo.

Per quanto riguarda la domanda finale, se sia l'encoder che il decodificatore conoscevano le vere probabilità dei simboli nel file che stiamo comprimendo, allora non dovrebbe essere trasmesso. E, in effetti, a volte lo facciamo nel mondo reale. Lo standard JPEG, ad esempio, specifica le tabelle di codifica predefinite per quei tempi in cui sono appropriati e consente ad un encoder fornire il proprio quando non sono.

Trasmissione di una tabella di codifica statica in modo efficiente (cioè la compressione) è un problema non tradizionale, specialmente per un grande alfabeto di codice. Per uno schema ben progettato, il costo della trasmissione della tabella dovrebbe uguale al "costo di apprendimento" di utilizzare un codice adattivo.