Komprimierungsfunktionen sind nur deshalb praktisch, weil „die in der Praxis vorkommenden Bitfolgen alles andere als zufällig sind“?

7

Ich hätte einen Kommentar abgegeben, da dies die Antwort von Andrej Bauer in diesem Thread betrifft ; Ich glaube jedoch, dass es eine Frage wert ist.

Andrej erklärt, dass eine verlustfreie Komprimierungsfunktion angesichts der Menge aller Bitfolgen mit einer Länge von 3 oder weniger nur einige von ihnen "komprimieren" kann. Die anderen, zum Beispiel "01", müssten tatsächlich zu einer Zeichenfolge wie "0001" mit der Länge 4 komprimiert werden. Das Komprimierungsverhältnis ist einfach die durchschnittliche Komprimierung über den Eingabesatz.

Dies lässt verlustfreie Komprimierung unpraktisch erscheinen, aber das wichtige Zitat lautet:

Die in der Praxis vorkommenden Bitfolgen sind alles andere als zufällig und weisen viel Regelmäßigkeit auf.

Es fällt mir schwer zu glauben, dass Multimediadateien beispielsweise durch etwas anderes als zufällige Bitfolgen dargestellt werden. Gibt es wirklich ein Muster, das Komprimierungsfunktionen nutzen, um den Algorithmus in der Realität nützlich zu machen?

AlexMayle
quelle
3
Ich bin kein Experte, aber es gibt definitiv viel Regelmäßigkeit in den Dingen. Betrachten Sie ein Bild eines Baumes; Grün und Braun dominieren das Bild. Da wir diese Werte häufig sehen, können wir sie auf kleinere Werte komprimieren. Betrachten Sie als nächstes die Idee der verlustfreien Komprimierung, es ist zu gut, um wahr zu sein. Etwas muss geben. Darüber wird hier gesprochen. Versuchen Sie zuletzt ein Experiment, bei dem Sie nach dem Zufallsprinzip Zeichenfolgen generieren und sehen, wie oft das Komprimierungsverhältnis gemittelt wird. Wenn Sie die Dinge richtig machen (was schwierig sein könnte), sollten Sie keinen wirklichen Gesamtvorteil sehen.
Jake
2
Selbst wenn Sie absichtlich zufällige Daten als Multimediadatei gespeichert haben, hat die Datei selbst eine Struktur, die sich wiederholt und komprimiert werden kann - Header, Rahmendaten (für Dinge mit Rahmen) und so weiter.
Luke Mathieson

Antworten:

10

Zunächst einmal haben Sie Recht: Multimediadateien werden (mehr oder weniger) als zufällige Dateien dargestellt. Der Grund dafür ist, dass diese Dateien bereits komprimiert sind (verlustbehaftet). Beachten Sie, dass MP3 zum Beispiel nichts anderes als ein Komprimierungsalgorithmus ist!
Eine Konsequenz ist, dass eine weitere Komprimierung keine merkliche Komprimierung ergibt (und in der Tat war eine verlustfreie Komprimierung bereits komprimierter (Multimedia-) Dateien nie ein Weg zum Erfolg).

Auch in Ihrem anderen Punkt haben Sie Recht: Verlustfreie Komprimierung kann im Durchschnitt nicht komprimiert werden. Um dies zu sehen, besteht Ihr möglicher Datensatz beispielsweise aus verschiedenen Elementen. Wie viele Bits benötigen Sie pro Datei, um Elemente immer von Ihrem Satz unterscheiden zu können? Richtig, . Insgesamt werden alle Dateien durch nicht weniger als Bits dargestellt. Wenn Sie nun einige dieser Dateien mit weniger als Bits darstellen, werden einige Dateien mit mehr als Bits dargestellt. Das ist ungefähr alles, was es zu sagen gibt. 2nnn2nnn

Kurz gesagt, verlustfreie Komprimierung funktioniert, weil Textdateien alles andere als zufällig sind (betrachten Sie einfach die Buchstabenverteilung meiner Antwort und vergleichen Sie die Anzahl der E mit der Anzahl der Z !) Und komprimieren Sie zufällige Daten (z. B. bereits komprimierte Daten oder verschlüsselte Daten) macht keinen Sinn.

john_leo
quelle
Ich denke, Sie mischen Probleme leicht. "Das Zippen von Multimediadateien war noch nie ein Weg zum Erfolg" - funktioniert LZ mit unkomprimierten Multimedia-Dateien , z. B. WAV oder TIFF? LZ wurde für Zeichenfolgen entwickelt, dh mit bestimmten Annahmen, die für Nicht-Zeichenfolgendaten gelten können oder nicht.
Raphael
Ich kann Ihren Standpunkt in Bezug auf Textdateien und die Verteilung von Briefen durchaus erkennen. Sehr interessantes Zeug.
AlexMayle
@Raphael Sie haben Recht, das Komprimieren von WAV oder TIFF sollte zu einer spürbaren Komprimierung führen. Ich habe das Wort "komprimiert" in den entsprechenden Teil aufgenommen. In Bezug auf Ihren anderen Punkt, ja, die LZ-Algorithmen wurden für Zeichenfolgen definiert, aber soweit ich weiß, funktionieren zip usw. für alle Binärdaten.
John_leo
Okay, aber noch ein Kommentar: Nicht alle Multimedia-Komprimierungen sind verlustbehaftet. Zum Beispiel komprimieren FLAC und PNG ohne Verluste erheblich. Der Vergleich von ZIP mit FLAC oder PNG (beginnend mit WAV oder TIFF) kann hinsichtlich der Auswirkungen von Entwurfsannahmen hilfreich sein.
Raphael
@Raphael Stattdessen habe ich beschlossen, den Verweis auf einen tatsächlichen Komprimierungsalgorithmus zu löschen. Ich habe festgestellt, dass das Sprechen über ZIP, FLAC oder WHATNOT ein anderes Thema sein könnte.
John_leo
9

Multimedia - Daten ist sehr weit von zufälligen, weshalb es so gut komprimiert. Beispielsweise entspricht eine einzelne Sekunde Video mit einer Auflösung von 1920 x 1080 Pixel, 24-Bit-Farbe und 24 Bildern pro Sekunde etwa 150 MB unkomprimierter Daten. Multimedia - Dateien wurden bereits komprimiert worden sind so hart , etwas weiter zu komprimieren.

Selbst unkomprimierte Multimediadaten sehen jedoch wahrscheinlich ziemlich zufällig aus, wenn Sie sie nur als einen Strom von Nullen und Einsen betrachten. (Allerdings werden GIFs mit LZW komprimiert, wobei sie im Wesentlichen als Bitstrom behandelt werden. Das funktioniert recht gut.) Wenn Sie sich Multimediadaten ansehen und wissen, was dies bedeutet, sind dort viele Strukturen vorhanden.

  • Bilder haben viele Farbverläufe und Blöcke mit ähnlichen Farben. JPEG verwendet so etwas sehr ähnlich.
  • In Videos sieht fast jedes Bild dem unmittelbar davor sehr ähnlich aus, wobei einige Teile ein wenig verschoben sind. MPEG nutzt dies ausgiebig.
  • Viele der Geräusche, an denen wir interessiert sind, sind Wellenformen von Resonanzobjekten, keine zufälligen Frequenzen.

Ich habe JPEG und MPEG erwähnt, die natürlich verlustbehaftet sind. Ich vermute jedoch, dass Sie diese Ideen im Prinzip verwenden könnten, um gute verlustfreie Komprimierungsverhältnisse dieser nicht zufälligen Daten zu erzielen. Ich bezweifle jedoch, dass irgendjemand versuchen würde, dies zu tun, da die Zeit zum Komprimieren wahrscheinlich unglaublich groß wäre.

David Richerby
quelle
Einige gute Beispiele hier.
AlexMayle
1920 * 1080 * 24 * 24 sind 1,11 GB unkomprimierte Daten. 150 MB reichen gerade für 320 x 480 Graustufen. @ 1fps.
FRob
@ FRob Bytes, keine Bits. Ich habe "Mb" auf "MB" korrigiert.
David Richerby
1
Zum letzten Absatz: So etwas wird tatsächlich gemacht. Es gibt verlustfreie Audio-Codecs, die auf einem Stream basieren, der einen verlustbehafteten Komprimierungsalgorithmus verwendet, zuzüglich des Unterschieds zu dem auf herkömmliche Weise komprimierten Original.
Carsten S
3

Ja, die verlustfreie Komprimierung nutzt die Tatsache aus, dass viele Dateien nicht zufällig sind. Ja, die meisten Multimediadateien sind nicht zufällig.

Faxbilder sind ein gutes Beispiel für diesen Effekt. In ihrer einfachsten Form ist ein Faxbild ein 2-D-Schwarzweißbild, das durch Scannen einer einzelnen Seite eines Dokuments erhalten wird. Wenn Sie dieses Bild als eine Folge von Bits darstellen, ein Bit pro Pixel (0 = weiß, 1 = schwarz), werden Sie feststellen, dass die resultierenden Binärdaten überhaupt nicht zufällig sind. Hier sind zum Beispiel einige nicht zufällige Muster, die Sie erkennen werden:

  • In der Regel haben Faxbilder viel mehr weiße als schwarze Pixel.

  • Außerdem hat jedes Pixel mit größerer Wahrscheinlichkeit dieselbe Farbe wie das Pixel links davon als eine andere Farbe.

  • Für ein komplexeres Muster: Stellen Sie sich vor, Sie scannen Pixel horizontal von links nach rechts und zählen die Länge jedes "Durchlaufs" aufeinanderfolgender Pixel mit derselben Farbe. Dann sind lange Läufe häufiger als kurze Läufe, und lange Läufe mit weißen Pixeln sind häufiger als lange Läufe mit schwarzen Pixeln.

Faxkomprimierungsalgorithmen wurden entwickelt, um diese nicht zufälligen Aspekte zu nutzen. Frühe Faxkomprimierungsalgorithmen sind ein besonders gutes Beispiel, da es sich um einfache verlustfreie Komprimierungsschemata handelt, die diese nicht zufälligen Eigenschaften gescannter Bilder sehr direkt ausnutzen.

Beispielsweise verwendete ein frühes Schema zum Komprimieren von Faxbildern eine Lauflängencodierung in Kombination mit einer Huffman-Codierung . Die Lauflängencodierung ersetzt jeden Lauf gleichfarbiger Pixel durch eine einzelne Ganzzahl, die die Länge des Laufs zählt. Beispielsweise wird 00000110001 zu "5 2 3 1". Die Lauflängencodierung nutzt die Tatsache aus, dass Pixel dazu neigen, in Läufen derselben Farbe zu kommen. Die Huffman-Codierung nutzt die Tatsache weiter aus, dass einige Lauflängen häufiger sind als andere. Sehen Sie hier für ein detailliertes Beispiel dafür , wie eine dieser frühen Systeme gearbeitet - das System ist einfach und elegant, und direkt nutzt die Muster oben erwähnt.

Diese Schemata bieten im Durchschnitt keine Komprimierung für zufällige Dateien. Gescannte Faxbilder sind jedoch nicht zufällig, und als Ergebnis können diese Komprimierungsschemata erhebliche Einsparungen bieten.

Ähnliche Kommentare gelten für andere Multimediadateien. Die in anderen Arten von Multimediadateien vorhandenen Muster können komplexer sein, es sind jedoch immer noch viele Muster vorhanden, die die Daten nicht zufällig machen.

DW
quelle
0

Eine zufällige Audiodatei ist eine Art Rauschen. Die meisten Menschen speichern Audiodateien mit Musik oder Sprache, nicht mit Rauschen.

Carsten S.
quelle
2
Danke für Ihren Beitrag. Könnten Sie einige Beispiele näher erläutern? Die Idee, die Sie gegeben haben, ist gut, stimmt, wurde aber bereits in drei vorherigen Antworten vorgestellt.
Böse
@ EvilJS, möglicherweise wahr. Ich denke nicht, dass es eine halbe Seite dauern sollte, um zu erklären, dass es einen Unterschied zwischen Sprache und Lärm gibt.
Carsten S
Es sollte keine halbe Seite dauern, um die wichtigsten Fakten zu erklären, damit Ihre Antwort erklärt, warum Sprache und Musik komprimiert werden, zufälliges Rauschen jedoch nicht.
David Richerby
@DavidRicherby, dass zufällige Daten nicht komprimiert werden, wurde bereits in der Frage akzeptiert. Die Frage war "Aber sind Multimediadaten nicht zufällig?" worauf die Antwort lautet, dass es offensichtlich nicht ist.
Carsten S