Relazione tra entropia a compressione senza perdita Tasso

Question

Fonte di Shannon Coding Teorema sappiamo che l'entropia di una stringa compressa è delimitata dal entropia della stringa originale in questo modo:

H(X) <= L < H(X) + 1/N 

dove H (X) è entropia della stringa di origine, N è la lunghezza della stringa di origine, e L è la lunghezza prevista della stringa compresso.

Ciò significa necessariamente che v'è un limite alla compressione senza perdita di dati.

Quello che mi piacerebbe sapere è:

• Possiamo riferirsi direttamente l'entropia a qualche rapporto di compressione previsto?

• Possiamo usare l'entropia di trovare qualche limite superiore per il rapporto di compressione?

Answer 1

Non è possibile riferirsi direttamente l'entropia di rapporto di compressione senza conoscere la lunghezza della stringa di origine, ma si può vedere il limite teorico per il massimo rapporto di compressione risolvendo per il più piccolo valore possibile di L. È possibile utilizzare questo limite una metrica per l'efficienza dei vostri algoritmi di compressione, anche se una brutta metrica non significa che un algoritmo migliore è stato scoperto o addirittura esiste.

Quindi, sì. È possibile utilizzare l'entropia per trovare il rapporto di massima teorica compressione senza perdita, ma no, non è possibile utilizzarlo per determinare il vostro rapporto di compressione previsto per qualsiasi algoritmo di compressione dato.

Answer 2

Il teorema di Shannon è definito in termini di dati casuali e probabilità. Allo stesso modo, il entropia di una stringa è definito solo per stringhe casuali - l'entropia è una proprietà della distribuzione, non di corde stesse. Quindi, siamo in grado di riformulare il Teorema di Shannon informalmente come:

  

Se si seleziona a caso una stringa da una data distribuzione di probabilità, allora il miglior rapporto di compressione medio che possiamo ottenere per la stringa è dato dal tasso di entropia della distribuzione di probabilità.

Dato uno stringa casuale, posso facilmente scrivere un algoritmo di compressione che comprime quella stringa giù in 1 ', ma il mio algoritmo necessariamente aumentare la lunghezza di alcune altre stringhe. Il mio algoritmo di compressione funziona nel modo seguente:

1. Se la stringa di input è uguale a qualche stringa casuale pre-scelto , l'uscita è la stringa di 1 bit "0"
2. In caso contrario, l'uscita è la stringa + 1 bit N di "1" seguito dalla stringa di input

L'algoritmo di decompressione corrispondente è:

1. Se l'ingresso è "0", l'uscita è il nostro precedente stringa casuale di pre-scelto
2. In caso contrario, l'uscita è tutto tranne per il primo bit di ingresso

La chiave qui è che non possiamo scrivere una algoritmo che, per tutte le stringhe di una data distribuzione, li comprime tutti ad un ritmo elevato, in media. C'è solo troppe stringhe.

Se abbiamo una data distribuzione di probabilità delle stringhe, siamo in grado di calcolare il tasso di entropia della distribuzione, e poi se casualmente scegliere una stringa di in base alla distribuzione e tentare di comprimerlo utilizzando qualsiasi l'algoritmo, la dimensione relativa della stringa compressa sarà, in media, mai essere inferiore al tasso di entropia. Questo è ciò che dice il teorema di Shannon.

Answer 3

Sì. Il tasso di entropia della lingua inglese è spesso citato come 1,5 bit per carattere (più o meno). codifiche tipici usano 8 bit per carattere. Quindi, un testo al massimo compressa dovrebbe essere 1,5 / 8 (~ 19%) il formato dell'originale. I risultati effettivi per una versione solo testo di Orgoglio e Pregiudizio di Jane Austin:. orig = 701K, bzip2 = 178K, per ~ 25%

Answer 4

Sì! Penso questo documento potrebbe puntare nella giusta direzione.

ETA appare come è necessario essere un membro del IEEE per leggere il giornale vero e proprio. Se qualcuno potesse trovare una risorsa a disposizione del pubblico (o spiegare la matematica qui), che sarebbe molto meglio ovviamente!