Fundamentale Ideen der Informatik

Stefan Franke

Fundamentale Ideen der Informatik

Datenkompression

Übersicht

Verlustfreie Kompression
- Codes mit variabler Wortlänge
- Lauflängen-Codierung
- Differenzcodierung
- LZW-Algorithmus
Verlustbehaftete Kompression (Datenreduktion)

Datenkompression – warum?

Daten sollen möglichst effizient gespeichert und übertragen werden:
- Datenmenge möglichst gering halten
- Übermittlungszeit reduzieren
- Speicherplatz sparen
Beispiel: Tar o. Zip zur Kompression von Dateien

Allgemeiner Ablauf

Umgang mit komprimierten Daten

Übung: Dateien komprimieren

						  1. Erstellen Sie einen Ordner Komprimierung mit zwei Unterordnern: Textdatei und Bild
					    

2. Erstellen Sie in Textdatei eine .txt-Datei mit beliebigem Beispielinhalt

						  3. Fotografieren Sie etwas mit dem Handy und speichern Sie das .jpg im Ordner Bild
					    

4. Komprimieren Sie den gesamten Ordner als .zip- oder .tar.gz-Datei

						  5. Senden Sie die komprimierte Datei per Mail an: stefan.franke@ph-weingarten.de
					    

						  📁 Komprimierung/

						    📁 Textdatei/

						      📄 text.txt

						    📁 Bild/

						      🖼️ foto.jpg

Zeit: 10:00

Arten der Datenkompression

Verlustfreie Datenkompression

Dekodierte Daten unterscheiden sich nicht von den Originaldaten
Anwendung: Wenn der Verlust einzelner Bits die Qualität wahrnehmbar verändert
Z.B. Texte, Tabellen, Quellcode

Verlustbehaftete Datenkompression

Ein Teil der Information geht bei der Kompression verloren
Anwendung: Qualitative Lücken in der menschlichen Wahrnehmung werden ausgenutzt
Z.B. Bilder, Audio, Video, Messdaten

Dateiformate — verlustfrei vs. verlustbehaftet

Verlustfrei

.png — Bilder (Grafiken, Screenshots)

.gif — Bilder (max. 256 Farben, Animationen)

.flac — Audio (CD-Qualität, kein Verlust)

.zip / .tar.gz — Archive (beliebige Dateien)

.pdf — Dokumente (Text + Vektorgrafik)

Verlustbehaftet

.jpg / .jpeg — Fotos (einstellbare Qualität)

.mp3 — Audio (unhörbare Frequenzen entfernt)

.mp4 / .h264 — Video (Bewegungskompensation)

.aac — Audio (Nachfolger von MP3)

.webp — Bilder (Web-optimiert, Google)

VERLUSTFREIE KOMPRESSION

Verlustfreie Kompression

Forderungen

Alle Informationen müssen erhalten bleiben
Informationen möglichst dicht packen

Analogie: Koffer packen

Alle Gegenstände werden eingepackt
Möglichst wenig Zwischenraum lassen
Größe hängt davon ab, welche Arten von Gegenständen eingepackt werden

Ziel: Koffer soll möglichst klein und kompakt gepackt werden

Generelles Ziel: Redundanz reduzieren

Redundanz

Informationen, die in einer Nachricht mehrfach vorkommen
Informationen, die ohne Informationsverlust weggelassen werden können

Konkurrierende Ziele:

Komprimierung

Redundanz in den Daten möglichst gering halten

↔

Fehlertoleranz

Redundante Daten unterstützen Fehlererkennung und Fehlerkorrektur

Redundanz am Beispiel von HTML-Code

Zwei Seiten mit sich wiederholenden Inline-Styles — wo ist die Redundanz?

index.html

<html>
<body>
  <h1 style="font-family: Arial;
    font-size: 30px; color: red;">
    Wartungsseite</h1>
  <p style="font-family: Arial;
    font-size: 16px; color: black;">
    Diese Homepage wird erstellt</p>
  <h2 style="font-family: Arial;
    font-size: 24px; color: orange;">
    Bitte habe noch etwas Geduld</h2>
</body>
</html>

kontakt.html

<html>
<body>
  <h1 style="font-family: Arial;
    font-size: 30px; color: blue;">
    Kontaktseite</h1>
  <p style="font-family: Arial;
    font-size: 16px; color: black;">
    Feedback? Dann melde dich:</p>
  <h2 style="font-family: Arial;
    font-size: 24px; color: orange;">
    dummy@email.de</h2>
</body>
</html>

Lösung: CSS — Redundanz auslagern

CSS-Syntax:

Selektor { Eigenschaft: Wert; }

Die wiederholten Styles in eine eigene Datei:

stylesheet.css

p {
  font-family: Arial;
  font-size: 16px;
  color: black;
}

h1 {
  font-family: Arial;
  font-size: 30px;
  color: red;
}

h2 {
  font-family: Arial;
  font-size: 24px;
  color: orange;
}

HTML aufgeräumt + externes Stylesheet

index.html

<html>
<head>
  <link rel="stylesheet"
        href="stylesheet.css">
</head>
<body>
  <h1>Wartungsseite</h1>
  <p>Diese Homepage wird erstellt
     von Name</p>
  <h2>Bitte habe noch etwas
     Geduld</h2>
  <p><a href="kontakt.html">
     Kontakt</a></p>
</body>
</html>

stylesheet.css

p {
  font-family: Arial;
  font-size: 16px;
  color: black;
}

h1 {
  font-family: Arial;
  font-size: 30px;
  color: red;
}

h2 {
  font-family: Arial;
  font-size: 24px;
  color: orange;
}

Styles nur einmal definiert — gilt für alle HTML-Dateien, die das Stylesheet einbinden.

Aufgabe: CSS auslagern

1. Laden Sie die Übungsdateien herunter: css-uebung.zip

2. Entpacken und öffnen Sie index.html und kontakt.html in einem Texteditor

						  3. Erstellen Sie eine stylesheet.css — lagern Sie die wiederholten Styles dorthin aus
					    

4. Verknüpfen Sie das Stylesheet per <link> in beiden HTML-Dateien

5. Passen Sie Farben, Schriftgrößen oder Inhalte nach eigenem Geschmack an

						  📁 css-uebung/

						    📄 index.html

						    📄 kontakt.html

						    📄 stylesheet.css ←

Zeit: 10:00

Ansätze zur verlustfreien
Datenkompression

Codes mit variabel langen Codewörtern
- Morse-Code
- Huffman-Codierung
Lauflängen-Codierung
Differenzcodierung
Arithmetische Codierung
LZW-Algorithmus

Codes mit variabler Wortlänge

Block-Codes (feste Wortlänge)

Jedes Zeichen wird mit gleich vielen Bits codiert
z.B. ASCII-Code: feste Wortlänge von 7 bzw. 8 Bit

Variable Wortlänge

Häufige Zeichen → kurze Bitfolge
Seltene Zeichen → lange Bitfolge
= statistische Datenkompression

Beispiel: Morse-Code

Zeichen werden durch kurze und lange Symbole dargestellt
Pausen als drittes Symbol trennen die einzelnen Zeichen

Herold et al. (2017): Grundlagen der Informatik

Fano-Bedingung für die
Dekodierbarkeit eines Codes

Codes mit variabler Wortlänge müssen für die Dekodierbarkeit folgende Bedingung erfüllen:

Ein Code erfüllt die Fano-Bedingung, wenn kein Wort aus dem Code der Anfang eines anderen Wortes ist.

Codes, die die Fano-Bedingung erfüllen, nennt man präfixfreie Codes.

Welche Codes erfüllen die
Fano-Bedingung?

Welche Codes erfüllen die
Fano-Bedingung?

Huffman-Algorithmus

Wurde 1952 von dem amerikanischen Mathematiker A. Huffman entwickelt
Effektivste Methode, um die Redundanz in einem Code für Einzelzeichen zu minimieren
Grundidee:
- Die Zeichen eines Texts, die häufig auftreten, werden in kurzen Codewörtern codiert.
- Der Code ist präfixfrei (s. Fano-Bedingung)
- Der Code wird über einen Code-Baum erzeugt

Vorgehensweise: Schritt 1 + 2

Vorgehensweise: Schritt 3

Vorgehensweise: Schritt 4

Vorgehensweise: Schritt 5

Vorgehensweise: Schritt 6

Vorgehensweise: Schritt 7

Vorgehensweise: Schritt 8

Vergleich: Huffman vs. ASCII-Code

Allgemein benötigen Huffman-codierte Texte ca. 2/3 des Speicherplatzes im Vergleich zur ASCII-Codierung.

Aufgabe: Dekomprimierung

Ist Komprimierung eine fundamentale Idee?

Überprüfung anhand der vier Kriterien (Schwill, 1993):

Horizontalkriterium

Komprimierung findet sich in Texten, Bildern, Audio, Video, Archiven, Datenbanken, Netzwerkprotokollen …

Vertikalkriterium

Von der Grundschule (ZIP-Dateien) bis zur Forschung (Informationstheorie, Shannon)

Zeitkriterium

Von Morse (1837) über Huffman (1952) bis heute (H.265, AVIF) — bleibt relevant

Sinnkriterium

Effizienz & Platzersparnis — im Alltag verankert (Streaming, Messenger, Cloud-Speicher)

Fragen?

Sitzungsreflexion

franke-lab.de/lehre/sose/fundidee/reflexion.html?sitzung=4

Artefakte & Reflexion verfassen → HTML kopieren → in Mahara einfügen

To Do's:

e-Portfolio aktualisieren (Reflexion Sitzung 4)
Übungsaufgaben fertigstellen