Esiste un algoritmo di compressione ottimale teoricamente provata?

Question

Is codifica di Huffman sempre ottimale in quanto utilizza le idee di Shanon? Che dire di testo, immagini, video, ... compressione?

E 'questo soggetto ancora attivo nel campo? Quali riferimenti classici o moderni dovrei leggere?

Answer 1

codifica di Huffman è ottimale per un simbolo simbolo-to-codifica in cui le probabilità di ogni simbolo sono indipendenti e conosciuto prima mano. Tuttavia, quando queste condizioni non sono soddisfatte (come in immagine, video), vengono utilizzate altre tecniche di codifica, come LZW, JPEG, ecc. Per maggiori dettagli, si può passare attraverso il libro "Introduzione alla compressione dei dati" di Khalid Sayood.

Answer 2

C'è una versione dell'algoritmo Lempel-Ziv, che è ottimale in alcuni scenari. Vale a dire, se l'ingresso viene da una catena di Markov ergodica, allora il tasso asintotico dell'algoritmo Lempel-Ziv uguale l'entropia. Per ulteriori informazioni su questo, dare un'occhiata al capitolo 13 della copertura e Thomas.

Answer 3

compressione Huffman, con alcune ipotesi, che non si applicano ai file reali, può essere dimostrato di essere ottimale.

Diversi algoritmi di compressione comprimere alcuni tipi di file più piccolo del Huffman algoritmo , quindi Huffman ISN 't ottimale. Questi algoritmi sfruttano uno o l'altro degli avvertimenti della ottimalità prova di Huffman.

Quando abbiamo (a) si codice ogni simbolo indipendentemente in un numero intero di bit, e (b) ciascun simbolo è "estranei" per gli altri simboli che trasmettono (senza informazione reciproca, statisticamente indipendenti, ecc), e (c) il ricevitore conosce la distribuzione di probabilità di ogni simbolo possibile, allora compressione Huffman è ottimale (produce più piccoli file compressi).

(a) simbolo-by-simbolo: Rilassando la restrizione binario Huffman che ogni simbolo ingresso deve essere codificato come un numero intero di bit, diversi algoritmi di compressione, come gamma di codifica, non sono mai peggio, e di solito meglio di standard Huffman.

(b) i simboli non correlati: la maggior parte dei file di dati reali hanno qualche informazione reciproca tra i simboli. Si può fare meglio di pianura Huffman per "decorrelazione" i simboli, e quindi utilizzando l'algoritmo di Huffman su questi simboli decorrelati.

(c) distribuzione di probabilità nota: Di solito il ricevitore non conosce l'esatta distribuzione di probabilità. Così tipiche algoritmi di compressione Huffman invia un tavolo prima frequenza, quindi inviare i dati compressi. Diversi algoritmi di compressione "adattivi", come Polar albero di codifica, possono ottenere una migliore compressione di Huffman, perché convergono sulla distribuzione di probabilità, o di adattarsi ad una distribuzione di probabilità che cambia, senza mai inviare esplicitamente una tabella di frequenza.

Libri e carte discutere tale compressione migliore del Huffman:

• comp.compression FAQ
• Matt Mahoney. Compressione Dati illustrati
• Ian H. Witten, Alistair Moffat, e Timothy C. Bell. Gestione Gigabyte.
• Wikibooks: Data Compression è una bozza
• Wikipedia: la compressione dei dati

Answer 4

Il rapporto di compressione ottimale è legato alla entropia dei dati.

Da Wikipedia l'articolo http://en.wikipedia.org/wiki/Shannon%27s_source_coding_theorem :

N i.i.d. variabili casuali ciascuno con entropia H (X) può essere compresso in più di N bit H (X) con trascurabile rischio di perdita di informazioni, come N tende all'infinito; ma al contrario, se vengono compressi in meno di n H (X) bit è praticamente certo che le informazioni essere perso.