STP025: Datenkompression

Schlüsseltechnologie

Trotz des Themas haben wir es nicht geschafft, uns kurz zu fassen. Xyrill musste den Preis dafür zahlen. In dieser Sendung: Ein Einstieg mit flachen Witzen, gezinkte Münzen, naive Betrachtungsweisen und schwierige Abwägungen.

Shownotes

• Einführungsbeispiel: simulierte schlechte Leitung ("xxxxxx heute xxxxxx Podcast xxxxxx Thema xxxxxx Kompression xxxxxx" -> "In unserer heutigen Folge unseres Podcasts ist das Thema die Datenkompression.")

  • naiver Impuls eines Erstsemester-Linguistikstudenten: "Warum sagt man nicht gleich 'heute Podcast Thema Kompression'?"
  • Sprache ist so gestaltet, dass auch teilweise fehlerhafte Informationen noch korrekt ankommen
  • beim Hören intuitiver Einsatz eines Vorhersagemodells, um kommende Silben/Wörter/Phrasen vorherzusagen

• theoretische Grundlagen

  • Bit: Basiseinheit für Informationsgehalt (enstprechend der Auswahl aus zwei gleich wahrscheinlichen Möglichkeiten), allerdings nicht im SI-System verankert
  • Beispiel Münzwurf:
    • ideale Münze (50% Kopf + 50% Zahl) liefert 1 Bit pro Wurf
    • reelle Münze liefert mehr als 1 Bit pro Wurf (z.B. 49,5% Kopf + 49,5% Zahl + 1% Kante -> 1,07 Bit pro Wurf)
    • gezinkte Münze liefert weniger als 1 Bit pro Wurf (z.B. 10% Kopf + 90% Zahl -> 0,469 Bit pro Wurf)
  • gute Komprimierbarkeit = niedriger Informationsgehalt -> häufiger, als man denkt (Bsp. nebeneinanderliegende Pixel eines Bildes sind ähnlich)
  • Zusammenhang mit physikalischer Entropie: Systeme mit geringer Entropie (z.B. Eisblock) sind einfach vorherzusagen, Beobachtungen haben geringen Informationsgehalt; Systeme mit hoher Entropie (z.B. Wasserdampf) sind schwer vorherzusagen, Beobachtungen haben hohen Informationsgehalt

• "naive" Kompressionsmethoden (die man auch als Mensch überblicken kann)

  • Nutzung von Allgemeinwissen
    • Beispiel aus der Vorbereitung: "Schachbrett" im Kontext von Exponentialfunktionen ruft die Assoziation einer ganzen Geschichte auf
  • Wörterbuchmethode für Text
    • Beispiel aus Wikipedia: "wenn Fliegen hinter Fliegen fliegen, fliegen Fliegen Fliegen nach" -> "wenn Fliegen hinter \2 fliegen, \5 \2 \2 nach"
  • RLE (Run-Length Encoding) z.B. in Bildern wie dem Coverart dieses Podcasts
  • Huffman-Kodierung wie im Morse-Code (Verbindung zur Linguistik!)
  • Minifizierung von Skripten
    • Beispiel: jQuery 3.6 ohne Minifizierung und mit Minifizierung

• zwei fundamentale Abwägungen

  • Geschwindigkeit vs. Stärke (z.B. Debian-Pakete mit zwei getrennten Bereichen, die verschiedene Kompressionsverfahren nutzen)
  • verlustfrei vs. verlustbehaftet (Bsp. Pentaradio vom Mai 2022: Radiofassung als FLAC 271,7 MiB; Endprodukt als Opus 52,0 MiB)

• Kompressionsmethoden im Audio-Video-Bereich beispielhaft anhand ihres Verlustverhaltens

  • Blockartefakte bei JPEG
  • Psychoakustik bei MP3
  • Datamoshing bei Videos (Beispiel) illustriert Bedeutung von Intra-Frames
    • siehe auch dasselbe Video, 1000-mal komprimiert und dekomprimiert
  • Einfluss fester Bitrate auf Audio/Videos

• theoretische Grenze: Kolmogorow-Komplexität

• Fußnoten:

  • ttimeless fühlt sich verpflichtet, auf den RFC-Podcast zu verlinken
  • David Kriesel: "Traue keinem Scan, den du nicht selbst gefälscht hast"