Beziehung von Entropy zu Lossless Compression Rate

Question

Shannons Quelle Satz Coding wir wissen, dass die Entropie eines komprimierten String ist durch die Entropie des ursprünglichen Zeichenfolge begrenzt wie folgt:

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

, wobei H (X) die Entropie der Primärzeichenfolge ist, n die Länge der Primärzeichenfolge, und L ist die erwartete Länge des komprimierten String.

Das notwendigerweise bedeutet, dass es eine Grenze für die verlustfreie Komprimierung ist.

Was ich möchte wissen, ist:

• Können wir direkt Entropie zu einem gewissen erwarteten Verdichtungsverhältnis beziehen?

• Können wir die Entropie eine obere Grenze für das Verdichtungsverhältnis zu finden?

Answer 1

Sie können nicht direkt Entropie zu Verdichtungsverhältnis beziehen, ohne die Länge der Quellzeichenfolge zu wissen, aber Sie können durch die Lösung für den kleinstmöglichen Wert von L. die theoretische Grenze für die maximale Verdichtungsverhältnis sehen Sie diese Grenze können als ein Maß für die Effizienz Ihrer Komprimierungsalgorithmen, obwohl eine schlechte Metrik bedeutet nicht, dass ein besserer Algorithmus entdeckt wurde, existiert oder sogar.

Also, ja. Sie können Entropie zu finden das theoretische Maximum lossless Verdichtungsverhältnis verwenden, aber nein, man kann es nicht benutzen, um Ihr erwartetes Verdichtungsverhältnis für einen bestimmten Kompressionsalgorithmus zu bestimmen.

Answer 2

Shannon Theorem wird in Form von Zufallsdaten und Wahrscheinlichkeiten definiert. In ähnlicher Weise wird die Entropie von einer Zeichenkette nur für zufällige Zeichenkette definiert - die Entropie ist eine Eigenschaft der Verteilung, nicht die Saiten selbst. So können wir Shannons Theorem informell als neu formulieren:

  

Wenn Sie zufällig eine Zeichenfolge aus einer bestimmten Wahrscheinlichkeitsverteilung wählen, dann ist das beste durchschnittliche Kompressionsverhältnis wir für die Zeichenfolge erhalten durch die Entropierate der Wahrscheinlichkeitsverteilung gegeben ist.

Bei jeder zufällige Zeichenfolge, kann ich leicht einen Kompressionsalgorithmus schreiben, die diese Zeichenfolge nach unten in 1 Bit komprimieren, aber mein Algorithmus wird die Länge von einigen anderen Saiten unbedingt erhöhen. Mein Komprimierungsalgorithmus funktioniert wie folgt:

1. Wenn die Eingabezeichenfolge gleich einig vorgewählten zufällige Zeichenfolge , ist der Ausgang der 1-Bit-String "0"
2. Andernfalls ist der Ausgang der N + 1-Bit-Kette von "1", gefolgt von der Eingabezeichenfolge

Der entsprechende Dekompression-Algorithmus ist:

1. Wenn die Eingabe "0" ist, ist der Ausgang unsere vorherige vorgewählten zufällige Zeichenfolge
2. Andernfalls ist der Ausgang alles mit Ausnahme des ersten Eingangs-Bit

Der Schlüssel hier ist, dass wir nicht aufschreiben können ein Algorithmus, der für alle Strings aus einer bestimmten Verteilung, sie komprimiert alle mit einer hohen Rate im Durchschnitt. Es gibt einfach zu viele Strings.

Wenn wir eine bestimmte Wahrscheinlichkeitsverteilung von Strings haben, können wir die Entropie Rate der Verteilung berechnen, und dann, wenn zufällig eine Zeichenfolge auswählen nach der Verteilung und versuchen, es zu komprimieren mit jeder Algorithmus, wird die relative Größe des komprimierten Zeichenfolge im Durchschnitt sein nie weniger als die Entropierate. Dies ist, was Shannon Theorem sagt.

Answer 3

Ja. Die Entropierate der englischen Sprache wird oft als 1,5 Bit pro Zeichen zitiert (mehr oder weniger). Typische Kodierungen verwenden 8 Bits pro Zeichen. So ein maximal komprimierter Text sollte 1,5 / 8 (~ 19%) die Größe des Originals sein. Die tatsächlichen Ergebnisse für eine reine Textversion von Jane Austin Stolz und Vorurteil: Orig. = 701K, bzip2 = 178K, für ~ 25%

Answer 4

Ja! Ich denke, dieses Papier würden Sie in die richtige Richtung zeigen.

ETA Sieht aus wie Sie ein IEEE-Mitglied sein, müssen das tatsächliche Papier zu lesen. Wenn jemand eine öffentlich zugängliche Ressource (oder erklärt die Mathematik hier) finden konnte, das wäre viel besser natürlich!