Gibt es ein bekanntes Maximum für die Komprimierung einer Zeichenfolge aus Nullen und Einsen?

38

Vor langer Zeit las ich einen Zeitungsartikel, in dem ein Professor sagte, dass wir in Zukunft Daten auf nur zwei Bits komprimieren können (oder so ähnlich).

Dies ist natürlich nicht korrekt (und es könnte sein, dass meine Erinnerung an das, was er genau sagte, nicht korrekt ist). Verständlicherweise wäre es nicht praktikabel, eine Folge von 0en und 1en auf nur zwei Bits zu komprimieren, da (selbst wenn dies technisch möglich wäre) zu viele verschiedene Arten von Folgen auf die gleichen zwei Bits komprimiert würden (da wir nur '01 haben) 'und' 10 'zur Auswahl).

Wie auch immer, dies brachte mich dazu, über die Machbarkeit nachzudenken, eine Zeichenfolge mit beliebiger Länge von Nullen und Einsen nach einem Schema zu komprimieren. Gibt es für diese Art von Zeichenfolge eine bekannte Beziehung zwischen der Zeichenfolgenlänge (das Verhältnis zwischen 0 und 1 spielt wahrscheinlich keine Rolle) und der maximalen Komprimierung?

Mit anderen Worten, gibt es eine Möglichkeit zu bestimmen, auf welche minimale (kleinstmögliche) Länge eine Zeichenfolge aus Nullen und Einsen komprimiert werden kann?

(Hier interessiert mich die mathematische Maximalkompression, nicht das, was derzeit technisch möglich ist.)

x457812
quelle
7
Wir hätten auch "00" und "11" zur Auswahl. Aber das Argument ist das gleiche, wenn Sie diese verwenden, gibt es nur vier verschiedene Zeichenfolgen, die Sie komprimieren können.
RemcoGerlich
3
mathoverflow.net/q/160099/34859 : Sehen Sie hier, dass es nach dem Pigeonhole - Prinzip immer unendlich viele Zeichenfolgen gibt, die nicht komprimiert werden können ... Unabhängig vom verwendeten Algorithmus (siehe Abschnitt 'Hintergrund' in die Frage
ARi
4
Die Komprimierung hängt von Ihrem Wissen über die Struktur der Daten ab. In diesem Artikel über das Komprimieren von Schachzügen wurde gezeigt, wie das Hinzufügen von Wissen zur Erhöhung der Komprimierung beiträgt.
Spektren
1
Können Sie klarstellen: Die Komprimierung kann "verlustbehaftet" oder "verlustfrei" sein (oder ein "Hybrid", der beide verwendet). Sprechen Sie von maximaler Komprimierung, indem Sie nur "verlustfreie" Komprimierungsmethoden verwenden, oder erlauben Sie auch die Verwendung von "verlustbehafteten" Komprimierungsmethoden. Mit anderen Worten, ich denke , es gibt 3 Möglichkeiten: Suche nach „maximaler Kompression“ , wobei (1) die Daten müssen immer in der Lage sein , genau dekomprimiert werden , wie es vor der Kompression war, (2) müssen die Daten in der Lage sein , dekomprimiert werden, aber Ein gewisser "Verlust" ist zulässig. (3) Es ist nicht erforderlich, dass die Daten dekomprimiert werden können.
Kevin Fegan
Hallo @ KevinFegan, in diesem Fall müsste es Option 1 sein: "Die Daten müssen immer genau so dekomprimiert werden können, wie sie vor der Komprimierung waren"
x457812 30.11.15

Antworten:

45

Die Komplexität von Kolmogorov ist ein Ansatz, um dies mathematisch zu formalisieren. Leider ist die Berechnung der Kolmogorov-Komplexität eines Strings ein unberechenbares Problem. Siehe auch: Approximation der Kolmogorov-Komplexität .

Es ist möglich, bessere Ergebnisse zu erzielen, wenn Sie die Quelle der Zeichenfolge und nicht die Zeichenfolge selbst analysieren . Mit anderen Worten, oft kann die Quelle als probabilistischer Prozess modelliert werden, der eine Zeichenfolge nach einer gewissen Verteilung zufällig auswählt. Die Entropie dieser Verteilung gibt dann Auskunft über die mathematisch bestmögliche Komprimierung (bis zu einer kleinen additiven Konstante).


Da eine perfekte Komprimierung nicht möglich ist, könnte Sie auch Folgendes interessieren.

DW
quelle
Komprimierung ist jedoch eine der Techniken zum Schätzen der Entropie. Können Kompression und Entropie zwei Facetten einer Sache sein?
Paul Uszak
1
@PaulUszak, ja, sie sind sehr eng miteinander verwandt: siehe z. B. Shannons Theorem . Bitte beachten Sie jedoch: Kommentare sollten nur verwendet werden, um Verbesserungen / Klarstellungen für den Beitrag vorzuschlagen, und nicht, um Folgefragen zu stellen. Um eine neue Frage zu stellen, verwenden Sie den Link "Frage stellen" oben rechts auf der Seite.
DW
35

Nlog2N

In vielen Fällen kümmern wir uns auch nicht um die exakte Rekonstruktion. Dies wird als verlustbehaftete Komprimierung bezeichnet und beschreibt, wie Musik und Videos komprimiert werden. In diesem Fall gilt die oben angegebene Untergrenze nicht, Sie können jedoch andere Untergrenzen festlegen.

Yuval Filmus
quelle
1
Nlog2N
27

Hier ist ein einfaches Schema, mit dem beliebige Bitfolgen verlustfrei komprimiert werden können, wobei das kleinste Ergebnis nur ein Bit ist:

WENN die Saite für die Aufnahme von Beethovens 9. Symphonie, vierter Satz, im AAC-Format, das auf der Festplatte meines Computers gespeichert ist, identisch ist, ist die Ausgabe ein einzelnes Bit '0'.

WENN die Zeichenfolge etwas anderes ist, ist die Ausgabe ein einzelnes Bit '1', gefolgt von einer identischen Kopie der ursprünglichen Zeichenfolge.

Dieses Schema reduziert eine mögliche Eingabe auf genau ein Bit und verlängert jede andere Eingabe. Es gibt ein allgemeines Prinzip: Wenn ein Komprimierungsalgorithmus eine Eingabezeichenfolge auf eine komprimierte Zeichenfolge abbilden kann, und es einen passenden Dekomprimierungsalgorithmus gibt, der eine komprimierte Zeichenfolge wieder auf die ursprüngliche Zeichenfolge abbildet, und der Komprimierungsalgorithmus eine Eingabe auf eine kürzere Zeichenfolge abbildet , dann müssen einige Eingabezeichenfolgen längeren Zeichenfolgen zugeordnet werden.

gnasher729
quelle
2
Gute Arbeit, um die Antwort klar und deutlich zu machen. Es ist erwähnenswert, dass dies dem entspricht, was ein guter Komprimierungsalgorithmus versucht: Versuchen Sie, für eine bestimmte Eingabedomäne die am häufigsten erwarteten Eingabetypen zu verkürzen, während weniger häufig verwendete Eingaben verlängert werden.
JBentley
6

Für jedes Komprimierungsschema, das Sie erstellen können, können Daten erstellt werden, die von diesen nicht komprimiert werden können. Selbst wenn Ihr Komprimierungsschema bei einigen Datentypen sehr effizient ist, wird es niemals konsistent auf ein bestimmtes Verhältnis komprimiert.

Die Erstellung eines Beispiels für nicht komprimierbare Daten für einen bestimmten Komprimierungsalgorithmus ist einfach: Nehmen Sie beliebige Daten und führen Sie sie wiederholt durch, bis die Größe nicht mehr abnimmt.

Die Komprimierbarkeit einer Bitfolge hängt also nicht wirklich von der Länge der Zeichenfolge ab, sondern von ihrer Komplexität im Verhältnis zum Komprimierungsalgorithmus.

m69 '' snarky and unwillkommen ''
quelle
Herzlich willkommen! Beachten Sie, dass dies nur für verlustfreie Komprimierung gilt. Eine verlustbehaftete Komprimierung kann alle Zeichenfolgen komprimieren (zumindest, solange Sie den Algorithmus "Leere Zeichenfolge zurückgeben" als verlustbehafteten Komprimierungsalgorithmus akzeptieren. ;-)).
David Richerby
@DavidRicherby Das stimmt natürlich. Aber ich hatte den Eindruck, dass das OP nach verlustfreier Komprimierung fragte, weil es wenig Sinn macht, die maximale Komprimierung eines verlustbehafteten Schemas zu diskutieren. Die Idee, dass Sie es zu unbrauchbaren Extremen bringen können, ist dem Konzept der verlustbehafteten Komprimierung inhärent.
m69 '' snarky and unwillkommen ''
Ja, ich denke das ist eine vernünftige Interpretation.
David Richerby
-2

Es gibt einen interessanten und völlig anderen Algorithmus, der von Unternehmenssicherungssystemen verwendet wird. Die Idee ist, dass, wenn Sie ein Unternehmen mit 10.000 Computern haben, viele, viele dieser Computer viele identische Dateien enthalten. Beispielsweise wird eine E-Mail, die an alle Mitarbeiter des Unternehmens gesendet wird, möglicherweise auf jeder einzelnen Festplatte als identische Datei gespeichert.

Ein Backup-System, das versucht, eine Datei zu sichern, sollte natürlich versuchen, die Datei zu komprimieren, um Speicherplatz zu sparen. Zuerst prüft das Backup-System jedoch, ob bereits eine absolut identische Datei gespeichert ist! Anstatt also irgendetwas zu sichern, merkt sich das Backup-System zum Beispiel nur, dass Sie die Dateinummer 1.487.578 auf dem Backup-System auf Ihrer Festplatte haben.

Dies ist beispielsweise dann besonders effizient, wenn 10.000 Benutzer dasselbe Betriebssystem und dieselben Anwendungen installiert haben. Für einzelne Benutzer ist es überhaupt nicht sehr nützlich.

gnasher729
quelle
4
Das ist interessant, aber ich verstehe nicht, wie es die Frage beantwortet. In der Frage wird nach Komprimierungsbeschränkungen gefragt, nicht nach allgemeinen Erläuterungen zu Unternehmenssicherungen.
David Richerby
Dies wird als Deduplizierung bezeichnet und erfolgt mithilfe von Hashes. Es braucht viel RAM, um einen 128-Bit-Hash für jeden Block auf der Festplatte zu speichern. ZFS kann dies tun, um einige Blöcke auf opportunistische Weise dazu zu bringen, sich beim Schreiben einen bestimmten Speicherplatz zu teilen. Diese Art von Komprimierungsproblem (bei dem Sie versuchen, einen umfangreichen Datensatz zu komprimieren, auf den Sie zufällig zugreifen müssen, und das ändert sich für eine normale Stream-Komprimierung zu schnell, weist jedoch Redundanz auf Blockebene auf) ist als Antwort darauf nicht relevant Frage.
Peter Cordes