Kein Komprimierungsalgorithmus kann alle Eingabenachrichten komprimieren?

8

Ich habe gerade angefangen, ein Buch mit dem Titel Einführung in die Datenkomprimierung von Guy E. Blelloch zu lesen. Auf Seite eins sagt er:

Die Wahrheit ist, dass, wenn eine Nachricht durch einen Algorithmus verkürzt wird, eine andere Nachricht verlängert werden muss. Sie können dies in der Praxis überprüfen, indem Sie GZIP für eine GIF-Datei ausführen. Es ist in der Tat möglich, weiter zu gehen und zu zeigen, dass für eine Reihe von Eingabenachrichten fester Länge, wenn eine Nachricht komprimiert wird, die durchschnittliche Länge der komprimierten Nachrichten über alle möglichen Eingaben immer länger als das Original sein wird Eingabenachrichten.

Betrachten Sie zum Beispiel die 8 möglichen 3-Bit-Nachrichten. Wenn eine auf zwei Bits komprimiert ist, ist es nicht schwer, sich davon zu überzeugen, dass zwei Nachrichten auf 4 Bits erweitert werden müssen, was einem Durchschnitt von 3 1/8 Bits entspricht.

"Ja wirklich?" Es fällt mir sehr schwer, mich davon zu überzeugen. In der Tat ist hier ein Gegenbeispiel. Betrachten Sie den Algorithmus, der eine 3-Bit-Zeichenfolge als Eingabe akzeptiert und den folgenden Ausgaben zugeordnet ist:

000 -> 0
001 -> 001
010 -> 010
011 -> 011
100 -> 100 
101 -> 101
110 -> 110
111 -> 111

Da sind Sie also - kein Eingang ist einem längeren Ausgang zugeordnet. Es gibt sicherlich keine "zwei Nachrichten", die auf 4 Bit erweitert wurden.

Worüber spricht der Autor genau? Ich vermute, dass es entweder eine implizite Einschränkung gibt, die mir einfach nicht klar ist, oder dass er eine Sprache verwendet, die viel zu umfassend ist.

Haftungsausschluss: Mir ist klar, dass Sie tatsächlich Daten verlieren, wenn mein Algorithmus iterativ angewendet wird. Versuchen Sie, es zweimal auf den Eingang 110 anzuwenden: 110 -> 000 -> 0, und jetzt wissen Sie nicht, welcher von 110 und 000 der ursprüngliche Eingang war. Wenn Sie es jedoch nur einmal anwenden, erscheint es mir verlustfrei. Hat das etwas mit dem zu tun, worüber der Autor spricht?

Jack M.
quelle
13
Ihr Code ist kein Code. Wie wollen Sie 00010 dekodieren?
3
Tatsächlich gibt es einen sehr einfachen Beweis für diese Tatsache, der auf dem Pigeonhole-Prinzip beruht. en.wikipedia.org/wiki/…
Chazisop
Wenn Sie jede 3-Bit-Nachricht auf <= 3 Bit komprimieren könnten, könnten Sie unendlich lange Nachrichten in nur wenigen Bits komprimieren. Wenn Ihr Vorschlag beispielsweise funktionieren würde, könnten Sie einfach xor mit dem am häufigsten vorkommenden 3-Bit-Wert verwenden, den Wert am Anfang hinzufügen und komprimieren. Dann wiederholen Sie einfach so lange, bis eine Nachricht nur noch wenige Bits benötigt.
JarkkoL

Antworten:

16

Was Sie vermissen, ist, dass Sie alle Bits der Größe 3 oder weniger berücksichtigen müssen . Das heißt: Wenn in einem Komprimierungsschema für Bits der Größe 3 oder weniger eine der 3-Bit-Zeichenfolgen zu einer 2-Bit-Zeichenfolge komprimiert wird, muss eine Zeichenfolge der Größe 3 oder weniger auf 3 Bit oder mehr erweitert werden.

Ein Kompressionsschema ohne Verlust ist eine Funktion von endlichen Bitfolgen zu endlichen Bitfolgen, die injektiv ist, dh wenn C ( x ) = C ( y ), dann bestimmt x = y , dh C ( x ) bestimmt x eindeutig .CC(x)=C(y)x=yC(x)x

Betrachten Sie ein beliebiges Komprimierungsschema und lassen Sie S eine Menge von Binärzeichenfolgen sein. Wir können ausdrücken, wie gut C auf S funktioniert, indem wir das Verhältnis CompressionRatio ( C , S ) = x S l e n g t h ( C ( x ) ) berechnen. CSCS Ein kleines Kompressionsverhältnis ist gut. Zum Beispiel, wenn es sich1/2Das bedeutetwir können im Durchschnitt Kompresse Saiten inSum 50% unter VerwendungC.

CompressionRatio(C,S)=xSlength(C(x))xSlength(x).
1/2SC

Wenn wir versuchen, alle Zeichenfolgen mit einer Länge von höchstens zu komprimieren, haben wir Probleme:n

SnCCompressionRatio(C,S)1

Das beste Komprimierungsschema der Welt ist also die Identitätsfunktion! Nun, nur wenn wir zufällige Bitfolgen komprimieren wollen . Die in der Praxis vorkommenden Bitfolgen sind alles andere als zufällig und weisen viel Regelmäßigkeit auf. Aus diesem Grund ist es trotz des obigen Satzes sinnvoll, Daten zu komprimieren.

Andrej Bauer
quelle
Vielen Dank. Also hat der Autor falsch geschrieben, oder? Er sagte "Nachrichten mit fester Länge" und "Betrachten Sie die 8 3-Bit-Nachrichten", aber er hätte sagen sollen "Nachrichten mit fester maximaler Länge" und "Betrachten Sie die 14 möglichen Nachrichten mit höchstens 3-Bit"?
Jack M
{0,1}
7

Nur eine zusätzliche Anmerkung zu Andrejs guter Antwort:

Sie können auch einen Blick auf die Komplexität von Kolmogorov werfen :

sC(s)s

Informell C(s)sC(s)|s|

Zwei grundlegende Sätze sind:

1) Unabhängig vom Berechnungsmodell gibt es eine Konstante so dass für jede Zeichenfolge scsC(s)|s|+cs

2) Für alle gibt es eine ZeichenfolgensnC(s)|s|

2nn<n

i=0n12i=2n1<2n

Vor
quelle
4

Ihr Gegenbeispiel ist falsch.

Ihre Liste der komprimierten Werte enthält einige versteckte Informationen, wodurch die durchschnittliche Länge länger als 3 Bit ist. Die zusätzliche Information ist die Länge der Ausgabezeichenfolge.

Mit unseren Augen können wir aus Ihrer Tabelle ersehen, dass die erste Ausgabezeichenfolge nur 1 Bit lang ist und die anderen 3 Bit, aber Sie betrügen, wenn Sie diese Tatsache nicht explizit codieren. Codieren wir das, indem wir ein weiteres Bit voranstellen. 0 bedeutet "Länge = 1" und 1 bedeutet "Länge = 3".

So wird Ihr Tisch wirklich:

000 -> 00
001 -> 1001
010 -> 1010
011 -> 1011
100 -> 1100 
101 -> 1101
110 -> 1110
111 -> 1111

... was durchschnittlich 3,75 Bit beträgt.

BEARBEITEN

Hier ist ein nachträglicher Gedanke, der den gleichen Punkt veranschaulicht. Es ist eine schöne Quizfrage:

Morsecode besteht nur aus Punkten und Strichen. Nennen wir Punkt 0 und Bindestrich 1. Alle Großbuchstaben werden als nicht mehr als vier Bits codiert.

E = . = 0
Q = --.- = 1101

Es gibt 26 Großbuchstaben. Vier Bits sollten jedoch nur 16 verschiedene Werte codieren können. Was ist los?

detmar
quelle
Ist das wirklich notwendig? Es scheint mir, dass es in einigen Situationen durchaus vernünftig ist, die Länge implizit zuzulassen - beispielsweise wenn Sie ein Protokoll haben, in dem JEDER Nachricht die Länge vorangestellt ist, die als Wort mit fester Breite codiert ist. Da es jeder Nachricht vorausgeht, ob komprimiert oder nicht, kann es vernachlässigt werden. Und Andrejs Beitrag beantwortet die Frage, während die Länge implizit ist, sodass Ihre Einschränkung unnötig erscheint. Natürlich immer noch ein guter Punkt, um so oder so angesprochen zu werden.
Jack M
Denken Sie tatsächlich, dass Ihre Einschränkung, die Länge explizit codieren zu müssen, möglicherweise der Einschränkung von Andrej entspricht , alle Zeichenfolgen mit weniger als 3 Bit codieren zu müssen?
Jack M
@JackM: In den meisten Fällen wird ein Komprimierungsschema nicht nur verwendet, um einzelne Datenstücke anderen (hoffentlich kleineren) einzelnen Datenelementen zuzuordnen, sondern um Sequenzen von Datenstücken anderen (hoffentlich kürzeren) Sequenzen von Daten zuzuordnen von Dateien. Wenn sich die Eingabesequenzen alle in einem einzelnen Stream befinden, der genügend Informationen enthält, um sie zu unterteilen, sollte die "Eingabelänge" alle Informationen enthalten, die zum Analysieren der Eingabe aus einem einzelnen Stream erforderlich sind, und die "Ausgabelänge" sollte alle erforderlichen Informationen enthalten Analysieren Sie die Ausgabe.
Supercat
0

2n+11nn+1. Wenn viele Zeichenfolgen jedoch viel kürzer als die maximale Länge sind, kann es hilfreich sein, alternative Codierungsschemata zu verwenden, die mehr als eine zur Länge der maximalen Zeichenfolgen, aber weniger zur Länge der kürzeren Zeichenfolgen hinzufügen. Folglich hängt die Menge an Informationen, die durch die Kenntnis der genauen Länge einer Zeichenfolge übermittelt wird, davon ab, wie lange man annehmen würde, dass die Zeichenfolge sein könnte, und wie bereit man wäre, kürzere Zeichenfolgen aufzufüllen.

Da solche Faktoren sehr stark von der Anwendung abhängen, ist es hilfreich, ein Berechnungsmodell anzunehmen, in dem angenommen wird, dass Eingabezeichenfolgen Informationen enthalten, die ausreichen, um den Leser wissen zu lassen, wo sie enden (selbst wenn sie mit beliebigen Mengen beliebiger Daten aufgefüllt wurden). und Ausgabezeichenfolgen sind ebenfalls erforderlich. Ein solches Berechnungsmodell ermöglicht es, dass alle Operationen, die mit einzelnen Datensätzen arbeiten würden, genauso gut mit jeder verketteten Folge von Datensätzen funktionieren [Code, der weiß, wann das Lesen ganzer unkomprimierter Datensätze beendet werden muss, kann genauso gut wissen, wann er gestoppt werden muss ganze komprimierte lesen].

Superkatze
quelle